編譯原理文字題
Ⅰ 給力！2011年新年散分啦。高分求助編譯原理高手幫忙做幾道模擬題
三、（ 8 分）化簡文法 G[S] ：
S → ASe | BCaD | aD | AC
A → Cb | DBS
C → bC | d
B → Ac
D → Ad
化簡後： S → ASe|AC A → Cb C → bC | d
四、（ 12 分） 設 L í {a,b,c}* 是滿足下述條件的符號串構成的語言：
(1)若出現 a ，則其後至少緊跟兩個 c ；
(2)若出現 b ，其後至少緊跟一個 c 。
試構造識別 L 的最小化的 DFA ，並給出描述 L 的正規表達式。
答：DFA 如圖所示。相應的正規式為 (c|acc|bc)* 。
五、（ 12 分） 已給文法 G[S] ： S → SaP | Sf | P P → qbP | q
將 G[S] 改造成 LL （ 1 ）文法，並給出 LL （ 1 ）分析表。
答：改造後的文法： S → PS' S' → aPS'| fS' | e P → qP' P' → bP | e
各候選式的 FIRST 集，各非終結符的 FOLLOW 集為
產生式 FIRST 集 FOLLOW 集
S → PS' {q} {#}
S' → aPS'
→ fS'
→ e {a}
{f}
{ e } {#}
P → qP' {q} {a,f,#}
P' → bP
→ e {b}
{ e } {a,f,#}
LL(1) 分析表為
六、（ 12 分） 給定文法 G[S] ： S → Aa|dAb|Bb|dBa A → c B → c
構造文法 G[S] 的 LR （ 1 ）分析表。
分析表如下圖所示
七、（ 8 分） 將下面的條件語句表示成逆波蘭式和四元式序列：
if a>b then x:=a+b*c else x:=b-a;
答：（ 1 ）逆波蘭式：
,其中， BLE 表示汪或等於時的轉向指令； [ … ] 表示標號。
（ 2 ）四元式：
(1) ( j>, a, b, (3))
(2) ( j, , , (7) )
(3) ( *, b, c, T1)
(4) ( +, a, T1, T2)
(5) ( :=, T2, , x)
(6) ( j, , , (9))
(7) ( -, b, a, T3)
(8) ( :=, T3, , x)
(9) ( … … )
八、（ 8 分） 給定基本塊：
A:=3*5
B:=E+F
C:=A+12
D:=E+F
A:=D+12
C:=C+1
E:=E+F
假定出基本塊後，只有 A 、 C 、 E 是活躍的，給出用 DAG 圖完成優化後的代碼序列。
答：化簡後的的四元式序列為
A :=D+12
E :=E+F
C :=28
Ⅱ 編譯原理實驗題，求解！謝謝!
第一問：
state=0;
while(1)
{
switch(state)
{
case 0:
c=nextchar();
if(c=='a')
state=1;
else if(c=='b')
state=2
else
error();
break;
case 1:
c=nextchar();
if(c=='a')
state=3;
else if(c=='b')
state=2;
else
error();
break;
case 2:
c=nextchar();
if(c=='b')
state=3;
else if(c=='a')
state=1;
else
error();
break;
case 3:
c=nextchar();
if(c=='a'||c=='b')
state=3;
else
error();
if(end)
return 1;
break;
}
}
第二問
如果不是dfa，可用子集夠造法化為dfa.
Ⅲ 有幾道編譯原理的題目不知道怎麼做了,求教!
1 選A，*與+的區別在於*包含0
2 B
3 D ABb>Abb>abb
4 D
5 B 循環優化的三種重要技術是： 代碼外提；刪除歸納變數和強度削弱。
1 錯
2 對
Ⅳ 請教幾個有關編譯原理的習題！
答:
一
1. S -> aS | ε
2. S -> aS | Sb | ab
二
設 有字元串序列 abc, 而字元串 abc 符合是文法S.
abc 有兩種推導 ① S -> Ac, A -> bc
② S -> aB, B -> bc
有兩語法樹,二義文法
三
不好意思忘記了短語、直接短語和句柄
課本上應該有
Ⅳ 編譯原理文法題
DFA
如果能幫上你，望採納！
Ⅵ 關於編譯原理的問題
1.當然是機器語言了，如果是匯編指令，那還得編譯一次！能運行的程序都是機器語言，只有機器語言才能控制CPU，NET或Java這些中間語言，程序在運行時會被CLR或JVM快速編譯成機器語言，因此這些程序速度上有損失。
高級語言源代碼（文本）-通過編譯器（compiler）-程序（二進制機器語言）
匯編代碼（文本）-通過匯編器（assembler）-程序（二進制語言）
看到這里，你可能會想那匯編語言到底有什麼用呢，編譯器完全能代替匯編啊？
（1）.編譯器是通過高級語言（c,c++)轉到機器語言的。轉換過的機器語言受限與高級語言，效率和功能上都有限制。比如c不等過分操作內存。但通過匯編器轉化過來的機器語言，效率高，且用匯編語言，直接和CPU對話！
（2）.匯編可以反匯編（逆向編譯），而這里高級語言沒有發言權，就是：
程序（二進制機器語言）-通過反匯編器（compiler）-可轉化為匯編代碼（文本）
但永遠不能轉化為高級語言的源代碼，。
以上兩點匯編存在的重要性。
2。當然是說移植源代碼。windows用x86機器語言，蘋果用powerPC機器語言，windows程序當然不能運行在蘋果機上，因為程序其實就是一串機器語言！但windows上有c的編譯器（vc++），蘋果機上也有c編譯器（gcc），因此同一個c的源代碼，當然就可以通過不同平台的同一種編譯器實現平台移植。
3.當然是NASM，我看的所有書都首先說NASM，他是開源的，就像Linux一樣，很受歡迎，還有MASN是微軟的，borland的也有匯編器，不過都不常見了。
4.這跟CPU有關，一般32位x86兼容的cpu有許多寄存器，多數是32位的，也有16位的。比如CS,ES,DS這些segment寄存器一直是16位的。
5.優勢太多了，這和32位和16位存在的優勢一樣，16位電腦最大內存1MB，寄存器都是16位的。32位，最大內存可以有4GB，整整是16位的4096倍啊！16位多渺小啊，同理64位基本上也可以蔑視32位，64內存最大內存用TB來衡量，寄存器多數是64位！地址匯流排也是64位。64對32位沒有什麼優勢劣勢可言，64位完全就是32位的下一代。
Ⅶ (高分)編譯原理的題,求高手,在線等,急急急!!!!!!
太多了，大概看了下考點：
若源程序是用高級語言編寫的,目標程序是 機器語言程序或匯編程序 ,則其翻譯程序稱為編譯程序.
何謂優化？按所涉及的程序范圍可分為哪幾級優化？
答：優化：對程序進行各種等價變換，使得從變換後的程序出發，能產生更有效的目標代碼。
三種級別：局部優化、循環優化、全局優化。
簡述常用的優化技術有哪些？
答：編譯程序中常用的優化技術有：
（1） 刪除公共子表示式；
（2） 復寫傳播；
（3） 刪除無用代碼；
（4） 代碼外提；
（5） 強度削弱；
（6） 刪除歸納變數；
（7） 合並常量。
一個句型中的最左 B 稱為該句型的句柄。
可選項有：
A. 短語 B. 簡單短語 C. 素短語 D. 終結符號
.遞歸下降法不允許任一非終極符是直接 左 遞歸的。
簡單優先方法每次歸約當前句型的 句柄 ，算符優先方法每次歸約當前句型的 最左素短語 ，二者都是不斷移進輸入符號，直到符號棧頂出現 可歸約串 的尾，再向前找到 可歸約串 的頭，然後歸約。
算符優先文法——設有一不含ε產生式的算符文法G，如果對任意兩個終結符對a，b之間至多隻有 、 和 三種關系中的一種成立，則稱G是一個算符優先文法。
常用的中間語言種類有哪幾種？
答：有逆波蘭式、三地址代碼、抽象語法樹和DAG。
Ⅷ 編譯原理判斷題 設M是一個NFA,並且L(M)={x,y,z},則M的狀態數至少為4個 請問這句話為什麼是錯誤的呢
M的狀態數至少為4個，這句話不正確。
比如下圖，同樣符合題目條件，但狀態只有2個。
Ⅸ 編譯原理文法問題，急急急
第一題
S->AB
A->aA'b
A'->aA'b|ε
B->B'
B'->dB'|ε
----------------------
第二題
S->aS'b
S'->aS'b|D
D->dD|ε
----------------------
第三題
最左推導的話，我認為要先消除左遞歸才行（把左遞歸轉成右遞歸），消除之後:
N->DN'
N'->DN'|ε
D->0|1|2|...|9
最左推導為 N->DN'->2N'->2DN'->25N'->25DN'->258N'->258
規范推導(最右推導)為N->ND->N8->ND8->N58->D58->258
----------------------
第四題
構造一下語法樹就知道了。直接短語是深度為2的節點（根節點是深度0）。短語是深度為2的節點代入深度為1的產生式中。句柄是所有直接短語中最左的那個。
1.baaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
_______|
______a
直接短語為 Aa、a
短語為 Aaa
句柄為 Aa
2.bBaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
直接短語為 Aa、a
短語為 Aaa
句柄為 Aa
Ⅹ 計算機科學與技術中編譯原理簡答題
時間有點久記得不太真切，用通俗語言說，希望題主盡量查閱書籍參考資料自行驗證理解。
1、什麼是移進項目，什麼是規約項目
這個是自頂向下和自下向上分析時候用到的。所謂移進就是不處理，所謂規約就是處理，合並，替換。比如當前符合某個正規式左部，就用這個正規式右部替換左部，稱為規約。兩種操作的目的都是為了分析整體是否符合語法樹。
2、請給出生成C語言語句序列的文法（假定s表示任意一個語句，它為終結符）
關於這個，我感覺你描述的不是很清楚，因為C語言文法包含的正規式還是挺多的，如果單指statement的話，
statement_listà
statement
| statement_list statement
Statementà
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
再配合上相應的終結符。
3、能用上下文無關文法生成正規集嗎？為什麼？
可以。不過無法保證不含沖突。
4、計算first集和follow集對於構造自頂向下的語法分析器有什麼作用？
可以用來排除沖突。例如移進-移進沖突，移進-規約沖突。
5、是否可能存在這樣一個DFA，它的所有狀態都是接受狀態，包括其實狀態，為什麼？
這個愛莫能助，據我的構想是可以的，但是這樣的DFA最終都會成為單一狀態DFA。