编译原理第四章语法分析自上而下分析

《编译原理第四章语法分析自上而下分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL(1)分析中的错误处理4.1语法分析器的功能功能定义：按照文法产生式，识别输入符号串是否为一个句子。技术路线：是否能从文法的开始符号出发推导出这个输入串。或者，建立一颗与输入串相匹配的语法分析树。策略：自上而下分析法，自下而上分析法。图4.1语法分析器在编译程序中的地位接收词法分析器输出的记号串，检查是否合乎语法。报告语法错误，并恢复语法错误，从而可以继续分析。输出是分析树的某种形式。分析时其它任务：将各种记号的信息收入符

2、号表、类型检查和其它语义检查、中间代码的生成，这些放在“前端的其它部分”完成。4.2自上而下分析面临的问题例4.1假定有文法(1)SxAy(2)A**

3、*对输入串x*y，构造语法树。构造过程：(1)把S作为根(2)用S的产生式构造子树(3)让输入串指示器IP指向输入串的第一个符号。(4)调整输入串指示器IP与叶结点进行匹配。(5)如果为非终结符，用A的下一个产生式构建子树。(6)如果匹配成功则结束；否则，回溯到步骤(4)。SxAySxAy**SxAy*自上而下分析法的缺点：是文法的左递归性问题。一个文法是含有左递归的自上而下的分析过程陷入无限循环。如PP。由于有回溯

4、，就会产生一大堆麻烦事情。在上述的自上而下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的。这种虚假现象，我们需要更复杂的回溯技术。一般说，要消除虚假匹配是很困难的。当最终报告分析不成功时，我们不知道输入串中出错的确切位置。4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析条件4.3.1左递归的消除一个简单例子：已知文法：PP

5、是一个左递归文法，它的等价的非左递归文法为：PP’P’P’

6、例2.2一般转换规则有：PP1

7、P2

8、…

9、Pm

10、1

11、2

12、…

13、n改写成P1P’

14、2P’

15、

16、…

17、nP’P’1P’

18、2P’

19、…

20、mP’

21、其中：i都不以P开头,I不等于一个反例：文法：SQc

22、c；QRb

23、b；RSa

24、a虽然不是直接左递归，但S、Q、R都是左递归。消除左递归算法：算法的思想是：首先构造直接左递归；再利用一般转换规则，消除直接左递归化简文法。下面算法在不含PP，也不含在右部产生式时可以消除左递归。消除一个文法的左递归算法：(1)把文法G的所有非终结符按任一种顺利排列成P1…Pn；按此顺序执行；(2)FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pj+1→Pj的规则改写成Pj+11

25、1

26、…k

27、

28、。其中Pj1

29、1

30、…k是关于Pj的所有规则；消除关于Pi规则的直接左递归性。END化简由（２）所得的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生规则。例子4.3：对4.3文法，它的非终结符排序为R,Q,S。把R代入Q，Q代入S得到：SSabc

31、abc

32、bc

33、c消除左递归后得到：SabcS’

34、bcS’

35、cS’S’abcS’

36、QSab

37、ab

38、b(化简消去)RSa

39、a（化简后消去）对不同的排列，会有不同形式的无左递归文法，但它们等价。4.3.2消除回溯、提左因子消除回溯的思路：对输入符号a，指派一个A的候选式1与a匹配，而再没有其他候选式i的

40、字符与a匹配。通过提取公共左因子，判断首字符集的差异。首字符集定义：对G的所有非终结符的每个候选，它的首字符集为FIRST()={a

41、a…，aVT}，若*，则规定FIRST()。提取公共左因子算法：A1

42、2

43、…

44、n

45、1

46、2

47、…

48、m(其中每个不以开头)那么可以把这些规则改写成：AA’

49、1

50、2

51、…

52、mA’1

53、2

54、…

55、n例4.4上述算法的不足：当非终结符A面临输入符号a,且a不属于A的任意候选首符集,但A的某个候选首符集包含时，就一定可以使A自动匹配。这是一种错误。4.3.3LL(1)分析条件定义FOLLOW(A)

56、集合：假定S是文法G的开始符号，对于G的任何非终结符A，我们定义FOLLOW(A)={a

57、S⇒*…Aa…,a∈VT}若S⇒*…A，则规定＃∈FOLLOW(A)。LL(1)文法的充分必要条件：文法不含左递归。若Ａ→1

58、2

59、…

60、n，则FIRST(i)∩FIRST(j)=Φ(i≠j)对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST(A)∩FOLLOW(A)=ΦLL(1)匹配算法：对输入符号a，A的所有产生式为：Ａ→1

61、2

62、…

63、n(1)若aFIRST(i)，则指派I去执行匹配任务。