成果编译原理chap

1、 ing/上载区/其他/编译原理（天平与成教）92/编译原理（天平与成教）第四章 自上而下语法分析4.1 语法分析程序的功能一、语法分析的地位 是编译程序的核心部分。二、语法分析的功能以单词符号为输入识别语法成份对单词序列进行语法检查报错或输出某种形式的语法树核心：识别由词法分析得出的单词序列是否是给定文法的句子。三、语法分析的理论基础上下文无关文法和下推自动机第四章 自上而下语法分析 4.1 语法分析程序的功能四、语法分析的方式1、自上而下语法分析 反复使用不同产生式进行推导以谋求与输入符号串相匹配。2、自下而上语法分析 对输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入

2、符号指词法分析所识别的单词。第四章 自上而下语法分析4.2 自上而下语法分析法一、下推自动机模型有限状态控制器下推栈输入带输出带注：1）PDA和FA的模型相比，多了一个下推栈。 2）PDA的动作由三个因素来决定：当前状态、读头所指向符号、下推栈栈顶符号。 3）一个输入串能被PDA所接受，仅当输入串读完，下推栈变空；或输入串读完，控制器到达某些终态。第四章 自上而下语法分析 4.2 自上而下语法分析法一、下推自动机模型注：4）输出带用以记录推导或规约构成所用的产生式编号。5)正规文法和有限自动机仅适合于描述和识别高级语言的各类单词，语句可用上下文无关文法来描述，而下推自动机又恰好能识别上下文无关

3、文法所能描述的语言，因此上下文无关文法及其对应的下推自动机就成为编译技术中语法分析的理论基础。第四章 自上而下语法分析 4.2 自上而下语法分析法二、下推自动机的形式定义PDA是一个七元组：M=(Q ,H,q0,z0,F)H：下推栈内字母表z0 ：下推栈的栈初始符，是H中的元素。 ：Q( )H到QH*的有限子集映射。例如： (q,a,z)(q1,r1),(q2，r2)(qn,rn),其意义是：设控制器当前状态为q,下推栈顶符号为z,输入符号为a(可为空)，则状态转换到序偶集(q1,r1),(q2,r2)(qn,rn)(qi为下一状态, ri为代替z的栈顶符号串)FQ是控制器的终态集第四章 自上

4、而下语法分析 4.2 自上而下语法分析法二、下推自动机的形式定义注：1)由此定义的PDA肯定是不确定的PDA。这给语法分析会带来不确定性。我们在构造PDA M的算法的时候，要对PDA做一些限制。 2) PDA采用“”来表示PDA做了一步动作。 3)输入串能为PDA所接受，仅当输入串读完，下推栈为空；或者输入串读完，控制器到达某些终态。 4)有时，下推自动机还配置输出带，以记录推导或归约过程所用的产生式编号。 5)对于形如A的产生式，有(q, ,A)=(q, ),这称为推导 6) (q, a,a)=(q, )称为匹配，其中a第四章 自上而下语法分析 4.2 自上而下语法分析法二、下推自动机的形式

5、定义由CFG G= （VN ，P，S） 构造PDA M的算法：G= （VN ，P，S） M=（Q,H,q0,z0,F）令：Q=F=q0 即控制器只有一个状态 H= VN ; z0 =S; 映射关系如下： （1）对于形如A的产生式，有(q, ,A)=(q, ),这称为推导 （2）(q, a,a)=(q, )称为匹配，其中a。此PDA 停止于栈空。第四章 自上而下语法分析 4.2 自上而下语法分析法二、下推自动机的形式定义例 试给出接受语言Lancbn|n=0 的下推自动机。解： 1、生成L语言相应文法的产生式为S aSb|c 2、生成相应的PDA M=(Q ,H,q0,z0,F) PDA M=(

6、q,a,b,c,S,a,b,c, ,q,S,q) 其中 为：1) (q,a,a)= (q, ) 2) (q,b,b)= (q, ) 3) (q,c,c)= (q, ) 4) (q, S)=(q,aSb),(q,c)有限状态控制器 aacbb#输出带S#其分析过程：(q,aacbb,S) a(q,aacbb,aSb) (q,acbb,Sb) a(q,acbb,aSbb) (q,cbb,Sbb) b(q,cbb,cbb) (q,bb,bb) (q,b,b) (q, , )第四章 自上而下语法分析 4.2 自上而下语法分析法三、自上而下语法分析的思想从文法的开始符号开始，反复使用不同产生式进行推导以

7、谋求与输入符号串相匹配。对任何输入串W试图用一切可能的方法，从文法的开始符号出发，自上而下地为它建立一颗语法树。若建立成功，则W为相应文法的一个句子。注：此处的输入符号串是指词法分析结果的一串二元式。 试探法1、基本构成 约定：下推栈的初始状态包含两个符号：#S，其中#为栈底，S为文法开始符号。有限状态控制器中的状态只有一个，因此可以省缺。整个分析过程在语法分析程序控制下进行。在语法分析过程中将用到文法的产生式；所有这些产生式都被放在一个表中，该表通常被称为语法表。语法分析程序语法表 a+b#输出带S#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法第四章 自上而下语法分析 4

8、.2 自上而下语法分析法四、一般方法2、试探法的算法（语法分析程序所要执行动作）：（1）若栈顶符号x是非终结符，查询语法表，找出一个以x作为左部的产生式，x出栈，并将其右部以自右向左顺序入栈，且输出带记下产生式编号推导。（2）若栈顶符号x是终结符，且读头下的符号也是x，则x出栈，读头指向下一个符号匹配。（3）若栈顶符号x是终结符，但读头下的符号不是x，则匹配失败。这说明可能前面推导时选错了候选式，退回到上次推导现场(包括栈顶符号、读头的指针和输出带上信息)回溯。第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法2、试探法的算法 （4）回溯后选取另一候选式进行推导，若没有候选式可选

9、，则进一步回溯。若回溯到开始符号又已无候选式可选，则识别失败。（5）若栈内仅剩下“”，且读头也指向“”，则识别成功。第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #输出带S#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1 xAy#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请

10、分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1Ay#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1,2*y#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1,2*y#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析

11、符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1Ay#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1,3*y#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1,3y#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法例 文法产生式如下，请分析符号串

12、x*y#的过程 1) S xAy 2) A * 3)A *语法分析程序语法表 x * y #1,3#第四章 自上而下语法分析 4.2 自上而下语法分析法四、一般方法3、带回溯的自上而下分析法的缺陷1）如果文法存在左递归，语法分析会无限循环下去。2）若产生式存在多个候选式，选择哪个进行推导完全是盲目的。3）回溯会引起时间和空间的大量消耗。4）如果被识别的语句是错的，算法无法指出错误的确切位置。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法1 、消除左递归1)什么是左递归左递归：文法存在产生式P Pa直接左递归： P Pa间接左递归

13、： P Aa , APb2)消除左递归消除直接左递归消除间接左递归第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法2 、消除直接左递归设有文法G=(VN, VT ,P,S)，其中产生式P为 P P| , V+ ， V+ 且不以P开头将它转换为等价式： P P P P| 一般地：将P P 1| P 2|. |P m|1| 2|.| n 转换为： P 1P| 2 p| n P P 1P| 2P| mP| 例：文法G: (1)E E+T|T (2)T T*F|F (3)F (E)| i转化为G: (1) E TE E +TE| (2)

14、T FT T *FT| (3) F (E)| i转化为：P BaPP P aPbP| 注：只有最左边的P参加变换。例：文法G:P PaPb|BaP第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法3 、消除间接左递归1）把文法G的所有非终结符按任意顺序排列成P1,P2,Pn,然后按此顺序执行步骤2。2） for (i=1,i=n,i+) for (k=1,k=i-1,k+) 把形如Pi Pk的规则改写为 Pi 1 | 2 | ,n , 其中Pk 1| 2| ,n 消除Pi规则的直接左递归；3)删去从文法开始符号不可达的非终结符产生式

15、。3 、消除间接左递归注：1)此算法适用于消除不含形如P P的产生式且不含以为右部的产生式的文法 2)这里第二步所做的工作是： a)若产生式出现直接左递归则用消除直接左递归的方法消除掉。 b)若产生式右部最左符号是非终结符且其序号大于左部的非终结符，则不处理。 c)若序号小于左部的非终结符，则将这序号小的非终结符用其右部串来取代，然后消除新的直接左递归。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法例：对下面文法消除左递归： (1) S Qc|c (2)Q Rb|b (3) R Sa|a解：1）对非终结符重新排序：R、Q、S 2

16、）对R：S的序号大于R的序号，不处理。 对Q: R的序号1小于Q的序号2,所以改写Q Rb|b ，将R Sa|a的右部取代R，得到： Q Sab|ab|b,记为：（2)式； 此时， S的序号大于Q的序号,不再处理。 对S： Q的序号2小于S的序号3,所以改写S Qc|c，将Q Sab|ab|b的右部取代Q，得到S Sabc|abc|bc|c;出现直接左递归，变换为： S (abc|bc|c)S S abcS| 3）由于 R Sa|a和 Q Sab|ab|b中的R,Q对开始符号S来说都是不可达非终结符，所以删除它们。故最后消除左递归后文法为： S (abc|bc|c)S S abcS| 注：1）

17、若非终结符排列顺序不同，改写后的文法也不同，但它们是等价的。 2）开始符号不能改变。附：采用扩充BNF表示法改写含直接左递规的规则使用扩充的BNF表示() 表提因子例: Uax|ay|az 改写为Ua(x|y|z) 重复次数的指定例：|50.a表a* 任选符号，表可有可无例:+|-第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法4、消除回溯1)产生回溯的原因 进行推导时，若产生式存在多个候选式，选择哪个候选式进行推导存在不确定性。2)消除回溯的基本原则 对文法的任何非终结符，若能根据当前读头下的符号，准确的选择一个候选式进行推导，

18、那么回溯就可以消除。 注:之所以会产生回溯是因为在推导匹配的过程中存在虚假匹配。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法4、消除回溯 3)消除回溯的方法 预测与提左因子 4)预测 根据读头下符号选择候选式，使其第一个符号与读头下符号相同，或该候选式可推导出的第一个符号与读头下符号相同。这相当于向前看了一个符号，所以称为预测。 注：使用了预测之后，选择候选式不再是盲目的了，所以也就无需回溯。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法4、消除回溯 5)求候选

19、式的终结首符集 令G是一个不含左递归的文法，对G的所有非终结符的各候选式可求出它的终结首符First(). First()a| a,a VT 特例:若 ,那么 First()。 即， First()集合包括了的所有可能推导的开头终结符或可能的。*第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法4、消除回溯 5)求候选式的终结首符集 设A是非终结符，且A|（此时与称为非终结符A的候选式 ），当A出现在下推栈的栈顶，且输入符号为a时，应如何选择A的候选式进行推导？这里分为四种情况： (a)若aFirst(),而aFirst()，则选A

20、 (b)若a First(),而a First()，则选A (C) 若a First(),且a First(),则表示输入有错 (d)若aFirst(),且a First(),则表示终结首符集相交，需改写原文法，进行公因子提取。注：对First()=情况，留待讨论。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯不带回溯的自上而下分析算法4、消除回溯 6)采用预测方法后PDA的运行设A为出现在栈顶的非终结符，如果A的所有候选式的候选首符集都两两不相交，那么，PDA可以根据它所面临的读头符号，准确地指派某候选式替换A;但是，许多文法都存在一些非终结符，其所有

21、候选的首符集并不是两两不相交，这样，仍无法选择用哪个候选式进行推导。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯4、消除回溯 7)提取公共左因子 将某产生式A1| 2|. | n 改写为 AA A1|2|. |n 注：1)可通过反复提取左因子，就能把所有非终结符的所有候选首符集变为两两不相交。 2)反复提取左因子也有一定代价，因为在提取过程中会大量引入非终结符和产生式，会增加语法分析的复杂性。5、求候选式的终结首符集1) 求串的终结首符集First() a)定义 假定是文法G的一个符号串， V* ，则 First()a| a,a VT 注： 若 ,那么

22、 First()。 First()集合是的所有可能推导出的开头终结符或所组成的集合。 b)算法 设=X1X2Xn，其中Xi(VNVT),1i n,为了求的首符集，分两步：首先求Xi的首符集，然后再求的首符集。*第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首符集1) 求串的终结首符集First() b)算法 第一步：求出文法中每个文法符号的首符集； 若x VT ，则First(x)=x; 若XVN ，且有产生式X a，则将a加到 First(X)中;若X , 则也加入到 First(X)； 第四章 自上而下语法分析 4.2 自上而下语法

23、分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首符集1) 求串的终结首符集First() b)算法第一步：求出文法中每个文法符号的首符集； 若X Y1Y2Yk，其中Yj(VNVT),1j k,则按如下算法求First(X) j=0; FIRST(X)=; /初始化 REPEAT j=j+1; FIRST(X)=FIRST(X)(FIRST(Yj)-) UNTIL FIRST(Yj) 或j=k IF (j=k 且 FIRST(Yk) THEN FIRST(X)=FIRST(X) 第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首

24、符集1) 求串的终结首符集First() b)算法第二步：求First() 设 =X1X2Xn，其中Xi(VNVT),1i n ,则按如下算法求First() i=0; FIRST()=; /初始化 REPEAT i=i+1; FIRST()=FIRST()(FIRST(Xi)-) UNTIL FIRST(Xi) 或i=n IF (i=n 且 FIRST(Xn) THEN FIRST()=FIRST()第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首符集2) 求非终结符A的随符集Follow(A) a)定义 假定S是文法G的开始符号，对

25、于G的任何非终结符A，定义 Follow(A)a|S Aa,a VT 注： 若 SA,则规定：# Follow(A)。 Follow(A)集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。 +第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首符集2) 求非终结符A的随符集Follow(A) b)算法第一步：对文法开始符号S，将#加入到Follow(S)中；第二步：若B A是文法G的一个产生式，则将First()-加入到Follow(A)中;第三步：若B A是文法G的一个产生式,或B A是文法G的一个产生式,且 ，则将Follow(B

26、)加入到Follow(A)中； 注：这里的文法必须是消除了左递归且提取了左因子后的文法。 +第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首符集2) 求非终结符A的随符集Follow(A) c)例：对如下文法G(已加上编号)： 1.E TE 2.E +TE 3.E 4.T FT 5.T *FT 6.T 7.F i 8.F (E)求各非终结符号的终结首符集和随符集。第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯5、求候选式的终结首符集2) 求非终结符A的随符集Follow(A)解：First(E)=

27、First(T)=First(F)=(, i First(E)=+, First(T)=*, Follow(E)= Follow(E)=),# Follow(T)= Follow(T)=+,),# Follow(F)=*,+,),#第四章 自上而下语法分析 4.2 自上而下语法分析法五、自上而下分析法的一般问题-回溯第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造 （一）不带回溯的预测分析程序1、带预测分析的PDA 在PDA中加入预测分析之后，可以消除自上而下分析中出现回溯的现象。此时PDA可以改造为：预测分析程序预测分析表 a+b#输出带S#矩阵MA,a第

28、四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造 （一）不带回溯的预测分析程序1、带预测分析的PDA注：1）改造后，整个分析过程都在预测分析程序控制下工作。 2）预测分析程序用了一个预测分析表，它是预测分析程序分析时的主要依据。第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造 （一）不带回溯的预测分析程序2、预测分析表 预测分析表是一矩阵MA,a，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素MA,a是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入

29、符号a。第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造 （一）不带回溯的预测分析程序3、预测分析程序算法描述预测分析程序预测分析表 a输出带X#第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造（一）不带回溯的预测分析程序3、预测分析程序算法描述 设栈顶符号为X，读入符号为a，则 1)若X=a=#，则表示识别成功，退出分析程序； 2)若X=a#，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但Xa，则调用error处理； 3)若XVN，则查预测分析表M。若MX,a中存放着关

30、于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若MX,a中存放着出错标记，则调用相应Error处理。第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造（二）构造预测分析表 1、基本思想 1）若A 是一个产生式，a First(),那么当A是栈顶符号且将读入a时，选择取代A匹配成功的希望最大。故，MA,a元素为A 。 2）若A ，而 ，或 ；当A是栈顶符号且将读入a时，若a Follow(A),则栈顶的A应被匹配；此时读头不前进，让A的随符与读头下的符号进行匹配，这样输入串匹配成功的可能最大。故MA,a元素为A (这

31、里 或 )。+第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造（二）构造预测分析表 2、构造算法 1）假定A 是一个产生式，a First(),那么当A是栈顶符号且将读入a时， A 就应作为选用的侯选式， A 应填入 MA,a中。 2）若A ，而 First() ,对每个a Follow(A), 在MA,a元素中应填A (一般填A )。 3）把所有无定义的MA,a都填上出错标志。注：1）用此算法可以为任意文法G构造其分析表M。 2）若是二义文法或没有消除左递归和提取左因子的文法，构造出的M包含有重定义项。即，它们的MA,a中填有一个以上的产生式。例：对如下文

32、法G, 构造预测分析表 1.E TE 2.E +TE 3.E 4.T FT 5.T *FT 6.T 7.F i 8.F (E)解：1）求出各非终结符的First集和Follow集 First(E)=First(T)=First(F)=(, i First(E)=+, First(T)=*, Follow(E)= Follow(E)=),# Follow(T)= Follow(T)=+,),# Follow(F)=*,+,),#2）根据算法构造预测分析表 返回 i + * ( )#EETEETEEE +TEEETTFTTFTTTT *FTTTFF iF (E)第四章 自上而下语法分析 4.2 自

33、上而下语法分析法六、预测分析法与预测分析表的构造（三） LL(1)文法1、定义 若文法G的预测分析表M中不含有多重定义项，则称G为LL (1)文法。注：1)LL(1)文法是无二义的，二义文法一定不是LL(1)文法。2) LL的含义是从左到右扫描输入串，采用最左推导分析句子。3)数字1表示分析句子时需向前看一个输入符号。3)有LL(1)就有 LL(k)，LL(k)向前查看k个输入符号，选择候选式更加准确，但M的尺寸会以nk增长，其中n=|+1。对程序设计语言取k1就够了。第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造（三） LL(1)文法2、证明定理 文法G是LL(1)文法当且仅当对于G的每个非终结符A的任何两个不同产生式A |有： 1）First() First()= 2）若 First() ，则First() Follow(A)= 注：1）可以使用这个定理直接根据首符集、随符集来判断文法是否是LL(1)。但判断之前，必须消除左递归和提取公共左因子,因为包含左递归和公共左因子的文法肯定不是LL(1)文法。2）LL(1)文法只是上下文无关文法的一个子集。第四章 自上而下语法分析 4.2 自上而下语法分析法六、预测分析法与预测分析表的构造（三） LL(1)文法例：判断下面