new第四章语法分析1(最后版本).ppt

* i + * ( ) ＃ E E→TE’ E→TE’ E’ E→+TE’ E’ →ε E’ →ε T Ｔ→FT’ T→FT’ T’ T’→ε T →*FT’ T’→ε T’→ε F F→i F→(E) 该表和书上p86表4.1完全相同 §4.2 自顶向下语法分析 三、LL(1)分析法 一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 * §4.2 自顶向下语法分析 三、LL(1)分析法 4. LL（1）文法 (1)定义 一个文法G，如果它的分析表M不含多重定义入口，则称该 文法是LL（1）文法，可以证明,一个LL(1)文法所定义的语 言，恰好是它分析表Ｍ所识别全部句子。 所谓多重定义入口是指分析表中某M[A，a]有两个或两个以 上产生式。 * LL（1）文法是2型文法，但并不是所有2型文法都是LL（1）文法。对LL（1）文法进行LL（1）分析才是有意义的。 §4.2 自顶向下语法分析 三、LL(1)分析法 * 例如 ：文法Ｇ［Ｓ］： Ｓ∷＝iＣtＳＳ′｜a Ｓ′∷＝eＳ｜ε Ｃ∷＝b 它是2型文法却不是LL（1）文法。 我们可以按照上述方法构造它的分析表，从该表可以看出，元素M[S’, e]有两条规则，即M[S’, e]有多重定义入口，所以该文法不是LL（1）文法。 a b e i t # S S’ C S::=a C::=b S’::eS,S’::=ε S::=iCtSS’ S’::=ε §4.2 自顶向下语法分析 三、LL(1)分析法 (2) LL(1)文法性质 LL（1）文法有一些明显的性质，它不是二义的，也不含左递归。 还可以证明Ｇ是LL（1）的，当且仅当Ｇ的任何两个规则Ａ∷＝α｜β 满足下面条件： 1) FIRST(α) ∩ FIRST(β)＝?，也就是α和β推导不出 以某个同一终结符a为首的符号串。 2) α和β中最多只有一个可能推出空串。 3) 如果β? *ε，那么α推出任何串不会以FOLLOW(A)中的 终结符开始，即若β? *ε则FIRST(α) ∩FOLLOW(A) ＝? * 注意：对于某些LL（1）文法可以通过消除左递归和提取左因子（消除回溯） 变成LL（1）文法 §4.2 自顶向下语法分析 三、LL(1)分析法 教材第142－143页 第1题(1)用重复法，(4)用改写法 第2题(2) 第4题(1)(用类PASCAL(或类C)和画框图 两种方法) * 第四章 语法分析 习题一 教材第143－144页 第4题(1)(画框图 ) 第5题(1)，(2)，(3) 第6题(2) * 第四章 语法分析 习题二 一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 * §4.2 自顶向下语法分析 三、LL(1)分析法 * 2. LL（1）分析方法 （1）基本思想 借助于一张分析表及一个语法分析栈，在一个总控程序控制下实现。我们通常把按LL（1）方法执行语法分析任务的程序称为LL（1）分析程序或LL（1）分析器，它由一个总控程序、一张分析表和一个分析栈组成，如下图所示。 a1 a2 … ai … an # 输入串 总控程序 分析表m X . . . # 分析栈 §4.2 自顶向下语法分析 三、LL(1)分析法 （2）LL（1）方法分析过程 考虑文法Ｇ［Ｅ］: Ｅ→ＴＥ′ Ｅ′→＋ＴＥ′｜ε Ｔ→FT′ Ｔ′→*ＦＴ′｜ε Ｆ→（Ｅ）｜i 1）建立文法LL（1）的分析表 相应的分析表如下表所示（其构造方法，在后面叙述)。 * §4.2 自顶向下语法分析 三、LL(1)分析法 * i + *