语法分析自顶向下分析.ppt

第4章 语法分析—自顶向下分析 Pursue breakthroughs in your life.  追求自我的突破。 第四章 语法分析—自顶向下分析(P61) 学 习 重 点 第四章 语法分析—自顶向下分析 第四章 语法分析—自顶向下分析 4.1自顶向下的分析方法（P61） 4.2 FIRST集合和FOLLOW集合（P62） 4.2 FIRST集合和FOLLOW集合 4.2 FIRST集合和FOLLOW集合 4.2 FIRST集合和FOLLOW集合 4.2 FIRST集合和FOLLOW集合 4.2 FIRST集合和FOLLOW集合 4.2 FIRST集合和FOLLOW集合 4.2 FIRST集合和FOLLOW集合 课堂练习 求文法G[S]的每一个非终结符号的FIRST集和FOLLOW集。 G[S]： S::=AB | bC A::=b |ε B::=aD |ε C::=AC | b |ε 自顶向下语法分析遇到的问题 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 4.3 递归下降分析(P64) 4.3 递归下降分析 4.3 递归下降分析 4.3 递归下降分析 4.3 递归下降分析 4.3 递归下降分析 4.3 递归下降分析 4.4 LL(1)分析方法(P70) 4.4 LL(1)分析方法 4.4 LL(1)分析方法 4.4 LL(1)分析方法---工作过程 4.4 LL(1)分析方法 4.4 LL(1)分析方法 4.4 LL(1)分析方法 4.4 LL(1)分析方法 4.4 LL(1)分析方法 小 结 习 题(P76) 习 题 习 题 习 题 作 业 一 作 业 二 1. 对下面文法，设计递归下降分析程序。 S→aAS|(A) , A→Ab|c 2. 设有文法G[Z]： Z∷=(A) , A∷=a|Bb , B∷=Aab 若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？ 3. 若有文法如下，设计递归下降分析程序。 语句→语句赋值语句|ε 赋值语句→ID=表达式； 表达式→项|表达式+项|表达式-项 项→因子|项*因子|项/因子 因子→ID|NUM|(表达式) 推论2：任何LL(1)文法均为无二义性文法。 证明：（反证法） 假设文法G是二义性文法，则存在句子α，它有两棵不同的语法树，即存在着两个不同的最左推导。从而可知，用LL(1)方法对句子α进行分析的某步，存在两种不同的产生式可用于推导，且均能正确进行语法分析，即LL(1)分析动作存在不确定性。 这与LL(1)的性质相矛盾。所以，文法G不是LL(1)文法。 例 验证下列文法是否为LL(1)文法。 G[S]: S::=AB|CDa A::=ab|c B::=dD|ε C::=eC|ε D::=fD|f 解：显然，文法G已压缩且无左递归。下面判断其是否有回溯。 ∵由D::=fD|f，有： SELECT(D::=fD)∩SELECT(D::=f) =FIRST(fD)∩FIRST(f) ={f}∩{f} ={f} ≠φ ∴该文法不是LL(1)文法。 练习（见P77习题4的第2小题） 有文法G[A]： A::=aABe|ε B::=Bb|b 判断该文法是LL(1)文法吗？ 解： ∵文法中存在左递归B::=Bb ∴该文法不是LL(1)文法。 递归下降分析(或递归子程序分析)的基本方法 其思路极为简单：为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识别。 1. 若U的右部只有一个候选式，则按从左向右的顺序构造U的识别过程代码。 （1）若有终结符号，则判断与输入符号是否匹配，如果相同，继续读入下一符号，否则就意味着有语法错误； （2）若有非终结符号，则调用该符号的子程序。 2. 若U的右部有多个候选式，则根据每个候选式的第一个符号确定该候选式分支。 3. 只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别。 例4-3(P64) 考虑文法Z::=(U)|aUb ，U::=dZ|e，为其构造递归下降分析子程序。并对