理自顶向下语法分析

资源描述

《理自顶向下语法分析》由会员分享，可在线阅读，更多相关《理自顶向下语法分析（73页珍藏版）》请在金锄头文库上搜索。

1、编译原理自顶向下语法分析第5章自顶向下语法分析方法教学目的：教学目的：正确理解自上而下分析的基本思想；正确理解自上而下分析的基本思想；熟练掌握递归下降分析基本方法：消除左递归，熟练掌握递归下降分析基本方法：消除左递归，消除回溯，构造递归下降子程序；掌握预测分析消除回溯，构造递归下降子程序；掌握预测分析程序的基本原理和预测分析表构造；理解程序的基本原理和预测分析表构造；理解LL(1)LL(1)方方法的定义法的定义教学重点、难点：教学重点、难点：LL(1)LL(1)文法的判别文法的判别课时分配：课时分配：6 6学时学时编译原理自顶向下语法分析本章知识点(内容)确定的自顶向

2、下分析思想LL(1)文法的判别结束自上而下分析面临的问题确定的自顶向下分析方法编译原理自顶向下语法分析语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。编译原理自顶向下语法分析语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子，并建立一棵与输入串相匹配的语法分析树。按照语法分析树的建立方法，可以把语法分析方法分成两类：一类是自上而下分析法一类是自下而上分析法编译原理自顶向下语法分析不确定的自顶向下分析法递归下降分析法确定的预测分析法LL(1) 语法分析方

3、法简单优先分析法优先分析法算符优先分析法自底向上分析法 LR(0)分析法LR分析法 SLR(1)分析法LR(1)分析法LALR(1)分析法语法分析技术概况首页结束编译原理自顶向下语法分析自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子，其主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。首页结束编译原理自顶向下语法分析要点： .由根向下构造语法树 .构造最左推导 .推

4、导出的终结符是否与当前输入符匹配S aaabA B a AS AB A aA | B b | bB 自上而下推导aaab. SAB S ABaAB A aAaaAB A aAaaaAB A aAaaa B A aaab B b首页结束编译原理自顶向下语法分析1 选择使用哪个产生式进行推导？ 2 假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？思考：首页结束编译原理自顶向下语法分析SXAY【例】假定有文法（1）SxAy(2）A*|*以及输入串x*y(记为）。为了自上而下构造的语法树，我们首先按文法的开始符号产生根结

5、s，并让指示器IP指向输入串的第一个符号x。然后，用S的规则（此处关于S的规则仅有一条）把这棵树发展为首页结束编译原理自顶向下语法分析SXAY*非终结符A有两个候选，试着用它的第一个候选去匹配输入串，于是把语法树发展为子树A的最左子结和IP所指的符号*相符，然后我们再把IP 调为指向下一符号并让A的第二个子结进入工作。但A的第二子结*和当前所指的符号y不一致。因此，A告失败。这意味着A的第一个候选此刻不适用于构造的语法树。这时应该回头（回溯），看A是否还有别的候选。编译原理自顶向下语法分析为了这种回溯，我们一方面应把A的第一候选所发展的子树注销掉，另一方面应把IP

6、恢复为进入A时的原值，也就是让它重新指向第二个输入符号。现在我们试探A的第二个候选，即考虑如下的语法树：XAYS*编译原理自顶向下语法分析由于子树A只有一个子结，而且它和IP所指的符号相一致，于是，A完成了匹配任务。在A 获得匹配后，指示器IP应指向下一个未被触及符号y。在S的第二子结A完成匹配后，接着就轮到第三个子结y进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了为构造语法树的任务，证明了是一个句子。首页结束编译原理自顶向下语法分析【例】文法G0S:(1) SSa(2) Sb分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)

7、来推导SSa语法树末端结点最左符号为非终结符，所以选用产生式(1) 继续推导SSaSaa此时语法树末端结点最左符号仍为非终结符，所以选用产生式 (1)继续推导SSaSaa Saaa 问题试图用S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求S去进行新的匹配。原因文法含有左递归。编译原理自顶向下语法分析自上而下分析法存在的困难不确定的自顶向下语法分析一、基本方法:从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。二、结论1、在推导过程中出现了大量的回朔现象。2、推导过程出现了死循环，应消除左递归。3、难以知道输入串中出错的确切位置首

8、页结束编译原理自顶向下语法分析自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递归性，并找出克服回溯的充分必要条件。首页结束编译原理自顶向下语法分析消除回朔实际上就是提取左因子。提取公共左因子A 1|2|.|n|1| 2 |m （其中每个不以开头）那末，可以把这些规则改写成： A A |1| 2 |m A 1|2|.|n首页结束编译原理自顶向下语法分析【例】考虑条件语句的产生式 stmt if expr then stmt if expr then stmt else stmtother 存在左因子 if e

9、xpr then stmt，妨碍自顶向下方法的使用。条件语句消除回朔后产生式的结果为：stmt if expr then stmt S otherS else stmt。首页结束编译原理自顶向下语法分析【例】文法： Stm id := Exp| id (ExpL)ExpL Exp | Exp,ExpLStm id StmStm := ExpStm ( ExpL )ExpL Exp ExpLExpL , Exp ExpLExpL 消除左公共因子的例子首页结束编译原理自顶向下语法分析（1）左递归的定义对于某些字符串，如果存在推导 A =+ A ，我们就称该文法含有左递归。左

10、递归的消除（2）左递归的危害导致推导过程中出现大量的死循环，妨碍自顶向下的语法分析。（3）左递归分类：直接左递归和间接左递归首页结束编译原理自顶向下语法分析直接左递归如果文法中含有如下形式的产生式，我们就称该文法含有直接左递归。A A，其中AVN ，（VNVT）* 间接左递归如果文法中含有如下形式的产生式，我们就称该文法含有间接左递归。A B，B A，其中A，B VN ，（ VNVT）* 编译原理自顶向下语法分析左递归的消除直接消除产生式中的左递归是比较容易的。假定关于非终结符P的规则为：PP| 其中，不以P开头。那么，我们可以把P的规则改写为如下的非直接左递归形式：

11、PPPP|编译原理自顶向下语法分析【例】消除文法中左递归 EE+T|T TT*F|F F(E)|i消除左递归后产生式为：ETEE+TE|TFTT*FT| F(E)|i 编译原理自顶向下语法分析u假定P关于的全部产生式是 PP1|P2|.|Pm|1| 2|.| n 其中，每个都不等于，而每个都不以P开头那末，消除P的直接左递归性就是把这些规则改写成：P 1P| 2P|.| nP P 1 P| 2 P|.|m P| 消除文法中左递归规则编译原理自顶向下语法分析【例】试构造与下列文法GS等价的无左递归文法。GS: SSa|Nb|c (1)N Sd|Ne|f (2)对于（1）我们

13、i 1| 2|.| k，其中Pj 1|2|.|k是关于Pj的所有规则规则消除关于Pi规则规则的直接左递归递归性END编译原理自顶向下语法分析【例】考虑文法：SQc|cQ Rb|bR Sa|a 消除左递归。【解】将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入到Q中有关的候选式： Q Sab|ab|b 现在Q同样不含直接左递归，把它带入S的有关候选式：S Sabc|abc|bc|c经消除S的直接左递归后我们们得到整个文法S abcS|bcS|cSS abcS|Q Sab|ab|bR Sa|a由于关于Q,R的规则式多余的则可化简得到：S abcS|bcS|cSS abcS|编译原理自顶向下语法分析例：1 A B 1 | a2 B C 2 | b3 C A 3 | c2:i j 1 没有直接左递归，无须改写1:非终结符排序：A,B,C 3:新文法中的产生式是1245消除3中的直接左递归，引入新非终结符C：4 C(b13|a3|c)C 5 C213C| 2 把2代入3得：3 CC213|b13|a3|c3 1 把1代入3得：3 C(B1|a)3|c2 1 无须替换，没有直

展开阅读全文

理自顶向下语法分析

最新文档