Project Log Analyzer #2

เมื่อวาน implement ส่วน Log Parser เสร็จไปแล้ว
วันนี้ก็จะเริ่มทำส่วน Index Repository กับส่วน Query บ้าง

Index Repository
Index Repository ก็คือ พื้นที่ที่เก็บ mapping
ระหว่าง label กับ rownumber ของ log file

ในส่วนนี้เราจะนำเอา class BitSet มาใช้
implement ง่ายๆ ดังนี้

Map labelMap;
public void addLabel(String labelId, 
            String labelValue, int rowNumber) {
  BitSet bs = null;
  if (labelMap.containsKey(labelValue)) {
    bs = (BitSet) labelMap.get(labelValue);
  } else {
    bs = new BitSet();
    labelMap.put(labelValue, bs);
  }
  bs.set(rowNumber);
}

Query
แยกทำเป็น 2 ส่วนคือ Basic Search กับ Advance Search

Basic Search
เป็นการค้นหาแบบง่่ายๆ ตรงไปตรงมา
user ใส่ข้อมูลในลักษณะเป็น "word (word)*"
เช่น
"sompop" -> ค้นหา line ที่มี label = sompop
"sompop uc2110" -> ค้นหา line ที่มี label = sompop และ = uc2110
basic search implement ได้ง่ายๆดังนี้

public int[] search(String[] labelValues) {
  BitSet bs = null;
  for (int i = 0; i < labelValues.length; i++) {
    BitSet tmp = (BitSet) repo.labelMap.get
                 (labelValues[i]);
    if (tmp != null) {
      if (bs == null) {
        bs = (BitSet) tmp.clone();
      } else {
        bs.and(tmp);
      }
    }
  }
  return converToArray(bs);
}

Advance Search
user สามารถใส่ข้อมูลในลักษณะ logical expression ได้เช่น
"sompop & (piya | uc2110)"
การ implement เลือกใช้ Antlr มาทำเป็น parser
เนื่องจากรู้สึกลืมๆไปหมดแล้ว เลยอยากทบทวน

Lexer
มี spec ดังนี้

class AdvQryLexer extends Lexer;
options {
 k = 2;
}

AND  : '&';
OR  : '|';
LPAREN : '(';
RPAREN : ')';
NEGATE : '!';
SEMI : ';';

WS : ( ' '
   | '\t'
   | "\r\n"
   | '\n'
   ) {$setType(Token.SKIP);}
   ;
    
protected
LETTER
     :   '\u0024' |
         '\u0041'..'\u005a' |
         '\u005f' |
         '\u0061'..'\u007a' |
         '\u00c0'..'\u00d6' |
         '\u00d8'..'\u00f6' |
         '\u00f8'..'\u00ff' |
         '\u0100'..'\u1fff' |
         '\u3040'..'\u318f' |
         '\u3300'..'\u337f' |
         '\u3400'..'\u3d2d' |
         '\u4e00'..'\u9fff' |
         '\uf900'..'\ufaff'
     ;
        
TERM : (LETTER|('0'..'9'))+
 ;

TERM -> คือ String ที่ใช้ในการ search ประกอบด้วย
ตัวอักษร (สังเกตุว่ามี unicode ด้วย) หรือ ตัวเลข
SEMI -> ใส่เพิ่มเข้ามาโดยโปรแกรมเพื่อให้รู้ว่าเป็นตัวปิดท้าย syntax
เป็นตัวปิดท้าย
{$setType(Token.SKIP);}
-> เป็นการบอก lexer ไม่ต้องส่ง token นั้นไปให้ parser

Parser

class AdvQryParser extends Parser;
options {
 k = 2;
 buildAST = true;
}
search    : expression SEMI!
           ;
  
primitive  : TERM
    | LPAREN! expression RPAREN!
    ;
  
unaryExpression  
           : (NEGATE^)?
             primitive
           ;
     
logicalExpression
    : unaryExpression 
      ((AND^ | OR^) unaryExpression
      )*
    ;
       
expression : logicalExpression
    ;

พวกที่เป็นตัวใหญ่หมด ก็คือ token ที่ define ไว้ใน lexer
ส่วนเครื่องหมาย "^" หมายถึงว่าต้องการให้ node นั้นเป็น root node
ใน AST ที่ generate ขึ้นมา
เครื่องหมาย "!" ที่ตามหลังก็คือไม่ต้องการให้รวม token นั้นเข้าไปใน AST
ในการเขียน parser เราต้องกำหนด rule ที่เป็นจุดท้ายเข้าหลัก
ของการ parse ในทีนี้ก้คือ "search"

Tree Parser
ผลลัพท์จากการ parse เราจะได้ AST ออกมา
ขั้นต่อไปก็คือการท่อง AST เพื่อที่จะ search Index Repository

class AdvQryTreeParser extends TreeParser;
options {
    importVocab=AdvQryParser;
}
{ // java code ที่ customize เพิ่มเข้าไป
  // มีวัตถุประสงค์หลักก็เพื่อเชื่อม object ภายนอกเข้ามา
  // เพื่อให้สามารถใช้ในขณะที่กำลัง process tree ได้
  static final java.util.BitSet EMPTY = new java.util.BitSet();
  IndexRepository repo;
 
  public void setIndexRepository(IndexRepository repo) {
    this.repo = repo;
  }
 
  public java.util.BitSet getByLabel(String labelValue) {
    return repo.getQuery().getByLabel(labelValue);
  }
}
search   
returns [java.util.BitSet ret = EMPTY;]
 :  ret = expr
 ;
    
expr   
returns [java.util.BitSet ret = EMPTY;]
        : ret = unaryExpr
 | ret = biExpr
 | ret = single
 ;
    
unaryExpr
returns [java.util.BitSet ret = EMPTY;]   
        :#(NEGATE ret=expr) 
  { ret.flip(0, ret.length());}    
 ;
    
biExpr returns [java.util.BitSet ret = EMPTY;]
{
java.util.BitSet left, right;
}
 :#(AND left=expr right=expr) {left.and(right); ret = left;}
 |#(OR  left=expr right=expr) {left.or(right); ret = left;}  
 ;
    
single 
returns [java.util.BitSet ret = EMPTY;]
 :label:TERM { ret = getByLabel(label.getText()); }
 ;

syntax ของ TreeParser จะเขียนเหมือน lexer กับ parser
คือขึ้นต้นด้วย rule name และตามด้วย Matching Syntax
วิธีการท่อง tree ของเราก็คือทุก node ที่เรา visit จะต้อง
return ผลลัพท์ออกมา ซึ่งผลลัทพ์นั้นก็มีทั้งได้จากการ search repository
หรือผลลัพท์ที่ได้จากการทำ operation AND หรือ operation OR
ประโยค
returns [java.util.BitSet ret = EMPTY;]
ก็คือการ define ว่า rule ของเราจะ return java Class อะไร
และมีค่า default เป็นอะไร
:#(AND left=expr right=expr)
หมายถึงการ matching node ที่มี root node เป็น AND และมี child node อยู่ 2 node
โดยทั้ง 2 node ต้องเป็น expr Node
:#(AND left=expr right=expr) {left.and(right); ret = left;}
กรณี่ที่ maching ได้ก็จะทำ Action ที่ระบุ ในกรณีนี้
ก็คือ call method and ของ object left(Class BitSet)
โดย pass parameter right(class BitSet) ไป
:label:TERM { ret = getByLabel(label.getText()); }
กรณีที่มี node เดียว, Matching Syntax สามารถใส่ตรงๆได้เลย
ไ่ม่ต้องมี #() ให้เกะกะ
ส่วนคำว่า label:TERM มีความหมายว่าให้สร้าง ตัวแปรชื่อ label
ใน code เพื่อที่เราจะใช้อ้างอิงใน action ได้

Integrate Lexer, Parser, TreeParser
หลังจากเรา define Lexer, Parser และ TreeParser
ก็จะต้องทำการ generate java Class ขึ้นมา
ทำโดยสั่งคำสั่ง

java antlr.Tool <inputfile>>

และในส่วน code ของการ search ก็จะเขียนดังนี้

public int[] advSearch(String searchStr) {
  AdvQryLexer lexer = new AdvQryLexer(
                          new StringReader(searchStr));
  AdvQryParser parser = new AdvQryParser(lexer);
  try {
    parser.search();
    AdvQryTreeParser tps = new AdvQryTreeParser();
    tps.setIndexRepository(repo);
    BitSet bs = tps.search(parser.getAST());
    return converToArray(bs);
   
  } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
  } 
  return null;
}

ข้อมูลอ้างอิง

• Antlr Reference Manual