编译原理第4章语法分析—自顶向下分析.pptVIP

第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集合 自顶向下语法分析遇到的问题 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 自顶向下语法分析问题的解决方法 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 采用自顶向下语法分析法对文法的要求 4.3 递归下降分析(P64) 4.3 递归下降分析 4.3 递归下降分析 4.3 递归下降分析 4.3 递归下降分析 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)分析方法 4.4 LL(1)分析方法 4.4 LL(1)分析方法 小 结 习 题(P76) 习 题 习 题 习 题 作 业 一 作 业 二 文法G的LL(1)分析表 S::=ε # S::=ε S::=(S)S S ) ( ACCEPT # # 6 S::=ε # #S 5 匹配) )# #S) 4 S::=ε )# #S)S 3 匹配( ()# #S)S( 2 S::=(S)S ()# #S 1 产生式 余留输入串 分析栈 步骤 (3) 输入符号串是“()”的LL(1)语法分析过程: 语法分析方法的分类 自顶向下的语法分析方法遇到的问题及其解决办法 FIRST集、FOLLOW集和SELECT集的求法 LL(1)文法的判断 递归子程序的构造方法 LL(1)分析表的构造方法 1. 对下面文法，设计递归下降分析程序。 S→aAS|(A) , A→Ab|c 2. 设有文法G[Z]： Z∷=(A) , A∷=a|Bb , B∷=Aab 若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？ 3. 若有文法如下，设计递归下降分析程序。 语句→语句赋值语句|ε 赋值语句→ID=表达式； 表达式→项|表达式+项|表达式-项 项→因子|项*因子|项/因子 因子→ID|NUM|(表达式) 递归下降分析(或递归子程序分析)的基本方法 其思路极为简单：为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识别。 1. 若U的右部只有一个候选式，则按从左向右的顺序构造U的识别过程代码。 （1）若有终结符号，则判断与输入符号是否匹配，如果相同，继续读入下一符号，否则就意味着有语法错误； （2）若有非终结符号，则调用该符号的子程序。 2. 若U的右部有多个候选式，则根据每个候选式的第一个符号确定该候选式分支。 3. 只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别。 总控程序可描述如下： begin READ(ch); if P(文法的开始符号) then if 当前符号=″#″ then write(″valid″) else write(″invalid″) endif else write(″invalid″) endif end 递归下降分析算法 它由一个总控程序和若干个非终结符号的分析子程序P(U)构成。其中若有n个非终结符号就有n个分析子程序。 对满足条件的文法按如下方法构造相应的语法分析子程序： ②对于产生式U::=α1|α2|…|αn, αi∈V ，P