編譯原理四元式咋寫
財富算神馬?10000分能值一塊錢么?你喊給100RMB,看看有多少人會給你回
② 請將表達式a *(b+c) - d * (b+c) 後綴式 三元式 間接三元式 四元式.
B 這個這樣分析 ((a*(b+c))-d) => (a*(b+c)),d,- => a,(b+c),*,d,- => a,b,c,+,*,d,-
③ 編譯原理 把下面程序段翻譯成四元式序列
四元式類似於三地址指令:波蘭式。
0:(=,M,—,A); 簡單賦值表達式翻譯:a = m;
1:(=,N,—,B); B=N;
2:(<,A,B,4) ; 控制語句翻譯 :IF A<B GOTO 4;
3:(jump,—,—,6); 直接轉移語句;JUMP TO 6;
4:(=,N,—,T); T=N;
5:(jump,—,—,7) jump to 7;
6:(=,M,—,T) T=M;
7:(=,T,—,C). C=T;
④ 編譯原理用C++生成四元式的程序,如果把生成四元式當成一個類來寫,那這個類應該有哪些函數
四元式的四個組成成分是:算符op,第一和第二運算對象ARG1和ARG@及運算結果RESULT。
你所有的事情也都是圍繞這四個東東來做呀,間接地就是生成「三地址指令」或是轉換成「語句」(例如 if B rop C goto L)之類的。
⑤ 編譯原理問題,高手進。
回答下列問題:(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
哈哈,估計認識!!
⑥ 為什麼要採用中間代碼中間代碼有哪幾種形式(編譯原理)
採用中間代碼是把源程序映射成中間代碼表示,再映射成目標代碼的工作分在幾個階段進行,使編譯演算法更加清晰。中間代碼有四種形式:
1、逆波蘭表示
逆波蘭表示又稱後綴表示法,它是最簡單的一種中間代碼表示形式,早在編譯程序出現之前,它就用於表示算術表達式。
2、四元式
四元式也是一種比較普遍採用的中間代碼形式,
其形式為:(OP,ARG1,ARG2,RESULT)
3、三元式
三元式表示是與四元式類似的一種表示法,所不同的僅是三元式中沒有表示運算結果的部分,凡要涉及到運算結果的均用三元式的位置或序號來代替。
4、樹表示
樹形表示是三元式的翻版。在樹的表示中,樹葉均為運算對象,即常量或變數,其他結點表示運算符。表達式的樹形表示很容易實現:簡單變數或常量的樹就是該變數或常量自身。
(6)編譯原理四元式咋寫擴展閱讀
中間語言的優點:
1、中間語言與具體機器特性無關,一種中間語言可以為生成多種不同型號的目標機的目標代碼服務。
2、可對中間語言進行與機器無關的優化,有利於提高目標代碼的質量。
對於中間語言,要求其不但與機器無關,而且有利於代碼生成。
⑦ 編譯原理 四元式
四元式是一種比較普遍採用的中間代碼形式。
代碼段的四元式表達式:
101 T:=0 (表達式為假的出口)
103 T:=1 (表達式為真的出口)
因為用戶的表達式只有一個A<B,因此A<B的真假出口就是表達式的真假出口,所以
100: if a<b goto 103 (a<b為真,跳到真出口103)
101: T:=0(否則,進入假出口)
102: goto 104 (要跳過真出口,否則T的值不就又進入真出口了,為真)
103: T:=1
104:(程序繼續執行)
(7)編譯原理四元式咋寫擴展閱讀:
四元式是一種更接近目標代碼的中間代碼形式。由於這種形式的中間代碼便於優化處理,因此,在目前許多編譯程序中得到了廣泛的應用。
四元式實際上是一種「三地址語句」的等價表示。它的一般形式為:
(op,arg1,arg2,result)
其中, op為一個二元 (也可是一元或零元)運算符;arg1,arg2分別為它的兩個運算 (或操作)對象,它們可以是變數、常數或系統定義的臨時變數名;運算的結果將放入result中。四元式還可寫為類似於PASCAL語言賦值語句的形式:
result ∶= arg1 op arg2
需要指出的是,每個四元式只能有一個運算符,所以,一個復雜的表達式須由多個四元式構成的序列來表示。例如,表達式A+B*C可寫為序列
T1∶=B*C
T2∶=A+T1
其中,T1,T2是編譯系統所產生的臨時變數名。當op為一元、零元運算符 (如無條件轉移)時,arg2甚至arg1應預設,即result∶=op arg1或 op result ;對應的一般形式為:
(op,arg1,,result)
或
(op,,,result)
⑧ 編譯原理寫出語句 if(a<b)then x:=y z;else x:=y-z ;的四元式表示
(100) if a<b goto (102)
(101) goto (105)
(102) t:=y+z //若不是+,需要進行相應修改
(103) x:=t
(104) goto (107)
(105) t:=y-z
(106) x:=t
(107)…
註: 原題if(a<b)then x:=y z,y和z之間的運算符沒給出,四元式中寫成了+,若是其他運算符進行相應修改即可
⑨ 編譯原理中 文法 文法G定義為四元組(Vn ,Vt,P,S)這4個是什麼意思 另外 終結符和非終結符是什麼意思
文法G是一個四元式(Vt,Vn,S,P)
其中Vt是一個非空有限集,它的每個元素稱為終結符號
Vn是一個非空有限集,它的每個元素稱為非終結符號(Vt和Vn的交集為空)
S是一個非終結符號,稱為開始符號
P是一個產生式集合(有限),每個產生式的形式是P-->a
開始S必須在某個產生式的左部出現一次
終結符指組成語言的基本符號(如基本字、標識符、常數、算符、界符)
非終結符號(也稱語法變數)表示一定符號串的集合。
你看到小寫字母一般是終結符,大寫字母肯定是非終結符
不明白可以聯系。
⑩ 編譯原理 四元式問題,a
好,我來幫你理解一下,先看基本知識:
四元式是一種比較普遍採用的中間代碼啟余形式.四元式的四個組成成分是:算符op,第一和第二運算對象ARG1和ARG@及運算結果RESULT.運算對象和運算結果有時指用戶自己姿兄定義的變數,有時指編譯程序引進的臨時變數.例如a∶=b*c+b*d的四元式表示如下:
(1)(*,b,c,t1)
(2)(*,b,d,t2)
(3)(+,t1,t2,t3)
(4)(∶=,t3,-,a)
四元式和三元式的主要不同在於,四元式對中間結果的引用必須通過給定的名字,而三元式是通過產生中間結果的三元式編號.也就是說,四元式之間的聯系是通過臨時變數實現的.
有時,為了更直觀,也把四元式的形式寫成簡單賦值形式或更易理解的形式.比如把上述四元式序列寫成:
(1)t1∶=b*c
(2)t2∶=b*d
(3)t3∶=t1+t2
(4)a∶=t3
把(jump,-,-,L)寫成goto L
把(jrop,B,C,L)寫成if B rop C goto L
好,下面分析一下a,6,
jjttll 舉報
״̬ô
Ƚ跡旁襲ϼ,