第一章
▪ 什么是编译器？
▪ 编译程序的结构分为几个阶段，各阶段的任务是什么？
▪ 遍、编译前端及编译后端的含义？
▪ 编译程序的生成方式有哪些？
第二章
▪ 1. 写一文法，使其语言是偶正整数的集合。
▪ 要求：（1）允许0打头 （2） 不允许0打头
解：（1）允许0开头的偶正整数集合的文法
      E→NT|D
      T→NT|D
      N→D|1|3|5|7|9
      D→0|2|4|6|8
（2）不允许0开头的偶正整数集合的文法
  E→NT|D
  T→FT|G
  N→D|1|3|5|7|9
  D→2|4|6|8
  F→N|0
  G→D|0
2.证明下述文法G［〈表达式〉］是二义的。
〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉
〈运算符〉∷=+|-|*|/
解：可为句子a+a*a构造两个不同的最右推导:
最右推导1  〈表达式〉⇒〈表达式〉〈运算符〉〈表达式〉
⇒〈表达式〉〈运算符〉a
⇒〈表达式〉* a
⇒〈表达式〉〈运算符〉〈表达式〉* a
⇒ 〈表达式〉〈运算符〉a  * a
⇒〈表达式〉+ a * a
⇒  a + a * a
最右推导2  〈表达式〉⇒〈表达式〉〈运算符〉〈表达式〉
⇒〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉
⇒〈表达式〉〈运算符〉〈表达式〉〈运算符〉 a
⇒〈表达式〉〈运算符〉〈表达式〉 * a
⇒ 〈表达式〉〈运算符〉a  * a
⇒〈表达式〉+ a * a
⇒  a + a * a
3. 给出生成下述语言的上下文无关文法：
        （1）{ anbnambm| n，m>=0} 
        （2）{ 1n0m1m0n| n，m>=0}
解： （1）{ anbnambm| n，m>=0}
S→AA
A→aAb|ε                                 
(2) { 1n0m1m0n| n，m>=0}
S→1S0|A
A→0A1|ε
in运算符的含义第三章
1、构造一个DFA，它接收∑={a, b}上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。
解：
已知∑={a, b}，根据题意得出相应的的正规式为： (b*abb*)*
根据正规式画出相应的DFA M，如下图所示
用子集法将其确定化
I
Ia
Ib
{X,1,2,3,Y}
{4}
{2,3}
{4}
—
{5,6,1,2,3,Y}
{2,3}
{4}
{2,3}
{5,6,1,2,3,Y}
{4}
{6,1,2,3,Y}
{6,1,2,3,Y}
{4}
{6,1,2,3,Y}
I
Ia
Ib
0
1
2
1
—
3
2
1
2
3
1
4
4
1
4
由DFA得状态图                    用最小化方法化简得：{0}，{1}，{2}，{3,4}，按顺序重新命名DFA M’
               
第四章
练习1：文法G[V]：
    V→N|N[E]        E→V|V+E          N→i
  是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。
解：
LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中含有回溯，所以先消除回溯得到文法G’[V]：
  G’[V]：    V→NV’      V’→ε|[E] 
          E→VE’      E’→ε|+E
                    N→i
由LL(1)文法的充要条件可证G’[V]是LL(1)文法
练习2：有文法G[s]:
    S→BA      A→BS|d    B→aA|bS|c
(1)证明文法G是LL(1)文法。
(2)构造LL(1)分析表。
(3)写出句子adccd的分析过程
解：(1)一个LL(1)文法的充要条件是：对每一个非终结符A的任何两个不同产生式A→α|β，有下面的条件成立：
    ① FIRST(α)∩FIRST(β)=Φ;
    ② 若β*⇒ε, 则有FIRST(α)∩FOLLOW(A)=Φ
对于文法G[s]: 
      S→BA      A→BS|d    B→aA|bS|c
其FIRST集如下：
    FIRST(B)={a, b, c};  FIRST(A)={a, b, c, d};  FIRST(S)={a, b, c}。
其FOLLOW集如下：
首先， FOLLOW(S)={#};
对S→BA有： FIRST(A)\{ε}加入FOLLOW(B), 即FOLLOW(B)={a, b, c, d };
对A→BS有：FIRST(S)\{ε}加入FOLLOW(B), 即FOLLOW(B)={a, b, c, d };
对B→aA有：FOLLOW(B)加入FOLLOW(A), 即FOLLOW(A)={a, b, c, d };
对B→bS有：FOLLOW(B)加入FOLLOW(S), 即FOLLOW(S)={#, a, b, c, d };
由A→BS|d得：
          FIRST(BS) ∩FIRST(d) = { a, b, c } ∩{d} = Φ;
由B→aA|bS|c得：
          FIRST(aA) ∩FIRST(bS) ∩FIRST(c) ={a} ∩{b} ∩{c}= Φ。
由于文法G[s]不存在形如 β→ε的产生式，故无需求解形如FIRST(α)∩FOLLOW(A)的值。也即，文法G[S]是一个LL(1)文法。
(2) 由G[s]:S→BA  A→BS|d  B→aA|bS|c的
FIRST(B)={a, b, c};      FOLLOW(B)={a, b, c, d };
FIRST(A)={a, b, c, d};  FOLLOW(A)={a, b, c, d };
FIRST(S)={a, b, c}。    FOLLOW(S)={#, a, b, c, d }可构造LL(1)预测分析表如下：
 
a
b
c
d
#
S
S→BA
S→BA
S→BA
 
 
A
A→BS
A→BS
A→BS
A→d
 
B
B→aA
B→bS
B→c
 
 
S
S→BA
S→BA
S→BA
 
 
A
A→BS
A→BS
A→BS
A→d
 
B
B→aA
B→bS
B→c
 
 
(3)在分析表的控制下，句子adccd的分析过程如下：
第五章
1 已知文法G[S]为：
  S→a|∧|(T)  　T→T,S|S
(1) 计算G[S]的FIRSTVT和LASTVT。
(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。
(3) 给出输入串 (a,(a,a))#的算符优先分析过程。
解：文法：
  S→a|∧|(T)    T→T,S|S
展开为：
  S→a　S→∧　S→(T)
  T→T,S      T→S
(1) FIRSTVT -- LASTVT表
非终结符
FIRSTVT集
LASTVT集
S
{ a ∧ ( }
{ a ∧ ) }
T
{ a ∧ ( , }
{ a ∧ ) , }
(2)算符优先关系表如下: 表中无多重入口所以是算符优先（OPG）文法。 
 
a
∧
(
)
,
#
a
∧
(
)
,
#

≮
≮
≮

≮
≮
≮

≮
≮
≮
≯
≯
≒
≯
≯
≯≯≮≯≯
≯
≯
≯
≒
(3) 输入串（a,(a,a)）# 的算符优先分析过程为：
栈
当前字符
剩余输入串
动作
#
#(
#(a
#(N
#(N,
#(N,(
#(N,(a
#(N,(N
#(N,(N,
#(N,(N,a
#(N,(N,N
#(N,(N
#(N,(N)
#(N,N
#(N
#(N)
#N
(
a
,
,
(
a
,
,
a
)
)
)
)
)
)
#
#
a,(a,a))#
,(a,a))#
(a,a))#
(a,a))#
a,a))#
,a))#
a))#
a))#
))#
)#
)#
)#
#
#
#
Move in
Move in
Reduce: S→a
Move in
Move in
Move in
Reduce: S→a
Move in
Move in
Reduce: S→a
Reduce: T→T,S
Move in
Reduce: S→(T)
Reduce: T→T,S
Move in
Reduce: S→(T)
第六章

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。