《编译原理》求 FIRSTVT 集和 LASTVT 集的步骤 - 例题解析
《编译原理》求 FIRSTVT 集和 LASTVT 集的步骤 - 例题解析
算符优先关系表的构造中涉及到求 FIRSTVT 集和 LASTVT 集。
表示及含义：
| FIRSTVT(T) | 非终结符T的最左终结符集合 |
|---|---|
| LASTVT(T) | 非终结符T的最右终结符集合 |
定义：
定义解释：
| FIRSTVT(T) | 非终结符T经过1步或多步推导，得到的最左端终结符，以及左端第二个终结符的集合 |
|---|---|
| LASTVT(T) | 非终结符T经过1步或多步推导，得到的最右端终结符，以及倒数第二个终结符的集合 |
求 FIRSTVT 集的步骤：
（1）若有产生式 T→a 或者 T→Ra…，则 a ∈ FIRSTVT(T)
（2）若 a ∈ FIRSTVT®，且有产生式 T→R…，则 a ∈ FIRSTVT(T)
就是说如果 a 是非终结符 R 的 FIRSTVT 集，且 T 可以推出以非终结 R 带头的右部，则 a 也是非终结符 T 的 FIRSTVT 集。
注： 省略号 … 可以为空，就是没有
求 LASTVT 集的步骤：
（1）若有产生式 T→…a 或者 T→…aR，则 a ∈ LASTVT(T)
（2）若 a ∈ LASTVT®，且有产生式 T→…R，则 a ∈ LASTVT(T)
例题：
已给文法：
G[S]:
S→a|b|(B)
A→S, A|S
B→A
求所有非终结符的 FIRSTVT，LASTVT 集
解析：
（1）只要是让求 FIRSTVT，LASTVT 集，则该文法就隐含条件为算符优先文法。
（2）算符优先文法的特点是：不会出现两个相邻的非终结符，即两个非终结符中间夹着一个终结符。如果第一个是终结符则第二个是非终结符。
结果：
| FIRSTVT 集 | LASTVT 集 | |
|---|---|---|
| S | {a, b, ( } | {a, b, ) } |
| A | {a, b, (, 逗号 } | {a, b, ), 逗号} |
| B | {a, b, (, 逗号 } | {a, b, ), 逗号} |