编译原理课件第4-2章.ppt

4.5 预测分析程序 FIRST 、FOLLOW集合构造 预测分析表的构造 预测分析过程 FIRST集的求法 FOLLOW集的求法 预测分析 预测分析过程 下面用预测分析方法对输入串i+i*i# 进行分析，给出栈的变化过程如下： 4.6 LL（1）中的错误处理 1、栈顶非终结符，面临输入符号...... 2、栈顶终结符和当前输入符号不相同。 第4章 总结 §4.5预测分析程序 —— 即LL(１)分析法介绍 二、构造分析表 构造分析表M的算法是: (1)对文法G的每个产生式A?执行第2步和第3步; (2)对每个终结符a∈FIRST(α),把A?α加至M[A,a]中; (3)若?∈FIRST(α),则对任何Bfollow(A)把 A?α加至 M[A,b]中; (4)把所有无定义的M[A,a]标上“出错标志”。 §4.5预测分析程序 —— 即LL(１)分析法介绍 举例：文法E?E+T|T;T?T*F|F;F?(E)|i的 LL(1)分析表如下所示 F?(E) F?i F T’?? T’?? T’?*FT’ T’?? T’ T?FT’ T?FT’ T E’?? E’?? E’?+TE’ E’ E?TE’ E?TE’ E # ) ( * + i E →TEE → +TE |εT → FTT → *FT |εF →(E) |i F T T E E # ) ( * + i 第1列为非终结符 第1行为终结符+’#’ 每个元素为产生式或空 E?TE E?TE E’?+TE E ? ? E ? ? T ? FT’ T ? FT’ T’? ? T’? ? T’? ? F?i F?(E) T’?*FT’ §4.5预测分析程序 —— 即LL(１)分析法介绍 三、分析程序工作过程 总控程序描述:课本77页 举例:课本78页例4.6 预测分析器模型 E?TE? i+i*i# #E 1 所用产生式 剩余输入串 分析栈 步骤 2 #E?T i+i*i# T?FT ? F?i i+i*i# #E?T?F 3 i匹配 i+i*i# #E?T?i 4 T??ε +i*i# #E?T? 5 E??+TE? +i*i# #E? 6 所用产生式 剩余输入串 分析栈 步骤 接受 # # 17 E? ? ε # #E? 16 T? ? ε # #E?T? 15 i匹配 i# #E?T?i 14 F ? i i# #E?T?F 13 *匹配 *i# #E?T?F* 12 T? ? *FT? *i# #E?T? 11 i匹配 i*i# #E?T?i 10 F ? i i*i# #E?T?F 9 T?FT i*i# #E?T 8 +匹配 +i*i# #E?T+ 7 * 第四章　语法分析—自上而下分析 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL（1）分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL（1）分析中的错误处理 §4.１语法分析器的功能 1、任务：在词法分析识别出单词符号串的 基础上，分析并判定程序的语法 结构是否符合语法规则。 2、语法分析器的地位： 单词符号 取下一单 词符号 语法分 析树 符号表 词法分析器 语法分析器 编译程序 后续部分 源程序 §4.１语法分析器的功能 3、本质：按文法的产生式，识别输入符 号串是否为一个句子。 4、语法分析方法分类： 自上而下分析法 自下而上分析法 §4.2自上而下面临的问题 一、基本思想： 1、自上而下：从文法的开始符号出发，向下 推导，推出句子 2、主旨：对任何输入串，试图用一切可能的 办法，从开始符号出发，自上而下 地为输入串建立一棵语法树。 §4.2自上而下面临的问题 二、举例： 自上而下方法的分析过程本质上 是一种试探过程，是反复使用不同产生 式谋求匹配输入串的过程。 §4.2自上而下面临的问题 S x A y S x A y * * S x A y * 例：文法 　S?xAy 　 A?**|* 输入串α :x*y §4.2自上而下面临的问题 实现上述带回溯试探法的简单途径： 让每个非终结符对应一个递归子程序。每 个这种子程序可作为一个布尔过程。一旦发现 它的某个候选与输入串相匹配，就用这个候选 去扩展语法树，并返回“真”值；否则，保持原来 的语法树和IP值不变，并返回“假”值。 §4.2自上而下面临的问题 三、困难和缺点 1、文法的左递归性问题?使自上而下的分析 过程陷入无限循环 2、回溯问题 3、虚假匹配难以消