预测分析法也称为 LL ( 1 )分析法。这种分析法是确定的自上而下分析的另一种方法,采用这种方法进行语法分析要求描述语言的文法是 LL ( 1 )文法。
一个预测分析器由一张预测分析表(也称为 LL ( 1 )分析表)、一个先进后出分析栈和一个总控程序三部分组成,见图 4.3 。
图中输入缓冲区 T [j ]中存放待分析的输入符号串,它以右界符 $ 作为结束。分析栈S [ k ]中存放替换当前非终结符的某规则右部符号串,句子左界符“ $ ”存入栈底。预测分析表是一个 M [ A ,a ]形式的矩阵,其中 A 为非终 结符, a 是终结 符或“ $ ”。分析表元素M [ A , a ]中的内容为一条关于 A 的规则,表明当 A 面临输入符号 a 时,当前推导所应采用的候选式,当元素的内容为“出错标志”(表中用空白格表示“出错标志”)时,则表明 A 不应该面临输入符号 a 。
预测分析器的总控程序在任何时候都是根据栈顶符号和当前输入符号 a 来决定分析器的动作,其工作过程用流程图 4.4 表示。
预测分析器的总控程序对于不同的 LL ( 1 )文法都是相同的,而预测分析表对于不同的LL ( 1 )文法是不相同的,下面我们介绍对于任给的文法 G 构造预测分析表的算法。
输入:文法 G 。
输出:预测分析表 M 。
方法:
(1 )计算文法 G 的每一非终结符的 FIRST 集和 FOLLOW 集。
① 对每一文法符号 X ∈ ( V N ∪ V T ),计算 FIRST ( X ):
a. 若 X ∈ V T ,则 FIRST ( X ) = { X }。
b. 若 X ∈ V N 且有规则 X → a …, a ∈ V T ,则 a ∈FIRST ( X )。
c. 若 X ∈ V N 且有规则 X → ε ,则 ε ∈FIRST ( X )。
d. 若有规则 X → y 1 y 2 … y n ,对于任意的 i ( 1≤ i ≤ n ),当 y 1 y 2 … y i -1 都是非终结符,且y 1 y 2 … y i -1 ⇒* ε 时,则将
FIRST ( y i )中的非 ε 元素加到 FIRST ( X )中。
特别是,若 y 1 y 2 … y n ⇒* ε,则 ε ∈FIRST ( X )。
e. 反复使用 a. ~d. 直到 FIRST 集不再增大为止。
② 对文法中的每一个 A ∈ V N ,计算 FOLLOW ( A ):
a. 对文法的开始符号 S ,则将“ $ ”加到 FOLLOW ( S )中。
b. 若 A → αB β 是一条规则,则把 FIRST (β )中的非 ε 元素加到 FOLLOW (B )中。
c. 若 A → αB 或 A → αB β 是一条规则且 β ⇒* ε,则把 FOLLOW ( A )加到 FOLLOW ( B )中。
d. 反复使用 b.~c. 直到每个非终结符的 FOLLOW 集不再增大为止。
(2 )对文法的每个规则 A → α ,若 a ∈FIRST ( α ),则置 M [ A , a ] = A → α 。
(3 )若 ε ∈FIRST ( α ),对任何 b ∈FOLLOW ( A ),则置 M [ A , b ] = A → α 。
(4 )把分析表中无定义的元素标上出错标志 error (表中用空白格表示)。
【例 4.10 】设有文法 G [ S ]:
S → a |∧| ( T )
T → ST'
T' → , ST' | ε
试构造该文法的预测分析表。
分析 首先判断该文法是否 LL ( 1 )文法,在例 4.9 中已经证明该文法是 LL ( 1 )文法。
计算该文法每个非终结符的 FIRST 集和 FOLLOW 集:
对规则 S → a ,因为 FIRST (a ) = { a },所以置 M [ S , a ] = S → a 。
对规则 S →∧ ,因为 FIRST ( ∧ ) = { ∧ },所以置 M [ S , ∧ ] = S →∧
。
对规则 S → ( T ),因为 FIRST (( T )) = {(},所以置 M [ S ,(] = S → ( T )。
对规则 T → ST’ ,因 为 FIRST ( ST’ ) = {(,a , ∧ },所 以 置 M [ T ,(] = T → ST’ ,M [ T , a ] = T → ST’ , M [ T , ∧ ] = T → ST’ 。
对规则 T’ → ,ST’ ,因为 FIRST (, ST’ ) = {,},所以置 M [ T’ ,]。 = T’ → , ST’ 。
对规则 T’ → ε ,因为 FOLLOW ( T’ ) = {)},所以置 M [ T’ ,)] = T’ → ε 。
文法 G [ S ]的分析表见表 4.1 。
对输入串(a , a ) $ 预测分析器作出的移动如表 4.2 所示。
可以证明,若一个文法 G 的分析表 M 不含多重定义元素,则该文法是 LL ( 1 )文法。