《编译原理》PPT课件

《《编译原理》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析—自上而下分析内容语法分析器的功能自上而下分析面临的问题LL（1）分析法递归下降分析程序构造预测分析程序LL（1）分析中的错误处理4.1语法分析器的功能语法分析器的功能语法分析器的功能语法分析方法自上而下分析面临的问题LL（1）分析法递归下降分析程序构造预测分析程序LL（1）分析中的错误处理4.1.1语法分析器的功能高级语言的语法结构适合用上下文无关文法描述语法分析器任务：分析与判定程序的语法结构是否符合语法规则工作本质：根据产生式识别输入串是否为一个句子在编译器中的地位：核心部分词法分析器语法分析器编译器的后继部分符号表源程序单词符号取下一个单词符号语法分析树4.1.

2、2语法分析方法自上而下分析法从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导将文法开始符号做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树SAAcabdcabdcabd规约过程构造的推导：cAdcabdScAdSSScAdcAdab推导过程：ScAdcAdcabd例：文法G：S→cAdA→abA→a识别输入串w=cabd是否为该文法的句子自上而下分析自下而上分析4.2自上而下分析面临的问题语法分析器的功能自上

3、而下分析面临的问题自上而下分析的主旨回溯举例自上而下的带回溯试探法自上而下分析面临的问题左递归与回溯LL（1）分析法递归下降分析程序构造预测分析程序LL（1）分析中的错误处理4.2.1自上而下分析的主旨自上而下从文法的开始符号出发，向下推导，推出句子存在问题：带“回溯”克服方法不带回溯的递归子程序（递归下降）分析方法自上而下分析的主旨为输入串寻找一个最左推导对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树4.2.2回溯举例例4.1假定有文法(1)S→xAy(2)A→**

4、*分析输入串x*y(记为)。Sx*yIPSx*yIPAxySx

5、*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*证明是一个句子实现途径让每个非终结符对应一个递归子程序如果发现某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值否则，保持原来的语法树和IP值不变，并返回“假”值4.2.3自上而下的带回溯试探法自上而下分析面临的五个问题消除左递归性克服回溯消除虚假匹配确定出错位置避免穷尽一切4.2.4自上而下分析面临的问题LL(1)分析法文法的左递归问题一个文法是含有左递归的，若存在非终结符P将使自上而下分析陷入无限循环回溯问题分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可

6、能是暂时的。这时，不得不“回溯”4.2.5左递归与回溯4.3LL(1)分析法语法分析器的功能自上而下分析面临的问题LL(1)分析法不带回溯的自上而下分析算法左递归的消除回溯的消除LL(1)分析条件递归下降分析程序构造预测分析程序LL(1)分析中的错误处理4.3.1不带回溯的自上而下分析算法自上而下分析方法不允许文法含有任何左递归构造不带回溯的自上而下分析算法消除文法的左递归性找出克服回溯的充分必要条件4.3.2左递归的消除（一）直接消除产生式中的左递归假定关于非终结符P的规则为P→P

7、其中不以P开头那么，我们可以把P的规则等价地改写为如下的非直接左递归形式：P→PP→P

8、

9、4.3.2左递归的消除（二）一般而言，假定关于P的全部产生式是P→P1

10、P2

11、…

12、Pm

13、1

14、2

15、…

16、n其中，每个都不等于，而每个都不以P开头那么，消除P的直接左递归性就是改写这些规则：P→1P

17、2P

18、…

19、nPP→1P

20、2P

21、…

22、mP

23、4.3.2左递归的消除（三）例4.2文法E→E＋T

24、TT→T*F

25、FF→(E)

26、i经消去直接左递归后变成：E→TEE→+TE

27、T→FTT→*FT

28、F→(E)

29、i注意：这个例子后面将再度用到4.3.2左递归的消除（四）例如文法S→Qc

30、cQ→Rb

31、bR→Sa

32、a虽没有直接左递归，但S、Q、

33、R都是左递归的，如：SQcRbcSabc一个文法消除左递归的条件不含以为右部的产生式（空产生式）不含回路，形如4.3.2左递归的消除（五）消除左递归的算法把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pj的规则改写成Pi→1

34、2

35、…

36、k;(其中Pj→1

37、2

38、…

39、k是关于Pj的所有规则)消除关于Pi规则的直接左递归性END化简由