从正规式到词法分析

1、1从正规式到词法分析器 构造词法分析器的一般方法和步骤： 用正规式对模式进行描述； 为每个正规式构造一个NFA，它识别正规式所表示的正规集； 将构造出的NFA转换成等价的DFA，这一过程也被称为确定化； 优化DFA，使其状态数最少，这一过程也被称为最小化； 从优化后的DFA构造词法分析器。问题： 我们是从DFA构造词法分析器，为何不直接从正规式构造DFA，而要先构造NFA，然后转换为DFA？原因： 机器构造需要规范的算法； 正规式NFA：有规范的一对一的构造算法 DFA分析器：有便于记号的识别的算法21 从正规式到NFA 算法 Thompson 算法输入 字母表上的正规式r输出 接受L(r)的

2、NFA N方法 首先分解r，然后根据下述步骤构造NFA： 对，构造NFA如右。其中，s0为初态，f为终态，此NFA接受； s0f 对上的每一个字符a，构造NFA如右s0fa 若N(p)和N(q)是正规式p和q的NFA，则 （a） 对正规式p|q，构造NFA如右。其中，s0为初态，f为终态，此NFA接受L(p)L(q)； （b） 对正规式pq，构造NFA如右。其中，s0为初态，f为终态，此NFA接受L(p)L(q)； N(P)N(Q)s0f （c） 对正规式p*，构造NFA如右。其中，s0为初态，f为终态，此NFA接受L(p*)； N(P)s0f 对于正规式(p)，使用p本身的NFA，不再构造新

3、的NFA。 s0fN(P)N(Q)31 从正规式到NFA（续1）s0fs0faN(P)N(Q)s0fN(P)N(Q)s0fN(P)s0f正规式 NFAaP|QPQP*定义: 令是一个有限字母表，则上的正规式及其表示的集合递归定义如下: 1 . 是 正 规 式 ， 它 表 示 集 合L()= 2. 若a是上的字符，则a是正规式，它表示集合L(a)=a 3. 若正规式r和s分别表示集合L(r)和L(s)，则 （a） r|s是正规式，表示集合L(r)L(s)， （b） rs是正规式，表示集合L(r)L(s)， （c） r*是正规式，表示集合(L(r)*， （d）(r)是正规式，表示的集合仍然是L(r

4、)。（加括弧改变优先级、结合性） 可用正规式描述的语言称为正规语言或正规集。 41 从正规式到NFA（续2）例用Thompson算法构造正规式r=(a|b)*abb的NFA N(r) r11r9r10br7r8br5r6r4*( r3 )r1 | r2aba23a45b16078a9b10b 分解正规式 自下而上构造NFA强调： 算法的构造与正规式一一对应 构造一个新的NFA最多增加两个状态52 从NFA到DFA NFA识别记号的“并行”方法例从甲地到乙地，可以乘小轿车也可以骑自行车，具体路线如上。其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？（即识别

5、是否有从甲到乙标记为cc的路径） 甲乙123ccccbb试探（串行方式）： 甲 c 2 无路可走，退回 甲 c 1 c 3 无路可走，退回 甲 c 1 c 乙 到达乙地，成功 并行(假设有足够的小汽车，每次都是到达小汽车可能到达的全体) 甲 c 1, 2 c 3, 乙 到达乙地，成功 由于并行的方法在每试探一步时，考虑了所有的下一状态转移，因此所走的每一步都是确定的。 用NFA识别记号，并不采用串行的方法（算法不易构造，复杂度高且回溯），而是采用并行的方法，核心思想是将不确定的下一状态确定化。6NFA上识别记号的确定化方法 2 从NFA到DFA（续1）确定化的两个步骤（回顾DFA定义）计算下一

6、状态转移时： 消除 状态转移：-闭包(T) 消除多于一个的下一状态转移：smove(S, a)smove(S, a)：从状态集S出发，标记为a的下一状态全体。 与move(s, a)的唯一区别：用状态集取代状态-闭包(T)：从状态T出发，不经任何字符达到的状态全体。s1s2as3as4s5定义 状态集T的-闭包(T)是一个状态集，且满足：（1） T中所有状态属于-闭包(T)；（2） 任何smove(-闭包(T)，)属于-闭包(T)；（3） 再无其他状态属于-闭包(T)。 根据定义，上图中-闭包(s2)应该包括：1. s2自身s2（1）2. s4s2, s4（2）3. s5s2, s4, s5（

7、2）算法7算法 模拟NFA 2 从NFA到DFA（续2） 输入 NFA N，x（eof）， s0， F 输出 若N接受x，回答“yes”，否则“no” 方法 用下边的过程对x进行识别。S是一个状态的集合 S := -闭包(s0); - 所有可能初态的集合a := nextchar;while a eof loop S:=-闭包(smove(S，a)； - 所有下一状态的集合 a := nextchar;end loop;if SF then return “yes”; else return “no”; end if; 算法2.582 NFA到DFA（续3）例 在NFA上识别输入序列abb和a

8、bab 23a45b16078a9b10b识别abb: 1 计算初态集-闭包(0) = 0,1,2,4,7， A2 从A出发经a到达-闭包(smove(A, a) = 3,8,6,7,1,2,4， B3 从B出发经b到达： -闭包(smove(B, b) = 5,9,6,7,1,2,4， C4 从C出发经b到达： -闭包(smove(C, b) = 5,10,6,7,1,2,4， D5 结束且D10=10，接受。识别的路径为：A a B b C b D识别abab: 初态集：-闭包(s0)=0,1,2,4,7 A从A出发经a到达：-闭包(smove(A, a) = 3,8,6,7,1,2,4

9、B从B出发经b到达：-闭包(smove(B, b) = 5,9,6,7,1,2,4 C从C出发经a到达：-闭包(smove(C, a) = 3,8,6,7,1,2,4 B从B出发经b到达：-闭包(smove(B, b) = 5,9,6,7,1,2,4 C识别路径为：A a B b C a B b C。由于C10=，所以不接受 9 “子集法”构造DFA 2 NFA到DFA（续4） “并行”模拟NFA的弱点：每次动态计算下一状态转移的集合，效率低。 改进方法：将NFA上的全部路径均确定化并且记录下来，得到与NFA等价的DFA。 甲乙123ccccbb甲1,23,乙3乙cbcbb 回顾从甲地到乙地的

10、路径，它的数学模型实质上是一个NFA （右上） 。 可以找到一个等价的DFA（右下），它们识别的路径均是：ccccbcbb例 用DFA识别cc和cbc： 甲 c 1,2 c 3,乙， 接受 甲 c 1,2 b 3 c ?，不接受 优点： 1. 消除了不确定性（将NFA的下一状态集合并为一个状态） 2. 无需动态计算状态集合（针对模拟NFA的算法）10算法 从NFA构造DFA（子集法） 2 NFA到DFA（续5）输入 NFA N输出 等价的DFA D。初态含有NFA初态，终态集是含有NFA终态的状态集合方法 用下述过程构造DFA ：-闭包(s0)是Dstates仅有的状态，且尚未标记;while

11、 Dstates有尚未标记的状态T loop 标记T; for 每一个输入字符a loop U := -闭包(smove(T，a); if U不在Dstates中 then U作为尚未标记的状态加入Dstates; end if; DtranT，a := U;- 记录状态转移 end loop;end loop; 两个数据结构：Dstates(状态)，Dtran(状态转移)112 NFA到DFA（续6）例 构造(a|b)*abb的DFA 010124356789ababb-闭包(0)=0,1,2,4,7* A-闭包(smove(A, a)=3,8,6,7,1,2,4* B-闭包(smove(A

12、, b)=5,6,7,1,2,4* C-闭包(smove(B, a)=3,8,6,7,1,2,4 B-闭包(smove(B, b)=5,9,6,7,1,2,4* D-闭包(smove(C, a)=3,8,6,7,1,2,4 B-闭包(smove(C, b)=5,6,7,1,2,4 C-闭包(smove(D, a)=3,8,6,7,1,2,4 B-闭包(smove(D, b)=5,10,6,7,1,2,4* E-闭包(smove(E, a)=3,8,6,7,1,2,4 B-闭包(smove(E, b)=5,6,7,1,2,4 C1032aabbbbaa问题：用哪个DFA识别输入序列？识别abb和

13、abab：A a B b D b E 接受 A a B b D a B b D 不接受 ABabCaDbabaEbab123 最小化DFA 定义: 对于任何两个状态t和s，若从一状态出发接受输入字符串，而从另一状态出发不接受，或者从t出发和从s出发到达不同的接受状态，则称对状态t和s是可区分的。 反方向思考定义： 设想任何输入序列对s和t均是不可区分的，则说明从s出发和从t出发，分析任何输入序列均得到相同结果。 因此，s和t可以合并成一个状态。 引入一个“可区分”的概念：正规式NFADFA13算法 最小化DFA的状态数 3 最小化DFA（续1）输入 DFA D=S，move，s0，F。输出 等

14、价的D=S，move，s0，F，（D状态数最少）方法 执行如下步骤：1. 初始划分=S-F，F1，F2，.，Fi是F的子集，接受不同记号；2. 应用下述过程构造新的划分new： for 的每一个组G loop 划分G，G的两个状态s和t在同一组中的充要条件是: a.(move(s,a)Gimove(t,a)Gi)；- Gi是中某个组 用新划分的组替代G，形成新的划分new； end loop；3. 若new=，令final=，转4；否则令=new并重复步骤2； 4. 在final每个组Gi中选一个代表si，使得D中从Gi所有状态出发的状态转移在D中均从si出发，D中所有转向Gi中的状态转移在D

15、中均转向si；含有D中s0的状态组G0的代表s0称为D的初态，D中所有含F中状态的Gj的代表sj构成D的终态集F； 5. 删除死状态，即不是终态且对所有输入字符均转向其自身，或从初态不可到达的状态。 14最小化DFA算法的主要步骤： 3 最小化DFA（续2） 初始划分：终态与非终态； 利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂； 由最终划分构造D，关键是选代表和修改状态转移； 消除可能的死状态和不可达状态。 BAEDabbbbaCbaaa例 用算法2.6化简DFAm(A,a)=B, m(A,b)=Cm(B,a)=B, m(B,b)=Dm(C,a)=B, m(C,b)=Cm(D,a

16、)=B, m(D,b)=Em(E,a)=B, m(E,b)=C1初始化划分1=ABCD，E2根据算法中步骤2，反复分裂划分中的组： m(D, b)=E 2=ABC，D，E m(B, b)=D 3=AC，B，D，E 3？ 于是：final=AC，B，D，E 4根据final构造D： 选代表，用A代表AC组； 修改状态转移： m(A,a)=B, m(A,b)=Am(B,a)=B, m(B,b)=Dm(D,a)=B, m(D,b)=Em(E,a)=B, m(E,b)=A用0、1、2、3代替A、B、D、E，得： 1032aabbbbaa154 由DFA构造词法分析器 表驱动型的词法分析器 驱动器（算法

17、2.1）输入字符序列分析表（DFA）记号流其中，需要：1. 有适当的数据结构存放DFA；2.修改算法2.1，以适应实际输入： 识别整个文件，而不是一个 记号； 满足最长匹配原则。对于输入序列：result := a + b 正确的识别：id := id + id 错误的识别： 1. 仅识别一个： id （result） 2. 不满足最长匹配：id id .（r或re或res . ） 16 直接编码的词法分析器 在表驱动的词法分析器中，DFA是被动的，需要一个驱动器来模拟DFA的行为，以实现对输入序列的分析。 直接编码的词法分析器，将DFA和DFA识别输入序列的过程合并在一起，直接用程序代码模拟

18、DFA识别输入序列的过程。问题： 如何用程序模拟DFA识别输入序列的过程？即如何用程序模拟DFA的状态和它的状态转移？1. 状态和状态转移与语句的对应关系 初态程序的开始； 终态程序的结束（return语句，不同终态return不同记号）； 状态转移分情况或者条件语句（case/if）； 环循环语句（loop）； return满足最长匹配原则。17 直接编码的词法分析器（续1）1032aabbbbaa2. 识别(a|b)*abb的程序框架main() char buf=abba#, *ptr=buf; while (*ptr!=# ) l0: while (*ptr=b) ptr+;/ sta

19、te 0l1: while (*ptr=a) ptr+;/ state 1 switch (*ptr) case a: goto l1; case b: ptr+; switch (*ptr)/ state 2 case a: goto l1; case b: ptr+; switch (*ptr) / state3 case a: goto l1; case b: goto l0; case #: coutyesendl; return; default: break; default: break; default: break; break; / 遇到非法字符 cout no endl;

20、18 两类分析器的比较 表驱动直接编码分析器的速度慢快程序与模式的关系无关有关分析器的规模较大较小适合的编写方法工具生成手工编写5 词法分析器生成器简介 构造词法分析器的全过程均有算法：正规式NFADFA最小化DFA词法分析器（分析表） LEX的基本结构根据正规式构造的分析表驱动器框架（不变的） 利用LEX构造词法分析器的关键 用LEX提供的正规式集合设计记号的模式； 用LEX提供的语义支持识别记号或指出输入中的错误。195 小结（略） 词法分析的两个重要环节：规定所有合法输入识别合法输入重要内容： 记号、模式与单词 记号的说明：模式的形式化描述正规式 记号的识别：有限自动机NFA：与正规式有

21、对应关系，易于构造，状态数少；DFA：确定性便于记号的识别，不易构造，状态数可能会多；记号识别的方法： a. 模拟DFA： b. 模拟NFA（特殊情况下）：需要动态计算状态子集。 从正规式到词法分析器（等价变换的过程）正规式描述模式由正规式构造NFANFA的确定化（子集法：smove， -闭包）DFA的最小化（可区分概念）词法分析器：表驱动（自动生成）与直接编码（手工编写）20算法 求-闭包输入 状态集T。输出 状态集T的-闭包方法 用下边的函数计算-闭包 function -闭包(T) isbegin for T中每个状态t loop 加入t到U; push(t); end loop; wh

22、ile 栈不空 loop pop(t); for 每个u=move(t, ) loop if u不在U中 then 加入u到U; push(u); end if; end loop; end loop; return U;end-闭包; 用算法计算-闭包(s2)： U stack1. s2s22. s2, s4s43. s2, s4, s5s54. s2, s4, s5问题：试将函数直接写为递归的两个数据结构： 闭包U和模拟递归的stacks1s2as3as4s521LexLex与与Yacc Yacc 快速入门快速入门22Lex Lex 和和 Yacc Yacc 介绍介绍 lex 和和 yac

23、c 是什么是什么vLex :Lexical Analyzar, 是一种生成扫描器的工具。是一种生成扫描器的工具。 Yacc :Yet Another Compiler Compiler vlex 和和 yacc 是是自动编译代码的工具自动编译代码的工具，适合于解析简单，适合于解析简单的语言。的语言。vlex 和和 yacc 是一对配对工具。是一对配对工具。lex 将文件分解为成组将文件分解为成组的的“记号（记号（tokens） ”，大体上类似于单词。，大体上类似于单词。yacc 接接受成组的记号，并将它们装配为高层次的结构，类似受成组的记号，并将它们装配为高层次的结构，类似于句子。于句子。vy

24、acc 设计用来处理设计用来处理 lex 的输出，不过您也可以编写自的输出，不过您也可以编写自己的代码来完成此任务。同样，己的代码来完成此任务。同样，lex 的输出很大程度的输出很大程度上设计用于为某类解析器提供数据。上设计用于为某类解析器提供数据。 23实验工具简介总揽实验工具简介总揽(1/2)LEXYACC代码产生支撑函数24实验工具简介总揽实验工具简介总揽(2/2)25实验工具简介-LEXLex：一个词汇分析器生成器：一个词汇分析器生成器 。 当当 Lex 接收到文件或文本形式的输入时，它试图将文接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，本与

25、常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够直到找到一个匹配的模式。如果能够找到一个匹配的找到一个匹配的模式模式，Lex 就执行相关的动作就执行相关的动作（可能包括返回一个标（可能包括返回一个标记）。另一方面，如果记）。另一方面，如果没有没有可以匹配的常规表达式，可以匹配的常规表达式，将会将会停止停止进一步的处理，进一步的处理，Lex 将将显示一个错误消息显示一个错误消息。 程序有三个部分，用程序有三个部分，用 % 符号隔开。符号隔开。第一部分和最后第一部分和最后一个部分一个部分是普通而是普通而古老的古老的 C 代码代码。中间中间是有趣的一部是有趣的一部分。它分

26、。它由一系列规则构成由一系列规则构成，lex 将这些规则翻译为词汇将这些规则翻译为词汇分析器。每一个规则依次包含一个正则表达式以及该分析器。每一个规则依次包含一个正则表达式以及该正则表达式得到匹配时要运行的一些代码。任何没有正则表达式得到匹配时要运行的一些代码。任何没有得到匹配的文本则简单地拷贝到标准输出。得到匹配的文本则简单地拷贝到标准输出。26Lex 的常规表达式（的常规表达式（1）字符字符 含义含义 A-Z, 0-9, a-z 构成了部分模式的字符和数字。构成了部分模式的字符和数字。. 匹配任意字符，除了匹配任意字符，除了 n。- 用来指定范围。例如：用来指定范围。例如：A-Z 指从指从

27、 A 到到 Z 之间的所有之间的所有字符。字符。 一个字符集合。匹配括号内的一个字符集合。匹配括号内的 任意任意 字符。如果第一字符。如果第一个字符是个字符是 那么它表示否定模式。例如：那么它表示否定模式。例如：abC 匹配匹配 a, b 和和 C中的任何一个。中的任何一个。 * 匹配匹配 0个个或者多个上述的模式。或者多个上述的模式。 + 匹配匹配 1个个或者多个上述模式。或者多个上述模式。 ? 匹配匹配 0个或个或1个个上述模式。上述模式。 $ 作为模式的最后一个字符匹配一行的结尾。作为模式的最后一个字符匹配一行的结尾。27Lex 的常规表达式（的常规表达式（2）字符字符 含义含义 指出一

28、个模式可能出现的次数。指出一个模式可能出现的次数。 例如：例如：A1,3 表示表示 A 可能出现可能出现1次或次或3次。次。 用来转义元字符。同样用来覆盖字符在此表中用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。定义的特殊意义，只取字符的本意。 否定。否定。| 表达式间的逻辑或。表达式间的逻辑或。 字符的字面含义。元字符具有。字符的字面含义。元字符具有。/ 向前匹配。如果在匹配的模版中的向前匹配。如果在匹配的模版中的“/”后跟有后后跟有后续表达式，只匹配模版中续表达式，只匹配模版中“/”前面的部分。如：前面的部分。如：如果输入如果输入 A01，那么在模版，那么在模版

29、A0/1 中的中的 A0 是匹是匹配的。配的。( ) 将一系列常规表达式分组。将一系列常规表达式分组。28常规表达式举例常规表达式举例常规表达式常规表达式 含义含义 jokers 匹配匹配 jokes 或或 joker。A1,2shis+ 匹配匹配 AAshis, Ashis, Ashiss, Ashisss。(Ab-e)+ 匹配在匹配在 A 出现位置后跟随的从出现位置后跟随的从 b 到到 e 的的所有字符中的所有字符中的 1 个或个或 多个。多个。29标记声明举例标记声明举例标记标记 相关表达式相关表达式 含义含义 数字数字(number) (0-9)+1个或多个数字个或多个数字字符字符(c

30、hars)A-Za-z任意字符任意字符空格空格(blank) 一个空格一个空格字字(word)(chars)+1个或多个个或多个 chars 变量变量(variable)(字符字符)+(数字数字)*(字字符符)*(数字数字)*30Lex 编程编程Lex 编程可以分为三步：编程可以分为三步： 以以 Lex 可以理解的格式指定模式相关的动作。可以理解的格式指定模式相关的动作。 在这一文件上运行在这一文件上运行 Lex，生成扫描器的，生成扫描器的 C 代码。代码。 编译和链接编译和链接 C 代码，生成可执行的扫描器。代码，生成可执行的扫描器。Lex 的输入格式的输入格式 一个一个 Lex 程序分为三

31、个段：程序分为三个段：第一段：是第一段：是 C 和和 Lex 的全局声明的全局声明第二段：包括模式（第二段：包括模式（C 代码）代码）第三段：是补充的第三段：是补充的 C 函数。函数。 这些段以这些段以%来分界。来分界。31（1）C 和和 Lex 的全局声明的全局声明 这一段中我们可以增加这一段中我们可以增加 C 变量声明。变量声明。 % int wordCount = 0; /*保存统计出来的字数保存统计出来的字数 */ % chars A-Za-z numbers (0-9)+ delim nt whitespace delim+ words chars+ % 两个百分号标记指出了两个百分

32、号标记指出了 Lex 程序中这一段的结束程序中这一段的结束和三段中第二段的开始。和三段中第二段的开始。 32（2）Lex 的模式匹配规则的模式匹配规则words wordCount+; /* increase the word count by one*/ whitespace /* do nothing*/ numbers /* one may want to add some processing here*/ % 33（3）C 代码代码 Lex 编程的第三段，也就是最后一段覆盖了编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。的函数声明（有时是主函数）。Lex 有一套

33、可供有一套可供使用的函数和变量。使用的函数和变量。 其中之一就是其中之一就是 yywrap。一。一般来说，般来说，yywrap() 的定义如下例的定义如下例。 void main() yylex(); /* start the analysis*/ printf( No of words: %dn, wordCount); int yywrap() return 1; 34Lex 变量变量 Lex 有几个函数和变量提供了不同的信息，可以用来编译有几个函数和变量提供了不同的信息，可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数，以实现复杂函数的程序。下表中列出了一些变量和函数，以及它们

34、的使用。及它们的使用。yyinFILE* 类型。类型。 它指向它指向 lexer 正在解析的当前文件。正在解析的当前文件。yyoutFILE* 类型。类型。 它指向记录它指向记录 lexer 输出的位置。输出的位置。 缺缺省情况下，省情况下，yyin 和和 yyout 都指向标准输入和输出。都指向标准输入和输出。yytext匹配模式的文本存储在这一变量中（匹配模式的文本存储在这一变量中（char*）。）。yyleng给出匹配模式的长度。给出匹配模式的长度。yylineno 提供当前的行数信息。（提供当前的行数信息。（lexer不一定支持。）不一定支持。）35Lex 函数函数yylex()这一函

35、数开始分析。这一函数开始分析。 它由它由 Lex 自动生成。自动生成。yywrap()这一函数在文件（或输入）的末尾调用。如果函这一函数在文件（或输入）的末尾调用。如果函数的返回值是数的返回值是1，就停止解析。，就停止解析。 因此它可以用因此它可以用来解析多个文件。代码可以写在第三段，这来解析多个文件。代码可以写在第三段，这就能够解析多个文件。就能够解析多个文件。 方法是使用方法是使用 yyin 文件文件指针（见上表）指向不同的文件，直到所有指针（见上表）指向不同的文件，直到所有的文件都被解析。最后，的文件都被解析。最后，yywrap() 可以返回可以返回 1 来表示解析的结束。来表示解析的结

36、束。yyless(int n)这一函数可以用来送回除了前这一函数可以用来送回除了前n 个字符外的所有个字符外的所有读出标记。读出标记。yymore()这一函数告诉这一函数告诉 Lexer 将下一个标记附加到当前将下一个标记附加到当前标记后。标记后。36例：识别例：识别PL/0单词的单词的LEX程序程序%#include #include “code.h”#include “symbol.h”#include “y.tab.h”extern int level;int cc=0;%IDENT a-zA-Z a-zA-Z0-9*NUMBER 0-90-9*%37“ “ cc+ +; “t “ ta

37、blize( ); /* adjust cc to tab-position */“n“ cc=0;line_copy( ); /* copy a line of input file */“ “ cc+ +; return GT;“= “ cc+ +; return ET;“# “ cc+ +; return NT;“, “ cc+ +; return colon;“. “ cc+ +; return Period;“( “ cc+ +; return Lparen;“) “ cc+ +; return Rparen;“=“ cc+ +; cc+ +; return GE;“:= “ cc+

38、 +; cc+ +; return ASGN;“; “ cc+ +; return Semicolon;38NUMBER int n; cc += yyleng; sscanf(yytext,”%d”,&n); yylval.numder=n; return NUMBER; IDENT Symbol *s; cc += yyleng; if (s=lookup(yytext)=0) s=install(yytext,VARIABLE,level,0); if (s-type=C) yylval.numder=s-adr; else yylval.sym=s; return s-type; %3

39、9int yywrap() return 1; 40实验工具简介实验工具简介-YACC-YACC yacc：另一个编译器的编译器：另一个编译器的编译器 将输入拆分为一连串的记号。现在您需要一些将输入拆分为一连串的记号。现在您需要一些方法来识别高层次的模式。这就是方法来识别高层次的模式。这就是 yacc 要做要做的：的：yacc 让您可以描述希望怎样处理记号。让您可以描述希望怎样处理记号。 411 1. . E - E + E E - E + E2. E - E 2. E - E * * E E3. E - id 3. E - id 1 . x + y 1 . x + y * * z shift

40、 z shift 2 x . + y 2 x . + y * * z reduce(r3) z reduce(r3) 3 E . + y 3 E . + y * * z shift z shift 4 E + . y 4 E + . y * * z shift z shift 5 E + y . 5 E + y . * * z reduce(r3) z reduce(r3) 6 E + E . 6 E + E . * * z shift z shift 7 E + E 7 E + E * * . z shift . z shift 8 E + E 8 E + E * * z . reduce(

41、r3) z . reduce(r3) 9 E + E 9 E + E * * E . reduce(r2) emit E . reduce(r2) emit multiply multiply 10 E + E . reduce(r1) emit 10 E + E . reduce(r1) emit add add 11 E . accept 11 E . accept Input:x + y Input:x + y * * z z4243 用用 Yacc 编写语法编写语法 如同如同 Lex 一样一样, 一个一个 Yacc 程序也用双百分号程序也用双百分号分为三段。它们是：声明、语法规则和分为

42、三段。它们是：声明、语法规则和 C 代代码。码。44 C 与与 Yacc 的声明的声明C 声明可能会定义动作中使用的类型和声明可能会定义动作中使用的类型和变量，以及宏。还可以包含头文件。每变量，以及宏。还可以包含头文件。每个个 Yacc 声明段声明了终端符号和非终端声明段声明了终端符号和非终端符号（标记）的名称，还可能描述操作符号（标记）的名称，还可能描述操作符优先级和针对不同符号的数据类型。符优先级和针对不同符号的数据类型。 lexer (Lex) 一般返回这些标记。所有这些一般返回这些标记。所有这些标记都必须在标记都必须在 Yacc 声明中进行说明。声明中进行说明。45 终端和非终端符号终

43、端和非终端符号 终端符号终端符号: 代表一类在语法结构上等效的标记。终端符代表一类在语法结构上等效的标记。终端符号有三种类型：号有三种类型：命名标记命名标记: 这些由这些由 %token 标识符来定义。按照惯例，标识符来定义。按照惯例，它们都是大写。它们都是大写。字符标记字符标记: 字符常量的写法与字符常量的写法与 C 相同。例如相同。例如, ? 就是就是一个字符标记。一个字符标记。字符串标记字符串标记 : 写法与写法与 C 的字符串常量相同。例如，的字符串常量相同。例如， 就是一个字符串标记。就是一个字符串标记。 非终端符号非终端符号: 是一组非终端符号和终端符号组成的符号。是一组非终端符号

44、和终端符号组成的符号。按照惯例，它们都是小写。按照惯例，它们都是小写。 在例子中，在例子中，file 是一个非终是一个非终端标记而端标记而 NAME 是一个终端标记。是一个终端标记。46这意味着表达式可以是几种这意味着表达式可以是几种格式中的任意一种；例如，格式中的任意一种；例如，一个变量、一个加号或者一一个变量、一个加号或者一个数字都可以是一个表达式个数字都可以是一个表达式。管道字符（。管道字符（|）表明可供）表明可供选择。选择。lexer 生成的符号称生成的符号称为为 终结符（终结符（terminals） 或或者者 记号（记号（tokens）。从它。从它们装配而来的内容称为们装配而来的内容

45、称为 非非终结符（终结符（non-terminals）。所以，在这个例子中，。所以，在这个例子中，NUMBER 是一个终结符；是一个终结符；lexer 正是生成这种结果。正是生成这种结果。相反，相反，value 是一个非终结是一个非终结符，它是通过装配终结符而符，它是通过装配终结符而创建出来的。创建出来的。 47 yacc 可以识别出记号的模式；例如，如上面例子可以识别出记号的模式；例如，如上面例子中所示，它可以识别出一个表达式可能由一个值、中所示，它可以识别出一个表达式可能由一个值、一个加号或者减号以及另一个值构成。它还可以一个加号或者减号以及另一个值构成。它还可以采取动作；当解析器达到表达

46、式中的那个条件点采取动作；当解析器达到表达式中的那个条件点时，封装在时，封装在 中的代码块将会被执行。例如，有中的代码块将会被执行。例如，有人可能会编写：人可能会编写： expression: value + value printf(Matched a + expression.n); 48你可能会觉得你可能会觉得 YYSTYPE 有点奇怪。但是类似有点奇怪。但是类似 Lex, Yacc 也有一套变量也有一套变量和函数可供用户来进行功和函数可供用户来进行功能扩展。能扩展。 YYSTYPE 定定义了用来将值从义了用来将值从 lexer 拷拷贝到解析器或者贝到解析器或者 Yacc 的的 yylv

47、al （另一个（另一个 Yacc 变变量）的类型。默认的类型量）的类型。默认的类型是是 int。 由于字符串可以由于字符串可以从从 lexer 拷贝，类型被重拷贝，类型被重定义为定义为 char*。 49 Yacc 语法规则语法规则vYacc 语法规则具有以下一般格式：语法规则具有以下一般格式：vresult: components /* action to be taken in C */ ; v在这个例子中，在这个例子中，result 是规则描述的非终是规则描述的非终端符号。端符号。Components 是根据规则放在一是根据规则放在一起的不同的终端和非终端符号。起的不同的终端和非终端符号

48、。 如果匹配如果匹配特定序列的话特定序列的话 Components 后面可以跟随后面可以跟随要执行的动作。要执行的动作。50 考虑如下的例子：考虑如下的例子：param : NAME EQ NAME printf(tName:%stValue(name):%sn, $1,$3); | NAME EQ VALUE printf(tName:%stValue(value):%sn,$1,$3); ; 如果上例中序列如果上例中序列 NAME EQ NAME 被匹配，将执行相应的被匹配，将执行相应的 括号中的动作。括号中的动作。 这里另一个有用的就是这里另一个有用的就是 $1 和和 $3 的使用的使用

49、, 它们引用了标记它们引用了标记 NAME 和和 NAME（或者第二行的（或者第二行的 VALUE）的值。的值。51附加附加 C 代码代码现在让我们看一下语法文件的最现在让我们看一下语法文件的最后一段，附加后一段，附加 C 代码。（这一代码。（这一段是可选的，如果有人想要略过段是可选的，如果有人想要略过它的话：）一个函数如它的话：）一个函数如 main() 调用调用 yyparse() 函数（函数（Lex 的的 yylex() 等效函数）。等效函数）。 一般来说一般来说，Yacc 最好提供最好提供 yyerror(char msg) 函数的代码。函数的代码。 当解析器遇当解析器遇到错误时调用到错误时调用 yyerror(char msg)。错误消息作为参数来传。错误消息作为参数来传递。递。 52Lex Lex 与与 Yacc Yacc 结合起来结合起来定义节定义节%规则节规则节%支撑函数节支撑函数节 Token定义C codeSample%token %token INTEGERINTEGER#ifndef YYSTYPE #ifndef YYSTYPE #define YYSTYPE int #define YYSTYPE int #endif #endif #define INTEGER 258 #define INTEGER