【正文】 Regular expressions define terminals/tokens PLLab, NTHU,Cs2403 Programming Languages 6 Lex Source Program ? Lex source is a table of – regular expressions and – corresponding program fragments digit [09] letter [azAZ] %% {letter}({letter}|{digit})* printf(“id: %s\n”, yytext)。 ? regexp one or more blanks { actions (C code) } ? A null statement 。 ? | indicates that the action for this rule is from the action for the next rule – [ \t\n] 。} . | \n 。 %} letter [azAZ] %% {letter}+ {printf(“a word\n”)。 } 。 } 。 term : term 39。 PLLab, NTHU,Cs2403 Programming Languages 42 Rules Section ? Normally written like this ? Example: expr : expr 39。 expr 39。 term : term 39。)39。 term : term 39。)39。 term : term 39。)39。 term : term 39。)39。} %{ include include %} %token CHAR, FLOAT, ID, INT %% yacc d Produced : define CHAR 258 define FLOAT 259 define ID 260 define INT 261 PLLab, NTHU,Cs2403 Programming Languages 50 YACC ? Rules may be recursive ? Rules may be ambiguous* ? Uses bottom up Shift/Reduce parsing – Get a token – Push onto stack – Can it reduced (How do we know?) ? If yes: Reduce using a rule ? If no: Get another token ? Yacc cannot look ahead more than one token Phrase cart_animal AND CART | work_animal AND PLOW … PLLab, NTHU,Cs2403 Programming Languages 51 Yacc Example ? Taken from Lex amp。/39。\n39。 } 。 Parser (cont’d) PLLab, NTHU,Cs2403 Programming Languages 54 term: term 39。 factor: 39。 } | NUMBER { $$ = $1。 } $ { return 0。 39。 39。/39。+39。 Specify the grammar39。 yacc, 2nd Edition – by John , Tony Mason amp。 Declare the type of semantic values for a nonterminal symbol PLLab, NTHU,Cs2403 Programming Languages 63 YACC Declaration Summary `%right39。*39。 } | expr ?/? expr { if($3==0) yyerror(“divide 0”)。 39。 ) 39。 39。 return NUMBER。 { $$ = $2。/39。 } | expression 39。 statement: NAME 39。)39。39。 PLLab, NTHU,Cs2403 Programming Languages 47 Communication between LEX and YACC 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 LEX and YACC需要一套方法確認 token的身份 PLLab, NTHU,Cs2403 Programming Languages 48 Communication between LEX and YACC yacc d Will produce: ? Use enumeration ( 列舉 ) / define ? 由一方產(chǎn)生，另一方 include ? YACC 產(chǎn)生 ? LEX include PLLab, NTHU,Cs2403 Programming Languages 49 Communication between LEX and YACC %{ include include %} id [_azAZ][_azAZ09]* %% int { return INT。 } 。+39。 } 。+39。 } 。+39。 } 。+39。*39。(39。 return 0。 } | expression 39。 } PLLab, NTHU,Cs2403 Programming Languages 29 Usage ? To run Lex on a source file, type lex ? It produces a file named which is a C program for the lexical analyzer. ? To pile , type cc –ll ? To run the lexical analyzer program, type ./ inputfile PLLab, NTHU,Cs2403 Programming Languages 30 Versions of Lex ? ATamp。 chars += yyleng。} ink {nink++。 ↓ ↓ a=b+c。 Repeated Expressions ? a? = zero or one instance of a ? a* = zero or more instances of a ? a+ = one or more instances of a ? . ab?c = ac or abc [az]+ = all strings of lower case letters [azAZ][azAZ09]* = all alphanumeric strings with a leading alphabetic character PLLab, NTHU,Cs2403 Programming Languages 18 Precedence of Operators ? Level of precedence – Kleene closure (*), ?, + – concatenation – alternation (|) ? All operators are left associative. ? Ex: a*b|cd* = ((a*)