编译原理教程02词法分析.ppt

【说明】 I=ε_CLOSURE(X) Ja是从I中的状态出发经过有向边a而能到达的状态集 Ia=ε_CLOSURE(Ja) Jb是从I中的状态出发经过有向边b而能到达的状态集 Ib=ε_CLOSURE(Jb) 16 letter (letter∣digit)* {if (keyword (id)==0) 　 {return (16,null)； return (id) }; 　　 else return (keyword (id)) } 17 digit (digit)* {val=int (id)； return (17, null)； return (val)} 18(letter∣digit∣{∣}∣(∣)∣+∣?∣*∣/∣=∣；)* {return (18，null)； inslit (id)； return (pointer，lenth)} 　　该LEX源程序中用户子程序为空；其中识别规则{A18}语句中调用过程“inslit (id)”是指将字符串常量id存放到字符表中，“pointer”中存放该串的起始位置，“lenth”存放该串的长度。 　　LEX有两种使用方式：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具(如YACC)结合起来使用，以生成一个编译程序的扫描器和语法分析器。 习 题 二 ?　　2.1 完成下列选择题： 　　(1) 词法分析器的输出结果是 。 　a. 单词的种别编码 　　 b. 单词在符号表中的位置 　c. 单词的种别编码和自身值 　　d. 单词自身值 　　(2) 正规式M1和M2等价是指 。 　a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 　c. M1和M2所识别的语言集相等 　d. M1和M2的状态数和有向边条数相等 　　(3)? DFA M(见图2–32)接受的字集为 。 　a. 以0开头的二进制数组成的集合 　b. 以0结尾的二进制数组成的集合 　c. 含奇数个0的二进制数组成的集合 　　　d. 含偶数个0的二进制数组成的集合 图2–32 习题2.1的DFA M 　　2.2 什么是扫描器？扫描器的功能是什么？ 　　2.3 设M=({x,y},{a,b},f,x,{y})为一非确定的有限自动机，其中f定义如下： f(x,a)={x,y} f{x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M。 　　2.4 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。 　　2.5 设有L(G)={a2n+1b2ma2p+1∣?n≥0,p≥0,m≥1}。 　　(1) 给出描述该语言的正规表达式； 　　(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。 　　2.6 有语言L={w∣w∈(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0}，试构造接受该语言的确定有限状态自动机(DFA)。 　　2.7 已知正规式((a∣b)*∣aa)*b和正规式(a∣b)*b。 　　(1) 试用有限自动机的等价性证明这两个正规式是等价的； 　　(2) 给出相应的正规文法。 　　2.8 下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试: I=1; while (I=n) { sum=sum+a[I]; I=I+1; } 请用正规表达式表示这个程序段可能的执行序列。 　　2.9 将图2–33所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X为初态，Y为终态。 图2–33 习题2.9的NFA 　　2.10 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放≥3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。 　　 (1) 写出售货机售糖的正规表达式； 　　　(2) 构造识别上述正规式