【正文】 en stream Abstract Syntax Tree PLLab, NTHU,Cs2403 Programming Languages 35 An YACC File Example %{include %}%token NAME NUMBER%%statement: NAME 39。expression: expression 39。39。%%int yyerror(char *s){ fprintf(stderr, %s\n, s)。}PLLab, NTHU,Cs2403 Programming Languages 36 Works with Lex Y A C Cy y p a r s e ( )I n p u t p r o g r a m s12 + 26L E Xy y le x ( )How to work ? PLLab, NTHU,Cs2403 Programming Languages 37 Works with Lex Y A C Cy y p a r s e ( )I n p u t p r o g r a m s12 + 26L E Xy y le x ( )call yylex() [09]+ next token is NUM NUM ?+? NUM PLLab, NTHU,Cs2403 Programming Languages 38 YACC File Format %{ C declarations %} yacc declarations %% Grammar rules %% Additional C code – Comments enclosed in /* ... */ may appear in any of the sections. PLLab, NTHU,Cs2403 Programming Languages 39 Definitions Section %{ include include %} %token ID NUM %start expr It is a terminal 由 expr 開(kāi)始 parse PLLab, NTHU,Cs2403 Programming Languages 40 Start Symbol ? The first nonterminal specified in the grammar specification section. ? To overwrite it with %start declaraction. %start nonterminal PLLab, NTHU,Cs2403 Programming Languages 41 Rules Section ? This section defines grammar ? Example expr : expr 39。*39。 expr 39。+39。 factor | factor 。)39。 term { $$ = $1 + $3。*39。 factor : 39。 { $$ = $2。 term { $$ = $1 + $3。*39。 factor : 39。 { $$ = $2。 term { $$ = $1 + $3。*39。 factor : 39。 { $$ = $2。 term { $$ = $1 + $3。*39。 factor : 39。 { $$ = $2。 } char { return CHAR。 Yacc ? Simple calculator a = 4 + 6 a a=10 b = 7 c = a + b c c = 17 $ PLLab, NTHU,Cs2403 Programming Languages 52 Grammar expression ::= expression 39。 term | term term ::= term 39。 factor | factor factor ::= 39。 | 39。 | statement_list statement 39。=39。 expression: expression 39。39。*39。 factor { if ($3 == ) yyerror(divide by zero)。(39。 } | 39。 } | NAME { $$ = $1value。 } [ \t] 。 /* end of input */ } \n |”=“|”+”|””|”*”|”/” return yytext[0]。 e x p r | e x p r 39。 e x p r | 39。 . . . 。39。? %left 39。 highest precedence PLLab, NTHU,Cs2403 Programming Languages 60 Precedence / Association expr : expr ?+? expr { $$ = $1 + $3。 else $$ = $1 / $3。 39。 39。s start symbol `%union39。 Declare a terminal symbol (token type name) that is rightassociative `%left39。 Doug Brown – O?Reilly – ISBN: 1565920007 ? Mastering Regular Expressions – by Jeffrey . Friedl – O?Reilly – ISBN: 1565922573 。 Declare a terminal symbol (token type name) that is nonassociative (using it in a way that would be associative is a syntax error, ex: x op. y op. z is syntax error) PLLab, NTHU,Cs2403 Programming Languages 64 Reference Books ? lex amp。 Declare a terminal symbol (token type name) with no precedence or associativity specified `%type39。 %noassoc UMINUS PLLab, NTHU,Cs2403 Programming Languages 61 Shift/Reduce Conflicts ? shift/reduce conflict – occurs when a grammar is written in such a way that a decision between shifting and reducing can not be made. – ex: IFELSE ambigious. ? To resolve this conflict, yacc will choose to shift. PLLab, NTHU,Cs2403 Programming Languages 62 YACC Declaration Summary `%start39。 %left 39。 } %left 39。 } | expr ?*? expr { $$ = $1 * $3。 39。+39。39。 e x p r 39。 e x p r | e x p r 39。T) – yacc –d ? Bison (GNU) – bison –d –y