编译原理知识点

第四章作业及相关知识点

一、第一题知识点

1、消除左递归

\(P → Pα｜β\)等价于\(P→βP’（P’\)为新增加的非终结符\(）, P'→αP'｜ε\)

2、判断一个上下文无关文法是\(LL(1)\)文法

一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符的两个不同的产生式，\(A→α，A→β\)，满足：\(SELECT(A→α)∩SELECT(A→β)= φ\)

3、求\(select\)集

设$G=(Ｖ_T，Ｖ_N，S，P） α∈Ｖ* $

$FIRST(α)={a|α==*> aβ，a∈Ｖ_T}

若\(α==*>ε\)，则\(SELECT(A→α)= FIRST(α)\)

若\(α==*>ε\)，则\(SELECT(A→α) = (FIRST(α)-{ε})∪FOLLOW(A)\)

4、求\(first\)集

设$G=(Ｖ_T，Ｖ_N，S，P） α∈Ｖ* $

$FIRST(α)={a|α==*> aβ，a∈Ｖ_T}

若\(α==*>ε，则ε∈FIRST(α)\)

\(FIRST(α)\)是\(α\)的所有可能推导的首遇终结符号或ε，是选择产生式的依据。

5、求\(follow\)集

\(A∈Ｖ_N\)
\(FOLLOW(A)={ a｜S==*>…Aa…，a∈Ｖ_T }\)
若\(S==*>…A\)，则#\(∈FOLLOW（A）\)
'#'—输入串的结束符 也可看作是句子的括号 #S#
\(FOLLOW(A)\)表示了句型中可能紧跟在\(A\)后面的终结符号

6、构造预测分析表

设有文法\(G\)，预测分析表构造过程：

• 计算所有候选式\(α\)的首符集 \(FIRST（α）\)
• 计算所有非终结符A的后继符集\(FOLLOW（A）\)
• 计算所有产生式的\(SELECT(A→α)\)集合
• 构造预测分析表 \(M\)