編譯原理回溯的定義

① 編譯原理

編譯原理)：利用編譯程序從源語言編寫的源程序產生目標程序的過程； 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。

編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；語義檢查和中間代碼生成

(1)編譯原理回溯的定義擴展閱讀：

編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。

編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。

而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。

② 編譯原理的定義是什麼

編譯原理，說得通俗易懂一些就是：讓機器通過某種機制和規則，將一種由人們書寫的高級程序代碼，經過若干步驟，最終翻譯成機器可理解執行的二進制代碼。
編譯原理技術的具體應用，例如：
（1）、我們用戶通常編寫的 C/C++ 程序源代碼（*.C/*.CPP），通過 Microsoft Visual C++ 編譯器，將由人工書寫的 C/C++ 語言程序源代碼（*.C/*.CPP），最終翻譯成機器可執行的二進制代碼（*.EXE）；
（2）、人工智慧領域中的自然語言處理、機器翻譯技術（例如：英/漢翻譯、日/漢翻譯系統等）等，都需要使用到編譯原理技術。

③ 編譯原理-LL1文法詳細講解

我們知道2型文法( CFG )，它的每個產生式類型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一個表達式的文法:

最終推導出 id + (id + id) 的句子，那麼它的推導過程就會構成一顆樹，即 CFG 分析樹：

從分析樹可以看出，我們從文法開始符號起，不斷地利用產生式的右部替換產生式左部的非終結符，最終推導出我們想要的句子。這種方式我們稱為自頂向下分析法。

從文法開始符號起，不斷用非終結符的候選式(即產生式)替換當前句型中的非終結符，最終得到相應的句子。
在每一步推導過程中，我們需要做兩個選擇:

因為一個句型中，可能存在多個非終結符，我們就不確定選擇那一個非終結符進行替換。
對於這種情況，我們就需要做強制規定，每次都選擇句型中第一個非終結符進行替換(或者每次都選擇句型中最後一個非終結符進行替換)。

自頂向下的語法分析採用最左推導方式，即總是選擇每個句型的最左非終結符進行替換。

最終的結果是要推導出一個特定句子(例如 id + (id + id) )。
我們將特定句子看成一個輸入字元串，而每一個非終結符對應一個處理方法，這個處理方法用來匹配輸入字元串的部分，演算法如下:

方法解析:

這種方式稱為遞歸下降分析( Recursive-Descent Parsing )：

當選擇的候選式不正確，就需要回溯( backtracking )，重新選擇候選式，進行下一次嘗試匹配。因為要不斷的回溯，導致分析效率比較低。

這種方式叫做預測分析( Predictive Parsing )：

要實現預測分析，我們必須保證從文法開始符號起，每一個推導過程中，當前句型最左非終結符 A 對於當前輸入字元 a ,只能得到唯一的 A 候選式。

根據上面的解決方法，我們首先想到，如果非終結符 A 的候選式只有一個以終結符 a 開頭候選式不就行了么。
進而我們可以得出，如果一個非終結符 A ，它的候選式都是以終結符開頭，並且這些終結符都各不相同，那麼本身就符合預測分析了。

這就是S_文法，滿足下面兩個條件:

例子:

這就是一個典型的S_文法，它的每一個非終結符遇到任一終結符得到候選式是確定的。如 S -> aA | bAB , 只有遇到終結符 a 和 b 的時候，才能返回 S 的候選式，遇到其他終結符時，直接報錯，匹配不成功。

雖然S_文法可以實現預測分析，但是從它的定義上看，S_文法不支持空產生式(ε產生式)，極大地限制了它的應用。

什麼是空產生式(ε產生式)？

例子

這里 A 有了空產生式，那麼 S 的產生式組 S -> aA | bAB ，就可以是 a | bB ,這樣 a , bb , bc 就變成這個文法 G 的新句子了。

根據預測分析的定義，非終結符對於任一終結符得到的產生式是確定的，要麼能獲取唯一的產生式，要麼不匹配直接報錯。

那麼空產生式何時被選擇呢？

由此可以引入非終結符 A 的後繼符號集的概念:
定義: 由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符 a 的集合，就是這個非終結符 A 的後繼符號集，記為 FOLLOW(A) 。

因此對於 A -> ε 空產生式，只要遇到非終結符 A 的後繼符號集中的字元，可以選擇這個空產生式。
那麼對於 A -> a 這樣的產生式，只要遇到終結符 a 就可以選擇了。

由此我們引入的產生式可選集概念:
定義: 在進行推導時，選用非終結符 A 一個產生式 A→β 對應的輸入符號的集合，記為 SELECT(A→β)

因為預測分析要求非終結符 A 對於輸入字元 a ,只能得到唯一的 A 候選式。
那麼對於一個文法 G 的所有產生式組，要求有相同左部的產生式，它們的可選集不相交。

在 S_文法基礎上，我們允許有空產生式，但是要做限制:

將上面例子中的文法改造:

但是q_文法的產生式不能是非終結符打頭，這就限制了其應用，因此引入LL(1)文法。

LL(1)文法允許產生式的右部首字元是非終結符，那麼怎麼得到這個產生式可選集。
我們知道對於產生式:

定義: 給定一個文法符號串 α ， α 的 串首終結符集 FIRST(α) 被定義為可以從 α 推導出的所有串首終結符構成的集合。

定義已經了解清楚了，那麼該如何求呢？
例如一個文法符號串 BCDe , 其中 B C D 都是非終結符， e 是終結符。

因此對於一個文法符號串 X1X2 … Xn ，求解 串首終結符集 FIRST(X1X2 … Xn) 演算法:

但是這里有一個關鍵點，如何求非終結符的串首終結符集？

因此對於一個非終結符 A , 求解 串首終結符集 FIRST(A) 演算法:

這里大家可能有個疑惑，怎麼能將 FIRST(Bβ) 添加到 FIRST(A) 中，如果問文法符號串 Bβ 中包含非終結符 A ，就產生了循環調用的情況，該怎麼辦?

對於 串首終結符集 ，我想大家疑惑的點就是，串首終結符集到底是針對 文法符號串 的，還是針對 非終結符 的，這個容易弄混。
其實我們應該知道， 非終結符 本身就屬於一個特殊的 文法符號串 。
而求解 文法符號串 的串首終結符集，其實就是要知道文法符號串中每個字元的串首終結符集:

上面章節我們知道了，對於非終結符 A 的 後繼符號集 :
就是由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符的集合，記為 FOLLOW(A) 。

仔細想一下，什麼樣的終結符可以出現在非終結符 A 後面，應該是在產生式中就位於 A 後面的終結符。例如 S -> Aa ，那麼終結符 a 肯定屬於 FOLLOW(A) 。

因此求非終結符 A 的 後繼符號集 演算法：

如果非終結符 A 是產生式結尾，那麼說明這個產生式左部非終結符後面能出現的終結符，也都可以出現在非終結符 A 後面。

我們可以求出 LL(1) 文法中每個產生式可選集:

根據產生式可選集，我們可以構建一個預測分析表，表中的每一行都是一個非終結符，表中的每一列都是一個終結符，包括結束符號 $ ，而表中的值就是產生式。
這樣進行語法推導的時候，非終結符遇到當前輸入字元，就可以從預測分析表中獲取對應的產生式了。

有了預測分析表，我們就可以進行預測分析了，具體流程:

可以這么理解：

我們知道要實現預測分析，要求相同左部的產生式，它們的可選集是不相交。
但是有的文法結構不符合這個要求，要進行改造。

如果相同左部的多個產生式有共同前綴，那麼它們的可選集必然相交。
例如:

那麼如何進行改造呢？
其實很簡單，進行如下轉換:

如此文法的相同左部的產生式，它們的可選集是不相交，符合現預測分析。

這種改造方法稱為 提取公因子演算法 。

當我們自頂向下的語法分析時，就需要採用最左推導方式。
而這個時候，如果產生式左部和產生式右部首字元一樣(即A→Aα)，那麼推導就可能陷入無限循環。
例如:

因此對於:

文法中不能包含這兩種形式，不然最左推導就沒辦法進行。

例如:

它能夠推導出如下:

你會驚奇的發現，它能推導出 b 和 (a)* (即由 0 個 a 或者無數個 a 生成的文法符號串)。其實就可以改造成:

因此消除 直接左遞歸 演算法的一般形式：

例如:

消除間接左遞歸的方法就是直接帶入消除，即

消除間接左遞歸演算法：

這個演算法看起來描述很多，其實理解起來很簡單：

思考 : 我們通過 Ai -> Ajβ 來判斷是不是間接左遞歸，那如果有產生式 Ai -> BAjβ 且 B -> ε ,那麼它是不是間接左遞歸呢？
間接地我們可以推出如果一個產生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。

④ 編譯原理試題·

Lex和Yacc應用方法(一).初識Lex
草木瓜 20070301
Lex(Lexical Analyzar 詞法分析生成器)，Yacc(Yet Another Compiler Compiler
編譯器代碼生成器)是Unix下十分重要的詞法分析，語法分析的工具。經常用於語言分
析，公式編譯等廣泛領域。遺憾的是網上中文資料介紹不是過於簡單，就是跳躍太大，
入門參考意義並不大。本文通過循序漸進的例子，從0開始了解掌握Lex和Yacc的用法。

一.Lex(Lexical Analyzar) 初步示例
先看簡單的例子(註：本文所有實例皆在RetHat linux下完成):
一個簡單的Lex文件 exfirst.l 內容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下執行命令flex解析，會自動生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
進行編譯生成parser可執行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll鏈結選項，cc編譯時會出現以下錯誤，後面會進一步說明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status

創建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通過已生成的可執行程序，進行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法會有個直觀的了解：
1.定義Lex描述文件
2.通過lex，flex工具解析成lex.yy.c文件
3.使用cc編譯lex.yy.c生成可執行程序

再來看一個比較完整的Lex描述文件 exsec.l ：

%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
進行解析編譯：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
這里就沒有加-ll選項，但是可以編譯通過。下面開始著重整理下Lex描述文件.l。

二.Lex(Lexical Analyzar) 描述文件的結構介紹
Lex工具是一種詞法分析程序生成器，它可以根據詞法規則說明書的要求來生成單詞識
別程序，由該程序識別出輸入文本中的各個單詞。一般可以分為<定義部分><規則部
分><用戶子程序部分>。其中規則部分是必須的，定義和用戶子程序部分是任選的。

(1)定義部分
定義部分起始於 %{ 符號，終止於 %} 符號，其間可以是包括include語句、聲明語句
在內的C語句。這部分跟普通C程序開頭沒什麼區別。
%{
#include "stdio.h"
int linenum;
%}
(2) 規則部分
規則部分起始於"%%"符號，終止於"%%"符號，其間則是詞法規則。詞法規則由模式和
動作兩部分組成。模式部分可以由任意的正則表達式組成，動作部分是由C語言語句組
成，這些語句用來對所匹配的模式進行相應處理。需要注意的是，lex將識別出來的單
詞存放在yytext[]字元數據中，因此該數組的內容就代表了所識別出來的單詞的內容。
類似yytext這些預定義的變數函數會隨著後面內容展開一一介紹。動作部分如果有多
行執行語句，也可以用{}括起來。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.規則部分的正則表達式
規則部分是Lex描述文件中最為復雜的一部分，下面列出一些模式部分的正則表達式字
符含義：
A-Z, 0-9, a-z 構成模式部分的字元和數字。
- 指定范圍。例如：a-z 指從 a 到 z 之間的所有字元。
\ 轉義元字元。用來覆蓋字元在此表達式中定義的特殊意義，
只取字元的本身。

[] 表示一個字元集合。匹配括弧內的任意字元。如果第一個字
符是^那麼它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一個。

^ 表示否定。
* 匹配0個或者多個上述模式。
+ 匹配1個或者多個上述模式。
? 匹配0個或1個上述模式。
$ 作為模式的最後一個字元時匹配一行的結尾。
{ } 表示一個模式可能出現的次數。 例如: A{1,3} 表示 A 可
能出現1次或3次。[a-z]{5} 表示長度為5的，由a-z組成的
字元。此外，還可以表示預定義的變數。

. 匹配任意字元，除了 \n。
( ) 將一系列常規表達式分組。如：{Letter}({Letter}|{Digit})*
| 表達式間的邏輯或。
"一些符號" 字元的字面含義。元字元具有。如："*" 相當於 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"後跟有後續表達式，
只匹配模版中"/"前面的部分。如：模式為 ABC/D 輸入 ABCD，
時ABC會匹配ABC/D，而D會匹配相應的模式。輸入ABCE的話，
ABCE就不會去匹配ABC/D。

B.規則部分的優先順序

規則部分具有優先順序的概念，先舉個簡單的例子：

%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此時，如果輸入內容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析詞法時，是逐個字元進行讀取，自上而下進行規則匹配的，讀取到第一個A字元
時，遍歷後發現三個規則皆匹配成功，Lex會繼續分析下去，讀至第五個字元時，發現
"AAAA"只有一個規則可用，即按行為進行處理，以此類推。可見Lex會選擇最長的字元
匹配規則。
如果將規則
AAAA {printf("THREE\n");};
改為
AAAAA {printf("THREE\n");};
./parser < file1.txt 輸出結果為：
THREE
TWO

再來一個特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
並輸入title，Lex解析完後發現，仍然存在兩個規則，這時Lex只會選擇第一個規則，下面
的則被忽略的。這里就體現了Lex的順序優先順序。把這個例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex編譯時會提示：warning, rule cannot be matched.這時處理title字元時，匹配
到第一個規則後，第二個規則就無效了。
再把剛才第一個例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 顯示效果是一樣的，最後一項規則肯定是會忽略掉的。

C.規則部分的使用變數
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之間，加入了一些類似變數的東西，注意是沒有;的，這表示int，float分
別代指特定的含義，在兩個%%之間，可以通過{int}{float}進行直接引用，簡化模
式定義。

(3) 用戶子程序部分
最後一個%%後面的內容是用戶子程序部分，可以包含用C語言編寫的子程序，而這些子
程序可以用在前面的動作中，這樣就可以達到簡化編程的目的。這里需要注意的是，
當編譯時不帶-ll選項時，是必須加入main函數和yywrap(yywrap將下後面說明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}

三.Lex(Lexical Analyzar) 一些的內部變數和函數
內部預定義變數：
yytext char * 當前匹配的字元串
yyleng int 當前匹配的字元串長度
yyin FILE * lex當前的解析文件，默認為標准輸出
yyout FILE * lex解析後的輸出文件，默認為標准輸入
yylineno int 當前的行數信息
內部預定義宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字元的
默認動作

內部預定義的函數：
int yylex(void) 調用Lex進行詞法分析
int yywrap(void) 在文件(或輸入)的末尾調用。如果函數的返回值是1，就停止解
析。 因此它可以用來解析多個文件。代碼可以寫在第三段，這
樣可以解析多個文件。 方法是使用 yyin 文件指針指向不同的
文件，直到所有的文件都被解析。最後，yywrap() 可以返回1
來表示解析的結束。

lex和flex都是解析Lex文件的工具，用法相近，flex意為fast lexical analyzer generator。
可以看成lex的升級版本。

相關更多內容就需要參考flex的man手冊了，十分詳盡。

四.關於Lex的一些綜述
Lex其實就是詞法分析器，通過配置文件*.l，依據正則表達式逐字元去順序解析文件，
並動態更新內存的數據解析狀態。不過Lex只有狀態和狀態轉換能力。因為它沒有堆棧，
它不適合用於剖析外殼結構。而yacc增加了一個堆棧，並且能夠輕易處理像括弧這樣的
結構。Lex善長於模式匹配，如果有更多的運算要求就需要yacc了。

⑤ 回溯的在編譯原理中的運用

如左圖，在發生虛假匹配時需要進行回溯，就是退回到開始的位置

⑥ 編譯原理題目

習題一、單項選擇題
1、將編譯程序分成若干個「遍」是為了 。
a．提高程序的執行效率
b．使程序的結構更加清晰
c．利用有限的機器內存並提高機器的執行效率
d．利用有限的機器內存但降低了機器的執行效率
2、構造編譯程序應掌握 。
a．源程序 b．目標語言
c．編譯方法 d．以上三項都是
3、變數應當 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、編譯程序絕大多數時間花在 上。
a．出錯處理 b．詞法分析
c．目標代碼生成 d．管理表格
5、 不可能是目標代碼。
a．匯編指令代碼 b．可重定位指令代碼
c．絕對指令代碼 d．中間代碼
6、使用 可以定義一個程序的意義。
a．語義規則 b．詞法規則
c．產生規則 d．詞法規則
7、詞法分析器的輸入是 。
a．單詞符號串 b．源程序
c．語法單位 d．目標程序
8、中間代碼生成時所遵循的是- 。
a．語法規則 b．詞法規則
c．語義規則 d．等價變換規則
9、編譯程序是對 。
a．匯編程序的翻譯 b．高級語言程序的解釋執行
c．機器語言的執行 d．高級語言的翻譯
10、語法分析應遵循 。
a．語義規則 b．語法規則
c．構詞規則 d．等價變換規則
解答
1、將編譯程序分成若干個「遍」是為了使編譯程序的結構更加清晰，故選b。
2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。
3、對編譯而言，變數既持有左值又持有右值，故選c。
4、編譯程序打交道最多的就是各種表格，因此選d。
5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。
6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間代碼生成遵循的是語義規則，並且語義規則可以定義一個程序的意義。因此選a。
7、b 8、c 9、d 10、c
二、多項選擇題
1、編譯程序各階段的工作都涉及到 。
a．語法分析 b．表格管理 c．出錯處理
d．語義分析 e．詞法分析
2、編譯程序工作時，通常有 階段。
a．詞法分析 b．語法分析 c．中間代碼生成
d．語義檢查 e．目標代碼生成
解答
1．b、c 2. a、b、c、e
三、填空題
1、解釋程序和編譯程序的區別在於 。
2、編譯過程通常可分為5個階段，分別是 、語法分析 、代碼優化和目標代碼生成。 3、編譯程序工作過程中，第一段輸入是 ，最後階段的輸出為 程序。
4、編譯程序是指將 程序翻譯成 程序的程序。 解答
是否生成目標程序 2、詞法分析 中間代碼生成 3、源程序 目標代碼生成 4、源程序 目標語言
一、單項選擇題
1、文法G：S→xSx|y所識別的語言是 。
a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法G描述的語言L(G)是指 。
a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}
c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)}
3、有限狀態自動機能識別 。
a. 上下文無關文法 b. 上下文有關文法
c.正規文法 d. 短語文法
4、設G為算符優先文法，G的任意終結符對a、b有以下關系成立 。
a. 若f(a)>g(b)，則a>b b.若f(a)<g(b)，則a<b
c. a~b都不一定成立 d. a~b一定成立
5、如果文法G是無二義的，則它的任何句子α 。
a. 最左推導和最右推導對應的語法樹必定相同
b. 最左推導和最右推導對應的語法樹可能不同
c. 最左推導和最右推導必定相同
d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同
6、由文法的開始符經0步或多步推導產生的文法符號序列是 。
a. 短語 b.句柄 c. 句型 d. 句子
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
則句型P+T+i的句柄和最左素短語為 。
a.P+T和i b. P和P+T c. i和P+T+i d.P和T
8、設文法為：S→SA|A
A→a|b
則對句子aba，下面 是規范推導。
a. SÞSAÞSAAÞAAAÞaAAÞabAÞaba
b. SÞSAÞSAAÞAAAÞAAaÞAbaÞaba
c. SÞSAÞSAAÞSAaÞSbaÞAbaÞaba
d. SÞSAÞSaÞSAaÞSbaÞAbaÞaba
9、文法G：S→b|∧(T)
T→T,S|S
則FIRSTVT(T) 。
a. {b,∧,(} b. {b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}
10、產生正規語言的文法為 。
a. 0型 b. 1型 c. 2型 d. 3型
11、採用自上而下分析，必須 。
a. 消除左遞歸 b. 消除右遞歸 c. 消除回溯 d. 提取公共左因子
12、在規范歸約中，用 來刻畫可歸約串。
a. 直接短語 b. 句柄 c. 最左素短語 d. 素短語
13、有文法G：E→E*T|T
T→T+i|i
句子1+2*8+6按該文法G歸約，其值為 。
a. 23 B. 42 c. 30 d. 17
14、規范歸約指 。
a. 最左推導的逆過程 b. 最右推導的逆過程
c. 規范推導 d. 最左歸約的逆過程
[解答]
1、選c。
2、選a。
3、選c。
4、雖然a與b沒有優先關系，但構造優先函數後，a與b就一定存在優先關系了。所以，由f(a)>g)(b)或f(a)<g(b)並不能判定原來的a與b之間是否存在優先關系：故選c。
5、如果文法G無二義性，則最左推導是先生長右邊的枝葉：對於d，如果有兩個不同的是了左推導，則必然有二義性。故選a。
6、選c。
7、由圖2-8-1的語法樹和優先關系可以看出應選b。

8、規范推導是最左推導，故選d。
9、由T→T,…和T→(… 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}； 因此選c。
10、d 11、c 12、b 13、b 14、b
二、多項選擇題
1、下面哪些說法是錯誤的 。
a. 有向圖是一個狀態轉換圖 b. 狀態轉換圖是一個有向圖
c.有向圖是一個DFA d.DFA可以用狀態轉換圖表示
2、對無二義性文法來說，一棵語法樹往往代表了 。
a. 多種推導過程 b. 多種最左推導過程 c.一種最左推導過程
d.僅一種推導過程 e.一種最左推導過程
3、如果文法G存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。
a. 該句子的最左推導與最右推導相同
b. 該句子有兩個不同的最左推導
c. 該句子有兩棵不同的最右推導
d. 該句子有兩棵不同的語法樹
e.該句子的語法樹只有一個
4、有一文法G：S→AB
A→aAb|ε
B→cBd|ε
它不產生下面 集合。
a. {anbmcndm|n,m≥0} b. {anbncmdm|n,m>0}
c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0}
e. {anbncndn|n≥0}
5、自下而上的語法分析中，應從 開始分析。
a. 句型 b. 句子 c. 以單詞為單位的程序
d. 文法的開始符 e. 句柄
6、對正規文法描述的語言，以下 有能力描述它。
a.0型文法 b.1型文法 c.上下文無關文法 d.右線性文法 e.左線性文法
解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e
三、填空題
1、文法中的終結符和非終結符的交集是 。詞法分析器交給語法分析器的文法符號一定是 ，它一定只出現在產生式的 部。
2、最左推導是指每次都對句型中的 非終結符進行擴展。
3、在語法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。
4、採用 語法分析時，必須消除文法的左遞歸。
5、 樹代表推導過程， 樹代表歸約過程。
6、自下而上分析法採用 、歸約、錯誤處理、 等四種操作。
7、Chomsky把文法分為 種類型，編譯器構造中採用 和 文法，它們分別產生 和 語言，並分別用 和 自動機識別所產生的語言。
解答 1、空集 終結符 右
2、最左
3、自上而上 自下而上
4、自上而上
5、語法 分析
6、移進 接受
7、4 2 型 3型 上下文無關語言 正規語言 下推自動機 有限
四、判斷題
1、文法 S→aS|bR|ε描述的語言是(a|bc)* ( )
R→cS
2、在自下而上的語法分析中，語法樹與分析樹一定相同。 （ ）
3、二義文法不是上下文無關文法。 （ ）
4、語法分析時必須先消除文法中的左遞歸。 （ ）
5、規范歸約和規范推導是互逆的兩個過程。 （ ）
6、一個文法所有句型的集合形成該文法所能接受的語言。 （ ）
解答 1、對 2、錯 3、錯 4、錯 5、錯 6、錯
五、簡答題
1、句柄 2、素短語 3、語法樹 4、歸約 5、推導
[解答]
1、句柄：一個句型的最左直接短語稱為該句型的句柄。
2、素短語：至少含有一個終結符的素短語，並且除它自身之外不再含任何更小的素短語。
3、語法樹：滿足下面4個條件的樹稱之為文法G[S]的一棵語法樹。
①每一終結均有一標記，此標記為VN∪VT中的一個符號；
②樹的根結點以文法G[S]的開始符S標記；
③若一結點至少有一個直接後繼，則此結點上的標記為VN中的一個符號；
④若一個以A為標記的結點有K個直接後繼，且按從左至右的順序，這些結點的標記分別為X1,X2,…,XK，則A→X1,X2,…,XK，必然是G的一個產生式。
4、歸約：我們稱αγβ直接歸約出αAβ，僅當A→γ 是一個產生式，且α、β∈(VN∪VT)*。歸約過程就是從輸入串開始，反復用產生式右部的符號替換成產生式左部符號，直至文法開始符。
5、推導：我們稱αAβ直接推出αγβ，即αAβÞαγβ，僅當A→ γ 是一個產生式，且α、β∈(VN∪VT)*。如果α1Þα2Þ…Þαn，則我們稱這個序列是從α1至α2的一個推導。若存在一個從α1αn的推導，則稱α1可推導出αn。推導是歸約的逆過程。
六、問答題
1、給出上下文無關文法的定義。
[解答]
一個上下文無關文法G是一個四元式（VT,VN,S, P），其中：
●VT是一個非空有限集，它的每個元素稱為終結符號；
●VN是一個非空有限集，它的每個元素稱為非終結符號，VT∩VN=Φ；
●S是一個非終結符號，稱為開始符號；
●P是一個產生式集合（有限），每個產生式的形式是P→α，其中，P∈VN，
α∈(VT∪VN)*。開始符號S至少必須在某個產生式的左部出現一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的語言是什麼？
[解答]
（1）由於產生式左部存在終結符號，且所有產生式左部符號的長度均小於等於產生式右部的符號長度，所以文法G[S]是Chomsky1型文法，即上下文有關文法。
（2）按產生式出現的順序規定優先順序由高到低（否則無法推出句子），我們可以得到：
SÞabQÞabc
SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc
SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞ
aaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc
……
於是得到文法G[S]生成的語言L={anbncn|n≥1}
3、按指定類型，給出語言的文法。
L={aibj|j＞i≥1}的上下文無關文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求該語言對應的上下文無關文法首先應有S→aSb型產生式，以保證b的個數不少於a的個數；其次，還需有S→Sb或S→bS型的產生式，用以保證b的個數多於a的個數；也即所求上下文無關文法G[S]為：
G[S]：S→aSb|Sb|b
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）寫出句子acabcbbdcc的最左推導過程。
【解答】（1）分別畫出對應兩句型的語法樹，如圖2-8-2所示
句柄:AaB Bd

圖2-8-2 語法樹
（2）句子acabcbbdcc的最左推導如下：
SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA
ÞacabcbbdcAÞacabcbbdcc
5、對於文法G[S]：
S→（L）|aS|a L→L, S|S
（1）畫出句型（S,（a））的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。
【解答】
（1）句型（S,（a））的語法樹如圖2-8-3所示

（2）由圖2-8-3可知：
①短語：S、a、(a)、S,(a)、(S,(a))；
②直接短語：a、S；
③句柄：S；
④素短語：素短語可由圖2-8-3中相鄰終結符之間的優先關系求得，即；

因此素短語為a。
6、考慮文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
證明T*P↑（T*F）是該文法的一個句型，並指出直接短語和句柄。
【解答】
首先構造T*P↑（T*F）的語法樹如圖2-8-4所示。

由圖2-8-4可知，T*P↑（T*F）是文法G[T]的一個句型。
直接短語有兩個，即P和T*F；句柄為P。

一、單項選擇題
1、詞法分析所依據的是 。
a. 語義規則 b. 構詞規則 c. 語法規則 d. 等價變換規則
2、詞法分析器的輸出結果是 。
a. 單詞的種別編碼 b. 單詞在符號表中的位置
c. 單詞的種別編碼和自身值 d. 單詞自身值
3、正規式M1和M2等價是指 。
a. M1和M2的狀態數相等 b. M1和M2的有向弧條數相等
c. M1和M2所識別的語言集相等 d. M1和M2狀態數和有向弧條數相等
4、狀態轉換圖（見圖3-6-1）接受的字集為 。

a. 以 0開頭的二進制數組成的集合 b. 以0結尾的二進制數組成的集合
c. 含奇數個0的二進制數組成的集合 d. 含偶數個0的二進制數組成的集合
5、詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確，因此， 。
a. 詞法分析器應作為獨立的一遍 b. 詞法分析器作為子程序較好
c. 詞法分析器分解為多個過程，由語法分析器選擇使用 d. 詞法分析器並不作為一個獨立的階段
解答 1、b 2、c 3、c 4、d 5、b
二、多項選擇題
1、在詞法分析中，能識別出 。
a. 基本字 b. 四元式 c. 運算符
d. 逆波蘭式 e. 常數
2、令∑={a,b}，則∑上所有以b開頭，後跟若干個ab的字的全體對應的正規式為 。
a. b(ab)* b. b(ab)+ c.(ba)*b
d. (ba)+b e. b(a|b)
解答 1、a、c、e 2、a、b、d
三、填空題
1、確定有限自動機DFA是 的一個特例。
2、若二個正規式所表示的 相同，則認為二者是等價的。
3、一個字集是正規的，當且僅當它可由 所 。
解答 1、NFA 2、正規集 3、DFA（NFA）所識別
四、判斷題
1、一個有限狀態自動機中，有且僅有一個唯一終態。 （ ）
2、設r和s分別是正規式，則有L（r|s）=L(r)|L(s)。 （ ）
3、自動機M和M′的狀態數不同，則二者必不等價。 （ ）
4、確定的自動機以及不確定的自動機都能正確地識別正規集。 （ ）
5、對任意一個右線性文法G，都存在一個NFA M，滿足L(G)=L(M)。 （ ）
6、對任意一個右線性文法G，都存在一個DFA M，滿足L(G)=L(M)。 （ ）
7、對任何正規表達式e，都存在一個NFA M，滿足L(G)=L(e)。 （ ）
8、對任何正規表達式e，都存在一個DFA M，滿足L(G)=L(e)。 （ ）
解答 1 、2、3、錯 4、5、6、7、8、正確
五、基本題
1、設M＝（{x,y}, {a,b}, f,x,{y}）為一非確定的有限自動機，其中f定義如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
試構造相應的確定有限自動機M′。
解答：對照自動機的定義M=(S,Σ,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數，所以是一非確定有限自動機，先畫出NFA M相應的狀態圖，如圖3-6-2所示。

用子集法構造狀態轉換矩陣表3-6-3所示。
I Ia Ib
{x} {x,y} {y}
{y} — {x,y}
{x,y} {x,y} {x,y}
將轉換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態轉換矩陣。
表3-6-4 狀態轉換矩陣
a b
0 2 1
1 — 2
2 2 2
即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其狀態轉換圖如圖3-6-5所示。

將圖3-6-5的DFA M′最小化。首先，將M′的狀態分成終態組{1，2}與非終態組{0}；其次，考察{1,2}。由於{1,2}a={1,2}b={2}⊂{1,2}，所以不再將其劃分了，也即整個劃分只有兩組{0}，{1,2}：令狀態1代表{1,2}，即把原來到達2的弧都導向1，並刪除狀態2。最後，得到如圖3-6-6所示化簡DFA M′。

2、對給定正規式b*（d|ad）（b|ab）+，構造其NFA M；
解答：首先用A+=AA*改造正規式得：b*(d|ad)(b|ab)(b|ab)*；其次，構造該正規式的NFA M，如圖3-6-7所示。
求採納為滿意回答。

⑦ 編譯原理回溯

消除回溯：提取左公因子a,（註：用e代表一補西農符號,就是反三的那個符號,在電腦上不知道怎麼打那個符號）
S→aS'|(L)
S'→S|e
消除左遞歸：
L→SL'
L'→,SL'|e (注意S前面有一個符號「,」)

⑧ 編譯原理文法

編譯原理文法的概念為：每一種自然語言或者是編程語言都需要文法來描述，文法相當於語言學的語義分析，即分析每一句話所表示的含義，編譯器需要利用文法來完成其語法分析和語義分析。

字母表是元素的非空有窮集合，字母表中的元素稱之為符號，因此，字母表也稱之為符號集。例如C語言中的字母表由字母、數字、關鍵字等組成。

符號串，就是由符號集中的元素組成的序列。例如，給定符號集a、b、c，那麼abc、abb、ac就是由該符號集組成的符號串。一個文法中，含有一個，或多個產生式，產生式，描述了將終結符集合和非終結符集合組合成串的方法。

⑨ 編譯原理語法分析中消除左遞歸的問題。比如A→Ab|c中為什麼說它是左遞歸呢，明明是A定義為Ab或者

A->Ab|c為什麼是左遞歸，和為什麼要消除左遞歸：

定義，就無需爭辯了。至於為什麼自頂向下文法不能處理左遞歸,解釋如下：

c∈FIRST(A)，所以當預測分析的棧頂出現非終結符A，而輸入字元串最左邊為c時，就不知道用產生式A->Ab還是A->c了。無法構造預測分析表。比如輸入字元串為cbb，我們人當然容易知道是A->Ab->Abb->cbb了，但是電腦沒那麼聰明，如果不消除左遞歸，只有回溯了。

⑩ 編譯原理全部的名詞解釋

書上有別那麼懶！。。。。
編譯過程的六個階段：詞法分析，語法分析，語義分析，中間代碼生成，代碼優化，目標代碼生成
解釋程序：把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序，然後再執行目標程序。解釋方式是接受某高級語言的一個語句輸入，進行解釋並控制計算機執行，馬上得到這句的執行結果，然後再接受下一句。
編譯程序：就是指這樣一種程序，通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序)。
解釋程序和編譯程序的根本區別：是否生成目標代碼
句子的二義性（這里的二義性是指語法結構上的。）:文法G[S]的一個句子如果能找到兩種不同的最左推導(或最右推導)，或者存在兩棵不同的語法樹，則稱這個句子是二義性的。
文法的二義性:一個文法如果包含二義性的句子，則這個文法是二義文法，否則是無二義文法。
LL(1)的含義：(LL(1)文法是無二義的； LL(1)文法不含左遞歸)
第1個L：從左到右掃描輸入串 第2個L：生成的是最左推導
1 ：向右看1個輸入符號便可決定選擇哪個產生式
某些非LL(1)文法到LL(1)文法的等價變換: 1. 提取公因子 2. 消除左遞歸
文法符號的屬性:單詞的含義，即與文法符號相關的一些信息。如，類型、值、存儲地址等。
一個屬性文法(attribute grammar)是一個三元組A=(G, V, F)
G：上下文無關文法。
V：屬性的有窮集。每個屬性與文法的一個終結符或非終結符相連。屬性與變數一樣，可以進行計算和傳遞。
F：關於屬性的斷言或謂詞(一組屬性的計算規則)的有窮集。斷言或語義規則與一個產生式相聯，只引用該產生式左端或右端的終結符或非終結符相聯的屬性。
綜合屬性:若產生式左部的單非終結符A的屬性值由右部各非終結符的屬性值決定,則A的屬性稱為綜合屬
繼承屬性:若產生式右部符號B的屬性值是根據左部非終結符的屬性值或者右部其它符號的屬性值決定的,則B的屬性為繼承屬性。
(1)非終結符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性。
(2) 終結符只有綜合屬性，沒有繼承屬性，它們由詞法程序提供。
在計算時： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞。
語法制導翻譯：是指在語法分析過程中，完成附加在所使用的產生式上的語義規則描述的動作。
語法制導翻譯實現：對單詞符號串進行語法分析，構造語法分析樹，然後根據需要構造屬性依賴圖，遍歷語法樹並在語法樹的各結點處按語義規則進行計算。
中間代碼（中間語言）
1、是復雜性介於源程序語言和機器語言的一種表示形式。
2、一般，快速編譯程序直接生成目標代碼。
3、為了使編譯程序結構在邏輯上更為簡單明確，常採用中間代碼，這樣可以將與機器相關的某些實現細節置於代碼生成階段仔細處理，並且可以在中間代碼一級進行優化工作，使得代碼優化比較容易實現。
何謂中間代碼：源程序的一種內部表示，不依賴目標機的結構，易於代碼的機械生成。
為何要轉換成中間代碼:(1)邏輯結構清楚；利於不同目標機上實現同一種語言。
(2)便於移植，便於修改，便於進行與機器無關的優化。
中間代碼的幾種形式：逆波蘭記號 ，三元式和樹形表示 ，四元式
符號表的一般形式：一張符號表的的組成包括兩項，即名字欄和信息欄。
信息欄包含許多子欄和標志位，用來記錄相應名字和種種不同屬性，名字欄也稱主欄。主欄的內容稱為關鍵字（key word）。
符號表的功能：（1）收集符號屬性 (2) 上下文語義的合法性檢查的依據： 檢查標識符屬性在上下文中的一致性和合法性。(3)作為目標代碼生成階段地址分配的依據
符號的主要屬性及作用：
1. 符號名 2. 符號的類型 （整型、實型、字元串型等））3. 符號的存儲類別（公共、私有）
4. 符號的作用域及可視性 （全局、局部） 5. 符號變數的存儲分配信息 （靜態存儲區、動態存儲區）
存儲分配方案策略：靜態存儲分配；動態存儲分配：棧式、 堆式。
靜態存儲分配
1、基本策略
在編譯時就安排好目標程序運行時的全部數據空間，並能確定每個數據項的單元地址。
2、適用的分配對象：子程序的目標代碼段；全局數據目標（全局變數）
3、靜態存儲分配的要求：不允許遞歸調用，不含有可變數組。
FORTRAN程序是段結構，不允許遞歸，數據名大小、性質固定。 是典型的靜態分配
動態存儲分配
1、如果一個程序設計語言允許遞歸過程、可變數組或允許用戶自由申請和釋放空間，那麼，就需要採用動態存儲管理技術。
2、兩種動態存儲分配方式：棧式，堆式
棧式動態存儲分配
分配策略：將整個程序的數據空間設計為一個棧。
【例】在具有遞歸結構的語言程序中，每當調用一個過程時，它所需的數據空間就分配在棧頂，每當過程工作結束時就釋放這部分空間。
過程所需的數據空間包括兩部分
一部分是生存期在本過程這次活動中的數據對象。如局部變數、參數單元、臨時變數等；
另一部分則是用以管理過程活動的記錄信息(連接數據)。
活動記錄（AR）
一個過程的一次執行所需要的信息使用一個連續的存儲區來管理，這個區 (塊)叫做一個活動記錄。
構成
1、臨時工作單元；2、局部變數；3、機器狀態信息；4、存取鏈；
5、控制鏈；6、實參；7、返回地址
什麼是代碼優化
所謂優化，就是對代碼進行等價變換，使得變換後的代碼運行結果與變換前代碼運行結果相同，而運行速度加快或佔用存儲空間減少。
優化原則：等價原則：經過優化後不應改變程序運行的結果。
有效原則：使優化後所產生的目標代碼運行時間較短，佔用的存儲空間較小。
合算原則：以盡可能低的代價取得較好的優化效果。
常見的優化技術
(1) 刪除多餘運算(刪除公共子表達式) (2) 代碼外提 +刪除歸納變數+ (3)強度削弱; (4)變換循環控制條件 (5)合並已知量與復寫傳播 (6)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列，稱為程序的一個基本塊。

給我分數啊。。。