语法分析总结练习.ppt

1、第四章 语法分析,自上而下分析法： 从文法的开始符号出发，反复使用文法的产生式，为待识别句子建立一个最左推导，以寻找与输入符号串匹配的推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，从叶子节点，由底上向上逐步建立一棵完整的语法树，直至归约到文法的开始符号（树根）。,自顶向下分析 递归下降分析法（递归子程序法） 预测分析法LL(1) 注意：首先消除左递归和提取左公因子。 自底向上分析 算符优先分析 LR分析: SLR(1), LR(1), LALR(1),FIRST集：设G=(VN,VT,P，S)是上下文无关文法 FIRST（）=a| =a,aVT, , V* 若 =则规定FRIST（

2、）,*,*,开始符号FIRST集和后跟符号FOLLOW集,自上而下分析,LL(1)文法,一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式ij ，下面的条件成立：,FIRST (i ) FIRST (j ) = ,对文法G的所有含有产生式的非终结符A定义它的FOLLOW(A)。对含有的A的所有候选式i ，希望有 FIRST (i ) FOLLOW (A ) = ,LL(1)含义： L：从左至右顺序扫描输入串； L：按最左推导方式； 1：每一次推导均向前查看一个输入符号准确指派产生式。 LL(1)文法性质: 没有公共左因子； 无二义性； 不含左递归。,LL（1）文法的判

3、别： 对文法计算FIRST、FOLLOW集合 判别文法是否为LL（1）文法,1）消除左递归： 消除直接左递归, 消除间接左递归,非LL(1)文法的改造,2）提左公因子 将产生式A | 变换为： A B B | ,预测分析法,对文法构造预测分析表,2）根据算法构造预测分析表,ETE,ETE,TFT,TFT,Fi,F (E),E +TE,E,E,T *FT,T,T,T,1）求出各非终结符的First集和Follow集,从输入串开始，进行最左归约，直到到达文法的开始符号为止。 大致过程：把输入符号逐个移进到一个栈里，当栈顶形成某个产生式的右部（ 句柄）时，把栈顶的这一部分替换成（归约为）它的左部符号

4、。称作“移进归约”分析。,自下而上分析,算符优先分析法,在文法的相邻符号之间建立优先关系。 从左到右依次扫描某句型中符号，且每扫视一个符号都检查它和后继符号间优先关系，以期找到句柄。,简单优先分析法,在文法的相邻终结符号符号之间建立优先关系。 从左到右依次扫描某句型中符号，且每扫视一个符号都检查它和后继符号间优先关系，以期找到最左素短语。,优先分析,LR分析,特征: 规范的； 符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)； 分析决策依据栈顶状态和现行输入符号。识别活前缀的 DFA. 四种技术 LR(0) SLR(1) LR(1) LALR(1),LR分析器概述,总控程序,

5、LR分析器的总控程序,总控程序的动作由当前栈顶状态Sm和扫描符号ai查表决定。 1、移进 把(Sm, ai)的下一状态S=GOTOSm，ai连同扫描符号进栈，栈顶成(S, ai)，扫描指针后移； 2、归约 用产生式A进行归约。若的长度为，则弹出栈顶项，使栈顶状态变为Sm- ，然后将(Sm- ,A)的下一状态S=GOTOSm- ,A连同A一起入栈，栈顶变为(S,A)。扫描指针不动，即不改变现行输入符号。 3、接受 4、报错 注：不管哪一类分析程序，总控程序的动作都一样。,例：由文法的LR分析表分析输入串 i*ii的LR动作过程。 1） E E+T 2）E T 3）T T*F 4）T F 5）F

6、(E) 6）F i,利用这张分析表分析输入串i*i+i的LR动作过程,0,#,i*i+i#,05,移进，状态转到5,03,#F,*i+i#,r6归约，0态遇F转3态,#i,*i+i#,02,#T,*i+i#,r4归约，0态遇T转2态,027,#T*,i+i#,移进，状态转到7,0275,#T*i,+i#,移进，状态转到5,02710,#T*F,+i#,r6归约,02,#T,+i#,r3归约,01,#E,+i#,r2归约,016,#E+,i#,移进,0165,#E+i,#,移进,0163,#E+F,#,r6归约,0169,#E+T,#,r4归约,01,#E,#,r1归约,成功,构造LR分析表的基

7、本方法,构造基本分析表的基本策略： 构造文法G的一个DFA，用于识别所有活前缀。 生成文法G的LR项目 对文法G的每个产生式右部添加一个圆点，称为G的一个LR(0)项目(简称项目)。 A 或A,Aa,aVT 移进项目 AB,BVN 待归约项目,A 归约项目,SS, SS 接受项目,识别所有规范句型全部活前缀的DFA,DFA的每个状态由若干LR项目集来表示。整个状态集称为LR项目集规范族。 将文法进行拓广，即增加产生式SS，并令S S作为初态项目I0。 定义和构造项目集的闭包。设I是拓广文法G的一个项目集，则定义和构造I的闭包CLOSURE(I)。 确定状态转移。 利用转换函数GO实现。 构造L

8、R项目集规范族Q。将所有项目集，以及所有状态间转移全部构造出来。,LR(0)分析表的构造,SLR(1)分析表的构造,LR(1)分析表的构造,LR(1)项目：形如(A，a)的二元式称为LR(1)项目。其中A是文法的一个产生式，a是终结符，称为搜索符。,若项目AIk，则对任何终结符a Follow(A)，置ACTIONk,a=rj；其中j是产生式A的编号，即按该产生式进行归约。,若规约项目AIi, 则对任何终结符a, 置ACTIONi, a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式；,1、设文法G(S): SS+aF|aF|+aF F*aF|*a 消除左递归和回溯

9、； 构造相应的FIRST和FOLLOW集合； 构造预测分析表,练习,答： SaFS|+aFS S+aFS| F*aF FF|,FIRST(S)=a,+ FOLLOW(S)=#FIRST(S)=+, FOLLOW(S)=#FIRST(F)=* FOLLOW(F)=+,#FIRST(F)=*,) FOLLOW(F)=+,#,2、文法G：EE+T|P T T+P P (E)|i 则句型P+T+i的句柄和最左素短语分别是_ A. P+T和i B. P和i C. i和P+T+i D. P和P 3、文法G：Sb|(T) T T,S|S 则FIRSTVT(T)=_ A. b,( B. b,) C. b,(

10、, ， D. b,), 4、文法G：EE*T|T T T+i|i 句子1+2*8+6按该文法进行归约，其值为_ A. 23 B. 42 C. 30 D. 17 5、一个_指明了在分析过程的某时刻所能看到产生式多大一部分。 A. 活前缀 B. 前缀 C. 项目 D. 项目集 6、对LR分析表的构造，不可能存在 动作冲突。 A移进/移进 B归约/归约 C移进/归约 D.以上都不对,B,C,B,C,A,7、请指出下图的LR分析表（a）、（b）、（c）分属于LR(0)、SLR(1)、LR(1)中的那一种，并说明理由。,解答： (a)表为LR(1)分析表，因为在不同行有相同的r2存在； (b)表为LR(

11、0)分析表，因为有rj的行每行都填满了，且同一行j相同，不同行j不同 (c)表为SLR(1)分析表，因为存在没填满rj的行，且不同行j不同。,(a),(b),(c),8、给出文法GS及图所示的LR(1)项目集规范族中的0、1、2、3、4。 GS: SS;B|B BBaA|A Ab(S),S S;B, #/;,S B, #/;,B BaA, #/;/a,B A, #/;/a,A b(S), #/;/a,S S , #,S S ;B, #/;,S B , #/;,B B aA, #/;/a,B A , #/;/a,A b (S), #/;/a,b,A,B,S,9、判定下面的文法是否为SLR(1)文法，若不是，请重写一个等价的SLR（1）文法。 GS: SMa|bMc|dc|bda Md,S S,S Ma,S bMc,S dc,S bda,M d,S b Mc,S b da,S bd a,M d ,b,M d,d,因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进归约冲突。等价的SLR（1）文法GS: S da|bdc|dc|bda,10、证明文法GS：SAaAb|BbBa A B 是LL（1）文法，但不是SLR（1）文法。,证明：FIRST(A