編譯原理action表的順序

1. 編譯原理項目集規范族問題GO(I,X)中的X是安什麼順序進行測試的

這個問題本身不太准確。

GO(I,X)是一個轉換函數，它的定義如下：

GO(I,X)中的X是一個文法符號，可以是終結符或非終結符，CLOSURE(J)是J的閉包函數，閉包函數的定義就不多說了。

問題「GO(I,X)中的X是按什麼順序進行測試」，是否可解釋成「X是按出現在產生式中的順序進行測試」

2. 編譯原理詞法分析實驗中， 文件寫入順序的問題(fputs)

1)fopen在代碼中出現2次，沒有必要

2）你的程序不對 你搞混和S這個字元和TOKEN。

你的第一個WHILE讀入的是字元S，而TOKEN是由若干字元S構成的。而你的SWITCH(S)裡面按理應該是組成TOKEN的規則，而你直接就輸出了。這樣如果你要結果，我給你改了下，你看下：

int main()
{
char token[20] = {''};
char s;
char strings[10] = "(34,_)";
struct _iobuf* fp_cifa;
int i = 0, j;
strings[6] = ' '
strings[7] = ''
//fp_cifa = fopen(「D:\cifa.txt "a+");

while((size_t)i != strlen(file))
{
for(j = 0; j < 20; j++)
{
token[j] = ''
}
s = file[i++];
while(s == ' ' || s == ' ')
{
s = file[i++];
}
switch(s)
{
caseƇ':
token[0]=s;
token[1]=''
digitprint(token, value_num, num_list);
break;
case'=':
token[0]=s;
token[1]=''
digitprint(token, value_num, num_list);
//fputs(strings, fp_cifa);
break;
default:
cout<<"error"<<endl;
}
}
//fclose(fp_cifa);
return 0;
}

• void digitprint(char* a, int& value_num_, char num_list[100][20])//a是需要評定的字元串//num在符號表中的位置，需要轉化為字元串然後輸入到文件中
  {
  FILE* fp_cifa;
  char c[20] = "(34,01)";
  fp_cifa = fopen("D:\cifa.txt ", "a+");
  //fputs(c, fp_cifa);
  fputs(a,fp_cifa);//這里要顯示 a 而不是c 你可以把a 拼到 c然後，再顯示c
  fclose(fp_cifa);
  }

3. 編譯原理——LR分析表

自底向上的語法分析

LR分析表的結構如上，其分為兩個部分 Action Goto

兩個參數狀態i，終結符號a（s(i)代表第i個狀態，r(i)代表第i條表達式）

Goto[i,A]=j

文法

容易得知這個文法可以推出 0 1 00 01 等的字元串。因為它是 左遞歸 。不適用於 LL 文法分析，只能使用 LR 分析。

因為本題入口有兩個—— S → L·L S → L ，所以需要構造額外的產生式 S'->S

2.1 第一次遍歷

我們從 [S -> . L·L] 開始，構造這個狀態的閉包，也就是加上所有能從這個產生式推出的表項。

首先，判斷 . 後面是否為 非終結符號A 。如果是，那我們就得找所有由 A-> 推出的產生式，並將它們添加進入 閉包 里(也就是State包里)。循環做即可。

因此我們可以得到 State 0 有

下一步，就是我的 . 往下一位移動。對每個符號X後有個 . 的項，都可以從 State 0 過渡到其他狀態。

由以上6條式子可以得知下一位符號可以是 S L B 0 1 。所以自然可以得到5個狀態。

State 1 是由 State 0 通過 S 轉移到這里的，所以我們找出所有 State 0 中在 S 前有 . 的項。

此狀態作為結束狀態 Accept ，不需要繼續狀態轉移了。

State 2 是由 State 0 通過 L 轉移到這里的，所以我們找出所有 State 0 中在 L 前有 . 的項。

S -> . L·L S -> . L L -> . LB

有3條式子，現在我們將 . 向後推一格，就得到 State 1 的項了。

但是 . 之後的符號分別是 · $ B ， B 為非終結符號，我們得包含 B -> 的項

State 3 是由 State 0 通過 B 轉移到這里的，所以我們找出所有 State 0 中在 B 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

State 4 是由 State 0 通過 0 轉移到這里的，所以我們找出所有 State 0 中在 0 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

很簡單，同樣的道理找 State 5

State 5 是由 State 0 通過 1 轉移到這里的，所以我們找出所有 State 0 中在 1 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

好的，現在我們第一次遍歷完成。

2.2 第二次遍歷

第二次遍歷自然從 State 2 開始。

我們回到 State2 ，可以看出 . 之後的符號有 · B 0 1 。

State 6 是由 State 2 通過 · 轉移到這里的，所以我們找出所有 State 2 中在 · 前有 . 的項。

S -> L. ·L 只有1條，我們往後移發現 L 又為非終結符號，參考 State 0 做的操作，我們得找出所有的式子。

共有5條式子，共同組成 State 6 ，由上面的式子可以看出我們還得繼續下一次遍歷。先不管著，我們進行下一次狀態查找。

State 7 是由 State 2 通過 B 轉移到這里的，所以我們找出所有 State 2 中在 B 前有 . 的項。

L -> L. B 也是只有1條，我們往後移發現沒有非終結符號了，那就不需要再繼續添加其他式子了。

這個狀態也不需要繼續進行轉移了。

接下來很關鍵，因為我們通過 State2 的 . 後的符號找出了 State 6 State 7 ，接下來還差符號 0 1 ，那麼是否像之前一樣按例添加狀態呢， 答案是不是的 ，因為我們發現通過 0 1 找到的閉包集分別是 B -> 0 B -> 1 ，這與我們的之前的 State 4 State 5 相同。所以我們得將其整合起來，相當於 State 2 通過 0 1 符號找到了 State 4 State 5 狀態。

2.3 第三次遍歷

回頭看第二次遍歷，可以看出只有 State 6 可以進行狀態轉移了。

那麼就將 State 6 作為第三次遍歷的源頭，可以看出 . 之後的符號有 L B 0 1 。

State 8 是由 State 6 通過 L 轉移到這里的，所以我們找出所有 State 6 在 L 前有 . 的項。

S -> L· .L L -> . LB 有兩條式子，往後移發現有非終結符號 B ，所以經過整合可以得到

可以看出 . 的後面還有一個符號，所以這里我們還得再進行一次遍歷。

接下來，又是遇到重復的包的情況，可以看出我們由 State 6 通過 B 0 1 得到的閉包分別是 L->B B->0 B->1 ，很明顯，這分別對應於 State 3 State 4 State 5 。

第三次遍歷也就結束了。

2.4 第四次遍歷

回看第三次遍歷，可以看出只有 State 8 可以進行狀態轉移，其 . 之後的符號分別是 B 0 1 。

誒，感覺很熟悉，就是上面幾行剛說的情況，也就是說通過這三個符號找到的閉包是我們之前遇到的狀態，分別是 State 3 State 4 State 5 。

做到這里，我們發現我們已經全部遍歷完畢！

總共有8個狀態，通過以上流程做成個圖是什麼樣子的？來看看！

這么一看就很清晰明了了，我們就可以通過這個圖做出我們的 LR分析表

其實就是我們之前呈現的表

在狀態 I2 和 I8 中，既有 移入 項目，也有 規約 項目，存在 移入 - 規約的沖突 ，所以不是 LR(0) 文法，但是因為 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解決沖突，所以該文法是 SLR(1) 文法。

上表我們發現還有 r1，r2，r3 等。這個其實就是代表狀態停止轉移時為 第幾條表達式 ，r3代表第三條表達式 L -> LB 。

當我們構建了表之後，我們如何運用起來呢？

下面我們通過一個例子來說明

以上字元串是如何被SLR分析器識別的呢？

4. 有關編譯原理

⑴拓廣文法 1 分
G[S ′ ]: S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA ：

⑵ 該文法的 LR(0) 分析表：
狀態 ACTION GOTO
a b # S A
0 S 2 1
1 S 3 acc
2 r 3 r 3 r 3
3 S 5 4
4 r 2 r 2 /S 6 r 2
5 r 5 r 5 r 5
6 S 2 7
7 r 4 /S 3 r 4 r 4
⑶ LR(0) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中沒有沖突狀態。
該文法不是 LR(0) 文法
因為存在沖突狀態： I 4 和 I 7
⑷ SLR(1) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中有沖突狀態，沖突可用 FOLLOW 集解決。
該文法不是 SLR(1) 文法。
因為 FOLLOW(S)={a,b,#} ，所以無法解決沖突

5. [高分,急!]編譯原理LR(1)分析表題目

I0： S->.T,# T->.T(T),#
I1: S->T.,# T->T.(T),#
I2: S->T(.T),# T->.T(T),) T->.ε,)
I3: S->T(T.),# T->T.(T),)

(1,() 是s2
(1,#) 是acc (就是接受)
T下1 是1
T下3 是3

6. 編譯原理問題，高手進。

回答下列問題：(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
哈哈，估計認識！！

7. 編譯原理 有文法G（S）這道題怎麼做

首先擴展文法為：

1)S1->S

2)S->aS

3)S->bS

4)S->a

則：

I0=Closure({S1->.S})={S1->.S,S->.aS,S->.bS,S->.a}

go(I0,S)=Closure({S1->S.})={S1->S.}=I1

go(I0,a)=Closure({S->a.S,S->a.})={S->a.S,S->.aS,S->.bS,S->.a,S->a.}=I2

go(I0,b)=Closure({S->b.S})={S->b.S,S->.aS,S->.bS,S->.a}=I3

go(I2,S)=closure({S->aS.})={S->aS.}=I4

go(I2,a)=Closure({S->a.S,S->a.})=I2

go(I2,b)=Closure({S->b.S})=I3

go(I3,S)=Closure({S->bS.})={S->bS.}=I5

go(I3,a)=Closure({S->a.S,S->a.})=I2

go(I3,b)=Closure({S->b.S})=I3

由圖所示，狀態I2,既有歸約項目(S->a.)又有移近項目(S->.aS,S->.bS,S->.a)，產生沖突。當用SRL分析法時，需向前看一步，即求出：

Follow(S)=Follow(S1)={#}

則，Follow(S)∩{a,b}=∮

故而Action(I2,a)=s2

Action(I2,b)=s3

Action(I2,#)=r4

則構造出srl分析表如下所示：

ActionGoto

ab# S

I0 s2s3 1

I1 acc

I2s2s3 r4 4

I3s2s3 5

I4 r2r2r2

I5 r3r3 r3