编译原理总结4语法.ppt

1S.PO.P语义分析、生成中间代码语义分析、生成中间代码生成目标程序生成目标程序代码优化代码优化语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理语法分析语法分析2任务：任务：根据文法规则，从源程序单词符号串中识别出根据文法规则，从源程序单词符号串中识别出 语法成分，并进行语法检查。语法成分，并进行语法检查。两大类分析方法：两大类分析方法：自顶向下分析自顶向下分析自底向上分析自底向上分析4.1 4.1 语法分析的任务语法分析的任务3存在主要问题存在主要问题:回溯问题回溯问题,左递归问题左递归问题主要方法：主要方法：递归下降分析法、递归下降分析法、LL分析法分析法自顶向下分析算法的基本思想为：自顶向下分析算法的基本思想为：自底向上分析算法的基本思想为：自底向上分析算法的基本思想为：+若若Sx 则则x L(GS)否则否则x L(GS)GS存在主要问题存在主要问题:“可归约串可归约串”的识别问题的识别问题主要方法：主要方法：算符优先分析法、算符优先分析法、LR分析法分析法4.1 4.1 语法分析的任务语法分析的任务+若若xS 则则x L(GS)否则否则x L(GS)GS4自顶向下分析的一般过程自顶向下分析的一般过程l 从从S S出发采用最左推导，试图逐步推出输入串出发采用最左推导，试图逐步推出输入串,L(GS)?l S S作为语法树的根，试图自上而下地为作为语法树的根，试图自上而下地为构造一棵语法树：构造一棵语法树：p 若叶结点从左向右排列恰好若叶结点从左向右排列恰好，则表示，则表示是文法的句子，是文法的句子，而这棵语法树就是句子而这棵语法树就是句子的语法结构；的语法结构；p 若构造不出语法树，则若构造不出语法树，则不是文法的句子。不是文法的句子。4.2 4.2 自顶向下分析法概述自顶向下分析法概述5l自上而下分析中的关键问题：自上而下分析中的关键问题：左递归左递归：当文法中出现左递归时，会使分析过程：当文法中出现左递归时，会使分析过程陷入无限循环。陷入无限循环。回溯回溯：假定要被代换的非终结符号是：假定要被代换的非终结符号是V V，且有，且有 n n 条规则：条规则：VAVA1 1|A|A2 2|A|An n，那么如何确定，那么如何确定 用哪个右部用哪个右部A Ai i去替代去替代V V呢？会造成回溯。呢？会造成回溯。4.2 4.2 自顶向下分析法概述自顶向下分析法概述回溯问题回溯问题左递归问题左递归问题61.1.回溯问题回溯问题什么是回溯（什么是回溯（backtrackingbacktracking）?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部地退回去重做叫回溯回溯造成回溯的条件：造成回溯的条件：文法中，对于某个非终结符号的文法中，对于某个非终结符号的规则其右部有多个选择规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。能出现回溯。回溯带来的问题：回溯带来的问题：严重的严重的低效率低效率，只有在理论上的意义而无实际意义。，只有在理论上的意义而无实际意义。4.2 4.2 自顶向下分析法概述自顶向下分析法概述7消除回溯的途径：消除回溯的途径：改写文法改写文法对具有多个右部的规则对具有多个右部的规则反复反复提取提取左因子左因子例：对下述两个产生式，提取公共左因子改造文法。例：对下述两个产生式，提取公共左因子改造文法。ifif E then Sif E then S1 1 else S else S2 2 ifif E then Sif E then S1 1 改造为：改造为：if E then S1U Uelse S2|4.2 4.2 自顶向下分析法概述自顶向下分析法概述8A1|2|n如果如果1n中还有几个首符号相同，可反复中还有几个首符号相同，可反复提取引入了许多非终结符和提取引入了许多非终结符和产生式。产生式。A AA 1|2|n提取公共左因子提取公共左因子4.2 4.2 自顶向下分析法概述自顶向下分析法概述9某些文法不能在有限步骤内提取左公共因子。某些文法不能在有限步骤内提取左公共因子。【例例】文法文法G:G:S SAp|Bq Ap|Bq A AaAp|d aAp|d B BaBq|eaBq|eS SaAppaApp|aBqqaBqqS Sdp|eqdp|eqA AaAp|d aAp|d B BaBq|eaBq|eS Sa(App|Bqq)a(App|Bqq)S SaSaS S SApp|BqApp|Bqq qS Sdp|eqdp|eqA AaAp|daAp|dB BaBq|eaBq|eS SaSaS S Sdp|eqdp|eqS SaAaAppp|aBqqqppp|aBqqqS S dpp|eqqdpp|eqqA AaAp|daAp|dB BaBq|eaBq|e可可以以看看出出产产生生式式A A、B B继继续续替替换换，只只能能使使文文法法的的产产生生式式愈愈来来愈愈多多无无限限增增加加下下去去，变变成成循循环环递递归归，不不能能得得到到提提取取左左公共因子的预期结果。公共因子的预期结果。不一定每个文法的公共左因子都能在有限的步骤不一定每个文法的公共左因子都能在有限的步骤 内替换成无公共左因子的文法。内替换成无公共左因子的文法。一个文法提取了左公共因子后，只解决了相同左一个文法提取了左公共因子后，只解决了相同左 部产生式右部的部产生式右部的FIRSTFIRST集不相交问题，集不相交问题，当改写后的文当改写后的文 法不含空产生式，且无左递归时，则改写后的文法是法不含空产生式，且无左递归时，则改写后的文法是 LL(1)LL(1)文法。文法。否则还需用否则还需用LL(1)LL(1)文法的定义进行判断文法的定义进行判断 才能确定是否为才能确定是否为LL(1)LL(1)文法。文法。4.2 4.2 自顶向下分析法概述自顶向下分析法概述102.2.左递归问题左递归问题例：文法例：文法GEGE：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|i给出给出i*i+ii*i+i自顶向下的分析过程。自顶向下的分析过程。左递归文法会使自顶向下分析法陷入死循环左递归文法会使自顶向下分析法陷入死循环 如果文法具有间接左递归，则也将发生上述问题，如果文法具有间接左递归，则也将发生上述问题，只不过循环的圈子兜的更大。只不过循环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归要实行自顶向下分析，必须要消除文法的左递归从左向右扫描源程序，从左向右扫描源程序，同时实施最左推导。同时实施最左推导。4.2 4.2 自顶向下分析法概述自顶向下分析法概述11（1 1）消除直接左递归）消除直接左递归方法一：使用方法一：使用EBNF表示来改写文法表示来改写文法例：文法例：文法GEGE：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|iET+TET+TTF*F TF*F F(E)|iF(E)|iA A|A|A 规则一规则一A A 4.2 4.2 自顶向下分析法概述自顶向下分析法概述12例：文法例：文法GEGE：EE+T|E-T|TEE+T|E-T|T TT*F|T/F|F TT*F|T/F|F F(E)|i F(E)|iET(+|ET(+|)T)TTF(*|/)F TF(*|/)F F(E)|i F(E)|i AA|A 规则二规则二A AA(A(|)4.2 4.2 自顶向下分析法概述自顶向下分析法概述13方法二：将左递归规则改为右递归规则方法二：将左递归规则改为右递归规则AA|课堂练习课堂练习文法文法GEGE：EE+T|E-T|TEE+T|E-T|T TT*F|T/F|F TT*F|T/F|F F(E)|i F(E)|iE ETETE E E+TE+TE|T TFTFT T T*FT*FT|F F(E)|i(E)|i消除左递归消除左递归A AA A|4.2 4.2 自顶向下分析法概述自顶向下分析法概述14间接左递归间接左递归直接左递归直接左递归右递归右递归【例例】文法文法G:AG:AaBaB A ABbBb B BAcAc B Bd dA AaBaBA ABbBbB BaBcaBcB BBbcBbcB Bd dB BaBcaBc|d dB BBbcBbc B B(aBcaBc|d)Bd)BBBbcB|bcB|A AaBaBA ABbBbB B(aBc|d)BaBc|d)B B Bbc bc B B|4.2 4.2 自顶向下分析法概述自顶向下分析法概述(2)(2)消除间接左递归消除间接左递归15l 对对文文法法中中一一切切左左递递归归的的消消除除要要求求文文法法中中不不含含回回 路，即无路，即无 A A A A 的推导。的推导。l 满满足足该该文文法法的的充充分分条条件件是是：文文法法中中不不包包含含形形如如 A A A A 的有害规则和的有害规则和 A A 的产生式。的产生式。+算法步骤如下：算法步骤如下：4.2 4.2 自顶向下分析法概述自顶向下分析法概述(2)(2)消除间接左递归消除间接左递归16（2 2）从）从A A1 1开始消除左部为开始消除左部为A A1 1的产生式的直接左递归，然后把左部的产生式的直接左递归，然后把左部 为为A A1 1的所有规则的右部逐个替换左部为的所有规则的右部逐个替换左部为A A2 2右部以右部以A A1 1开始的产开始的产 生式中的生式中的A A1 1，并消除左部为，并消除左部为A A2 2的产生式中的直接左递归。继的产生式中的直接左递归。继 而以同样方式把而以同样方式把A A1 1、A A2 2的右部代入左部为的右部代入左部为A A3 3右部以右部以 A A1 1 或或 A A2 2 开始的产生式中，消除左部为开始的产生式中，消除左部为A A3 3的产生式之直接左递归，直的产生式之直接左递归，直 到把左部为到把左部为A A1 1，A A2 2，A An-1n-1的右部代入左部为的右部代入左部为A An n的产生式中的产生式中 ，从，从A An n中消除直接左递归。中消除直接左递归。（1 1）把文法的所有非终结符按某一顺序排序）把文法的所有非终结符按某一顺序排序,如如:A:A1 1|A|A2 2|A|An n（3 3）去掉无用产生式。）去掉无用产生式。消除递归的算法消除递归的算法4.2 4.2 自顶向下分析法概述自顶向下分析法概述171 1）把）把G G的非终结符整理成某种顺序的非终结符整理成某种顺序A A1 1，A A2 2，A An n2 2）for i:=1 to n dofor i:=1 to n do for j:=1 to i-1 do for j:=1 to i-1 do 把每个形如把每个形如A Ai i=A=Aj jr r的规则替换成的规则替换成 A Ai i=(=(1 1|2 2|k k)r)r 其中其中A Aj j=1 1|2 2|k k是当前是当前 全部全部A Aj j的规则的规则 消除消除AiAi规则中的直接左递归规则中的直接左递归 3 3）去掉无用的产生式）去掉无用的产生式4.2 4.2 自顶向下分析法概述自顶向下分析法概述