【導(dǎo)讀】takeaglanceatLex!WhatisLex?a=b+c*d;words,punctuationmarks,…Identifiers,operators,keywords,…{letter}({letter}|{digit})*printf(“id:%s\n”,yytext);\nprintf(“newline\n”);yylex();Lex. Yacc. parser.Regularexpression. [a-z]=>aorborcor…orz

　　

【正文】 | term 。 Parser (cont’d) PLLab, NTHU,Cs2403 Programming Languages 54 term: term 39。*39。 factor { $$ = $1 * $3。 } | term 39。/39。 factor { if ($3 == ) yyerror(divide by zero)。 else $$ = $1 / $3。 } | factor 。 factor: 39。(39。 expression 39。)39。 { $$ = $2。 } | 39。39。 factor { $$ = $2。 } | NUMBER { $$ = $1。 } | NAME { $$ = $1value。 } 。 %% Parser (cont’d) PLLab, NTHU,Cs2403 Programming Languages 55 %{ include include include %} %% ([09]+|([09]*\.[09]+)([eE][+]?[09]+)?) { = atof(yytext)。 return NUMBER。 } [ \t] 。 /* ignore white space */ Scanner PLLab, NTHU,Cs2403 Programming Languages 56 [AZaz][AZaz09]* { /* return symbol pointer */ = symlook(yytext)。 return NAME。 } $ { return 0。 /* end of input */ } \n |”=“|”+”|””|”*”|”/” return yytext[0]。 %% Scanner (cont’d) PLLab, NTHU,Cs2403 Programming Languages 57 YACC Command ? Yacc (ATamp。T) – yacc –d ? Bison (GNU) – bison –d –y 產(chǎn)生 , 與 yacc相同 不然會產(chǎn)生 PLLab, NTHU,Cs2403 Programming Languages 58 Precedence / Association 1. 123 = (12)3? or 1(23)? Define ?? operator is leftassociation. 2. 12*3 = 1(2*3) Define “*” operator is precedent to “” operator e x p r : e x p r 39。 39。 e x p r | e x p r 39。 * 39。 e x p r | e x p r 39。 39。 e x p r | 39。 ( 39。 e x p r 39。 ) 39。 . . . 。(1) 1 – 2 3 (2) 1 – 2 * 3 PLLab, NTHU,Cs2403 Programming Languages 59 Precedence / Association %right ?=? %left 39。39。 39。39。 NE LE GE %left 39。+39。 39。? %left 39。*39。 39。/39。 highest precedence PLLab, NTHU,Cs2403 Programming Languages 60 Precedence / Association expr : expr ?+? expr { $$ = $1 + $3。 } | expr ?? expr { $$ = $1 $3。 } | expr ?*? expr { $$ = $1 * $3。 } | expr ?/? expr { if($3==0) yyerror(“divide 0”)。 else $$ = $1 / $3。 } | ?? expr %prec UMINUS {$$ = $2。 } %left 39。+39。 39。39。 %left 39。*39。 39。/39。 %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。 Specify the grammar39。s start symbol `%union39。 Declare the collection of data types that semantic values may have `%token39。 Declare a terminal symbol (token type name) with no precedence or associativity specified `%type39。 Declare the type of semantic values for a nonterminal symbol PLLab, NTHU,Cs2403 Programming Languages 63 YACC Declaration Summary `%right39。 Declare a terminal symbol (token type name) that is rightassociative `%left39。 Declare a terminal symbol (token type name) that is leftassociative `%nonassoc39。 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。 yacc, 2nd Edition – by John , Tony Mason amp。 Doug Brown – O?Reilly – ISBN: 1565920007 ? Mastering Regular Expressions – by Jeffrey . Friedl – O?Reilly – ISBN: 1565922573