ᕕ( ᐛ )ᕗ Jimyag's Blog

编译原理 - 作业

课上不努力、课后徒伤悲。好好听网课，好好学习！

FIRST 集合

定义

FIRST(X) 是 X 所有可能推导的开头终结符号或可能推导的ε所构成的集合。

构造 FIRST 集合

对于每个非终结符或终结符 X 连续使用以下规则，直至每个 X 的 FIRST 集合不再增大为止

  1. 若左边第一个符号是终结符或者是ε，将其放在 FIRST(X) 中;
  2. 若左边第一个符号是非终结符，将其 FIRST 集合中非ε元素加入 FIRST(X) 中;
  3. 若左边第一个符号是非终结符而且紧随其后有很多非终结符，要注意是否有ε;
  4. 若第 i 个非终结符的 FIRST 集中有ε，则把第 i+1 个非终结符的 FIRST 集合除ε的元素加入 FRIST(X);
  5. 若所有非终结符的 FIRST 集中都有ε，则把ε加入 FIRST(X);

重复使用以上规则，直至每个 X 的 FIRST 集合不再增大为止。

例题

对于文法 G(E):

$$E-> TE^{\prime} $$

$$E^{\prime}-> +TE^{\prime} |ε $$

$$T->FT^{\prime}$$

$$T^{\prime}->*FT^{\prime}|ε$$

$$F->(E)|i$$

构造每个非终结符的 FIRST 集合

我们使用上述规则进行构造

第一轮
E-> TE1

左边第一个是非终结符、紧随其后的也是终结符符合2,3规则，但是他们的 FISRT 集合都为空。

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
E1-> +TE1|ε

规则 1：左边第一个是终结符和ε，将他们放进 FIRST{E1}集中

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε
T->FT1

规则2: 将 FIRSR{F}中的非ε元素加入 FIRST(T)，FIRST{T}为空

规则3:FIRST{T}和 FIRST{F1}为空

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε
T1->*FT1|ε

规则1:将 *，ε加入 FIRST{T1}

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε *，ε
F->(E)|i

规则1:将（，i 加入 FIRST{F}

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε *，ε （，i

FIRST 集合还在增大所以继续下一轮

第二轮
E-> TE1

规则2: FISRT{T}为空

规则3: FISRT{T}为空

不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε *，ε （，i
E1-> +TE1|ε

规则 1：左边第一个是终结符和ε，将他们放进 FIRST{E1}集中。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε *，ε （，i
T->FT1

规则2: 将 FIRSR{F}中的非ε元素加入 FIRST(T) 变化了。

规则3:FIRST{F}没有ε，不用考虑了。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε （，i *，ε （，i
T1->*FT1|ε

规则1:将 *，ε加入 FIRST{T1}。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε （，i *，ε （，i
F->(E)|i

规则1:将（，i 加入 FIRST{F}不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
+，ε （，i *，ε （，i

有变化，继续从头开始扫描

第三轮
E-> TE1

规则2: 把 FISRT{T}放入 FISRT{E}中 有变化

规则3: FISRT{T}中没有ε，不用管

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
E1-> +TE1|ε

规则 1：左边第一个是终结符和ε，将他们放进 FIRST{E1}集中。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
T->FT1

规则2: 将 FIRSR{F}中的非ε元素加入 FIRST(T)。已经放过了

规则3:FIRST{F}没有ε，不用考虑了。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
T1->*FT1|ε

规则1:将 *，ε加入 FIRST{T1}。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
F->(E)|i

规则1:将（，i 加入 FIRST{F}不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i

有变化，继续从头开始扫描

第四轮
E-> TE1

规则2: 把 FISRT{T}放入 FISRT{E}中。没有增大

规则3: FISRT{T}中没有ε，不用管

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
E1-> +TE1|ε

规则 1：左边第一个是终结符和ε，将他们放进 FIRST{E1}集中。没有增大

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
T->FT1

规则2: 将 FIRSR{F}中的非ε元素加入 FIRST(T)。没有增大

规则3:FIRST{F}没有ε，不用考虑了。不变

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
T1->*FT1|ε

规则1:将 *，ε加入 FIRST{T1}。没有增大

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i
F->(E)|i

规则1:将（，i 加入 FIRST{F} 没有增大

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i

没有增大 结束。

最终结果为：

$$FIRST{E}$$ $$FIRST{E^{\prime}}$$ $$FIRST{T}$$ $$FIRST{T^{\prime}}$$ $$FIRST{F}$$
（，i +，ε （，i *，ε （，i

FOLLOW 集合

定义

FOLLOW(A) 是所有矩形中出现在紧接 A 之后的终结符或#所构成的集合

构造 FOLLOW 集合、

对于每个非终结符 A，连续使用以下规则，直至每个 FOLLOW 集合不再增大

  1. 对于文法的开始符号 S，置#于 FOLLOW(S) 中
  2. 若 A-> αBβ是一个产生式，则把 FISRT{β}中非ε元素放入 FOLLOW{B}中
  3. 若 A-> αB 或 A-> αBβ【ε∈FISRT{B}】则把 FOLLOW{A}中的元素放入 FOLLOW{B}。

αβ是由终结符和非终结符构成的

例题

对于文法 G(E):

$$E-> TE^{\prime} $$

$$E^{\prime}-> +TE^{\prime} |ε $$

$$T->FT^{\prime}$$

$$T^{\prime}->*FT^{\prime}|ε$$

$$F->(E)|i$$

构造每个非终结符的 FOLLOW 集合

根据规则1将# 放入 FOLLOW{E}中

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃
第一轮
E-> TE1

规则 2：α为空，B 为 T，E1 为β。将 FISRT{E1}中非ε元素放入 FOLLOW{T}中

规则 3：α为 T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有ε，将 FOLLOW{E}中的元素放入 FOLLOW{T}。

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃ ＃ +，＃
E1-> +TE1|ε

规则 2：α为＋，B 为 T，β为 E1，将 FISRT{E1}中非ε元素放入 FOLLOW{T}中

规则 3：α为＋T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有ε，将 FOLLOW{E}中的元素放入 FOLLOW{T}。

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃ ＃ +，＃
T->FT1

规则 2：α为空，B 为 F，T1 为β。将 FISRT{T1}中非ε元素放入 FOLLOW{F}中

规则 3：α为 F，B 为 T1 FOLLOW{T}中的元素放入 FOLLOW{T1}。

规则 3：α为空，B 为 F，T1 为β，FISRT{T1}中有ε，将 FOLLOW{T}中的元素放入 FOLLOW{F}。

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃ ＃ +，＃ +，＃ *，+，＃
T1->*FT1|ε

规则 2：α为＊，B 为 F，T1 为β。将 FISRT{T1}中非ε元素放入 FOLLOW{F}中

规则 3：α为＊F，B 为 T1 FOLLOW{T1}中的元素放入 FOLLOW{T1}。不变

规则 3：α为＊，B 为 F，T1 为β，FISRT{T1}中有ε，将 FOLLOW{T1}中的元素放入 FOLLOW{F}。不变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃ ＃ +，＃ +，＃ *，+，＃
F->(E)|i

规则 2：α为（，B 为 E，）为β。将 FISRT{）}中非ε元素放入 FOLLOW{E}中

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃ +，＃ +，＃ *
第二轮
E-> TE1

规则 2：α为空，B 为 T，E1 为β。将 FISRT{E1}中非ε元素放入 FOLLOW{T}中。已经放过

规则 3：α为 T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有ε，将 FOLLOW{E}中的元素放入 FOLLOW{T}。已经放过

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃ +，＃ *，+，＃
E1-> +TE1|ε

规则 2：α为＋，B 为 T，β为 E1，将 FISRT{E1}中非ε元素放入 FOLLOW{T}中

规则 3：α为＋T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。没变

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有ε，将 FOLLOW{E}中的元素放入 FOLLOW{T}。没变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃ *，+，＃
T->FT1

规则 2：α为空，B 为 F，T1 为β。将 FISRT{T1}中非ε元素放入 FOLLOW{F}中。没变

规则 3：α为 F，B 为 T1 FOLLOW{T}中的元素放入 FOLLOW{T1}。变了

规则 3：α为空，B 为 F，T1 为β，FISRT{T1}中有ε，将 FOLLOW{T}中的元素放入 FOLLOW{F}。变了

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）
T1->*FT1|ε

规则 2：α为＊，B 为 F，T1 为β。将 FISRT{T1}中非ε元素放入 FOLLOW{F}中。已经放过

规则 3：α为＊F，B 为 T1 FOLLOW{T1}中的元素放入 FOLLOW{T1}。不变

规则 3：α为＊，B 为 F，T1 为β，FISRT{T1}中有ε，将 FOLLOW{T1}中的元素放入 FOLLOW{F}。不变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）
F->(E)|i

规则 2：α为（，B 为 E，）为β。将 FISRT{）}中非ε元素放入 FOLLOW{E}中。不变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）
第三轮
E-> TE1

规则 2：α为空，B 为 T，E1 为β。将 FISRT{E1}中非ε元素放入 FOLLOW{T}中。已经放过

规则 3：α为 T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。没变

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有ε，将 FOLLOW{E}中的元素放入 FOLLOW{T}。已经放过

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃ +，＃ *，+，＃
E1-> +TE1|ε

规则 2：α为＋，B 为 T，β为 E1，将 FISRT{E1}中非ε元素放入 FOLLOW{T}中。已经放过

规则 3：α为＋T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。没变

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有ε，将 FOLLOW{E}中的元素放入 FOLLOW{T}。没变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃ *，+，＃
T->FT1

规则 2：α为空，B 为 F，T1 为β。将 FISRT{T1}中非ε元素放入 FOLLOW{F}中。已经放过

规则 3：α为 F，B 为 T1 FOLLOW{T}中的元素放入 FOLLOW{T1}。没变

规则 3：α为空，B 为 F，T1 为β，FISRT{T1}中有ε，将 FOLLOW{T}中的元素放入 FOLLOW{F}。没变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）
T1->*FT1|ε

规则 2：α为＊，B 为 F，T1 为β。将 FISRT{T1}中非ε元素放入 FOLLOW{F}中。已经放过

规则 3：α为＊F，B 为 T1 FOLLOW{T1}中的元素放入 FOLLOW{T1}。不变

规则 3：α为＊，B 为 F，T1 为β，FISRT{T1}中有ε，将 FOLLOW{T1}中的元素放入 FOLLOW{F}。不变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）
F->(E)|i

规则 2：α为（，B 为 E，）为β。将 FISRT{）}中非ε元素放入 FOLLOW{E}中。不变

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）

所有的 FOLLOW 已经没在变化了，这时候已经计算完了。

最后的结果为：

$$FOLLOW{E}$$ $$FOLLOW{E^{\prime}}$$ $$FOLLOW{T}$$ $$FOLLOW{T^{\prime}}$$ $$FOLLOW{F}$$
＃，） ＃，） +，＃，） +，＃，） *，+，＃，）

消除左递归

法一

将左递归变为右递归

P->Pα|β

变为

P->βP1

P1->αP1|ε

对于文法P->Pα|β我们可以推导出他能识别的串，它是以β开头后面接着 0-n 个α的串；βαααααα….

法二

条件
  1. 不含以ε为右部的产生式
  2. 不含回路（p->p）
方法
  1. 对非终结符进行排列 P1…..Pn
  2. 从 P1 到 Pn 遍历，把 Pi 改为α|Pi+1|Pi+2|...|Pn
    1. 从 j=1 到 j=i-1 把形如 Pi->Pjγ的改写为Pi->ζ1γ|ζ2γ|...|ζkγ 其中Pj->ζ1|ζ2|...|ζk。此时就可以得到形如 Pi->α|Pi|Pi|...|Pi+k|...
    2. 使用直接消除 Pi 使用方法一
  3. 化简2，去除从开始符号出发永远无法到达的非终结符产生规则

例题

考虑文法 G[S]

S->(T)|a+S|a

T->T，S|S

消除左递归

第一步

只有两个非终结符，按照一定顺序排序，按照 T，S 的顺序排列

第二步

  1. 先处理 T

    T->T，S|S

    由于 T 在前面，S 在后面，所以 S 不处理 (2.1)。由于本身有左递归，使用方法一直接消除左递归

    T->ST1

    T1-> ,ST1|ε

  2. 处理 S

    S->(T)|a+S|a

    由于 T 在 S 的前面，所以要将 T 处理掉。T 又有（T->ST1）进行替换

    S->(ST1)|a+S|a

    不含有左递归，处理结束

  3. 化简

    S->(ST1)|a+S|a

    T->ST1

    T1-> ,ST1|ε

    从开始符号都可以到达，所以不用去掉

结果为

S->(ST1)|a+S|a

T->ST1

T1-> ,ST1|ε

提取左公共因子

对于规则 S

S -> aB1|aB2|aB3|aB4|…|aBn|y

可以改写为

S-> aS1|y S1 -> B1|B2|B3…|Bn

FISRTVT 集合

方法

  1. A->a….. 则将 a 加入 FIRSTVT(A) 中
  2. A->B…. 将 FIRSTVT(B) 加入到 FIRSTVT(A) 中
  3. A->Ba…

例题

已给文法：

G[S]: S→a|b|(B) A→S, A|S B→A

求非终结符的 FISRTVT 集合

求 FIRSTVT(S)

S→a|b|(B)

根据规则1可得

FIRSTVT(S)= {a,b,(}

求 FIRSTVT(A)

A→S, A|S

根据规则2可得，应该 FISRTVT(S) 中的放入 FIRSTVT(A) 中

FIRSTVT(A) = {a,b,(}

根据规则3，应该把,放入 FIRSTVT(A) 中

FIRSTVT(A) = {a,b,(,逗号}

求 FIRSTVT(B)

B→A

根据规则3，应该 FISRTVT(A) 中的放入 FIRSTVT(B) 中

FIRSTVT(B) = {a,b,(,逗号}

FISRTVT
S {a,b,(}
A {a,b,(,逗号}
B {a,b,(,逗号}

LASTVT 集合

方法

  1. A->…..a 把 a 加入 LASTVT(A) 中
  2. A->…..B 把 LASTVT(B) 加入 LASTVT(A) 中
  3. A->….aB 把 a 加入 LASTVT(A) 中

例题

已给文法：

G[S]: S→a|b|(B) A→S, A|S B→A

求非终结符的 LASTVT 集合

求 LASTVT(S)

S→a|b|(B)

根据规则1可得

LASTVT(S)= {a,b,)}

求 LASTVT(A)

A→S, A|S

根据规则2可得，应该 LASTVT(S) 中的放入 LASTVT(A) 中

LASTVT(A) = {a,b,)}

根据规则3，应该把,放入 LASTVT(A) 中

LASTVT(A) = {a,b,),逗号}

求 LASTVT(B)

B→A

根据规则3，应该 LASTVT(A) 中的放入 LASTVT(B) 中

FIRSTVT(B) = {a,b,),逗号}

LASTVT
S {a,b,)}
A {a,b,),逗号}
B {a,b,),逗号}

算符优先文法 OPG 的条件

  1. OPG 文法条件
    1. 无 S->…AB…
    2. 无ε产生式
  2. 两两终结符间至多一种优先关系

判断算符优先级

方法一

  1. 找出所有非终结符，画出一下表格

    a b c … n
    a
    b
    c
    …
    n

  2. ＝ 找 aQb 形式的，a=b，横排找 a，竖排找 b

  3. < 找 aQ 形式的，a 与 FISRSTVT(Q) 的每个元素交叉处填<，a 为横排元素

  4. > 找 Qa 形式的，在竖排中找到 a，在横排中找到 LASTVT(Q) 中的元素，相交处填>

  5. # < FIRSTVT(A)

  6. LASTVT(A)>#

例题

已给文法：

G[S]: S→a|b|(B) A→S, A|S B→A

判断算符优先级

根据上面我们已经求出非终结符的 FIRSTVT 和 LASTVT 集合。列表

a b （ ） ，
a
b
（
）
，
  1. = 我们可以找到(B)是符合要求的，则
a b （ ） ，
a
b
（ =
）
，
  1. < 我们找到 aQ 形式的，有(B,,A 则从横排找(,在竖排中找到 FIRSTVT(B)，在交叉处填上<。在横排中找到，在竖排中国找到 FIRSTVT(A) 中的元素，在交叉处填上<
a b （ ） ，
a
b
（ < < < = <
）
， < < < <

  1. > 我们找到 Qa 形式的，有B),S, ，在竖排中找到),在横排中找到 LASTVT(B) 中的元素，在交叉处填上>, 在竖排找到, 在横排找到 LASTVT(S)，在交叉处填上>

    a b （ ） ，
    a > >
    b > >
    （ < < < = <
    ） > >
    ， < < < > <

  2. # < FIRSTVT(A) 横纵额外添加一列 (行)#

    a b （ ） ， #
    a > > >
    b > > >
    （ < < < = <
    ） > > >
    ， < < < > <
    # < < < < >

    # < FIRSTVT(S)

    # < FIRSTVT(A)

    # < FIRSTVT(B)

  3. LASTVTVT(A)>#

    LASTVTVT(S)>#

    LASTVTVT(A)>#

    LASTVTVT(B)>#

结果如下

a b （ ） ， #
a > > >
b > > >
（ < < < = <
） > > >
， < < < > <
# < < < < >

方法二

  1. 对于文法的开始符号 S，增加拓广文法 S1->#S#

  2. 找出所有非终结符，画出一下表格

    a b c … n #
    a
    b
    c
    …
    n
    #

  3. ＝ 找 aQb 形式的，a=b，横排找 a，竖排找 b

  4. < 找 aQ 形式的，a 与 FISRSTVT(Q) 的每个元素交叉处填<，a 为横排元素

  5. > 找 Qa 形式的，在竖排中找到 a，在横排中找到 LASTVT(Q) 中的元素，相交处填>

此方法不用额外判断#的优先级，在与其他的处理过程中，会一同处理

#复习资料