《编译原理总结4语法.ppt》由会员分享，可在线阅读，更多相关《编译原理总结4语法.ppt（17页珍藏版）》请在三一办公上搜索。
1、1,S.P,O.P,语法分析,2,任务：根据文法规则，从源程序单词符号串中识别出 语法成分，并进行语法检查。,两大类分析方法：,自顶向下分析,自底向上分析,4.1 语法分析的任务,3,存在主要问题:回溯问题,左递归问题,主要方法：递归下降分析法、LL分析法,自顶向下分析算法的基本思想为：,自底向上分析算法的基本思想为：,存在主要问题:“可归约串”的识别问题,主要方法：算符优先分析法、LR分析法,4.1 语法分析的任务,4,自顶向下分析的一般过程,从S出发采用最左推导，试图逐步推出输入串,L(GS)?S作为语法树的根，试图自上而下地为构造一棵语法树：若叶结点从左向右排列恰好，则表示是文法的句子，
2、而这棵语法树就是句子的语法结构；若构造不出语法树，则不是文法的句子。,4.2 自顶向下分析法概述,5,自上而下分析中的关键问题：左递归：当文法中出现左递归时，会使分析过程陷入无限循环。回溯：假定要被代换的非终结符号是V，且有 n 条规则：VA1|A2|An，那么如何确定 用哪个右部Ai去替代V呢？会造成回溯。,4.2 自顶向下分析法概述,回溯问题,左递归问题,6,1.回溯问题,什么是回溯（backtracking）?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件：,文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。,回
3、溯带来的问题：,严重的低效率，只有在理论上的意义而无实际意义。,4.2 自顶向下分析法概述,7,消除回溯的途径：,改写文法,对具有多个右部的规则反复提取左因子,例：对下述两个产生式，提取公共左因子改造文法。if E then S1 else S2 if E then S1,改造为：if E then S1U Uelse S2|,4.2 自顶向下分析法概述,8,A1|2|n,如果1n中还有几个首符号相同，可反复提取引入了许多非终结符和产生式。,A AA 1|2|n,提取公共左因子,4.2 自顶向下分析法概述,9,某些文法不能在有限步骤内提取左公共因子。,【例】文法G:,SAp|Bq AaAp|d
4、 BaBq|e,SaApp|aBqqSdp|eqAaAp|d BaBq|e,Sa(App|Bqq),SaSSApp|BqqSdp|eqAaAp|dBaBq|e,SaSSdp|eqSaAppp|aBqqqSdpp|eqqAaAp|dBaBq|e,可以看出产生式A、B继续替换，只能使文法的产生式愈来愈多无限增加下去，变成循环递归，不能得到提取左公共因子的预期结果。,不一定每个文法的公共左因子都能在有限的步骤 内替换成无公共左因子的文法。一个文法提取了左公共因子后，只解决了相同左 部产生式右部的FIRST集不相交问题，当改写后的文 法不含空产生式，且无左递归时，则改写后的文法是 LL(1)文法。否则
5、还需用LL(1)文法的定义进行判断 才能确定是否为LL(1)文法。,4.2 自顶向下分析法概述,10,2.左递归问题,例：文法GE：EE+T|T TT*F|F F(E)|i给出i*i+i自顶向下的分析过程。,左递归文法会使自顶向下分析法陷入死循环,如果文法具有间接左递归，则也将发生上述问题，只不过循环的圈子兜的更大。,要实行自顶向下分析，必须要消除文法的左递归,从左向右扫描源程序，同时实施最左推导。,4.2 自顶向下分析法概述,11,（1）消除直接左递归,方法一：使用EBNF表示来改写文法,例：文法GE：EE+T|T TT*F|F F(E)|i,ET+TTF*F F(E)|i,A|A,规则一,
6、A,4.2 自顶向下分析法概述,12,例：文法GE：EE+T|E-T|T TT*F|T/F|F F(E)|i,ET(+|)TTF(*|/)F F(E)|i,AA|A,规则二,4.2 自顶向下分析法概述,13,方法二：将左递归规则改为右递归规则,AA|,课堂练习,文法GE：EE+T|E-T|T TT*F|T/F|F F(E)|i,ETEE+TE|TFTT*FT|F(E)|i,消除左递归,AAAA|,4.2 自顶向下分析法概述,14,间接左递归直接左递归右递归,【例】文法G:AaB ABb BAc Bd,AaBABbBaBcBBbcBd,BaBc|dBBbc,B(aBc|d)BBbcB|,AaBA
7、BbB(aBc|d)BBbc B|,4.2 自顶向下分析法概述,(2)消除间接左递归,15,算法步骤如下：,4.2 自顶向下分析法概述,(2)消除间接左递归,16,（2）从A1开始消除左部为A1的产生式的直接左递归，然后把左部 为A1的所有规则的右部逐个替换左部为A2右部以A1开始的产 生式中的A1，并消除左部为A2的产生式中的直接左递归。继 而以同样方式把A1、A2的右部代入左部为A3右部以 A1 或 A2 开始的产生式中，消除左部为A3的产生式之直接左递归，直 到把左部为A1，A2，An-1的右部代入左部为An的产生式中，从An中消除直接左递归。,（1）把文法的所有非终结符按某一顺序排序,如:A1|A2|An,（3）去掉无用产生式。,消除递归的算法,4.2 自顶向下分析法概述,17,1）把G的非终结符整理成某种顺序A1，A2，An,2）for i:=1 to n do for j:=1 to i-1 do 把每个形如Ai=Ajr的规则替换成 Ai=(1|2|k)r 其中Aj=1|2|k是当前 全部Aj的规则 消除Ai规则中的直接左递归,3）去掉无用的产生式,4.2 自顶向下分析法概述,
