Lexical analyzer generator Last Lecture Review ？ Lexical analyzer generator State convention graph Regular expression Computer realization Regular expression grammar Equivalence Equivalence Subset construction Nondeterministic finite automaton Deterministic finite automaton Minimalist deterministic finite automaton Combining the undistinguishable states Deterministic finite automaton Language Sate enumeration method

2.5 Lexical Analyzer Generator Creating a lexical analyzer with Lex Lex compiler Lex source code lex.l lex.yy.c C a.out Input Stream Sequence of tokens

2.5 Lexical Analyzer Generator Lex program has three parts Declarations ％％ Translation rules auxiliary functions Lex translation rules p1 {action 1} p2 {action 2} … … pn {action n}

2.5 Lexical Analyzer Generator ex---Declarations %{ /* defination of manifest constants LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP*/ %} /* regular definations */ delim [ \t \n ] ws {delim}+ letter [A Za  z] digit [09] id {letter}({letter}|{digit})* number {digit}+(\ .{digit}+)?(E[+\]?{digit}+)?

2.5 Lexical Analyzer Generator ex---translation rule {ws} {/* no actions，no return */} while {return (WHILE);} do {return (DO);} {id} {yylval = install_id ( ); return (ID);} {number} {yylval = install_num( ); return (NUMBER);} “ < ” {yylval = LT; return (RELOP);} “ <= ” {yylval = LE; return (RELOP);} “ = ” {yylval = EQ; return (RELOP);} “ <> ” {yylval = NE; return (RELOP);} “ > ” {yylval = GT; return (RELOP);} “ >= ” {yylval = GE; return (RELOP);}

2.5 Lexical Analyzer Generator ex---auxiliary fuction install_ id ( ) { /* function to install the lexeme。 yytext points to the first character of lexeme， yyleng is the length of lexeme */ } install_num ( ) { /* similar to install_id,but puts numerical constrants into a separate table */

2.5 Lexical Analyzer Generator Example for experiment : example.l int num_lines = 0, num_chars = 0; %% \n ++num_lines; ++num_chars; . ++num_chars; main() { yylex(); printf("# of lines = %d, # of chars = %d\n ",num_lines,num_chars); }

2.5 Lexical Analyzer Generator Example for experiment : example.l hello world wo ai tian an men hello world i love lex.yy. exe # of lines = 3, # of chars = 49

Chapter Checklist Lex Manual Computer Realization Source code characters combination lexemes tokens pattern Transition Diagrams Name Lex equal Non-Formalization Description Formalization Description Syntax-directed Non-deterministic Finite Automata Minimization of Finite Automata Regular Expression letters combination string Language set Alphabet Table Merge undistinguished state Subset construction State Enumeration Deterministic Finite Automata Union LUM concatenation LM closure L* Positive closure L+ conjunction exponent

HOMEWORK 1、从软件学院编译原理论坛下载“软件学院编译原理实践.zip”，阅读教程中有关PL/0词法分析器的源代码。 2、从软件学院编译原理论坛下载“lex_实验.zip”，按照 “flex 说明.txt”要求完成如下上机题(选作)：

1、编写一个词法分析器，它针对输入文件，实现以下功能： 1）每遇到你的学号，就输出你的名字，对于其他的串原样输出。 2）统计输入文件中字母的数目。 例如：（以肖永跃的上机题为例）： 输入文件如下所示： 200213001 hello world wo ai tian an men hello world i love 200213001 输出应该如下所示： 肖永钦 hello world wo ai tian an men hello world i love 肖永钦 # of ids = 11, # of chars = 66