firstvt编译原理

A. 编译原理问题--优先关系表怎么画

先求出FIRSTVT和LASTVT。

找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现：

A->a.......，即以终结符开头，该终结符入Firstvt

A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt

A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现：

A->.......a，即以终结符结尾，该终结符入Lastvt

A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt

A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt

然后逐条扫描文法规则。例题如下，参考这个例题能很好地理解如何构造优先关系表。

《编译原理》(第4版)第三章例题4.12

B. 关于编译原理first follow 和select

首先要明白这三个集的作用和用途，知道了他们是用来做什么的之后，理解起来就简单一些
First（A）集的作用是标示在替换非终结符A的时候，替换后的文法的首字母集合，语法分析程序根据这个来判断给定的语言是否是合法的，是符合规则的。
Follow（A）的作用是标示那些可以出现在A之后的字符，语法分析程序根据这个，在A可以被替换为e（空）的时候来进行判断，看当前的文法是否是合法的。
这里简单说明下，比如A->b,A->e(空) 当给定的语言是 bXXXXX的时候，根据第一句文法就可以判定句子合法，但是如果给的语言是cXXXXX的时候，因为A->可以替换为空，这时候就需要一句A的follow集来进行判断，若A的follow集里面含有c 则语言是合法的
Select集的作用是将first集和follow集进行合并，如果两个文法的左端都是A，若他们的select集交集为空，表明他们是两个无关的，不会产生不确定性的文法，反之，则表明文法不是LL(1)文法
计算的公式很繁杂，理解了意思之后，看就能看出来。。。。

C. 编译原理follow集与first集的计算

下面我将介绍一下我关于LL（1）文法部分的计算文法非终结符First集以及Follow集两个知识点的理解。

首先是First集的计算部分，计算First集首先看我们原文法的左边，原文法左边不重复的都要进行First集的计算，计算时具体有以下三种情况：

（1）先看产生式后面的第一个符号，如果是终结符，那就可以直接把它写到这个产生式的First集中，例如：产生式为M->nDc,那在First集中我们就可以直接写上First (M)={ n }；

（2）如果产生式后面的第一个符号是非终结符，就看这个非终结符的产生式，看的时候同样利用前面的两种看法；但是当产生式为ε时，则需要把ε带入到待求First集的元素的产生式中再判断。例如：A->Bc； B->aM；B->ε，求First(A)时，我们看到A的第一个产生式中的第一个符号是B，B是一个非终结符，所以我们就要接着看B的产生式，B的第一个产生式的第一个符号为a，a是一个终结符，直接把a写入First(A)，B的第二个产生式为ε，把ε带入A->Bc中，A->c(注意：如果将B->ε带入表达式后A的产生式为A->ε，ε不可以忽略)，c是终结符，所以把c也写入First(A)，最后First (A)={ a，c }。

（3）当产生式右边全为非终结符，且两个非终结符又都可以推出ε时，我们需要把这个产生式的所有情况都列出来，再分析。例如：A->BC;B->b|ε;C->c|ε。我们把A的所有产生式利用上述两种方法列出来就是A->bc,A->b;A->c,A->ε;最后First (A)={b,c, ε}。

接下来介绍一下Follow集的部分，先简单介绍一下计算Follow集的大致规则。比如我们要求Follow(X)，文法中多个产生式中含有X，则需要考虑多种情况，以下是具体计算时的三种情况：

（1）文法开始符：所有文法开始符的Follow集中都有一个#。

（2）S->αB的形式：求Follow(B)，因为B的后面为空，把Follow(S)写入B的Follow集中。

（3）S->αBβ的形式：求Follow(B)，B后部不为空。

①当β是终结符时，直接把β写入Follow(B)。

②当β是非终结符时，将First (β)（如果First(B)中有ε，就把ε删掉）写入Follow(B)中。（需要注意的是：如果β->ε，那么原产生式就变成了S->αB,也就是第二种情况，这两种情况都要算在Follow(B)中）。

D. 【编译原理】第四章：语法分析

从分析树的根节点到叶节点方向构造分析树。
即从开始符号S推导出词串w的过程。

例：

总是选择每个句型的 最左非终结符 进行替换。

总是选择每个句型的 最右非终结符 进行替换。

在自底向上的分析中，总是采用 最左规约 的方式，因此把 最左规约 称为 规范规约 ，对应的 最右推导 称为 规范推导 。

最左推导、最右推导具有唯一性。

自顶向下的语法分析采用最左推导方试，总是选择每个句型的 最左非终结符 进行替换。

由一组 过程 组成，每一个过程对应一个 非终结符 。
从文法开始符号S开始，递归调用文法中的其他非终结符，最终扫描整个输入串，完成分析。

如果其间有不唯一的产生式，就可能需要退回上一步重新尝试的情况，称为 回溯 。

预测分析 是 递归下降分析 技术的一个特例，通过输入中向前看固定个数的符号选择正确的产生式。
如果一个文法可以构造出向前看k个符号的预测分析器，称为LL(k)文法 。

预测分析不需要回溯，具有确定性。

含有 形式产生式的文法称为是 直接左递归 的。
如果一个文法中有一个非终结符A使得对某个串存在推导 ，那么这个文法是 左递归 的。其中，经过两步或以上推导产生的左递归，称为 间接左递归 的。
左递归会使递归下降分析器陷入无限循环。

文法
即
该文法是直接左递归的，会陷入无限循环。

将以上文法转换为：


即可消除左递归。事实上，这个过程把左递归转换成了右递归。

消除直接左递归的一般形式

使用代入法。

对于一个文法，通过改写产生式来 推迟决定 ，等获得足够多的输入信息再做正确的决定。

例：文法：

可以改写为：

从文法的开始符号S开始，每一步推导根据当前句型的最左非终结符A和当前输入符号α，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

S_文法（简单的确定型文法）

可能在某个举行中紧跟在A后面的终结符a的集合，记为 FOLLOW(A) 。
如果A是某个句型的最右符号，则将结束符“ $ ”添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符号串α串首终结符的集合，记作 FIRST(A) 。

E. 编译原理计算first 集和follow集的简单方法 S->bBS' S'->aAS'|ε A->aB|c B->dB' B'->bB'|ε 求计算过程

first ： S'=a,ε
S=b
A=a,c
B=d
B'=b,ε
follow: S'=#
S=#
A=a
B=a
B'=a

F. 编译原理关于FIRST,FLLOW的问题。

求FIRST,FLLOW集合的过程是一个递归过程．．描述出来很繁琐的，
我打字慢．．．．．．

编译原理书上有算法的描述的．．你自己理解一下，不难的．．．
不懂的地方最好问身边的同学或老师．．．当面讲解比较清楚一点．

给你个例子吧：
文法：
E->E+T|T
T->T*F|F
F->(E)|i
按照求文法FIRST,FLLOW的算法，FIRST(E)过程大概是：
1.FIRST(E)=FIRST(E) U FIRST(T) //E,T都是非终结符，所以
继续求First

2.FIRST(T)=FIRST(T) U FIRST(F)//F,T都是非终结符，所以
继续求First

3.FIRST(F)={(,i} //(,i是终结符，得出最后结果．

FIRST(E)={(,i}．．

FIRST懂了的话，看FLLOW的算法也就好懂了．．．

还有什么问题的话．．．可以发消息给我．．

G. 谁能够解释下编译原理中什么是FIRSTVT,和LASTVT，尽量浅显易懂点谢谢

Firstvt和Lastvt是为了画算符优先关系表的（就是表里面填优先大于小于等于的那个）。
然后要注意他们可都是终结符的集合。
Firstvt
找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现：
A->a.......，即以终结符开头，该终结符入Firstvt
A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt
A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

Lastvt
找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现：
A->.......a，即以终结符结尾，该终结符入Lastvt
A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt
A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Firstvt

H. 编译原理搜索符的问题

从初态开始，（S':=.S，# ） ，初态的核心项目的搜索符为#号，这是定的，然后扩充初态，就是把所有的（S:=. αβ，# ）加进去，若α为一个非终结符，假设为A，则把（A：= .γ）加进去，A：= .γ的搜索符为誉漏凯 FIRST（β#），就是说若β为空，则为原来S的搜索符，若β不为空，则为β的首终结符。继续扩γ，一庆唤直到初态不搜坦能扩充为止。goto时，核心项目的搜索符是继承过来的。
例子，若某状态的核心项目为(A：=α.Bβ,a),则把项目(B:= .γ,FIRST（βa）)加进去。