第4章自顶向下语法分析

1、 2022年2月25日 编编 译译 原原 理理S.PO.P语义分析、生成中间代码语义分析、生成中间代码生成目标程序生成目标程序代码优化代码优化语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理 2022年2月25日 编编 译译 原原 理理第第4 4章语法分析章语法分析 要求明确语法分析在编译过程所处的要求明确语法分析在编译过程所处的阶段和作用阶段和作用。 明确语法分析的明确语法分析的基本分析方法基本分析方法。 掌握掌握句柄、最左素短语、活前缀和项目句柄、最左素短语、活前缀和项目等基本概念。等基本概念。 掌握掌握消除文法左递归消除文法左递归的方法。的方法。 掌握

2、构造掌握构造LL(1)LL(1)分析表分析表的方法，会使用的方法，会使用LL(1)LL(1)分析法分析法分分析句子。析句子。 掌握构造掌握构造优先关系表优先关系表的方法，会使用的方法，会使用算符优先分析法算符优先分析法分析句子。分析句子。 掌握构造掌握构造LR(0)LR(0)、SLR(1)SLR(1)分析表分析表的方法，会使用的方法，会使用LRLR分析分析法法分析句子。分析句子。教学目标教学目标 2022年2月25日 编编 译译 原原 理理 4.1 4.1 语法分析的任务语法分析的任务 4.2 4.2 自顶向下分析法自顶向下分析法 4.3 4.3 自底向上分析法自底向上分析法 4.4 4.4

3、算符优先分析法算符优先分析法 4.5 LR4.5 LR分析法分析法教学内容教学内容 2022年2月25日 编编 译译 原原 理理任务：任务：根据文法规则，从源程序单词符号串中识别出语法根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。成分，并进行语法检查。 两大类分析方法：两大类分析方法：自顶向下分析自顶向下分析自底向上分析自底向上分析4.14.1语法分析的任务语法分析的任务 2022年2月25日 编编 译译 原原 理理+若若xS 则则x L(GS) 否则否则x L(GS) GS存在主要问题存在主要问题: 回溯问题回溯问题,左递归问题左递归问题主要方法：主要方法：递归子程序法、

4、递归子程序法、 LL分析法分析法自顶向下分析算法的基本思想为：自顶向下分析算法的基本思想为：自底向上分析算法的基本思想为：自底向上分析算法的基本思想为：+若若xS 则则x L(GS) 否则否则x L(GS) GS存在主要问题存在主要问题:“可归约串可归约串”的识别问题的识别问题主要方法：主要方法：算符优先分析法、算符优先分析法、 LR分析法分析法 2022年2月25日 编编 译译 原原 理理4.24.2自顶向下分析法自顶向下分析法4.2.1 自顶向下分析的一般过程自顶向下分析的一般过程从从S S出发采用最左推导，试图逐步推出输入串出发采用最左推导，试图逐步推出输入串, L(GS)?S S作为语

5、法树的根，试图自上而下地为作为语法树的根，试图自上而下地为构造一棵语法树构造一棵语法树若叶结点从左向右排列恰好若叶结点从左向右排列恰好，则表示，则表示是文法的句子，是文法的句子，而这棵语法树就是句子而这棵语法树就是句子的语法结构的语法结构若构造不出语法树，则若构造不出语法树，则不是文法的句子不是文法的句子 2022年2月25日 编编 译译 原原 理理【例】【例】 =acbGS:SaAbAcd|c 分析过程是设法建立一分析过程是设法建立一棵语法树棵语法树,使语法树的末端结使语法树的末端结点与给定符号串相匹配点与给定符号串相匹配.1.开始开始:令令S为根结点为根结点 S2.用用S的右部的右部,符号

6、串去匹配输入串符号串去匹配输入串 SaAb完成一步推导完成一步推导SaAb 检查检查 a-a匹配匹配 A是非终结符是非终结符,将匹配任务交给将匹配任务交给A 2022年2月25日 编编 译译 原原 理理3.选用选用A的右部符号串匹配输入串的右部符号串匹配输入串 A有两个右部有两个右部,选第一个选第一个 aAbcdS完成进一步推导完成进一步推导Acd 检查检查,c-c匹配匹配,b-d不匹配不匹配(失败失败)但是还不能冒然宣布但是还不能冒然宣布 L(GS) 4.回溯回溯 即砍掉即砍掉A的子树的子树 改选改选A的第二右部的第二右部SaAbcAc 检查检查 c-c匹配匹配 b-b匹配匹配建立语法树建立

7、语法树,末端结点为末端结点为acb与输入与输入acb相匹配相匹配,建立了推导序列建立了推导序列 SaAbacbacb L(GS)=acbGS: SaAbAcd|c 2022年2月25日 编编 译译 原原 理理自顶向下分析方法分类自顶向下分析方法分类确定的确定的不确定的不确定的回溯回溯 2022年2月25日 编编 译译 原原 理理1.回溯问题回溯问题什么是回溯（什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部地退回去重做叫回溯回溯造成回溯的条件：造成回溯的条件： 文法中，对于某个非终结符号的文法中，对于某个非终结符号的规则其右部规则其右部有多个选

8、择有多个选择，并根据所面临的输入符号不能准确，并根据所面临的输入符号不能准确地确定所要的选择时，就可能出现回溯。地确定所要的选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的低效率，只有在理论上的意义而无实际意义严重的低效率，只有在理论上的意义而无实际意义4.2.2 自顶向下分析存在的主要问题自顶向下分析存在的主要问题 2022年2月25日 编编 译译 原原 理理迷宫求解迷宫求解 2022年2月25日 编编 译译 原原 理理效率低的原因效率低的原因1)语法分析要重做语法分析要重做2)语义处理工作要推倒重来语义处理工作要推倒重来 2022年2月25日 编编 译译 原原 理理消除回溯的

9、途径：消除回溯的途径：改写文法改写文法对具有多个右部的规则对具有多个右部的规则反复反复提取提取左因子左因子【例】对下述两个产生式，提取公共左因子改造文法。【例】对下述两个产生式，提取公共左因子改造文法。if E then S1 else S2 if E then S1 if E then S1 U U else S2 | 2022年2月25日 编编 译译 原原 理理A1|2|n如果如果1n中还有几个首符号相同，可反复提取中还有几个首符号相同，可反复提取引入了许多非终结符和引入了许多非终结符和产生式产生式 AAA 1|2|n 2022年2月25日 编编 译译 原原 理理2.左递归问题左递归问题【

10、例】文法【例】文法GE：EE+T|TTT*F|FF(E)|i给出给出i*i+i自顶向下的分析过程。自顶向下的分析过程。 左递归文法会使自顶向下分析法陷入死循环左递归文法会使自顶向下分析法陷入死循环 如果文法具有间接左递归，则也将发生上述问题，只不过循如果文法具有间接左递归，则也将发生上述问题，只不过循环的圈子兜的更大环的圈子兜的更大要实行自顶向下分析，必须要消除文法的左递归要实行自顶向下分析，必须要消除文法的左递归从左向右扫描源程从左向右扫描源程序，同时实施最左序，同时实施最左推导推导 2022年2月25日 编编 译译 原原 理理（1）消除直接左递归消除直接左递归方法一：使用方法一：使用EBN

11、F表示来表示来改写文法改写文法【例】文法【例】文法GE：EE+T|TTT*F|FF(E)|iE T+TT F*F F(E)|i A |A 规则一规则一A 花括号花括号 表示符号串表示符号串x出现零次或出现零次或多次。多次。 2022年2月25日 编编 译译 原原 理理【例】文法【例】文法GE：EE+T| E-T|TTT*F| T/F|F F(E)|iE T(+|)TT F(*|/)F F(E)|i AA |A 规则二规则二A A( | ) 圆括号（圆括号（ ）利用圆括号可提出一个非终结利用圆括号可提出一个非终结符的多个产生式右部的公共因符的多个产生式右部的公共因子。子。 2022年2月25日

12、编编 译译 原原 理理【例】【例】 if | if ；else if ；else 方括号方括号 方括号用来表示可选项。方括号用来表示可选项。x = x或或 ，表示符号串，表示符号串x可出现一可出现一次或不出现。次或不出现。 2022年2月25日 编编 译译 原原 理理方法二：将左递归规则改为右递归规则方法二：将左递归规则改为右递归规则AA | 课堂练习课堂练习【例】文法【例】文法GE：EE+T| E-T|TTT*F| T/F|F F(E)|iETEE+TE|-TE| TFTT*FT| /FT| F(E)|i消除左递归消除左递归A AA A| 2022年2月25日 编编 译译 原原 理理同一非终

13、结符有多个候选式时同一非终结符有多个候选式时 引起回溯的原因引起回溯的原因 【例】【例】 =acbGS: SaAbAcd|c（1 1）候选式的候选式的首首终结符号相同终结符号相同 （2 2）候选式的候选式的首首终结符号相同终结符号相同【例】【例】 SAaAa| 2022年2月25日 编编 译译 原原 理理LL的含义的含义自左向右扫描分析输入符号串自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导从识别符号开始生成句子的最左推导LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看向前看k个输入符号，才能唯一确定当前

14、应选择的规则个输入符号，才能唯一确定当前应选择的规则4.2.3 LL(1)4.2.3 LL(1)文法文法在自上而下的分析过程中，为了避免回溯，对描述语言的在自上而下的分析过程中，为了避免回溯，对描述语言的文法有一定的要求，即要求描述语言的文法是文法有一定的要求，即要求描述语言的文法是LL（1）文法。）文法。 2022年2月25日 编编 译译 原原 理理同一非终结符有多个候选式时同一非终结符有多个候选式时 引起回溯的原因引起回溯的原因 【例】【例】 =acbGS: SaAbAcd|c（1 1）候选式的候选式的首首终结符号相终结符号相同同（2 2）候选式的候选式的首首终结符号相终结符号相同同【例】

15、【例】 SAaAa| 2022年2月25日 编编 译译 原原 理理 S-S-文法：文法： 每个产生式右边都以终每个产生式右边都以终结符开始；结符开始； 同一个非终结符的各个同一个非终结符的各个侯选式的首终结符不同侯选式的首终结符不同； 例如例如: :文法文法GS:GS:(1)SaBC(1)SaBC(2)BbC(2)BbC(3)BdB(3)BdB(4)Cc(4)Cc(5)Ca(5)Ca分析句子分析句子adbcaadbca 为了保证能够进行确定的自顶向下为了保证能够进行确定的自顶向下的分析，文法应该满足在分析的过程中的分析，文法应该满足在分析的过程中，每次对产生式的选择都是唯一的。，每次对产生式的

16、选择都是唯一的。 2022年2月25日 编编 译译 原原 理理 Q-Q-文法文法： 每个产生式右边都为每个产生式右边都为或或以终结符开始；以终结符开始； 具有相同左部的产生式具有相同左部的产生式具有不相交的具有不相交的可选集可选集； 例如例如: :文法文法GS:GS:(1)SaBC(1)SaBC(2)BbC(2)BbC(3)BdB(3)BdB(4)B (4)B (5)Cc(5)Cc(6)Ca(6)Ca分析句子分析句子adaada 2022年2月25日 编编 译译 原原 理理 一个上下文无关文法称为是一个上下文无关文法称为是LLLL（1 1）文法，当且仅）文法，当且仅当同一非终结符的各个产生式的

17、可选集互不相交。当同一非终结符的各个产生式的可选集互不相交。 LL(1)LL(1)含义含义: : 自左向右扫描输入串自左向右扫描输入串, ,使用最左推导方法分析句子使用最左推导方法分析句子,1,1表示表示分析时需要向前查看一个符号分析时需要向前查看一个符号为判别一个文法是否为为判别一个文法是否为LLLL（1 1）文法，需引进三个集合）文法，需引进三个集合： FIRST,FOLLOWFIRST,FOLLOW和和SELECTSELECT。 2022年2月25日 编编 译译 原原 理理1. FIRST1. FIRST集集 FIRST()：从从可能推导出的所有开头终结符号或可能推导出的所有开头终结符号

18、或对于文法对于文法G的所有非终结符的每个候选式的所有非终结符的每个候选式 ，即，即A ,其其首首终结符号集合称为终结符号集合称为FIRST集，定义如下：集，定义如下： ，则规定，则规定 FIRST( )若若 【例】【例】 SaAbAcd|ca ，aVTFIRST( )=a| FIRST(aAb) =aFIRST(cd) =cFIRST(c) =c【例】【例】 SAaAa| FIRST(a) =aFIRST( ) = FIRST(Aa) =aFIRST(S) =aFIRST(A) =cFIRST(S) =aFIRST(A) =a, 2022年2月25日 编编 译译 原原 理理（1 1）若）若=a

19、=a，且，且aVaVT T ，则，则aFIRST()aFIRST()； 例：例： FIRST(i)=i FIRST(+TE)=+ETEE+TE| TFTT*FT| F(E)|i构造构造FIRSTFIRST集的算法集的算法(P67)(P67)（2 2）若）若=X=X，XVXVN N，且有产生式，且有产生式XbXb，则把，则把b b加入加入到到FIRST()FIRST()中；中； 例：例： FIRST(FT)=(,i 2022年2月25日 编编 译译 原原 理理 将将FIRST(XFIRST(X1 1) )中的一切非中的一切非的终结符加进的终结符加进FIRST()FIRST()； 若若FIRST(

20、XFIRST(X1 1),),则将则将FIRST(XFIRST(X2 2) )中的一切非中的一切非的终结符的终结符加进加进FIRST()FIRST()； 若若FIRST(XFIRST(X1 1) )且且FIRST(XFIRST(X2 2),),则将则将FIRST(XFIRST(X3 3) )中的一中的一切非切非的终结符加进的终结符加进FIRST()FIRST()； 依此类推，若对于一切依此类推，若对于一切1in,FIRST(X1in,FIRST(Xi i) )，则将，则将加进加进FIRST()FIRST()。（3 3）若）若=X=X1 1X X2 2 X Xn n，其中，其中X Xi iVVN

21、 N , 1in , 1in；ETEE+TE| TFTT*FT| F(E)|i例：例：FIRST(FT)= 注意：要顺序往下做，一旦不满足条件，注意：要顺序往下做，一旦不满足条件，过程就要中断进行过程就要中断进行FIRST(F)-=(,i 2022年2月25日 编编 译译 原原 理理FIRST(F)=(,iFIRST(T )=*,FIRST(T)=FIRST(F)-=(,iFIRST(E )=+,FIRST(E)= FIRST(T)-=(,iFIRST(TE)=FIRST(T)-=(,iFIRST(+TE)=+ FIRST()=FIRST(FT)= FIRST(F)-=(,iFIRST(*FT

22、) =*FIRST(（E）)=(FIRST(i)=i【例】【例】 GEGEETEE+TE| TFTT*FT| F(E)|i 2022年2月25日 编编 译译 原原 理理2. FOLLOW2. FOLLOW集集 FOLLOW(A)：是所有句型中紧接是所有句型中紧接A之后的终结符号或之后的终结符号或$对 于 文 法对 于 文 法 G 的的 非 终 结 符 的 后 继 符 号 集 称 为非 终 结 符 的 后 继 符 号 集 称 为FOLLOW集，定义如下：集，定义如下： A，则规定，则规定$FOLLOW(A)若若SAa，a VTFOLLOW(A) =a|S ETEE+TE| TFTT*FT| F(

23、E)|iT+TE ，则，则+FOLLOW(T)E 2022年2月25日 编编 译译 原原 理理构造集合构造集合FOLLOW的算法的算法(P67)（1）若为开始符号，则把）若为开始符号，则把“#”加入加入FOLLOW(A)中；中；（2）若）若B A ( )，则把，则把FIRST( )- 加入加入FOLLOW(A)中；中； 注：注：FOLLOW集合中不能有集合中不能有（3）若）若B A 或或B A ，且，且 则把则把FOLLOW(B)加入加入FOLLOW(A) 中。中。 ，ETEE+TE| TFTT*FT| F(E)|i$FOLLOW(E)由由F(E)可知，可知， )FOLLOW(E)由由ETE，

24、应把，应把FOLLOW(E)加入加入FOLLOW(E)由由E + TE 且且E ，应把应把FOLLOW(E )加入加入FOLLOW(T) 2022年2月25日 编编 译译 原原 理理【例】【例】 GEGEETEE+TE| TFTT*FT| F(E)|i求求FOLLOWFOLLOW(E)=$,) E是开始符号是开始符号$FOLLOW(E) 又又F (E) )FOLLOW(E)FOLLOW(E)=$,) E TE FOLLOW(E)加入加入 FOLLOW(E)FOLLOW(T)=+,), $ E +TEFIRST(E)-加入加入FOLLOW(T) 又又E， FOLLOW(E)加入加入FOLLOW(

25、T)FOLLOW(T)= FOLLOW(T)= +,), $ T FT FOLLOW(T)加入加入FOLLOW(T)FOLLOW(F)=*,+,), $ T FT FOLLOW(F)=FIRST（T）- 又又T FOLLOW(T)加入加入FOLLOW(F)FIRST(F)=(,iFIRST(T)=*,FIRST(T) =(,iFIRST(E)=+,FIRST(E)=(,i 2022年2月25日 编编 译译 原原 理理例例 设文法设文法GSGS：1 S A1 S A2 A BA2 A BA 3 A3 A iBA iBA4 B CB4 B CB 5 B5 B +CB +CB6 C ) A6 C )

26、 A* *| (| (改写成简单产生式改写成简单产生式1 S A1 S A2 A BA2 A BA 3 A3 A iBA iBA 4 4 A A 5 B CB5 B CB 6 B6 B +CB +CB 7 7 B B 8 C ) A8 C ) A* *9 C (9 C ( 2022年2月25日 编编 译译 原原 理理3.SELECT 集合集合(P67)设设AA是文法是文法G G的任意产生式，它的编号为的任意产生式，它的编号为i i，则它的可选集则它的可选集SELECTSELECT（i i）定义如下：）定义如下：（1）如果）如果，且，且是不可空的，则是不可空的，则 SELECT（i）=FIRST

27、（）（2 2）如果）如果，但，但是可空的，则是可空的，则 SELECTSELECT（i i）=FIRST=FIRST（） FOLLOW FOLLOW（A A）（3 3）如果）如果=，即产生式为，即产生式为AA则则 SELECTSELECT（i i）=FOLLOW=FOLLOW（A A） 2022年2月25日 编编 译译 原原 理理若一个文法满足以下条件，则称该文法若一个文法满足以下条件，则称该文法G G为为LL(1)LL(1)文法：文法：（1 1）文法）文法不含左递归不含左递归；（2 2）对于每个非终结符）对于每个非终结符A A的各个候选式的首的各个候选式的首终结符号集终结符号集两两不相交两两

28、不相交。即，如果。即，如果AA1 1|2 2|n n，则，则FIRST(FIRST(i i)FIRST()FIRST(j j)= )= ，其中，其中1i1i，jnjn，且，且ijij。（3 3）对于文法中每个非终结符）对于文法中每个非终结符A A，若它某个候选式的首，若它某个候选式的首终结符号集包含终结符号集包含，则，则FIRST(A)FOLLOW(A)FIRST(A)FOLLOW(A)4 4LL(1)LL(1)文法的判别条件文法的判别条件 2022年2月25日 编编 译译 原原 理理例例 文法文法GSGS改写成简单产生式改写成简单产生式1 S A1 S A2 A BA2 A BA 3 A3

29、A iBA iBA 4 4 A A 5 B CB5 B CB 6 B6 B +CB +CB 7 7 B B 8 C ) A8 C ) A* *9 C (9 C (因为因为: :select(3)select(3)select(4)=select(4)=select(6)select(6)select(7)=select(7)=select(8)select(8)select(9)=select(9)=所以该文法是所以该文法是LL(1)LL(1)文法文法可选集计算如下：可选集计算如下：Select(1)Select(1)=first(A)=first(BA)=first(A)=first(BA)

30、=first(C)= ),( =first(C)= ),( Select(2Select(2)=first(BA)=first(C)=first(BA)=first(C)= ),( = ),( Select(3)=first(iBA)= i Select(3)=first(iBA)= i Select(4)=follow(A)Select(4)=follow(A)= follow(A)follow(S)= follow(A)follow(S) =* *, $, $ Select(5)Select(5)=first(CB)= ),( =first(CB)= ),( Select(6)=first

31、(+CB)=+Select(6)=first(+CB)=+Select(7)=follow(B)Select(7)=follow(B)=first(A=first(A ) follow(A) ) follow(A) follow(S)follow(S)=i, =i, * *, $ , $ Select(8)=first()ASelect(8)=first()A* *)= ) )= ) Select(9)=first()= ( Select(9)=first()= ( 2022年2月25日 编编 译译 原原 理理例文法例文法GEGE改写成简单产生式改写成简单产生式1 EE+T1 EE+T2 ET

32、2 ET3 TT3 TT* *F F4 4 TFTF5 F(E)5 F(E)6 Fid6 Fid消除左递归：消除左递归：1 ETE1 ETE2 E+TE2 E+TE3 E 3 E 4 4 TFTTFT5 T5 T* *FTFT6 T 6 T 7 F(E)7 F(E)8 Fid8 Fid可选集计算如下：可选集计算如下：Select(1)Select(1)=first(TE)=first(FT)=first(TE)=first(FT)= (= (，id id Select(2Select(2)=first(+TE)= + )=first(+TE)= + Select(3)=Select(3)= f

33、ollow(E) follow(E)= follow(E)= follow(E)=), $), $ Select(4)Select(4)=first(FT)= (=first(FT)= (，id id Select(5)Select(5)=first(=first(* *FT)= FT)= * * Select(6)Select(6)= follow(T)= follow(T)= follow(T)= follow(T)=first(E)=first(E)follow(E)follow(E)=+,=+,), $), $ Select(7)Select(7)=first(E)= ( =first

34、(E)= ( Select(8)Select(8)=first(id)= id =first(id)= id 因为因为select(2)select(2)select(3)= select(3)= select(5) select(5)select(6)= select(6)= select(7) select(7)select(8)= select(8)= 所以该文法是所以该文法是LLLL（1 1）文法。）文法。 2022年2月25日 编编 译译 原原 理理5 5某些非某些非LL(1)LL(1)文法到文法到LL(1)LL(1)文法的等价转换文法的等价转换 消除左递归和提取公共左因子消除左递归

35、和提取公共左因子 【例】【例】 GS:GS:SaSb|AAbAc|bBcBBa|aSaSb|AAbAc|bBcBaBBaB| 消除左递归消除左递归提取公提取公因子因子 SaSb|AAbAAAc|BcBaBBaB| LL(1)LL(1)文法的判别条件文法的判别条件LL(1)LL(1)文法文法 2022年2月25日 编编 译译 原原 理理 S SaSb|AaSb|A AbAAbA A AAc|BcAc|Bc B BaBaB B BaBaB | | SELECTSELECT(S SaSb)=aaSb)=a SELECT(SSELECT(SA)=bA)=b SELECT(ASELECT(AAc)=bA

36、c)=b SELECT(ASELECT(ABc)=aBc)=a SELECT(BSELECT(BaBaB )=a)=a SELECT(BSELECT(BaBaB )=a)=a SELECT(BSELECT(B )=FOLLOW(B)=FOLLOW(B) = = FOLLOW(BFOLLOW(B)=c)=c 2022年2月25日 编编 译译 原原 理理 它是一种确定的自上而下分析方法它是一种确定的自上而下分析方法, ,也是编译程序中使也是编译程序中使用得最为广泛的一类分析程序。用得最为广泛的一类分析程序。 要求：所依据的文法是要求：所依据的文法是LLLL（1 1）文法。）文法。 基本思想基本思想

37、：为文法中的每个非终结符编写一个函数（或：为文法中的每个非终结符编写一个函数（或子程序），这个函数或子程序的功能是识别由该非终结子程序），这个函数或子程序的功能是识别由该非终结符表示的语法成分。符表示的语法成分。 由于描述语言的文法常常是递归定义的，因此相应的这由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，组函数（或子程序）必然以相互递归的方式进行调用，所以将这种方法成为所以将这种方法成为“递归下降法递归下降法”。 2022年2月25日 编编 译译 原原 理理 一般情况下，用非终结符表示过程的名字，过程体则按一般情况下，用非终结符表示过程的名字

38、，过程体则按产生式右部符号串顺序编写。每匹配一个终结符，则再产生式右部符号串顺序编写。每匹配一个终结符，则再读入下一个符号，对于产生式右部的每一个非终结符，读入下一个符号，对于产生式右部的每一个非终结符，则调用相应的过程。当一个非终结符对应多个侯选式时则调用相应的过程。当一个非终结符对应多个侯选式时，则过程体将按可选集来决定选用哪个侯选式。在递归，则过程体将按可选集来决定选用哪个侯选式。在递归下降法中，递归子程序数等于文法中的非终结符个数。下降法中，递归子程序数等于文法中的非终结符个数。 2022年2月25日 编编 译译 原原 理理 构造递归下降分析程序时，每个函数名是相应的非终结符，构造递归

39、下降分析程序时，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。函数体则是根据规则右部符号串的结构编写。 （1 1）当遇到终结符）当遇到终结符a a时，则编写语句：时，则编写语句： if if （当前读入的输入符号（当前读入的输入符号=a)(=a)(匹配匹配),),读入下一个符号；读入下一个符号； if (ch = aif (ch = a） then READ(ch) else errorthen READ(ch) else error （2 2）当遇到非终结符）当遇到非终结符A A时，则编写语句调用相应的函数时，则编写语句调用相应的函数A A（）（）； （3 3）当遇到）

40、当遇到AA时，则编写语句：时，则编写语句： ifif（当前读入的符号（当前读入的符号FOLLOWFOLLOW（A A）,ERROR( );,ERROR( ); (4) (4)当某个非终结符的规则有多个侯选式时，按当某个非终结符的规则有多个侯选式时，按LLLL（1 1）文法）文法的条件唯一地选择一个侯选式进行匹配。的条件唯一地选择一个侯选式进行匹配。 2022年2月25日 编编 译译 原原 理理E +|-T| E (+|-) TT F| T (*|/)FF id|num| (E)EBNF表示表示E +|- T(+|-) T T F(*|/) F F id|num| (E)例：例：某种某种语言表达

41、式文法语言表达式文法 2022年2月25日 编编 译译 原原 理理E( ) if (sym=+| sym=- ) getsym( ); T( ); else T( ); while (sym=+| sym=- ) getsym( ); T( );E +|- T(+|-) T 2022年2月25日 编编 译译 原原 理理T F(*|/) FT( ) F( ); while (sym=*| sym=/) getsym( );F( ); 2022年2月25日 编编 译译 原原 理理F id|num| (E)F ( ) if(strcmp(sym,ident)=0) /当前读进的单词是标识符当前读进的

42、单词是标识符 getsym( ); else if (sym=num) getsym();/当前读进的单词是数字当前读进的单词是数字 else if(sym=( ) getsym ( );E( ); if(sym=) getsym( ); else error( ); else error ( ); 2022年2月25日 编编 译译 原原 理理 问题问题: :为什么要编成递归子程序？为什么要编成递归子程序？ 因为文法具有递归性。前面已经讲过，自顶向因为文法具有递归性。前面已经讲过，自顶向下分析不能处理左递归文法，若有左递归，则应改写文法下分析不能处理左递归文法，若有左递归，则应改写文法，但是消

43、除了左递归并不等于消除了文法中的所有递归性，但是消除了左递归并不等于消除了文法中的所有递归性质，此时文法有右递归性或自嵌入性。如在文法中可能有质，此时文法有右递归性或自嵌入性。如在文法中可能有如下规则：如下规则： UUUU UU UU 此仍为递归规则，所以要编成递归子程序。此仍为递归规则，所以要编成递归子程序。 2022年2月25日 编编 译译 原原 理理 优点：优点：最主要一点是编写速度快；最主要一点是编写速度快；由于分析器和文法的紧密对应性，容易保证语法分析器的由于分析器和文法的紧密对应性，容易保证语法分析器的正确性。至少使得错误都变得简单和易于发现。正确性。至少使得错误都变得简单和易于发

44、现。构造方法非常简单构造方法非常简单, ,程序结构清晰。程序结构清晰。 缺点：缺点： 递归调用较多，占用内存多、速度慢，递归调用较多，占用内存多、速度慢，如果所采用的高级语言不允许递归，则不能使用此方法如果所采用的高级语言不允许递归，则不能使用此方法 2022年2月25日 编编 译译 原原 理理4.2.5 LL(1)4.2.5 LL(1)分析法分析法自左向右自左向右扫描分析输入符号串扫描分析输入符号串从识别符号开始生成句子的从识别符号开始生成句子的最左推导最左推导 LL(1):向前看向前看一个一个输入符号，便能唯一确定产生式输入符号，便能唯一确定产生式 LL(k):向前看向前看k个个输入符号，

45、才能唯一确定产生式输入符号，才能唯一确定产生式基本思想：基本思想：预测分析法预测分析法 2022年2月25日 编编 译译 原原 理理对于对于LL(1)LL(1)文法，利用文法，利用SELECTSELECT集，我们还可以得到十分有集，我们还可以得到十分有助于句子分析的结果：助于句子分析的结果：(1)(1)分析过程某一步，当非终结符分析过程某一步，当非终结符U U正处于正处于栈顶栈顶时，时， 若若aaSELECT (USELECT (U ),),且且a a是是当前输入符号当前输入符号，则可选用产，则可选用产生式生式UU ； 若若aaSELECT (U),SELECT (U),且且a a是是当前输入

46、符号当前输入符号，则可选用，则可选用产生式产生式UU。(2)(2)由于由于LL(1)LL(1)文法的任何一对具有相同左部的产生式的文法的任何一对具有相同左部的产生式的SELECTSELECT集是不相交的，因此，集是不相交的，因此，根据现行的非终结符根据现行的非终结符( (已已在栈顶在栈顶) )和和当前的输入符号当前的输入符号就能唯一地确定分析过程中就能唯一地确定分析过程中的下一步动作，也就是说，我们完全可以为的下一步动作，也就是说，我们完全可以为LL(1)LL(1)文法文法构造一个确定的分析器。构造一个确定的分析器。 2022年2月25日 编编 译译 原原 理理a1 a2 a3 ai an#

47、分析表分析表M总控程序总控程序X1Xn-1Xn#LL(1)LL(1)分析器的逻辑结构：分析器的逻辑结构：分析栈、分析表、总控程序分析栈、分析表、总控程序文法符号文法符号根据栈顶符号根据栈顶符号X X和当前输入符号和当前输入符号a a来决定分析器的动作来决定分析器的动作 2022年2月25日 编编 译译 原原 理理总控程序总控程序预测分析表预测分析表分析栈分析栈SKSKS$a1X1a4X4$分析结束分析结束a3a2 2022年2月25日 编编 译译 原原 理理 1 1、分析栈、分析栈SKSK中的符号中的符号 X X1 1,X,X2 2,X,Xn n ，可以是终结符，可以是终结符，也可以是非终结符

48、。也可以是非终结符。 输入带输入带中的符号中的符号 a a1 1,a,a2 2,a,an n, ,必须是终结符。必须是终结符。 2 2、分析栈变化以预测分析表为依据；预测分析表的内容由、分析栈变化以预测分析表为依据；预测分析表的内容由文法的具体结构决定，通过计算产生式可选集生成的。文法的具体结构决定，通过计算产生式可选集生成的。 3 3、分析栈的变化，体现识别语法单位的推导过程。、分析栈的变化，体现识别语法单位的推导过程。 4 4、上述所有动作（读入符号、查询预测分析表、状态变换、上述所有动作（读入符号、查询预测分析表、状态变换、替换栈顶等）由总控程序操纵。、替换栈顶等）由总控程序操纵。 20

49、22年2月25日 编编 译译 原原 理理 预测分析表是根据文法产生式的可选集预测分析表是根据文法产生式的可选集(SELECT)(SELECT)构造的，可构造的，可用一个二维数组用一个二维数组 MA,aMA,a 来描述。来描述。 行行：文法中所有非终结符：文法中所有非终结符V VN N。 列列：文法中所有终结符：文法中所有终结符V VT T及文法结束符号及文法结束符号$ $。 矩阵元素：矩阵元素：（1 1）当前行非终结符当前行非终结符V VN N面临列终结符面临列终结符 V VT T时，继续推导所应采用的产生式，时，继续推导所应采用的产生式， （或产生式标号）。（或产生式标号）。 （2 2）也可

50、存放一个）也可存放一个ERRORERROR（或空白）（或空白） 表示此时输入串中存在语法错误。表示此时输入串中存在语法错误。 2022年2月25日 编编 译译 原原 理理ETEE+TE| TFTT*FT| F(E)|i分析表：二维矩阵分析表：二维矩阵M A i errorMA,a= i + * ( ) $ E ETE ETE E E +TE E E T TFT TFT T T T*FT T T F F i F(E) 2022年2月25日 编编 译译 原原 理理1.以FIRST和FOLLOW集合定义的算法： 对文法的每一条产生式U， 若aFIRST()，则MU,a=U； 若FIRST()，且bF

51、OLLOW(U) 则MU, b= U； 分析表M的其它元素均为出错标志error，通常用空白表示。2.2.用用SELECTSELECT集合定义算法，有以下步骤：集合定义算法，有以下步骤： 对文法对文法G G的每个产生式的每个产生式UU ，计算，计算SELECT(USELECT(U ）若若SELECTSELECT（UU ）=a, a,=a, a,则置则置MU,aMU,a为产生式为产生式UU ；若若SELECTSELECT（UU ）=a=a1 1,a,a2 2,a,an n, a, a1 1,a,a2 2,a,an n都是终结符号或都是终结符号或，则置，则置MU,aMU,a1 1=MU,a=MU,

52、a2 2=MU,a=MU,an n 产生式为产生式为UU 。 对所有尚未定义的对所有尚未定义的MU,a,MU,a,置上置上ERRORERROR（用空白表示）。（用空白表示）。如果如果 a SELECT(A ) a SELECT(A ) 则则 MA,a = A MA,a = A 2022年2月25日 编编 译译 原原 理理 select ( Sa )= a select ( S )= select ( S(T)= ( select (T ST)= a , ( select (T , ST)= , select (T ) = ) T , S TT TTSTTSTTSTTS (T) S SaS$,)

53、(a 预测分析表预测分析表 MA,a 如下如下:(1)Sa (1)Sa (2)S (2)S (3)S(T) (3)S(T) (4)T ST(4)T ST(5)T(5)TSTST(6)T(6)T例例 设有文法设有文法GS:GS:ST 2022年2月25日 编编 译译 原原 理理$和文法开始符号进和文法开始符号进S栈栈第一个输入符号读进第一个输入符号读进a将将 y1 y2 yn 代替代替x逆序逆序入入S栈，如果是栈，如果是就不入栈就不入栈。S栈顶符号出栈放栈顶符号出栈放X中中查查MX,a=x y1 y2 yn出错出错出错出错将下一个将下一个输入符号输入符号读进读进astopYYYNNNNY栈栈顶顶

54、符符号号出出栈栈指指针针后后移移M M X X, ,a a 是是预预测测分分析析表表元元素素栈栈中中符符号号与与输输入入符符号号都都是是结结束束符符号号$ $时时分分析析结结束束NYX =a ?X VTX VT？X $? a =$ ? 2022年2月25日 编编 译译 原原 理理 1)1)当栈顶符号和当前输入符号是同一个终结符。当栈顶符号和当前输入符号是同一个终结符。 栈顶元素出栈，输入指针后移。栈顶元素出栈，输入指针后移。 2)2)当栈顶非终结符当栈顶非终结符X X和当前输入符号和当前输入符号a a 不相同时，不相同时， 查预测分析表查预测分析表 若若 MX,a = x yMX,a = x

55、y1 1 y y2 2 y yn n 产生式右部产生式右部 y y1 1 y y2 2 y yn n 代替左部代替左部 x x 逆序入栈。逆序入栈。 若若 MX,a = x MX,a = x 单做栈顶元素出栈。单做栈顶元素出栈。 3)3)当栈顶符号和当前输入符号同时是当栈顶符号和当前输入符号同时是“ “ $ ”$ ” 分析过程正常结束。分析过程正常结束。 4)4) 其他情况其他情况 出错处理。出错处理。 2022年2月25日 编编 译译 原原 理理 下面所要构造的非确定的自上而下分析器属于一般的下推下面所要构造的非确定的自上而下分析器属于一般的下推自动机（自动机（PDAPDA）类。）类。 所谓

56、一个下推或栈自动机（所谓一个下推或栈自动机（Stack AutomatonStack Automaton）, ,非形式地非形式地说，应包含：说，应包含：一个输入符号串；一个输入符号串；一个读头，它从左至右移动，每次读进一个输入符一个读头，它从左至右移动，每次读进一个输入符号；号；一个有穷状态自动机，用于控制整个系统的操作；一个有穷状态自动机，用于控制整个系统的操作；一个后进先出下推栈，一个后进先出下推栈， 2022年2月25日 编编 译译 原原 理理下推自动机的非空移动下推自动机的非空移动: : 2022年2月25日 编编 译译 原原 理理形式上说，一个形式上说，一个PDAPDA是一个七元组：

57、是一个七元组：(Q,H, q(Q,H, q0 0, Z, Z0 0,F),F) Q Q 是状态的有穷集，它的每个元素称为一个状态；是状态的有穷集，它的每个元素称为一个状态； 是有穷的字母表，它的每个元素是一个输入符号；是有穷的字母表，它的每个元素是一个输入符号； H H 是有穷的下推栈字符表，它的每个元素称为一个栈符是有穷的下推栈字符表，它的每个元素称为一个栈符号。号。 q q0 0QQ 是该是该PDAPDA的初态；的初态； Z Z0 0HH 是下推栈的初始符号；是下推栈的初始符号； F F Q Q 是一个终态集是一个终态集( (或接收状态集或接收状态集) )；它的每个元素称；它的每个元素称为

58、终态；为终态；( (可空可空) )。 2022年2月25日 编编 译译 原原 理理 是描述PDA动作与状态变化的。 PDA的动作可用定义式来表示为：定义式来表示为：（q,a,z)=(pq,a,z)=(p1 1,h,h1 1),(p),(p2 2,h,h2 2)(p)(pn n,h,hn n)它的含义为：它的含义为： 在控制器当前状态为q,下推栈顶符号为z ,输入符号为a的情况下，把控制器的状态改为pi,用hi 替换栈顶的z，并让读头右移一格。 2022年2月25日 编编 译译 原原 理理PDAPDA的一个构形是一个三元组：的一个构形是一个三元组：(q,w,h)(q,w,h) 其中，其中，qQq

59、Q；ww* *是尚待扫描的输入串，包括读头当前所是尚待扫描的输入串，包括读头当前所指的符号；指的符号；hHhH* *是栈的内容。是栈的内容。 PDAPDA的一次移动可看作是从一种构形变换成另一种构形的一的一次移动可看作是从一种构形变换成另一种构形的一种方式。反过来，构形又为定义种方式。反过来，构形又为定义PDAPDA的移动提供了一种更简的移动提供了一种更简单的手段。我们称单的手段。我们称(q,ax,Zh)(p,x,hh)(q,ax,Zh)(p,x,hh)是一次可能的移动，当且仅当是一次可能的移动，当且仅当(p,h)(q,a,Z) (p,h)(q,a,Z) 。 常用常用+表示由一次或多次移动组成

60、的序列。用表示由一次或多次移动组成的序列。用* *表示由零表示由零次或多次移动组成的序列。注意次或多次移动组成的序列。注意“零零”次移动并不改变当前次移动并不改变当前的构形。的构形。 2022年2月25日 编编 译译 原原 理理 PDA M PDA M 所识别的所识别的语言语言L L（M M）可表示为：可表示为：L L（M M）= =* *（P P0 0, ,，Z Z0 0)* *(P,(P, , , ) )(空栈接收）或空栈接收）或者者L L（M M）= =* *（P P0 0, ,，Z Z0 0)* *(P,(P, ,h,h) ) p p FF（终态（终态接收）接收） 2022年2月25日