Jakiego generatora parserów użyć?

Narzędzia do generacji parserów i skanerów. Spojrzenie z punktu widzenia programisty.

Przygotowali: Maciej Klesiewicz i Norbert Kocik

Omówienie zagadnienia

Zadaniem parsera jest analiza przetwarzanego tekstu (np. programu) i podejmowanie akcji zależnej od napotkanej sekwencji elementów przetwarzanego języka. Skaner zazwyzczaj ograniczony jest jedynie do rozpoznawania poszczególnych "słów", parser zaś analizuje zdanie złożone z tych słów i podejmuje odpowiednie akcje.


Dostępnych jest bardzo wiele rodzajów narzędzi do generowania skanerów i parserów. W opracowaniu tym chcemy pokazać tylko niektóre z nich, które naszym zdaniem zasługują na uwagę i dość znacznie różnią się między sobą.

Klasyczne rozwiązania - rodzina lex i yacc

Lex to program unixowy służący do tworzenia skanerów. Na podstawie opisu wymieszanego z kodem C generował kod skanera w języku C.
Oryginalny program już od dawna nie jest używany, jednak pod nazwą tą kryje się cała rodzina generatorów lekserów z grubsza kompatybilnych z oryginalnym lexem, takich jak: Specyfikacja do lexa ma układ:
definicje pomocnicze
%%
reguły 
%%
podprogramy pomocnicze
Poniższy przykład prezentuje reguły dla prostego skanera dla języka podobnego do Pascala:
{DIGIT}+    
{
            printf( "Liczba całkowita: %s (%d)\n", yytext, atoi( yytext ) );
}

{DIGIT}+"."{DIGIT}*        
{
            printf( "Liczba rzeczywista: %s (%g)\n", yytext, atof( yytext ) );
}

if|then|begin|end|procedure|function        
{
            printf( "Słowo kluczowe: %s\n", yytext );
}

{ID}        printf( "Identyfikator: %s\n", yytext );

"+"|"-"|"*"|"/"   printf( "Operator: %s\n", yytext );

"{"[^}\n]*"}"     

[ \t\n]+          /* pomijaj białe znaki */

.           printf( "Nieokreślone wyrażenie: %s\n", yytext );
Yacc (Yet Another Compiler Compiler) to uniksowy program generujący parsery LALR. Opis składni jest przeplatany z kodem i zawarty w pliku o rozszerzeniu .y
Oryginalny yacc nie jest już używany, jednak powstało wiele programów o podobnej składni, takich jak: Specyfikacja dla yacca ma układ podobny do specykicji lexa:
//{deklaracje} 
%token NAZWA1 NAZWA2 NAZWA3
%%
//{reguły}
<lewa strona>  : <alternatywa 1>   {akcja 1}
| <alternatywa 2>   {akcja 2}
...
| <alternatywa n>   {akcja n}
;
%%
{procedury}
Parsery działają najlepiej jeśli mogą operować na dużych symbolach nie zaś na pojedynczych znakach, dlatego też parsowanie najlepiej poprzedzić analizą leksykalną.

lex & yacc

Generatory skanerów

Re2c

Re2c jest narzędziem do pisania bardzo szybkich i elastycznych skanerów. Generuje on kod w C/C++.
W przeciwieństwie do innych podobnych narzędzi (np. flexa) generuje on bardzo efektywny kod dla wyrażeń regularnych - jest mniejszy i szybszy(około 2 razy).
Aby zastoswać re2c w kodzie programu, używamy kodu skanera wewnątrz specjalnego komentarza: /*!re2c */.
Poniżej pokazono przykład zastosowania użycia re2c:
char *scan(char *p){
char *q;
#define YYCTYPE         char
#define YYCURSOR        p
#define YYLIMIT         p
#define YYMARKER        q
#define YYFILL(n)
/*!re2c
        [0-9]+          {return YYCURSOR;}
        [\000-\377]     {return NULL;}
*/
}
Re2c ma jednak bardzo ubogą dokumentację. Może być bardzo dobrym narzędziem dla małych i średnich projektów programistycznych, w których potrzebujemy korzystać ze skanera wyrażeń regularnych, jednak dla dużych projektów, lepiej użyć sprawdzonych i znacznie lepiej udokumentowanych narzędzi.

JLex i JFlex

JLex i JFlex - to generatory skanerów napisane w Javie dla Javy dostępne na licencji open source.
Plik z opisem gramatyki dla JLexa jest podobny do pliku w Lexie.
JLex i JFlex współpracują z generatorem parserów CUP.
JLex generuje jako wynik klasę Yylex - klasa ta jest w pełni funkcjonalnym skanerem.
How to JLex work

/* JFlex example: part of Java language lexer specification */
import java_cup.runtime.*;

%%

%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()+">"); }

Generatory parserów

Prezentowane generatory parserów albo współpracują z generatorami skanerów, albo w sobie zawierają generatory skanerów

rdp

rdp jest systemem do implementowania procesorów językowych. Na swoje wejście rdp pobiera specyfikację skanera w notacji zbliżonej do EBNF, razem ze specyfikacją parsera zapisaną w C, zas na wyjsciu mamy kod w C/C++.
Przykładowa gramatyka rdp dla małego języka wspierającego deklarację zmiennych i przypisanie wartości całkowitych do tych zmiennych, a także operacje dodawania, odejmowania, mnożenia, dzielenia, minusa i plusa unarnego oraz potęgowania.
Specyfikacja taka powinna być zapisana w pliku o rozszerzeniu .bnf.
program   ::= {([var_dec | statement ]) ';' }.
var_dec   ::= 'int' ( ID [ '=' e1 ] )@','.
statement ::= ID '=' e0
              | 'if' e0 'then' statement [ 'else' statement ]
              | 'print' '(' ( e0 | String )@',' ')'.
e0 ::= e1 ['>' e1 | '<' e1 | '>=' e1 | '<=' e1 | '==' e1 | '!=' e1].
e1 ::= e2 {'+' e2 | '-' e2}.
e2 ::= e2 {'*' e3 | '/' e3}.
e3 ::= '+' e4 | '-' e4 | e4 .
e4 ::= e5 ['^' e1].
e5 ::= ID | INTEGER | '(' e1 ')' .
String ::= STRING_ESC('"' '\\') .

Gramatica

Gramatica to generator parserów dla C# i Javy, wspierający gramatyki LL(k), który wyróżnia się od innych poprzez: Przykład gramatyki w Gramatice dla prostego arytmetycznego języka
%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 ;
Parsowanie z użyciem Gramatici jest jednak wolniejsze w porównaniu z większością innych narzędzi, co jest największą wadą tego narzędzia.

ANTLR

ANTLR (Another Tool for Language Recognition) to narzędzie służące do tworzenia kompilatorów oraz translatorów z opisu gramatyki zawierającego akcje w języku Java, C++, C# lub Python. Autorem jest Terence Parr, pracujący obecnie na Uniwersytecie w San Francisco.
W przeciwieństwie do narzędzi z rodziny yacc, ANTLR generuje parser typu LL(k). Z tego powodu formalny opis parsera oraz leksera jest bardzo podobny, a generowany kod jest czytelny.
Domyślnie ANTLR generuje lekser i parser w Javie, a plik z gramatyką ma rozszerzenie .g ANTLR akceptuje trzy rodzaje gramatyk: parsery, leksery oraz drzewa parserów.
Drzewa AST (Abstract Syntax Tree) są używane jako wewnętrzna reprezentacja strumienia wejściowego, zwykle tworzone są podczas parsowania. Ponieważ drzewa AST są dwuwymiarowe, mogą zarówno przechowywać strukturę wejścia (rozpoznaną przez parser) jak i symbole wejściowe.
Omówienie przykładowego kalkulatora
Poniższy przykład pochodzi z dystrybucji ANTLRa, znajduje się w podkatalogu examples/java/calc.
options {
        buildAST = true;        // uses CommonAST by default
}

expr
        :       mexpr (PLUS^ mexpr)* SEMI!
        ;

mexpr
        :       atom (STAR^ atom)*
        ;

atom:   INT
        ;

class CalcLexer extends Lexer;

WS      :       (' '
        |       '\t'
        |       '\n'
        |       '\r')
                { _ttype = Token.SKIP; }
        ;

LPAREN: '('
        ;

RPAREN: ')'
        ;

STAR:   '*'
        ;

PLUS:   '+'
        ;

SEMI:   ';'
        ;

protected
DIGIT
        :       '0'..'9'
        ;

INT     :       (DIGIT)+
        ;

class CalcTreeWalker extends TreeParser;

expr returns [float r]
{
        float a,b;
        r=0;
}
        :       #(PLUS a=expr b=expr)   {r = a+b;}
        |       #(STAR a=expr b=expr)   {r = a*b;}
        |       i:INT                   {r = (float)Integer.parseInt(i.getText());}
        ;
Opis gramatyki dla parsera jest podobny do tego z Yacca.
Napisy expr, mexpr oraz atom są symbolami nieterminalnymi, PLUS, SEMI oraz STAR symbolami terminalnymi, dostarczonymi przez lekser. Znak daszka ^ za PLUS oraz STAR oznacza, że są to korzenie poddrzew w AST, natomiast wykrzyknik oznacza, że SEMI nie będzie włączone do wyjściowego drzewa.

JavaCC

JavaCC to generator parserów i skanerów. JavaCC czyta opis języka i generuje kod, napisany w Javie, który będzie analizował dany język.
Poniżej przedstawiono fragment kodu, za pomocą którego można w JavaCC zrealizować prosty kalkulator:
options
{
    LOOKAHEAD=2;
}

PARSER_BEGIN(Arithmetic)

public class Arithmetic
{
}

PARSER_END(Arithmetic)

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

TOKEN:
{
    < NUMBER: ()+ ( "." ()+ )? >
|   < DIGIT: ["0"-"9"] >
}

double expr():
{
    term() ( "+" expr() | "-" expr() )*
}

double term():
{
    unary() ( "*" term() | "/" term() )*
}

double unary():
{
    "-" element() | element()
}

double element():
{
     | "(" expr() ")"
}

Textransformer

TextTransformer to graficzne środowisko, które zwiera w sobie generator parserów z prostym kompilatorem i debugerem C++.
Program dystrybuowany jest w 3 wersjach: Główne okno programu wygląda następująco

TextTransformer

Dostępne w programie kreatory wspomagają tworzenie kodu.
TextTransformer stosowany jest przede wszystkim do parsowania tekstów, choć jego możliwości pozwalają mu na konkurowanie z innymi parserami pod innymi względami.

Testy

Trudno znaleźć porówania czy to skanerów czy parserów, gdyż to co dla jednego jest zaletą - dla innego może być wadą. Na stronie http://www.python.org/sigs/parser-sig/towards-standard.html dostępne są testy porównujące parsery dla YAPPS, Bison i Spark.

Parser Czas
BisonGen (C) 2.1
YAPPS (sre, no semantic actions) 9.5
YAPPS (sre) 11
SPARK 84

Podsumowanie

W referacie przedstawiono tylko kilka z wielu dostępnych narzędzi do generowania parserów i skanerów. Jednak pokazują one, że programista ma wybór między różnymi rzeczami. Często do większości rozwiązań wystarczające i efektywne będzie połączenie klasycznych rozwiązań (rodzina lex i yacc - i jej modyfikacje dla poszczególnych języków programowania). Jednak dla specyficznych projektów programista ma możliwość skorzystnia z szerokiej gamy narzędzi, mając na uwadze, czy to przejrzystość kodu, czy szybkość działania czy też platformę.