Wybrane narzędzia do tworzenia analizatorów leksykalnych i składniowych w Javie.

Zwięzły opis narzędzi wraz konkretnymi przykładami, próba porównania i rankingu, ciekawe zastosowania.

Spis treści:

  1. Wstęp
  2. Antlr
  3. Beaver
  4. Cup
  5. JavaCC
  6. Grammatica
  7. JFlex
  8. Chaperon
  9. Sax
  10. Podsumowanie

1. Wstęp

Analizator składniowy czyli parser jest narzędziem służącym do analizy przetwarzanych danych i ewentualnie wywoływaniu określonych akcji. Analizator leksykalny czyli skaner analizuje ciąg znaków i przekazuje je do parsera jako tokeny.
Istnieje wiele narzędzi do tworzenia analizatorów składniowych i leksykalnych. My wybraliśmy tylko kilka spośród nich. Jest to raczej forma skrótowego opisu możliwości i zasygnalizowania istnienia takiego narzędzia. Dla konkretnych opisów odsyłamy na strony domowe projektów.

2. Antlr (Another Tool for Language Recognition)

Antlr umożliwia tworzenie wewnętrznej reprezentacji strumienia wejściowego w formie drzewa AST, które będąc drzewem dwuwymiarowym może przechowywać strukturę wejścia jak i symbole wejściowe

Przykład

Szablon pliku zawierającego definicję gramatyki wygląda następująco:
      

header {
             // rzeczy mające zostać umieszczone na początku wszystkich wygenerowanych plików
       }
 
       options { 
            // opcje dotyczące calej gramatyki
       }

       class MojLexer extends Lexer;
       options { 
               // opcje dotyczące lexera
       }
       // tokeny
       // reguly 

       class MojParser extends Parser;
       options { 
               // opcje dotyczące lexera
       }
       // tokeny
       // reguly 

       class MojParserDrzewa extends TreeParser;
       options { 
               // opcje dotyczące lexera
       }
       // tokeny
       // reguly

W pliku o rozszerzeniu ".g" (może być też inne, ale wspomniane jest domyślnym rozszerzeniem programu dla ANTLRa) powinny się znaleźć przynajmniej dwie klasy, definjujące odpowiednio gramatyki dla parsera i dla leksera. Aby uruchomić ANTLRa używamy polecenia:
java antlr.Tool plik.g
W tym czasie ANTLR generuje pliki zawierające analizator leksykalny, składniowy oraz plik zawierający definicje tokenów.

Przykladowy parser (plik: simple.g)
class SimpleParser extends Parser;

entry : (d:DOB n:NAME a:AGE(SEMI)
      { 
        System.out.println(
          "Imie: "    + 
          n.getText() +
          ", Wiek: "   +
          a.getText() + 
          ", Data urodzenia: "   +
          d.getText()
        );
      })*
      ;
to class extends Parser

class SimpleLexer extends Lexer;

NAME : ('a'..'z'|'A'..'Z')+;

DOB  : ('0'..'9' '0'..'9' '/')=> 
       (('0'..'9')('0'..'9')'/')(('0'..'9')('0'..'9')'/')('0'..'9')('0'..'9') { $setType(DOB); }
     | ('0'..'9')+  { $setType(AGE); } ;

WS     :
    (' ' 
    | '\t' 
    | '\r' '\n' { newline(); } 
    | '\n'      { newline(); }
    ) 
    { $setType(Token.SKIP); } 
  ;

SEMI : ';' ;
plik Main.java:
import java.io.*;
import antlr.*;

public class Main{

public static void main(String args[])
{
    try {
	DataInputStream wej = new DataInputStream(System.in);
	SimpleLexer lekser = new SimpleLexer(wej);
	SimpleParser parser = new SimpleParser(lekser);
	
	parser.entry();
    } catch (Exception e) {System.err.println("Wyjatek: "+e); } 
}

}
wejście:
11/11/84 Tomasz 21;
01/01/84 Łukasz 21;

3. Beaver

Przykład

Szablon pliku zawierającego definicję gramatyki wygląda następująco:
      
%%

%left RPAREN;
%left MULT, DIV;
%left PLUS, MINUS;

%typeof NUMBER = "Number";
%typeof expr = "Expr";

%%

expr = expr.a MULT  expr.b   {: return new Expr(a.value * b.value); :}
     | expr.a DIV   expr.b   {: return new Expr(a.value / b.value); :}
     | expr.a PLUS  expr.b   {: return new Expr(a.value + b.value); :}
     | expr.a MINUS expr.b   {: return new Expr(a.value - b.value); :}
     | NUMBER.n              {: return new Expr(n.doubleValue());   :}
     | LPAREN expr.e RPAREN  {: return e; :}
     ;
Beaver używa kilku technik czyniących go bardzo wydajnym jeżeli chodzi o szybkość, np tworzy tablice parsingu zachowujące się jak tablice haszujące. Kompilator Beaver'a może być wywoływany zarówno z linii komend, a także jako zadanie Ant'a. Jego działanie musi być wspieranie przez stowarzyszony z nim skaner.

4. Cup

Przykład

Przykładowy plik zawierający gramatykę ( z rozszerzeniem .cup):
      
import java_cup.runtime.*;

/* Preliminaries to set up and use the scanner.  */
init with {: scanner.init();  :};
scan with {: return scanner.next_token(); :};

/* Terminals (tokens returned by the scanner). */
terminal           SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD;
terminal           UMINUS, LPAREN, RPAREN;
terminal Integer   NUMBER;

/* Non-terminals */
non terminal            expr_list, expr_part;
non terminal Integer    expr;

/* Precedences */
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;

/* The grammar */
expr_list ::= expr_list expr_part 
              | 
              expr_part;

expr_part ::= expr:e 
              {: System.out.println("= " + e); :} 
              SEMI              
              ;

expr      ::= expr:e1 PLUS expr:e2    
              {: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
              | 
              expr:e1 MINUS expr:e2    
              {: RESULT = new Integer(e1.intValue() - e2.intValue()); :} 
              | 
              expr:e1 TIMES expr:e2 
              {: RESULT = new Integer(e1.intValue() * e2.intValue()); :} 
              | 
              expr:e1 DIVIDE expr:e2 
              {: RESULT = new Integer(e1.intValue() / e2.intValue()); :} 
              | 
              expr:e1 MOD expr:e2 
              {: RESULT = new Integer(e1.intValue() % e2.intValue()); :} 
              | 
              NUMBER:n                 
              {: RESULT = n; :} 
              | 
              MINUS expr:e             
              {: RESULT = new Integer(0 - e.intValue()); :} 
              %prec UMINUS
              | 
              LPAREN expr:e RPAREN     
              {: RESULT = e; :} 
              ;

5. JavaCC (Java Compiler Compiler)

Plik z opisem gramatyki posiada następującą składnię:
          // opcje
          PARSER_BEGIN ( identyfikator)
          class identyfikator {
         } 
          PARSER_END ( identyfikator) 
          // produkcje 
          EOF
Rozpoczyna się listą opcji (opcjonalnie). "Identyfikator" stanowi nazwę generowanego parsera (na której podstawie powstaje tworzona jest nazwa pliku).

Przykład

      
PARSER_BEGIN (Ciag)


public class Ciag
{
}

PARSER_END (Ciag)

SKIP :
{
  " "
| "\n"
| "\r"
| "\t"
}


void Input() :
{}
{
  "a" ( BC1() | BC2() )
}

void BC1() :
{}
{
  "b" "c" "c"
}

void BC2() :
{}
{
  "b" "c" [ "c" ]
}

6. Grammatica

Przykład

Przykładowy plik z definicją gramatyki (z rozszerzeniem .grammar):
      
%header%

GRAMMARTYPE = "LL"
DESCRIPTION = "Gramatyka dla prostego języka arytmetycznego"
DATE  = "18.01.2006"

%tokens%

ADD                          = "+"
SUB                          = "-"
MUL                          = "*"
DIV                          = "/"
LEFT_PAREN                   = "("
RIGHT_PAREN                  = ")"
NUMBER                       = <<[0-9]+>>
IDENTIFIER                   = <<[a-z]>>
WHITESPACE                   = <<[ \t\n\r]+>> %ignore%


%productions%

Expression = Term [ExpressionTail] ;

ExpressionTail = "+" Expression
               | "-" Expression ;

Term = Factor [TermTail] ;
     
TermTail = "*" Term
         | "/" Term ;

Factor = Atom
       | "(" Expression ")" ;

Atom = NUMBER
     | IDENTIFIER ;
Grammatica automatycznie zapewnia "error recovery" bez konieczności wprowadzania zmian do gramatyki (ANTLR np. zapewnia error recovery przez dodawanie klauzul catch do gramatyki). Jednocześnie generuje szczegółowe komunikaty o błędach. Podobnie jak Beaver może być uruchamiana z poziomu Anta.

7. JFlex

Przykład

Przykład lexera dla części składni Javy:
      
/* JFlex example: part of Java language lexer specification */
import java_cup.runtime.*;

/**
 * This class is a simple example lexer.
 */
%%
%class Lexer
%unicode
%cup
%line
%column
%{
  StringBuffer string = new StringBuffer();

  private Symbol symbol(int type) {
    return new Symbol(type, yyline, yycolumn);
  }
  private Symbol symbol(int type, Object value) {
    return new Symbol(type, yyline, yycolumn, value);
  }
%}
LineTerminator = \r|\n|\r\n
InputCharacter = [^\r\n]
WhiteSpace     = {LineTerminator} | [ \t\f]

/* comments */
Comment = {TraditionalComment} | {EndOfLineComment} | {DocumentationComment}

TraditionalComment   = "/*" [^*] ~"*/" | "/*" "*"+ "/"
EndOfLineComment     = "//" {InputCharacter}* {LineTerminator}
DocumentationComment = "/**" {CommentContent} "*"+ "/"
CommentContent       = ( [^*] | \*+ [^/*] )*

Identifier = [:jletter:] [:jletterdigit:]*

DecIntegerLiteral = 0 | [1-9][0-9]*
%state STRING

%%
/* keywords */
 "abstract"           { return symbol(sym.ABSTRACT); }
 "boolean"            { return symbol(sym.BOOLEAN); }
 "break"              { return symbol(sym.BREAK); }
 {
  /* identifiers */ 
  {Identifier}                   { return symbol(sym.IDENTIFIER); }
 
  /* literals */
  {DecIntegerLiteral}            { return symbol(sym.INTEGER_LITERAL); }
  \"                             { string.setLength(0); yybegin(STRING); }

  /* operators */
  "="                            { return symbol(sym.EQ); }
  "=="                           { return symbol(sym.EQEQ); }
  "+"                            { return symbol(sym.PLUS); }

  /* comments */
  {Comment}                      { /* ignore */ }
 
  /* whitespace */
  {WhiteSpace}                   { /* ignore */ }
}
 {
  \"                             { yybegin(YYINITIAL); 
                                   return symbol(sym.STRING_LITERAL, 
                                   string.toString()); }
  [^\n\r\"\\]+                   { string.append( yytext() ); }
  \\t                            { string.append('\t'); }
  \\n                            { string.append('\n'); }

  \\r                            { string.append('\r'); }
  \\\"                           { string.append('\"'); }
  \\                             { string.append('\\'); }
}
/* error fallback */
.|\n                             { throw new Error("Illegal character <"+
                                                    yytext()+">"); }

8. Chaperon

Przykład

Przykład gramtyki w formie tekstowej:
      
%token id     "[A-Za-z]+";
%token number "[0-9]+";

%right mult   "\*";
%right div    "/";
%right plus   "\+";
%right minus  "\-";

%token pleft  "\(";
%token pright "\)";

%ignore "(\r\n\ \t)+";

%start exp;

%%

exp : exp   plus  exp
    | exp   minus exp
    | exp   mult  exp 
    | exp   div   exp
    | pleft exp   pright
    | id
    | number
    ;
Przykład gramtyki w formacie XML:
      
<?xml version="1.0"?>
<grammar>
 <priority>
  <terminal symbol="mult"/>
  <terminal symbol="div"/>
  <terminal symbol="plus"/>
  <terminal symbol="minus"/>
 </priority>

 <associativity symbol="mult"  type="right"/>
 <associativity symbol="div"   type="right"/>
 <associativity symbol="plus"  type="right"/>
 <associativity symbol="minus" type="right"/>


 <production symbol="exp">
  <nonterminal symbol="exp"/><terminal symbol="plus"/><nonterminal symbol="exp"/>
 </production>

 <production symbol="exp">
  <nonterminal symbol="exp"/><terminal symbol="minus"/><nonterminal symbol="exp"/>
 </production>

 <production symbol="exp">
  <nonterminal symbol="exp"/><terminal symbol="mult"/><nonterminal symbol="exp"/>
 </production>

 <production symbol="exp">
  <nonterminal symbol="exp"/><terminal symbol="div"/><nonterminal symbol="exp"/>
 </production>

 <production symbol="exp">
  <terminal symbol="pleft"/><nonterminal symbol="exp"/><terminal symbol="pright"/>
 </production>

 <production symbol="exp">
  <terminal symbol="id"/>
 </production>

 <production symbol="exp">
  <terminal symbol="number"/>
 </production>

 <start symbol="exp"/>
</grammar>

9. SAX

10. Podsumowanie

W referacie zawarto omówienie jedynie kilku z ogromnej liczby dostępnych narzędzi do tworzenia analizatorów leksykalnych oraz syntaktycznych. Część z nich umożliwia generowanie kodu wynikowego nie tylko w javie, ale także w C++ oraz C#. Dzięki tej różnorodności istnieje możliwość wyboru odpowiedniego narzędzia, w zależności od rodzaju gramatyki wejściowej, przejrzystości kodu, szybkości działania itp.