编译原理_chapter3剖析.ppt

* * 3.3.1 Lex源程序 1、正规定义式 letter→A|B|C|…|Z|a|b|c|…|z digit→0|1|2|…|9 identifier→letter(letter|digit)* integer→digit(digit)* 2、识别规则 正规式 动作描述 token1 {action1} token2 {action2} …… tokenn {actionn} * * %{ #include stdio.h #include y.tab.h #define ID 1 #define INT 2 #define EXP 3 #define MULTI 4 #define COLON 5 #define EQ 6 #define NE 7 #define LE 8 #define GE 9 #define LT 10 #define GT 11 #define PLUS 12 #define MINUS 13 #define RDIV 14 #define COMMA 15 #define SEMIC 16 #define RELOP 17 #define ASSGIN 18 int line_no = 1; %} delim [\t\n] ws [delim]+ letter [a-zA-Z] digit [0-9] id {letter}({letter}|{digit})* number {digit}+ %% {ws} ; begin return(BEGIN); end return(END); if return(IF); then return(THEN); else return(ELSE); do return(DO); program return(PROGRAM); {id} {yyval = install_id(); return(ID);} {number} {yyval = install_num(); return(INT);} * * ? ? {yyval =LT; return(RELOP);} =“ {yyval =LE; return(RELOP);} = {yyval =EQ; return(RELOP);} {yyval =GT; return(RELOP);} =“ {yyval =GE; return(RELOP);} “ {yyval =NE; return(RELOP);} + return(PLUS); - return(MINUS); * return(MULTI); / return(RDIV); ** return(EXP); : return(COLON); := return(ASSGIN); , return(COMMA); ; return(SEMIC); \n? ? line_no++; .? ? { fprintf (stderr,%c (0%o): illegal charcter at line %d\n,?yytext[0], yytext[0], line_no); } %% install_id() {……} install_num() {……} * * LEX二义性问题的两条原则 1.最长匹配原则 在识别单词过程中，有一字符串 x x x x x 根据最长匹配原则，应识别为这是 一个符合Pk规则的单词， 而不是Pj和Pi规则的单词。 Pj Pi Pk 2.优先匹配原则 如果有一字符串有两条规则可以同时匹配时，那么用规则 序列中位于前面的规则相匹配，所以排列在最前面的规则优先 权最高。 如:begin:= * * Lex的功能是根据Lex源程序构造一个词法分析程序， 该词法分析器实质上是一个有穷自动机。 Lex的功能是根据Lex源程序生成状态转换矩阵和控制程序 3.3.2 Lex的实现原理 图 3.4　Lex生成的词法分析器结构 * * 三点说明 以上是Lex的构造原理，虽然是原理性的， 但据此就不难将Lex构造出来。 所构造出来的Lex是一个通用的工具， 用它可以生成各种语言的词法分析程序， 只需要根据不同的语言书写不同的LEX源文件 就可以了。 Lex不但能自动生成词法分析器， 而且也可以产