編譯原理符號表的五種操作

⑷ 急急急，編譯原理

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);

⑸ 編譯原理——語法制導翻譯1.2

語法樹是分析樹的壓縮形式。在語法樹中，運算符和關鍵字不再是葉節點，而是作為內部節點的父節點。

用以下函數建立帶有二元運算符的表達式語法樹節點，每個函數都返回一個指向新建節點的指針：

1.mknode（op，left，right）。它建立一個標記為op的運算符節點，其兩個域left和right是指向其左右運算對象的指針。

2.mkleaf（id，entry）。它建立標記為id的標識符節點，其域entry是指向該標識符在符號表中的相應表項的指針。

3.mkleaf（num，val）。它建立標記為num的數節點，域val保存該數的值。

表達式的無環有向圖（directed acyclic graph，簡稱dag）可以識別表達式中的公共子表達式。代表公共表達式的節點具有多個「父節點」。

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

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

⑺ 編譯原理中的詞法分析器的輸入與輸出是什麼

編譯原理中的詞法分析器的輸入是源程序，輸出是識別的記號流。

詞法分析器編制一個讀單詞的程序，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數、運算符和分隔符五大類。並依次輸出各個單詞的內部編碼及單詞符號自身值。（遇到錯誤時可顯示「Error」，然後跳過錯誤部分繼續顯示）。

(7)編譯原理符號表的五種操作擴展閱讀

詞法分析器的作用：

1、與符號表進行交互，存儲和讀取符號表中的標識符的信息。

2、讀入源程序的輸入字元，將他們組成詞素，生成並輸出一個詞法單元序列，每個詞法單元序列對應一個於一個詞素。

3、過濾掉程序中的注釋和空白。

4、將編譯器生成的錯誤消息與源程序的位置聯系起。

⑻ 如何建立符號表

Symbol Tables

為了維持靜態作用域的程序里各個名字的軌跡，編譯器需要依靠一種稱為符號表的數據結構。從最基本的層次上看，符號表就是一個字典：它把名字映射到編譯器已知的有關信息。這里最基本的操作是把一個新映射關系（名字對象約束）放入表裡，以及（非破壞性的）用一個給定名字去提取映射下的信息，以後我們把

這兩個操作分別稱為insert和lookup。大部分語言里的靜態作用域規則還提出了另外的復雜性，它們要求在程序里的不同部分有不同的引用環境。為了處理作用域規則，我們可能希望簡單增加一個remove操作。由於編譯器在語義分析階段要從頭到尾掃描代碼，這樣它就可以在某個作用域開始時插入新約束，在作用域最後撤銷它們。但是，存在一些因素使這種直接做法並不實際。

¨ 在許多有著嵌套作用域的語言里，內層聲明的效果可以遮蔽外層聲明，這就意味著符號表必須有能力為一個給定名字保存任意數目的映射。lookup操作必須返回最內層的映射，到作用域結束時還必須使外層映射重新變成可見的。

¨ 類Algol語言里的記錄（結構）具有某種作用域性質，但卻又不享有作用域那樣的良好嵌套結構。當語義分析器看到一個記錄聲明時，它就必須記下各個記錄域的名字（它們也是遞歸的，因為記錄可以嵌套）。在這種聲明結束時，各個域的名字又必須變成不可見的。然而，在此之後，一旦這一記錄類型的某個變數出現在程序的正文里（例如在my_rec.field_name），在引用中位於圓點之後的部分，這些域名又必須立即重新變成可見的。在Pascal和另一些有with語句的語言里，記錄域的名字還應該在多個語句的上下文里變成可見的。

¨ 某些時候一些名字有可能在它們被聲明之前使用，即使在類Algol語言里情況也如此。舉例說，Algol 60和Algol 68都允許標號的向前引用。Pascal避免了這種情況，它要求標號必須在作用域開始處聲明，但還是允許指針聲明的向前引用：

type

company = record

CEO : ^person; (* forward reference *)

...

end;

person = record

employer : ^company;

...

end;

¨ Pascal和其他語言都允許子程序的向前聲明，以便支持相互遞歸：

procere Q (A, B : integer); forward;

procere P (A, B : integer);

begin

...

Q (3, 4);

...

end;

procere Q; (* parameters are not repeated in Pascal *)

begin

...

P (4, 5);

...

end;

在看到這段代碼里的向前聲明時，語義分析器必須記住Q的參數，以便後面可以在Q的體里使它們重新變成可見的，但在此期間又必須使它們成為不可見的。這種操作類似於記住記錄域的名字。

¨ 雖然我們有可能希望在作用域結束時忘記有關的名字，甚至回收這些名字在符號表裡占據的空間，但有關它們的信息仍需要保存起來，以便符號糾錯系統（symbolic debugger）使用。這種糾錯系統是非常有用的工具，用戶可以藉助它方便地操縱程序，如啟動程序，停住它，讀出或者修改程序里的數據等等。為了分析來自用戶的高級名字（例如，要求列印出my_firm^.revenues[1999] 的值），符號糾錯程序必須能訪問編譯器的符號表。為了使符號表在運行時也可以用，編譯器通常會把這個表保存到最後的機器語言程序里的某個隱蔽的部分。

靜態作用域的大部分變化都可以通過擴充基本符號表的方式處理，通過增加一對enter_scope和leave_scope操作維持可見性的軌跡。任何東西都不會從符號表裡刪除，在整個編譯階段所有的結構都保留著，最後還要為糾錯系統使用而保存起來。帶有可見性處理的符號表可以以多種不同方式實現，下面描述的方式歸功於LeBlanc和Cook [CL83]。

在遇到每個作用域時賦給它一個序列號。給定最外層的作用域（其中包含著預定義的標識符）編號0，包含用戶定義全局名字的作用域給以編號1。其他作用域按遇到它們的順序進行編號。所有的編號互不相同，它們並不表示詞法嵌套的層次，但也有一點，嵌套於內部的子程序的編號自然會大於它們的外圍作用域的編號。

所有的名字都被放入一個大的散列表裡，以名字作為關鍵碼，無論其作用域如何。表裡的每項都包含一個符號名，其類屬（變數、常量、類型、過程、域名字、參數等等），作用域編號，類型（一個指向另一符號表項的指針），以及另一些特定類屬所擁有的信息。

除了這一散列表之外，符號表還包含一個作用域堆棧，它按順序指明組成當前引用環境的所有作用域。在語義分析器掃描程序的過程中，在進入或退出程序時分別壓入或者彈出這個堆棧。作用域堆棧的項里包含著作用域編號，指明這一作用域是否為閉的，有些情況下還可以有另外一些信息。

圖3.13 LeBlanc-Cook符號表的lookup演算法。

當需要到表裡查找名字時，我們會順著某個適當的散列表鏈向下找，這樣就會找到要找的名字所對應的一些項。對於每個匹配項，我們都向下掃描作用域堆棧，看看這個項所在的作用域是否可見。這種堆棧查看的深度不應超過最上面的閉作用域。要把導入項和導出項變為在它們的作用域之外可見的，方法就是在表裡建立另外的項，讓這些項里包含著指向實際項的指針。對於所有帶有作用域編號0的項，我們都不需要去檢查作用域堆棧，因為它們是滲透性的。圖3.13里是lookup演算法的偽代碼。

圖3.14的右下角是一個Mola-2程序的梗概，圖中其餘部分展現的是在過程P2里with語句處的引用環境的符號表配置情況。作用域堆棧里包含4個項，分別表示那個with語句，過程P2，模塊M和全局作用域。with語句的作用域指明了在這一特定作用域里的（域）名字屬於哪個記錄變數。最外面的滲透性作用域沒有顯式表示。

圖3.14 一個Mola-2例子程序的LeBlanc-Cook符號表。作用域堆棧表示在過程P2里with語句的引用環境。為清楚起見，許多指向符號表裡對應於integer和real的項都用帶括弧的 (1) 和 (2) 表示，沒有畫出箭頭。

因為這里的散列表以名字作為關鍵碼，特定名字的所有項都出現在同一個散列鏈里。在這個例子里，散列沖突導致A2、F2和T出現在同一個鏈里。變數V和I（M的I）有另外的項，使它們跨過閉作用域M的邊界後仍為可見的。當我們處於P2里時，對於I的查找操作將找到P2的I，M的I里的兩個項都不可見。類型T的項指明了在with語句期間放入作用域堆棧的作用域編號。每個子程序的項里包含了一個頭指針，指向子程序參數的鏈接表，以便做調用分析時使用（圖中沒有給出這些鏈的一些鏈接）。在代碼生成過程中，許多符號表項還可能包含另外的域，表示例如對象大小和運行時地址等等信息。

圖片信息，看參考資料。。。

⑼ 編譯原理對符號表進行操作有哪些

//----------------------------符號表---------------------------------------
//預定義
struct snode;
struct stable;
//符號表結點
struct snode
{
string text; //符號名稱
string type; //符號類型
union {int ival;double rval;}value; //值------------
int offset; //偏移量
snode *nextn; //指向下一個節點
stable *header; //指向下屬符號表的表頭
};
//符號表表頭
struct stable
{
stable *previous; //指向先前創建的符號表表頭
snode *firstnode; //指向第一個結點
stable *ifnoelements;//如果此表為空，則用它指向下一個表頭
};

//當前表頭
stable *currtab;
//建立新表，返回表頭指針
//參數：當前的節點的表頭
stable *mktable(stable *previous)
{
stable *newtable =new stable;
newtable->previous=previous;
newtable->ifnoelements=0;
newtable->firstnode=0;
if(previous->firstnode==0)
{
previous->ifnoelements=newtable;
}
else
{
snode* ininode=previous->firstnode;
while(ininode->nextn!=0)
{
ininode=ininode->nextn;
}
ininode->header=newtable;
}

currtab=newtable;
return newtable;
}
//在node指向的符號表中為text建立一個新表項，返回新建立的結點
//參數：node為當前的節點的表頭，text名稱，type類型，offset偏移
snode *enter(stable *table,string text,string type,int offset,double value)
{

//創建節點
snode *newnode = new snode;
newnode->text=text;
newnode->type=type;
newnode->offset=offset;
newnode->nextn=0;
newnode->header=0;
if(type=="int")
{
newnode->value.ival=value;
}
else if(type=="real")
{
newnode->value.rval=value;
}

//判斷此表是否無元素
if(currtab->firstnode==0)
{
currtab->firstnode=newnode;
currtab->ifnoelements=0;
}
else
{
snode* addnode=currtab->firstnode;
while(addnode->nextn!=0)
{
addnode=addnode->nextn;
}
addnode->nextn=newnode;
}

return newnode;
}
//初始化符號表，返回表頭節點
void inittab()
{
stable *initable = new stable;
initable->firstnode=0;
initable->previous=0;
initable->ifnoelements=0;
currtab=initable;
}
//查找指針，表示結果
snode *searchresult;
//查找變數，返回指向該變數的指針
//查找變數，返回指向該變數的指針
snode* search(string name)
{
//檢查表是否空
bool isempty=true;
stable* checktab=currtab;
if(checktab->firstnode!=0)
{isempty=false;}
while(checktab->previous!=0)
{
if(checktab->firstnode!=0)
{isempty=false;}
checktab=checktab->previous;
}
if(checktab->firstnode!=0)
{isempty=false;}
if(isempty)
{
return 0;
}
snode* lastnode;
if(currtab->firstnode==0)
{
//移到非空的表頭
stable* notnullhead=currtab;
while(notnullhead->firstnode==0)
{
notnullhead=notnullhead->previous;
}
snode* tmpnode=notnullhead->firstnode;
//移到最後的元素
while(tmpnode->nextn!=0)
{
tmpnode=tmpnode->nextn;
}
lastnode=tmpnode;
}
else
{
lastnode=currtab->firstnode;
while(lastnode->nextn!=0)
{
lastnode=lastnode->nextn;
}
}
//移到表頭
stable* fronttab=currtab;
while(fronttab->previous!=0)
{
fronttab=fronttab->previous;
}
snode* nownode=0;
while(nownode!=lastnode)
{
while(fronttab->ifnoelements!=0)
{
fronttab=fronttab->ifnoelements;
}
nownode=fronttab->firstnode;
while(nownode->nextn!=0)
{
if(nownode->text==name)
{
searchresult=nownode;
return searchresult;
}
nownode=nownode->nextn;
}
if(nownode->text==name)
{
searchresult=nownode;
return searchresult;
}
fronttab=nownode->header;
}
if(nownode->text==name)
{
searchresult=nownode;
return searchresult;
}
return 0;
}

//消毀符號表
void delNode()
{
//more codes here......
}