发布时间 : 星期四 文章哈工大编译原理习题及答案更新完毕开始阅读68851b05bed5b9f3f90f1ca1
? ?
5.证：因为是左递归文法，所以必存在左递归的非终结符A，及形如A→α|β的产生式,且αT* Ad.
则first(Ad) ∩first(β)≠φ,从而
first(α) ∩first(β)≠φ，即文法不满足LL（1）文法条件。得证。
?
6.证：LL（1）文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设LL(1)文法G是二义性文法，则存在句子α，它有两个不同的语法树。即存在着句子α有两个不同的最左推导。从而可知，用LL（1）方法进行句子α的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL（1）分析动作存在不确定性。与LL（1）性质矛盾。所以，G不是LL(1)文法。 ?
7.解：
(1)D产生式两个候选式fD和f的first集交集不为空，所以不是LL(1)的。 (2)此文法具有左递归性，据第5题结论，不是LL(1)的。
?
8.解：
(1)消除左递归性,得：
S→bZ11|aZ21A→bZ12|aZ22Z11→bZ11|εZ12→bZ12 Z21→bZ11|aZ21Z22→bZ12|aZ22|ε
消除无用产生式得：S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21 此文法已满足LL(1)文法的三个条件，
所以 G’[S]: S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21 (2) G’文法的各非终结符的FIRST 集和FOLLOW集：
产生式 S→bZ11 →aZ21 Z11→bZ11 →ε Z21→bZ11 →aZ21
LL(1)分析表为： S Z11 Z21
? (1)
产生式 S→SaB →bB A→S →a B→Ac a aZ21 aZ21 9.解：
FIRST 集 {b} {a} {b} {ε} {b} {a}
FOLLOW集 {#}
{#}
{#}
b bZ11 bZ11 bZ11
# ε
first集 {b}
follow集 {#,a,c}
{b} {b}
{c}
{a} {a,b}
{#,a,c}
(2)将S→SaB | bB改写为S→bBS’,S’ →aBS’|ω,可验证，新文法是LL(1)的。
? ?
10.解：
1）为方便书写，记：<布尔表达式>为A，<布尔因子>为B，<布尔二次量>为C，<布尔初等量>为D，原文法可以简化为：
A→A∨B | B B→B∧C | CC→┐D | DD→(A) | true | false, 显然，文法含有左递归，消去后等价LL(1)文法为： A→BA’ A’ →∨BA’|ω B→CB’,
B’ →∧CB’|ωC→┐D|DD→(A)| true|false
(2)略
?
证：若LL（1）文法G有形如B→aAAb的产生式，且AT+ε及AT*ag,根据FIRST集FOLLOW集的构造算法可知，FIRST(A)中一切非ε加到FOLLOW(A)中，则a∈FOLLOW(A)；又因为a∈FIRST(ag),所以两集合相交非空，因此，G不是LL(1)文法；与前提矛盾，假设不成立，得证。 ? (1) S A ( a) b S = = A = < = < ( = = < < < <
a > = < > >
> ) > > >> > b > >
不是简单优先文法。 (2)
S RT ( )∧ a, S > = R = T > ( < =< < < < ) > > ∧ > > a > > , < = < < < 是简单优先文法。 (3) S R (a , ) S = < < R > > ( = < < a > >
解：
, = < < ) > >
是简单优先文法。
o 首先消去无用产生式Z→E, Z→E+T
S Z T# i () S Z = = T > > # = < < < I > > ( = < < < ) > >
化简后的文法是简单优先文法；
?
S A / a
=
解：
S
<
< > >
> >
A
/ > =
= A >
A和/之间同时有关系=和<,所以不是简单优先文法；
?
提示：分析教材中给出的算法，选择一种合适的表示给定文法的方法（尽量简单），使得对文法的输入比较简单的同时(需要把输入转化为计算机语言表示，这种转化应该尽量简单)，能够比较简单地构造3个基本关系矩阵（=，LEAD和LAST）。 ?
证明：设xjxj+1...xi是满足条件xj-1 解：为描述方便，用符号表示各非终结符：D=<变量说明>,L=<变量表>, V= <变量>,T=<类型>，a=VAR,则消去V，并采用分层法改写文法，得到：D→aW:T;W→LL→L,i|iT→r|n|b|c 其全部简单优先关系是：