编译原理chapter3.pptVIP

例: 对下图所示的NFA M求正规式R，使L(R)=L(M)。 3.4 词法分析器的自动生成 把一个正规式编译（或称转换）为一个NFA进而转 换为DFA，而这个NFA或DFA正是识别该正规式所表示 的语言(正规集)的识别器。基于这种方法可以构造出词法 分析程序(扫描器)，这就是扫描器的自动生成原理。 LEX是一个广泛使用的工具，它用于构造各种各样语 言的词法分析程序。LEX编译系统的作用如图: LEX程序由三部分组成：说明部分、转换规则和辅助过程，它们之间用%%做间隔，其一般格式为： {辅助定义部分} %% {识别规则部分} %% {用户子程序部分} (1)辅助定义部分包括变量的说明、常量说明和正规式定义，所谓正规式定义是形如如下形式的一系列定义： d1→r1 d2→r2 … dn→rn 其中， di是代表这个正规式的简名，ri是Σ∪{d1,d2, …,di-1}上的正规式，即在ri中允许出现字母表Σ中的字符和前面定义的简名（d1,d2, …,di-1） (2)识别规则部分是LEX源程序的核心。它是一张表，左边一列是正规式，右边一列是相应的动作。 P1 {action1} P2 {action2} … Pm {actionm} 其中，每个Pi是Σ∪{d1,d2, …,di-1}上的正规式，称之为词形。 (3)用户子程序部分是在action的执行过程中用到的 过程或函数 。 IDENT [a－zA－Z] [a－zA－Z0－9]* //辅助定义部分，定义名字IDENT和NUMBER NUMBER [0－9] [0－9] * //各代表一个正规式，[ ]、－和*为正规式运算符 % ( //[ ]表示字符的集合，－表示范围，*表示闭包运算 #include sidio.h # include “code. H” # include “symbol. H”　　 // % ( 与 % ) 之间的部分为直接照抄的代码部分。 # include “ y. tab. H” extern int level; int cc=0 ; % ) 说明部分 %% { cc + + ; } 转换规则 \t { tablize () ; } 　 //将cc调整到tab的位置 \n { cc=0 ; line_copy( ) ; } 　 //换行 { cc++ ; return LT;} {cc++ ; return GT ; } = {cc++ ; return EQ ; } # {cc++ i return NE ; } , {cc++ ; return Colon; } 一个LEX源程序片段： . { cc++ ; return Period; } ( { cc++ ; return Lparen; } ) { cc++ ; return Rparen; } = {cc++ ;cc++ ;return LE; } = {cc++ ;cc+ + ;return GE; } := {cc++ ; cc++ ;return ASGN; } ; { cc++ ; return Semicolon; } {NUMBER} //辅助定义在识别规则中使用时要加{ }  { int n ; cc += yyleng ;