編譯原理中的候選式
⑴ 關於LL(1)文法的編譯原理題目
判斷是不是LL(1)，首先看候選式的首字元有沒有相同的，第二判斷首字元迭代進去是否會構成左遞歸。
如果首字元不相同，也沒用左遞歸就說明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一個產生式中存在左遞歸:M->MaH
第二個產生式中存在首字元相同:H->b(M) ,
H->b
怎麼改呢？
對第一個產生式，消除左遞歸就是要變成右遞歸，把右邊剩下的符號提到前面:
M->aHM'
M'->aHM'
對第二個產生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'
H'->(M)|ε
⑵ 編譯原理問題--優先關系表怎麼畫
先求出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
⑶ 編譯原理中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
⑷ 編譯原理問題，高手進。
回答下列問題：(30分)
(6分)對於下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執行的輸出結果。
答： (1) 3 (2) 16 (3) 16 (每個值2分)
(6分)計算文法G(M)的每個非終結符的FIRST和FOLLOW集合，並判斷該文法是否是LL(1)的，請說明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |
解答：
計算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}
檢查文法的所有產生式，我們可以得到：
1. 該文法不含左遞歸，
2. 該文法中每一個非終結符M，T，B，D的各個產生式的候選首符集兩兩不相交。
3. 該文法的非終結符T、B和D，它們都有候選式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以該文法不是LL(1)文法。(2分)
(4分)考慮下面的屬性文法
產 生 式 語 義 規 則
S→ABC
A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
畫出字元串abc的語法樹;
對於該語法樹，假設S.u的初始值為5，屬性計算完成後，S.v的值為多少。
答：(1) (2分)
(2) S.v的值為18 (2分)
(4分)運行時的DISPLAY表的內容是什麼？它的作用是什麼？
答：DISPLAY表是嵌套層次顯示表。每當進入一個過程後，在建立它的活動記錄區的同時建立一張嵌套層次顯示表diaplay.假定現在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現行層、直接外層、…、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變數。
(5分)對下列四元式序列生成目標代碼：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本塊出口之後是活躍變數， R0和R1是可用寄存器。
答: 目標代碼序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H
(5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。
答：
逆波蘭式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象語法樹：(2分)
(8分)構造一個DFA，它接受={a，b}上所有包含ab的字元串。
答：
(2分)構造相應的正規式：(a|b)*ab(a|b)*
(3分)
a a
a b
b b
(3分)確定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a
a b b
b
最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}
(6分)寫一個文法使其語言為L(G)={anbncm| m,n≥1，n為奇數，m為偶數}。
答：
文法G(S):
(8分)對於文法G(S):
1. 寫出句型b(Ma)b的最右推導並畫出語法樹。
2. 寫出上述句型的短語，直接短語和句柄。
答：
1. (4分)
2. (4分)
短語: Ma)， (Ma)， b(Ma)b
直接短語: Ma)
句柄: Ma)
(12分)對文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 構造各非終結符的FIRSTVT和LASTVT集合;
(2) 構造算符優先表;
(3) 是算符優先文法嗎?
(4) 構造優先函數。
答：
(1) (4分)
(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >
(3) 是算符優先文法，因為任何兩個終結符之間至多隻有一種優先關系。 (1分)
(4) 優先函數(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3
(8分)設某語言的do-while語句的語法形式為
S do S(1) While E
其語義解釋為：
針對自下而上的語法分析器，按如下要求構造該語句的翻譯模式，將該語句翻譯成四元式：
(1) 寫出適合語法制導翻譯的產生式；
(2) 寫出每個產生式對應的語義動作。
答：(1). 適合語法制導翻譯的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }
UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }
SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }
答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}
(10分)將語句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻譯成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112
(10分)設有基本塊如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
畫出DAG圖；
設L，M，N 是出基本塊後的活躍變數，請給出優化後的四元式序列。
答：
1. (6分)
L
*
T2,M T4 T2,N
* - +
T1 T3
3 A B 12 C D
2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D
(8分)文法G(S)及其LR分析表如下，請給出串baba#的分析過程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步驟 狀態 符號 輸入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估計認識！！
⑸ 在編譯原理中： 文法S——>SS+|SS*|a能產生什麼語言，並驗證！ 求高人指導！
為了使問題簡化，我們考慮文法S->ss+|a，考慮s->ss*時，只要把+換成*即可。
0層遞歸是，s->a,文法的語言是{a}。是後綴表達式。
1層以內遞歸時，文法語言是{a,aa+}。是後綴表達式。
2層以內遞歸時，文法語言是{a,aa+}.{a,aa+}.{+}。其中.表示連接，是後綴表達式。
依此類推，多少層的遞歸都是後綴表達式。
把表達式的+換成*後依然為後綴表達式。
下面證明文法產生的語言是所有的以a為變數，以+和*為運算符的後綴表達式。
因為每個表達式都對應一個常規的表達式（如1*2+3就是常規表達式），下面只需證明語言能產生的後綴表達式對應所有的常規表達式。當常規表達式只有一個運算符，對應aa+或aa*。當常規表達式有兩個運算符，可寫成(表達式1）.{+|*}.(表達式2），因為表達式1和2都只含一個運算符，所以可以用語言表示，上述常規表達式可用後綴表達式（表達式1）.（表達式2）.{+l*}表示。所以不管常規表達式有多少個運算符，都可以由語言的後綴表達式對應。
⑹ 誰能夠解釋下編譯原理中什麼是FIRSTVT,和LASTVT，盡量淺顯易懂點謝謝
給你COPY一個看管用不,雖然不懂你在問什麼...
算符優先分析 [上一節] [下一節]
5.2.1 算符優先文法及其優先表構造
一個文法，如果它的任一產生式的右部都不含兩個相繼（並列）的非終結符，即不含如下形式的產生式右部：
…QR…
則我們稱該文法為算符文法。
在後面的定義中，a、b代表任意終結符；P、Q、R代表任意非終結符；『…』代表由終結符和非終結符組成的任意序列，包括空字。
假定G是一個不含e-產生式的算符文法。對於任何一對終結符a、b，我們說：
1. a�6�7b當且僅當文法G中含有形如P→…ab…或P→…aQb…的產生式；
2. a�6�3b當且僅當G中含有形如P→…aR…的產生式，而Rb…或RQb…；
3. a�6�4b當且僅當G中含有形如P→…Rb…的產生式，而R…a或R…aQ。
如果一個算符文法G中的任何終結符對（a，b）至多隻滿足下述三關系之一：
a�6�7b，a�6�3b， a�6�4b
則稱G是一個算符優先文法。
現在來研究從算符優先文法G構造優先關系表的演算法。
通過檢查G的每個產生式的每個候選式，可找出所有滿足a�6�7b的終結符對。為了找出所有滿足關系�6�3和�6�4的終結符對，我們首先需要對G的每個非終結符P構造兩個集合FIRSTVT（P）和LASTVT（P）：
FIRSTVT（P）＝{a | Pa…或PQa…，a�0�2VT而Q�0�2VN}
LASTVT（P）＝{a | P…a或P…aQ，a�0�2VT而Q�0�2VN}
5.2.2 算符優先分析演算法
所謂素短語是指這樣的一個短語，它至少含有一個終結符，並且，除它自身之外不再含任何更小的素短語。所謂最左素短語是指處於句型最左邊的那個素短語。如上例，P*P和i是句型P*P+i的素短語，而P*P是它的最左素短語。
現在考慮算符優先文法，我們把句型（括在兩個＃之間）的一般形式寫成：
#N1a1N2a2…NnanNn+1# (5.4)
其中，每個ai都是終結符，Ni是可有可無的非終結符。換言之，句型中含有n個終結符，任何兩個終結符之間頂多隻有一個非終結符。必須記住，任何算符文法的句型都具有這種形式。我們可以證明如下定理（證明留給有興趣的讀者作練習）：
一個算符優先文法G的任何句型（5.4）的最左素短語是滿足如下條件的最左子串Njaj…NiaiNi+1，
aj-1�6�3aj
aj�6�7 aj+1，…，ai-1�6�7ai
ai�6�4ai+1
根據這個定理，下面我們討論算符優先分析演算法。為了和定理的敘述相適應，我們現在僅使用一個符號棧S，既用它寄存終結符，也用它寄存非終結符。下面的分析演算法是直接根據這個定理構造出來的，其中k代表符號棧S的使用深度。
5.2.3 優先函數
在實際實現算符優先分析演算法時，一般不用表5.1這樣的優先表，而是用兩個優先函數f和g。我們把每個終結符q與兩個自然數f（q）和g（q）相對應，使得
若q1�6�3q2 則 f（q1）<g（q2）
若q1�6�7q2 則 f（q1）= g（q2） （5.5）
若q1�6�4q2 則 f（q1）>g（q2）
函數f稱為入棧優先函數，g稱為比較優先函數。使用優先函數有兩方面的優點：便於作比較運算，並且節省存儲空間，因為優先關系表佔用的存儲量比較大。其缺點是，原先不存在優先關系的兩個終結符，由於與自然數相對應，變成可比較的了。因而，可能會掩蓋輸入串的某些錯誤。但是，我們可以通過檢查棧頂符號q和輸入符號a的具體內容來發現那些原先不可比較的情形。
如果優先函數存在，那麼，從優先表構造優先函數的一個簡單方法是：
1. 對於每個終結符a（包括＃）令其對應兩個符號fa和ga，畫一張以所有符號fa和ga為結點的方向圖，如果a �6�4�6�7b，那麼，就從fa畫一箭弧至gb；如果a�6�3�6�7b，就畫一條從gb到fa的箭弧。
⑺ 編譯原理
編譯原理)：利用編譯程序從源語言編寫的源程序產生目標程序的過程； 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。
編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；語義檢查和中間代碼生成
(7)編譯原理中的候選式擴展閱讀：
編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。
編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。
而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。
⑻ 編譯原理的LL（1）文法是什麼意思
1.文法不含左遞歸，沒有公共左因子
2.對於文法中的每個非終結符A的產生式的候選首符集兩兩不相交。
3.對於文法中的每個非終結符A，它存在某個候選首符集包括ε，則FIRST（A）∩FOLLOW（A）=空
滿足以上條件的文法為LL（1）文法