自上而下语法分析.ppt

《自上而下语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章自顶向下语法分析方法内容语法分析的任务与分类自上而下分析面临的问题LL（1）分析法递归下降分析程序构造预测分析程序5.1语法分析的任务与分类1.任务对于一个给定w∈VT*,判断w∈L(G)工作本质：根据产生式识别输入串是否为一个句子。2.语法分析器：是一个程序，它按照P，做识别w的工作。语法分析只管w在形式上是否正确，不管其具体含义，比如：“虎打武松”。5.1语法分析的任务与分类3.语法分析器在编译程序中的地位词法分析器语法分析器编译器的后继部分符号表源程序单词符号取下一个单词符号语法分析树5.1语法分析的任务与分类自上而下分析法从文法的开始符号出发，反复使用文法的产生式，寻找与

2、输入符号串匹配的推导将文法开始符号做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树4.语法分析的分类SAAcabdcabdcabd规约过程构造的推导：cAdcabdScAdSSScAdcAdab推导过程：ScAdcAdcabd例：文法G：S→cAdA→abA→a识别输入串w=cabd是否为该文法的句子自上而下分析自下而上分析5.2.1自上而下分析的主旨自上而下分析的主旨为输入串寻找一个最左推导对任何输入串，试图用一切可能的办法，从文

3、法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树例5.1假定有文法(1)S→xAy(2)A→**

4、*分析输入串x*y(记为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*证明是一个句子实现途径让每个非终结符对应一个递归子程序如果发现某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值否则，保持原来的语法树和IP值不变，并返回“假”值自上而下的带回溯试探法自上而下分析过程中存在回溯回溯的缺点，在分析的过程中不断的试探（穷举法），导致语法分析效率很低。文法的左递归5.2自上而下

5、分析面临的问题例：文法G:S->Sa

6、bw=baaaa#推导时，无法确定什么时候用S->b替换。文法的左递归问题一个文法是含有左递归的，若存在非终结符P将使自上而下分析陷入无限循环。回溯问题分析过程中，当一个非终结符用某一个候选式匹配成功时，这种匹配可能是暂时的。这时，不得不“回溯”，导致语法分析效率低下。5.2左递归与回溯区分三种左递归形式直接左递归形如：P→P/N→N间接左递归形如：N→AA→BβB→Nγ潜在左递归形如：N→Nε5.2左递归与回溯+5.3LL(1)分析法左递归的消除提取左公共因子LL(1)文法分析5.3.1左递归的消除1.采用下列变换公式消除直接左递归，

7、把直接左递归改写为右递归如：文法G：S→Sa

8、b可改写为：S→bSS→aS

9、改写后的文法所描述的L(G)={ban

10、n>=0}5.3.1左递归的消除一般而言，假定关于P的全部产生式是P→P1

11、P2

12、…

13、Pm

14、1

15、2

16、…

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

18、2P

19、…

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

21、2P

22、…

23、mP

24、5.3.1左递归的消除例5.2文法E→E＋T

25、TT→T*F

26、FF→(E)

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

28、T→FTT→*FT

29、F→(E)

30、i注意：这个例子

31、后面将再度用到5.3.1左递归的消除2.消除间接左递归（代入法）间接左递归的消除需先将间接左递归变为直接左递归，然后再按第1种方法消除直接左递归如：文法G：S→Q

32、b可改写为：Q→Pβ

33、b5.3.1左递归的消除代入法将一个产生式规则右部的中的VNN替换为N的候选式。如果N有n个候选式，右边重复n次，而且每一次重复都有N的不同候选式来代替N。例如：N→a

34、Bc

35、在S→pNq中的代入结果S→paq

36、pBcq

37、pq5.3.1左递归的消除写一个程序实现间接左递归，如何做？一条一条查看，第一条存在左递归消除之；第二条代入1进行分析；第三条代入1,2分析；以此类推，一直代到底。5.3.1左

38、递归的消除3.消除文法中一切左递归的算法若VN的排序为A1，A2，…,An代入法，发现直接左递归即消除（见P89-90）去掉无用产生式5.3.1左递归的消除消除左递归的算法把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pj的规则改写成Pi→1

39、2

40、…

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

42、2

43、…

44、k是关于Pj的所有规则)消除关于Pi规则的直