編譯原理tac序列

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

書上有別那麼懶！。。。。
編譯過程的六個階段：詞法分析，語法分析，語義分析，中間代碼生成，代碼優化，目標代碼生成
解釋程序：把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序，然後再執行目標程序。解釋方式是接受某高級語言的一個語句輸入，進行解釋並控制計算機執行，馬上得到這句的執行結果，然後再接受下一句。
編譯程序：就是指這樣一種程序，通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序)。
解釋程序和編譯程序的根本區別：是否生成目標代碼
句子的二義性（這里的二義性是指語法結構上的。）:文法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)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列，稱為程序的一個基本塊。

給我分數啊。。。

Ⅱ 有關編譯原理的幾個問題

最左推到就是從最左邊的非終結符開始替換，一個一個替換，直到替換為題目要求的。預測分析表什麼的太煩了，不高興寫。你按著書上例題步驟一步一步寫就可以了。給你寫個第五題。

Ⅲ 編譯原理 寫出表達式 三元序列

三元式
(1)（a，b，+）
(2)(a,b,-)
(3)((1),(2),/)
(4)(b,c,*)
(5)(a,(4),+)
(6)((3),(5),-)
四元式
（a，b，+,x1）
(a,b,-,x2)
(x1,x2,/,x3)
(b,c,*,x4)
(a,x4,+,x5)
(x3,x5,-,x6)

Ⅳ 編譯原理編程

1)0*10*10*

2)0*(10+)*(1|0)

3)(0*10*10*)*

第一題跟第三題是差不多的

這時候可以發現,只要用一個count來做對錯的識別就能解決,並不是沒有用到state狀態,而是該狀態變為隱性了,如下

/**

*@fnintcheck_data(char*d_line,intn)

*@brief檢查資列串是否符合給定的正則表達式

*@return0不符;1符合

*/

intcheck_data(char*d_line,intn){

inti,count;

for(count=0,i=0;i<n;i++){//只要算出1的個數即可

if(d_line[i]=='1')count++;

}

return(1-(count&1));//當count奇數表示失敗;當count偶數成功

}

第二題的話,就會用到state來紀錄狀態,

而最後離開狀態S4還是被隱含在執行判斷的過程中

#defineS10

#defineS21

#defineS32

#defineS43

intcheck_data(char*d_line,intn){

inti,state;

state=S1;

for(i=0;i<n;i++){

switch(state){

caseS1:

if(d_line[i]=='1')state=S2;break;

caseS2:

if(d_line[i]=='1')return0;//失敗了

/*d_line[i]為'0'*/state=S3;break;

caseS3:

if(d_line[i]=='1')state=S2;break;

caseS4:break;

}

}

return1;

}

基本上上述程式對照自動機就可以比較清楚了

Ⅳ 編譯原理課程設計－詞法分析器設計（C語言）

#include"stdio.h"/*定義I/O庫所用的某些宏和變數*/

#include"string.h"/*定義字元串庫函數*/

#include"conio.h"/*提供有關屏幕窗口操作函數*/

#include"ctype.h"/*分類函數*/

charprog[80]={''},

token[8];/*存放構成單詞符號的字元串*/

charch;

intsyn,/*存放單詞字元的種別碼*/

n,

sum,/*存放整數型單詞*/

m,p;/*p是緩沖區prog的指針，m是token的指針*/

char*rwtab[6]={"begin","if","then","while","do","end"};

voidscaner(){

m=0;

sum=0;

for(n=0;n<8;n++)

token[n]='';

ch=prog[p++];

while(ch=='')

ch=prog[p++];

if(isalpha(ch))/*ch為字母字元*/{

while(isalpha(ch)||isdigit(ch))/*ch為字母字元或者數字字元*/{

token[m++]=ch;

ch=prog[p++];}

token[m++]='';

ch=prog[p--];

syn=10;

for(n=0;n<6;n++)

if(strcmp(token,rwtab[n])==0)/*字元串的比較*/{

syn=n+1;

break;}}

else

if(isdigit(ch))/*ch是數字字元*/{

while(isdigit(ch))/*ch是數字字元*/{

sum=sum*10+ch-'0';

ch=prog[p++];}

ch=prog[p--];

syn=11;}

else

switch(ch){

case'<':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='>'){

syn=21;

token[m++]=ch;}

elseif(ch=='='){

syn=22;

token[m++]=ch;}

else{

syn=20;

ch=prog[p--];}

break;

case'>':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=24;

token[m++]=ch;}

else{

syn=23;

ch=prog[p--];}

break;

case':':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=18;

token[m++]=ch;}

else{

syn=17;

ch=prog[p--];}

break;

case'+':syn=13;token[0]=ch;break;

case'-':syn=14;token[0]=ch;break;

case'*':syn=15;token[0]=ch;break;

case'/':syn=16;token[0]=ch;break;

case'=':syn=25;token[0]=ch;break;

case';':syn=26;token[0]=ch;break;

case'(':syn=27;token[0]=ch;break;

case')':syn=28;token[0]=ch;break;

case'#':syn=0;token[0]=ch;break;

default:syn=-1;}}

main()

{

printf(" Thesignificanceofthefigures: "

"1.figures1to6saidKeyword "

"2. "

"3.figures13to28saidOperators ");

p=0;

printf(" pleaseinputstring: ");

do{

ch=getchar();

prog[p++]=ch;

}while(ch!='#');

p=0;

do{

scaner();

switch(syn){

case11:printf("(%d,%d) ",syn,sum);break;

case-1:printf(" ERROR; ");break;

default:printf("(%d,%s) ",syn,token);

}

}while(syn!=0);

getch();

}

程序測試結果

對源程序beginx:=9:ifx>9thenx:=2*x+1/3;end#的源文件，經過詞法分析後輸出如下圖5-1所示：

具體的你在修改修改吧

Ⅵ 編譯原理。。

我直接寫答案了：
1.A、B
2.A、D
3.B、C
4.C、D
5.C、D
6.A、D與第二題一樣
7.C、D
以上答案只供參考

Ⅶ 編譯原理 名詞解釋

1、識別源程序中意義獨立的最小單位--單詞
2、不確定的有窮自動機(Nondeterministic Finite Automata)--NFA
3、是指程序—順序執行的語句序列，其中只有一個入口和一個出口，入口就是其中的第—個語句，出口就是其中的最後一個語句--基本塊
4、它把高級語言編寫的源程序翻譯成與之在邏輯上等價的機器語言或匯編語言的目標程序--編譯程序

5、是規則的非空有窮集合--文法
6、確定的有窮自動(Deterministic Finite Automata)--DFA

Ⅷ 計算機科學與技術中編譯原理簡答題

時間有點久記得不太真切，用通俗語言說，希望題主盡量查閱書籍參考資料自行驗證理解。

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。

Ⅸ 急急急，編譯原理

using namespace std;

struct BiNode
{
char data;
BiNode *lchild, *rchild;
};
typedef BiNode *BiTree;

int CreateBiTree(BiTree &T, const char *s1, const char *s2, int len)
{
if (len<=0)
{
T = NULL;
return 1;
}
else
{
T = new BiNode;
T->data = *s1;
int i;
for ( i=0; i<len; i++) if (s2[i]==*s1) break;
CreateBiTree(T->lchild, s1+1, s2, i);
CreateBiTree(T->rchild, s1+i+1, s2+i+1, len-(i+1));
}
return 1;
}

int DestroyBiTree(BiTree &T)
{
if (T==NULL) return 1;
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
delete T;
T = NULL;
return 1;
}

int ATraverse(BiTree &T)
{
if (T==NULL) return 1;
ATraverse(T->lchild);
ATraverse(T->rchild);
cout<<T->data;
return 1;
}

main()
{
char a[2000],b[2000];
while(cin>>a>>b)
{
BiTree T;
int count=0;
int n;
for(n=0;a[n]!='\0';n++);
CreateBiTree(T,a,b,n);
ATraverse(T);
cout<<" ";

cout<<endl;
DestroyBiTree(T);