5-自顶向下语法方法规范.ppt

第5章 自顶向下的语法分析方法 语法分析的作用是识别由词法分析给出的 单词符号序列是否是给定文法的正确句子(程序)。 目前语法分析常用的方法有: 1、自顶向下（自上而下）分析 2、自底向上（自下而上）分析 自顶向下分析法也就是从文法的开始符号出 发企图推导出与输入的单词串完全相匹配的 句子，若输入串是给定文法的句子，则必能 推出，反之必然出错。 5.1 确定的自顶向下分析思想 确定的自顶向下分析方法:首先要解决从某文法 的开始符号出发，对给定的输入符号串如何根据 当前的输入符号(单词符号)唯一地确定选用哪个 产生式替换相应非终结符往下推导. 5.2 LL(1) 文法的定义和判别 由5.1的例1～例6可知，一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个非终结符能推出 ε 时则与该非终结符的后跟符号集合也有关。综合以上两点，即一个文法能否用确定的自顶向下分析与产生式的Select集有关。此外在产生式中不存在左递归。 定义5.4 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=? 　　其中α，β不同时能 ε LL(1)文法的含义： 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向右看一个输入符号便可 决定选择哪个产生式。 例：判断下列文法是否是LL(1)文法 G：S→aA S→d A→bAS A→ε 例：判断下列文法是否是LL(1)文法 文法G [S]为：　　S→aAS　　S→b　　A→bA　　A→ε LL(1)文法的判别 当我们需选用自顶向下分析技术时，首先必 须判别所给文法是否是LL(1)文法。因而我 们对任给文法需计算FIRST、FOLLOW、 SELECT集合，进而判别文法是否为LL(1)文 法。 非LL(1)文法到LL(1)文法的等价转换 由前面可知：确定的自顶向下分析要求对给 定语言的文法必须是LL(1)形式。然而，不 一定每个语言都有LL(1)文法。对一个语言 的非LL(1)文法是否能变换为等价的LL(1)形 式以及如何变换是本节讨论的主要问题。 c) 消除文法中一切左递归的算法。 步骤(P83－ P84 算法步骤）1) 把文法的所有非终结符按某一顺序排序；　　如A1，A2,…,An 2) A1产生式右部用A2，…,An表示， A2产生式右部用A3，…,An表示， A3产生式右部用A4，…,An表示， ……, An产生式右部用An表示。消除An中的直接左递归。 3) 去掉无用产生式。 表驱动予测分析程序模型 Input 其中只有预测分析表与文法有关，而分析表又可用 一个矩阵M(或称二维数组)表示。矩阵的元素 M[A，a]中的下标A表示非终结符，a为终结符或 句子括号“#”，矩阵元素M[A,a]中的内容为存放着 一条关于A的产生式，表明当用非终结符A向下推 导时，面临输入符a时，所应采取的候选产生式， 当元素内容无产生式时，则表明用A为左部向下推 导时遇到了不该出现的符号，因此元素内容为转向 出错处理的信息 解：(1) 判断它是否是LL（1）文法因为该文法含有左递归，所以不是LL（1）文法，必须改写成LL(1)文法： G’[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a 分析输入串#a+a# 栈内容 栈顶符号 当前输入 余留串 M[X,b ] 1 #E E a +a# E – TE’ 2 #E’T T a +a# T – FT