大连理工大学编译原理复习介绍

答案：stmt->if expr then stmt optional_else_part | other optional_else_part->else |ε （3）形式语言鸟瞰[选择题2分]； [1] Chomsky把文法分为4种类型，其中描述能力最强的是（ ）。 A. 0型 B. 1型 C. 2型 D. 3型 答案：A [2] 文法分为四种类型，即0型、1型、2型、3型。其中1型文法是（ ）。 A. 短语文法 B. 正则文法 C. 上下文有关文法 D. 上下文无关文法 答案：C [3] 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（ ）。 A. 短语文法 B. 正则文法 C. 上下文有关文法 D. 上下文无关文法 答案：B G 第三章 3.3 自上而下分析 （1）LL(1)文法概念[选择题2分]； [1] 3在下面的各种编译方法中，属于自顶向下的语法分析算法的是（ ）。 A. LL(1)分析方法 B. LR(K) 分析方法 C. SLR分析方法

D. LALR(1) 分析方法 答案：A [2] LL(1)分析法的名字中，第二个“L”的含义是（ ）。 A. 自左向右进行扫描 B. 每次采用最左推导 C. 采用最右推导的逆过程——最左规约 D. 向输入串中查看一个输入符号 答案：B [3] LL(1)分析法的名字中，第一个“L”的含义是（ ）。 A. 自左向右进行扫描 B. 每次采用最左推导 C. 采用最右推导的逆过程——最左规约 D. 向输入串中查看一个输入符号 答案：A （2）构造预测分析表（包括求FIRST、FOLLOW集）[简答题10分]； [1] 设文法 G(S)： S→S ＋ aF|aF| ＋ aF F→*aF|*a （1）消除左递归和回溯； （2）构造相应的 FIRST 和 Follow 集合。 答案： （1） S->aFS'|＋aFS' S'->＋aFS'|ε F->*aF'

F'->F|ε （2） FIRST（S）＝｛a，+｝ FOLLOW（S）＝｛＃｝ FIRST（S'）＝｛+，ε ｝ FOLLOW（S'）＝｛＃｝ FIRST（F）＝｛*｝ FOLLoW（F）＝（+，＃｝ FIRST（F'）＝｛*，ε｝ FOLLOW（+，＃｝ [2] 文法： S->MH|a H->LSo| ε K->dML| ε L->eHf M->K|bLM 判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。 答案： 各符号的FIRST集和FOLLOW集为： 预测分析表为：

由于预测分析表中无多重入口，所以可判定文法是LL(1)的。 [3] 请给对文法G[S]进行改写成LL（1）文法，并给出改写后文法的预测分析表，要求计算出改写后文法各非终极符的FIRST和FOLLOW集合。 S → S*aA | aA| *aA A→ +aA | +a 答案： 改写文法如下： S?*aAS’ | aAS’ S’?*aAS’ | ? A?+aA’ A’?A | ? S S’ A A’ 预测分析表： * a + # FIRST {*，a} {*,?} {+} {+,?} FOLLOW {#} {#} {*,#} {*,#}