编译设计习题（英文题）

Question

编译设计课留的题，专业采用全英教学，因此题是英文的，但是正常人都可以看懂，求个专家来帮忙

Answer 1

基于Monster 组和GPT的调写：

• A) 一个a可以直接推导成S，然后(S)可以推导成S-(L)，L可以推导成a，(a,a)可以推导成L，所以可以得到以下左推导过程：
  G => S => (L) => (L,S) => (L,a,S) => (a,a,S) => (a,(L),S) => (a,(L,S)) => (a,(a,S)) => (a,(a,(L))) => (a,(a,a))

• B) 一个a可以直接推导成S，然后(S)可以推导成S-(L)，L可以推导成a，(a,a)可以推导成L，所以可以得到以下右推导过程：
  G => S => (L) => (a,L) => (a,L,S) => (a,(L),S) => (a,(L,S)) => (a,(a,S)) => (a,(a,(L))) => (a,(a,a))

• C) 由于某个非终结符的一个产生式的FIRST集合与另一个产生式的FIRST集合有交集，所以这个文法不是LL(1)的。具体来说，L的两个产生式的FIRST集合都包含a，而S的产生式的FIRST集合包含s，这就导致了S的产生式和L的产生式存在冲突，无法进行预测性分析。

• D) 对文法进行改写如下：

G -> S
S -> aS' | sS'
S' -> ,SaS' | ε

首先计算FIRST集合和FOLLOW集合：

FIRST(S) = {a, s}
FIRST(S') = {,, ε}
FIRST(G) = FIRST(S) = {a, s}
FOLLOW(S) = {), ,}
FOLLOW(S') = {), ,}
FOLLOW(G) = {$, )}

• 然后可以构造LL(1)分析表：

这个分析表没有任何冲突，所以这个文法是LL(1)的。