第章语法分析.pdf

Compilers：Principles and Techniques Chapter 5 Syntax Analysis Fall 2010 li weihua Department of Computer Science technology, Informational school, Yunnan University 2010-9-8 1 基本思想 语法分析 − 核心问题：句型分析 对任意上下文无关文法G = (V ，T ，P，S ) 和任意w ∈ VT * ，是否有w ∈ L(G)？ 若成立， 则给出分析树或推导步骤；否则，进行报错处理。 − 两种实现途径 自顶向下（top-down ）分析 自底向上 （bottom-up ）分析 2010-9-8 2 自顶向下语法分析 预测分析 LL(1) 分析 文法变换：消除左递归、提取左公因子 LL(1) 分析中的错误处理 2010-9-8 3 基本思想 自顶向下分析举例 −对aaab 的一个自顶向下分析过程 文法 G （S ）: S （S → AB ） ⇒ AB （A → aA ） S → AB ⇒ aAB （B → b ） A → aA | ε ⇒ aAb （A → aA ） B → b | bB ⇒ aaAb （A → aA ） ⇒ aaaAb （A → ε ） ⇒ aaab 2010-9-8 4 一般方法(带回溯的自顶向下分析) − 两类非确定性 在每一步推导中，选择对哪一个非终结符、 哪一个产生式都可能是非确定的 分析成功的结果：得到一个推导 2010-9-8 5 带回溯的自顶向下分析 举例 − 对 aaab 的一个自顶向下分析过程 S （1 ） 文法 G （S ）: ⇒ AB （2 ） ⇒ aAB （5 ） （1 ）S → AB ⇒ aAbB （2 ）