Posted on 2006-05-31 23:55
形式系统 阅读(1364)
评论(4) 编辑 收藏 引用 网摘 所属分类:
编译原理
1、 已知文法 G ( S )
S → *A A → 0A1 | *
(1) 求文法 G 的各非终结符号的 FIRSTVT 和 LASTVT 集合。
(2) 构造文法 G 的优先关系矩阵,并判断该文法是否算符优先文法。
(3) 分析句子 *0*1 ,并写出分析过程。
分析:FIRSTVT 及 LASTVT 求法
构造集合 FIRSTVT ( P )的两条规则。
(i) 若有产生式 P→a… ,或 P→Qa… ,则 a ∈ FIRSTVT ( P )。
(ii) 若 a ∈ FIRSTVT ( P ),且有产生式 P→Q… ,则 a ∈ FIRSTVT ( P )。
构造集合 FIRSTVT ( P )的两条规则
(i) 有产生式P→…a,或P→…aQ,则a∈LASTVT(P)。
(ii) 若 a ∈ LASTVT ( Q ),且有产生式 P→Q… ,则 a ∈ FIRSTVT ( P )。
(1) | FIRSTVT | LASTVT |
S | * | 1 * |
A | 0 * | 1 * |
分析: 若有产生式的候选形为: …aPb… 则 a=•b
若有个产生式的候选形为: …aP… 则 b ∈ FIRSTVT ( P ) a<•b
若有个产生式的候选形为: …Pb… 则 a ∈ LASTVT ( P ) a•>b
(3) 符号栈 优先关系 输入 # < *
# * < 0
# * 0 < *
# * 0 * > 1
# * 0 A = 1
# * 0 A 1 > #
# * A > #
# S = #
2、考虑下列文法G: