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）)加進去。