A Tutorial Generov´an´ı syntaktick´ych analyz´ator˚ u George J. Klir Jan Koneˇcn´y State University of New York (SUNY) Binghamton, New York 13902, USA
[email protected] Palacky University, Olomouc, Czech Republic
!
prepared for International Centre for Information and Uncertainty, Palacky University, Olomouc
! !
! J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
1 / 28
lex & yacc
N´astroje pro psan´ı program˚ u, kter´e zpracov´avaj´ı (transformuj´ı) strukturovan´e vstupy. Dva hlavn´ı poˇzadavky na takov´e programy: rozdˇelen´ı vstupu do smyslupln´ych jednotek. nalezen´ı vztah˚ u mezi tˇemi jednotkami. lex je n´astroj pro vytv´aˇren´ı lexik´aln´ıch analyz´ator˚ u (t´eˇz lexer˚ u). yacc (Yet Another Compiler Compiler) je n´astroj pro vytv´aˇren´ı syntaktick´ych analyz´ator˚ u (t´eˇz parser˚ u).
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
2 / 28
Lex Struktura vstupn´ıho souboru: sekce definic %% sekce pravidel %% sekce C k´ odu V´ystupem je k´od v C sekce definic definuje makra a importuje hlaviˇckov´e soubory v C. T´eˇz je moˇzno ps´at sem jak´ykoli k´od v C. sekce pravidel spojuje regul´arn´ı v´yrazy s k´odem v C. Kdyˇz je rozpozn´an text odpovidaj´ıc´ı regul´arn´ımu v´yrazu, je spuˇstˇen odpov´ıdaj´ıc´ı k´od. sekce C k´odu obsahuje libovoln´y k´od v C, J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
3 / 28
Prvn´ı easy example:
Example Specifikace pro desetinn´a ˇc´ısla %% [\n\t ] ; -?(([0-9]+)|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) { printf("number\n"); } . ECHO; %% main() { yylex(); }
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
4 / 28
Prvn´ı easy example:
Example (cont.) Pˇreklad: > lex first.l > cc lex.yy.c -o first -ll Spuˇstˇen´ı: .65ea12 number eanumber
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
5 / 28
Poˇc´ıt´an´ı slov Vytvoˇr´ıme program na poˇc´ıt´an´ı slov, podobn´y UNIXov´emu programu wc. Definiˇ cn´ı sekce: %{ unsigned charCount = 0, wordCount = 0, lineCount = 0; %} word [^ \t\n]+ eol \n Sekce pravidel: %% {word} { wordcount++; charcount += yyleng; } {eol} { charcount++; linecount++; } . charcount++; J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
6 / 28
Sekce C k´ odu: main() { yylex(); printf("%d %d %d\n", lineCount, wordcount, charcount); } nedˇel´a to nic zvl´aˇstn´ıho, jen vyuˇz´ıv´a toho, ˇze lex defaultnˇe ˇcte ze standardn´ıho vstupu. pokud bychom to chtˇeli vylepˇsit. . .
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
7 / 28
main(argc,argv) int argc ; char **argv; { if (argc > 1) { FILE *file; file = fopen(argv[l], "r"); if (!file) { fprintf(stderr,"could not open %s\n",argv[1]); exit(1); } yyin = file; } yylex(); printf("%d %d %d\n",charCount, wordCount, linecount); return 0; } J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
8 / 28
Parsov´an´ı pˇr´ıkazov´e ˇr´adky % { unsigned verbose; char *progName; % } %% -h | "-?"| -help { printf("usage is: %s [-help | -h | -? ]" "[-verbose | -v] [(-file | -f) filename]\n", progName); } -v | -verbose { printf ("verbose mode is on\n"); verbose = 1; } J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
9 / 28
%% main(argc, argv) int argc; char **argv; { progName = *argv; yylex(); } Probl´ em: tohle ale jeˇstˇe neˇcte z pˇr´ıkazov´e ˇr´adky, ale ze vstupu. ˇ Reˇsen´ı: m˚ uˇzeme pˇredefinovat funkce input a unput, aby zach´azely s argv. Probl´ em: jeˇstˇe nem´ame -file
. ˇ Reˇsen´ı: lex umoˇznˇuje pouˇz´ıt alternativn´ı poˇc´ateˇcn´ı stavy a zahrnout tak kontextovou z´avislost. J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
10 / 28
Gener´ator syntaktick´ych analyz´ator˚ u
vstup: gramatika (LL(1), LR(1), SLR, LALR(1)) v´ystup: syntaktick´y analyz´ator – rozhoduje platn´a slova gramatiky. Prvn´ı co zkus´ıme: statement → NAME = expr expr → NUMBER | expr + NUMBER | expr - NUMBER
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
11 / 28
Shift/Reduce Parsing; trocha velmi zjednoduˇsen´e teorie Gener´ator podle gramatiky vytvoˇr´ı mnoˇzinu stav˚ u, kaˇzd´y z nich odpov´ıd´a moˇzn´e pozici v jednom nebo v´ıce ˇc´asteˇcnˇe parsovan´eho pravidla. Parser ˇcte tokeny: pokud token neukonˇcuje pravidlo, uloˇz´ıme ho na z´asobn´ık a pˇresuneme se jin´eho stavu =shift, pˇresun, symboly na zasobn´ıku tvoˇr´ı pravou stranu pravidla, popnem je, a pushnem levou stranu pravida =redukce. pˇri redukci je spuˇstˇen odpov´ıdaj´ıc´ı kousek k´ odu =akce.
http://vychodil.inf.upol.cz/publications/white-papers/lalr.pdf
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
12 / 28
Vstup pro yacc vstup m´a stejnou strukturu jako vstup lexu. Sekce definic %token NAME NUMBER Sekce pravidel %% statement: NAME ’=’ expr | expr ; expr: expr ’+’ NUMBER | expr ’-’ NUMBER | NUMBER ; J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
13 / 28
Hodnoty symbol˚ u a akce
kaˇzd´y symbol m´a hodnotu netermin´aln´ı symboly maj´ı hodnotu vytvoˇrenou k´odem v parseru (ve skuteˇcn´ych parserech r˚ uzn´e datov´e typy ⇒ union typedef YYSYTYPE). Defaultnˇe je vˇse int. Kdykoli parser redukuje, spust´ı uˇzivatelsk´y k´od asociovan´y k pravidlu – akce. Akce se odkazuje na hodnoty symbol˚ u na prav´e stranˇe jako $1, $2. . . a nastavuje hodnotu symbolu na lev´e stranˇe pˇres $$.
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
14 / 28
Sekce pravidel (s doplnˇ en´ ymi akcemi) statement: NAME ’=’ expr | expr { printf("= %d\n",$1); } ; expr: expr ’+’ NUMBER { $$ = $1 + $3; } | expr ’-’ NUMBER { $$ = $1 - $3; } | NUMBER { $$ = $1; } ;
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
15 / 28
Lexer Abychom mohli vyzkouˇset n´aˇs parser, potˇrebujeme mu dodat tokeny. %{ #include "y.tab.h" extern int yylval; %} %% [0-9]+ { yylval = atoi(yytext) ; return NUMBER;} [ \t] ; /* ignore whitespace */ \n return 0; /* logical EOF */ . return yytext[0]; %% J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
16 / 28
> yacc -d calc.y > lex calc.1 > cc -c calc y.tab.c lex.yy.c -ly -ll > calc 99+12 = 111 > calc 2 + 3-14+33 = 24 > calc 100 + -50 syntax error
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
17 / 28
Aritmetick´e v´yrazy a nejednoznaˇcnost expr: expr ’+’ expr { $$ = $1 + $3; } | expr ’-’ expr { $$ = $1 -$3; } | expr ’*’ expr { $$ = $1 * $3; } | expr ’/’ expr { if ($3 == 0) yyerror( "divide by zero") ; else $$ = $1 / $3; } | ’-’ expr { $$ = -$2; } | ’(’ expr ’)’ { $$ = $2; } | NUMBER { $$ = $1; }
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
18 / 28
Ta gramatika m´a ale probl´em – nejednoznaˇcnost.
Example Parsujeme ”2+3*4”: 2 pˇresuˇn NUMBER E redukce E → NUMBER E+ pˇresuˇn + E+3 pˇresuˇn NUMBER E+E redukce E → NUMBER ’ Ted m˚ uˇzeme pˇresunout ’*’ a pozdˇeji redukovat pˇres pravidlo E→E*E nebo rovnou redukovat E→E+E Neˇrekli jsme, kter´y oper´ator m´a pˇrednost, ani nic o asociativitˇe.
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
19 / 28
Mohli bychom to ˇreˇsit pˇr´ımo v gramatice: expr: expr ’+’ mlexp | expr ’-’ mlexp | mlexp ; mlexp: mlexp ’*’ primary | mlexp ’/’ primary | primary ; primary: ’(’ expr ’)’ | ’-’ primary | NUMBER ; J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
20 / 28
M˚ uˇzeme to ale dodat explicitnˇe %left ’+’ ’-’ %left ’*’ ’/’ %nonassoc UMINUS
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
21 / 28
statement: NAME ’=’ expr | expr { printf ("= %d\n", $1) ; } expr: expr ’+’ expr { $$ = $1 + $3; } | expr ’-’ expr { $$ = $1 -$3; } | expr ’*’ expr { $$ = $1 * $3; } | expr ’/’ expr { if ($3 == 0) yyerror("divide by zero"); else $$ = $1 / $3;} | ’-’ expr %prec UMINUS { $$ = -$2; } | ’(’ expr ’)’ { $$ = $2; } | NUMBER { $$ = $1; } ; %% J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
22 / 28
Promˇenn´e a typovan´e tokeny (a v´ıce vyhodnocovan´ych v´yraz˚ u) %{ double vbltable[26]; %} %union { double dval; int vblno; } %token NAME %token NUMBER %left ’+’ ’-’ %left ’*’ ’/’ %nonassoc UMINUS %type expression %% J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
23 / 28
statement-list: statement ’\n’ | statement-list statement ’\n’
statement: NAME ’=’ expr { vbltable[$l] = $3; } | expr { printf ("= %g\n", $1) ; } expr: · · · | NAME { $$ = vbltable[$1]; } ;
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
24 / 28
%{ #include #include <math.h> extern double vbltable[26]; %} %% ([0-9]+)|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) { yylval.dval=atof(yytext); return NUMBER; } [ \t]; [a-z] { yylval.vblno = yytext[0] - ’a’; return NAME; } "$" { return 0; /* end of input */ } \n | . return yytext[0]; %% J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
25 / 28
v souboru y.tab.h: #define NAME 257 #define NUMBER 258 #define UMINUS 259 typedef union { double dval; int vblno; } YYSTYPE; extern YYSTYPE yylval; Proto uv´ad´ıme %token NAME %token NUMBER %type expression J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
26 / 28
Jak to jeˇstˇe m˚ uˇzem vylepˇsit
libovoln´a jm´ena pro promˇenn´e. funkce (sqrt, log, exp) DOMAC´I UKOL ...
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
27 / 28
Chcete vˇedˇet v´ıc? Bison manual: http://www.gnu.org/software/bison/manual/bison.pdf
LALR Gramatiky (VV) http://vychodil.inf.upol.cz/publications/white-papers/lalr.pdf
lex & yacc, 2nd Edition By Doug Brown, John Levine, Tony Mason, Publisher: O’Reilly Media Released: October 1992
J. Koneˇ cn´ y (DAMOL)
Generov´ an´ı syntaktick´ ych analyz´ ator˚ u
12. kvˇ etna 2014
28 / 28
