編譯語法分析原理
1. 編譯原理實驗二 LL(1)分析法
通過完成預測分析法的語法分析程序,了解預測分析法和遞歸子程序法的區別和聯系。使學生了解語法分析的功能,掌握語法分析程序設計的原理和構造方法,訓練學生掌握開發應用程序的基本方法。有利於提高學生的專業素質,為培養適應社會多方面需要的能力。
根據某一文法編制調試 LL(1)分析程序,以便對任意輸入的符號串進行分析。
構造預測分析表,並利用分析表和一個棧來實現對上述程序設計語言的分析程序。
分析法的功能是利用LL(1)控製程序根據顯示棧棧頂內容、向前看符號以及LL(1)分析表,對輸入符號串自上而下的分析過程。
對文法 的句子進行不含回溯的自上向下語法分析的充分必要條件是:
(1)文法不含左遞歸;
(2)對於文法中的每一個非終結符 的各個產生式的候選首符集兩兩不相交,即,若
Follow集合構造:
對於文法 的每個非終結符 構造 的演算法是,連續使用下面的規則,直至每個 不再增大為止:
僅給出核心部分
(1) GrammerSymbol.java
(2) GrammerSymbols.java
(3) Grammer.java
(4) LL1Grammer.java
2. 編譯原理中詞法分析和語法分析的任務分別是什麼
在編譯原理中,語法規則和詞法規則不同之處在於:規則主要識別單詞,而語法主要識別多個單片語成的句子。
詞法分析和詞法分析程序:
詞法分析階段是編譯過程的第一個階段。這個階段的任務是從左到右一個字元一個字元地讀入源程序,即對構成源程序的字元流進行掃描然後根據構詞規則識別單詞(也稱單詞符號或符號)。詞法分析程序實現這個任務。詞法分析程序可以使用lex等工具自動生成。
語法分析(Syntax analysis或Parsing)和語法分析程序(Parser)
語法分析是編譯過程的一個邏輯階段。語法分析的任務是在詞法分析的基礎上將單詞序列組合成各類語法短語,如「程序」,「語句」,「表達式」等等.語法分析程序判斷源程序在結構上是否正確.源程序的結構由上下文無關文法描述.
語義分析(Syntax analysis)
語義分析是編譯過程的一個邏輯階段. 語義分析的任務是對結構上正確的源程序進行上下文有關性質的審查, 進行類型審查.語義分析將審查類型並報告錯誤:不能在表達式中使用一個數組變數,賦值語句的右端和左端的類型不匹配.
3. 編譯原理筆記7:語法分析(1)語法分析器的任務、語法錯誤的處理
語法分析器的兩項主要任務,分別:
源程序中的錯誤可以分為詞法/語法錯誤、語義錯誤兩類。前者主要形式是命名不合法、關鍵字書寫錯誤、語法結構有問題(比如缺分號、該配對的東西不配對)等;後者則可分為靜態/動態兩種,靜態例如類型使用錯誤、參數使用錯誤等,動態語義錯誤則是無窮遞歸這類邏輯性的問題。
例如:
緊急恢復:x = a+b+d; // 丟棄掉 b 後的記號,直到遇到 +
短語級恢復: x = a+b; // 加入分號
在寫程序時,要養成減少錯誤的好習慣:每次用變數、參數時,要在使用之前進行初始化,並在直接使用之前檢查一下是否出現值為空等問題,防止出現不可預知的錯誤
4. 編譯原理詞法分析
編譯的詞法分析,一般是先畫一個狀態轉換圖,一般是有多少分支,就有多少if語句,分支裡面再分(可能有循環語句)。注意記住詞的類別和詞的字元串,請以以下代碼為例,理會一下詞法分析的大致過程。
while(s[i]!='#')
{
while(s[i]==' '||s[i]=='\t'||s[i]=='\n')
{
if(s[i]=='\n')
line++;
i++;
}
if(s[i]=='#')
break;
j=i;
if(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z')
{
i++;
while(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z'||s[i]>='0'&&s[i]<='9')
i++;
if((i-j)==2&&s[j]=='i'&&s[j+1]=='f')
{
strcpy(dancishuzu[dancigeshu].name,"if");
dancishuzu[dancigeshu].bianhao=4;
dancigeshu++;
}
else if((i-j)==3&&s[j]=='i'&&s[j+1]=='n'&&s[j+2]=='t')
{
strcpy(dancishuzu[dancigeshu].name,"int");
dancishuzu[dancigeshu].bianhao=2;
dancigeshu++;
}
else if((i-j)==3&&s[j]=='f'&&s[j+1]=='o'&&s[j+2]=='r')
{
strcpy(dancishuzu[dancigeshu].name,"for");
dancishuzu[dancigeshu].bianhao=6;
dancigeshu++;
}
else if((i-j)==4&&s[j]=='m'&&s[j+1]=='a'&&s[j+2]=='i'&&s[j+3]=='n')
{
strcpy(dancishuzu[dancigeshu].name,"main");
dancishuzu[dancigeshu].bianhao=1;
dancigeshu++;
}
else if ((i-j)==4&&s[j]=='c'&&s[j+1]=='h'&&s[j+2]=='a'&&s[j+3]=='r')
{
strcpy(dancishuzu[dancigeshu].name,"char");
dancishuzu[dancigeshu].bianhao=3;
dancigeshu++;
}
else if ((i-j)==4&&s[j]=='e'&&s[j+1]=='l'&&s[j+2]=='s'&&s[j+3]=='e')
{
strcpy(dancishuzu[dancigeshu].name,"else");
dancishuzu[dancigeshu].bianhao=5;
dancigeshu++;
}
else if ((i-j)==5&&s[j]=='w'&&s[j+1]=='h'&&s[j+2]=='i'&&s[j+3]=='l'&&s[j+4]=='e')
{
strcpy(dancishuzu[dancigeshu].name,"while");
dancishuzu[dancigeshu].bianhao=7;
dancigeshu++;
}
else{
dancishuzu[dancigeshu].bianhao=10;
count=0;
while(j<i)
{
dancishuzu[dancigeshu].name[count++]=s[j];
j++;
}
dancishuzu[dancigeshu].name[count]='\0';
dancigeshu++;
}
}
else if(s[i]>='0'&&s[i]<='9')
{
while(s[i]>='0'&&s[i]<='9')
i++;
dancishuzu[dancigeshu].bianhao=11;
count=0;
while(j<i)
{
dancishuzu[dancigeshu].name[count++]=s[j];
j++;
}
dancishuzu[dancigeshu].name[count]='\0';
dancigeshu++;
}
else if(s[i]=='=')
{
if(s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=30;
strcpy(dancishuzu[dancigeshu].name,"==");
dancigeshu++;
i+=2;
}
else
{
dancishuzu[dancigeshu].bianhao=12;
strcpy(dancishuzu[dancigeshu].name,"=");
dancigeshu++;
i++;
}
}
else if(s[i]=='+')
{
dancishuzu[dancigeshu].bianhao=13;
strcpy(dancishuzu[dancigeshu].name,"+");
dancigeshu++;
i++;
}
else if(s[i]=='-')
{
dancishuzu[dancigeshu].bianhao=14;
strcpy(dancishuzu[dancigeshu].name,"-");
dancigeshu++;
i++;
}
else if(s[i]=='*')
{
dancishuzu[dancigeshu].bianhao=15;
strcpy(dancishuzu[dancigeshu].name,"*");
dancigeshu++;
i++;
}
else if(s[i]=='/')
{
dancishuzu[dancigeshu].bianhao=16;
strcpy(dancishuzu[dancigeshu].name,"/");
dancigeshu++;
i++;
}
else if(s[i]=='(')
{
i++;
dancishuzu[dancigeshu].bianhao=17;
strcpy(dancishuzu[dancigeshu].name,"(");
dancigeshu++;
}
else if(s[i]==')')
{
i++;
dancishuzu[dancigeshu].bianhao=18;
strcpy(dancishuzu[dancigeshu].name,")");
dancigeshu++;
}
else if(s[i]=='[')
{
i++;
dancishuzu[dancigeshu].bianhao=19;
strcpy(dancishuzu[dancigeshu].name,"[");
dancigeshu++;
}
else if(s[i]==']')
{
i++;
dancishuzu[dancigeshu].bianhao=20;
strcpy(dancishuzu[dancigeshu].name,"]");
dancigeshu++;
}
else if(s[i]=='{')
{
i++;
dancishuzu[dancigeshu].bianhao=21;
strcpy(dancishuzu[dancigeshu].name,"{");
dancigeshu++;
}
else if(s[i]=='}')
{
i++;
dancishuzu[dancigeshu].bianhao=22;
strcpy(dancishuzu[dancigeshu].name,"}");
dancigeshu++;
}
else if(s[i]==',')
{
i++;
dancishuzu[dancigeshu].bianhao=23;
strcpy(dancishuzu[dancigeshu].name,",");
dancigeshu++;
}
else if(s[i]==':')
{
i++;
dancishuzu[dancigeshu].bianhao=24;
strcpy(dancishuzu[dancigeshu].name,":");
dancigeshu++;
}
else if(s[i]==';')
{
i++;
dancishuzu[dancigeshu].bianhao=25;
strcpy(dancishuzu[dancigeshu].name,";");
dancigeshu++;
}
else if(s[i]=='>')
{
if(s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=28;
strcpy(dancishuzu[dancigeshu].name,">=");
dancigeshu++;
i+=2;
}
else
{
i++;
dancishuzu[dancigeshu].bianhao=26;
strcpy(dancishuzu[dancigeshu].name,">");
dancigeshu++;
}
}
else if(s[i]=='<')
{
if(s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=29;
strcpy(dancishuzu[dancigeshu].name,"<=");
dancigeshu++;
i+=2;
}
else
{
i++;
dancishuzu[dancigeshu].bianhao=27;
strcpy(dancishuzu[dancigeshu].name,"<");
dancigeshu++;
}
}
else if(s[i]=='!'&&s[i+1]=='=')
{
dancishuzu[dancigeshu].bianhao=31;
strcpy(dancishuzu[dancigeshu].name,"!=");
dancigeshu++;
i+=2;
}
else
{
printf("\nline:%derror!",line);
i++;
return;
}
}
5. 編譯原理筆記9:語法分析樹、語法樹、二義性的消除
語法分析樹和語法樹不是一種東西 。習慣上,我們把前者叫做「具體語法樹」,其能夠體現推導的過程;後者叫做「抽象語法樹」,其不體現過程,只關心最後的結果。
語法分析樹是語言推導過程的圖形化表示方法。這種表示方法反映了語言的實質以及語言的推導過程。
定義:對於 CFG G 的句型,分析樹被定義為具有下述性質的一棵樹:
推導,有最左推導和最右推導,這兩種推導方式在推導過程中的分析樹可能不同,但因最終得到的句子是相同的,所以最終的分析樹是一樣的。
分析樹能反映句型的推導過程,也能反映句型的結構。然而實際上,我們往往不關心推導的過程,而只關心推導的結果。因此,我們要對 分析樹 進行改造,得到 語法樹 。語法樹中全是終結符,沒有非終結符。而且語法樹中沒有括弧
定義:
說白了,語法樹這玩意,就一句話: 葉子全是操作數,內部全是操作符 ,樹里沒有非終結符也不能有括弧。
語法樹要表達的東西,是操作符(運算)作用於操作數(運算對象)
舉倆例子吧:
【例】: -(id+id) 的語法樹:
【例】:-id+id 的語法樹:
顯然,我們從上面這兩個語法樹中,直接就能觀察出來它們的運算順序。
【例】:句型 if C then s1 else s2
二義性問題:一個句子可能對應多於一棵語法樹。
【例】: 設文法 G: E → E+E | E*E | (E) | -E | id
則,句子 id+id*id、id+id+id 可能的分析樹有:
在該例中,雖然 id+id+id 的 「+」 的結合性無論左右都不會影響結果。但萬一,萬一「+」的含義變成了「減法」,那麼左結合和右結合就會引起很大的問題了。
我們在這里講的「二義性」的「義」並非語義——我們現在在學習的內容是「語法分析器」,尚未到需要研究語言背後含義的階段。
我們現在講的「二義性」指的是一個句子對應多種分析樹。
二義性的體現,是文法對同一句子有不止一棵分析樹。這種問題由【句子產生過程中的某些推導有多於一種選擇】引起。懸空 else 問題就可以很好地體現這種【超過一種選擇】帶來的二義性問題,示例如下。
看下面這么個例子。。
(其實,我感覺這個其實比較像是「說話大喘氣」帶來的理解歧義問題。。。)上面的產生式中並沒體現出來該咋算分一塊,所以兩種完全不同的句子結構都是合法的。
二義性問題是有救的,大概有以下這三種辦法:
這些辦法的核心,其實都是將優先順序和結合性說明白。
核心:把優先順序和結合性說明白
既然要說明白,那就不能讓一個非終結符可以直接在當次推導中能推出會帶來優先順序和結合性歧義的東西。(對分析樹的一個內部節點,不會有出現在其下面的分支是相同的非終結符的情況。如果有得選,那就有得歧義了。沒得選才能確定地一路走到黑)
改寫為非二義文法的二義文法大概有下面這幾個特點:
改寫的關鍵步驟:
【例】改寫下面的二義文法為非二義文法。圖右側是要達成的優先順序和結合性
改寫的核心其實就兩句話:
所以能夠得到非終結符與運算的對應關系(因為不同的運算有不同的優先順序,我們想要引入多個優先順序就要引入多個新的非終結符。這樣每個非終結符就可以負責一個優先順序的運算符號,也就是說新的非終結符是與運算有關系的了。因此這里搞出來了「對應關系」四個字)如下:
優先順序由低到高分別是 +、 、-,而距離開始符號越近,優先順序越低。因此在這里的排序也可以+ -順序。每個符號對應一層的非終結符。根據所需要的結合性,則可確定是左遞歸還是右遞歸,以確定新的產生式長什麼樣子
【例】:規定優先順序和結合性,寫出改寫的非二義文法
我們已經掌握了一種叫做【改寫】的工具,能讓我們消除二義性。接下來我們就要用這個工具來嘗試搞搞懸空 else 問題!
懸空 else 問題出現的原因是 then 數量多於 else,讓 else 有多個可以結合的 then。在二義文法中,由於選哪兩個 then、else 配對都可以,故會引起出現二義的情況。在這里,我們規定 else 右結合,即與左邊最靠近的 then 結合。
為改寫此文法,可以將 S 分為完全匹配(MS)和不完全匹配(UMS)兩類。在 MS 中體現 then、else 個數相等即匹配且右結合;在UMS 中 then、else 不匹配,體現 else 右結合。
【例】:用改寫後的文法寫一個條件語句
經過檢查,無法再根據文法寫出其他分析樹,故已經消除了二義性
雖然二義文法會導致二義性,但是其並非一無是處。其有兩個顯著的優點:
在 Yacc 中,我們可以直接指定優先順序、結合性而無需自己重寫文法。
left 表示左結合,right 表示右結合。越往下的算符優先順序越高。
嗯就這么簡單。。。
我們其實可以把語言本身定義成沒有優先順序和結合性的。。然後所有的優先、結合都交由括弧進行控制,哪個先算就加括弧。把一個過程的結束用明確的標志標記出來。
比如在 Ada 中:
在 Pascal 中,給表達式加括弧:
6. 編譯原理文法
編譯原理文法的概念為:每一種自然語言或者是編程語言都需要文法來描述,文法相當於語言學的語義分析,即分析每一句話所表示的含義,編譯器需要利用文法來完成其語法分析和語義分析。
字母表是元素的非空有窮集合,字母表中的元素稱之為符號,因此,字母表也稱之為符號集。例如C語言中的字母表由字母、數字、關鍵字等組成。
符號串,就是由符號集中的元素組成的序列。例如,給定符號集a、b、c,那麼abc、abb、ac就是由該符號集組成的符號串。一個文法中,含有一個,或多個產生式,產生式,描述了將終結符集合和非終結符集合組合成串的方法。
7. 【編譯原理】第四章:語法分析
從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號S推導出詞串w的過程。
例:
總是選擇每個句型的 最左非終結符 進行替換。
總是選擇每個句型的 最右非終結符 進行替換。
在自底向上的分析中,總是採用 最左規約 的方式,因此把 最左規約 稱為 規范規約 ,對應的 最右推導 稱為 規范推導 。
最左推導、最右推導具有唯一性。
自頂向下的語法分析採用最左推導方試,總是選擇每個句型的 最左非終結符 進行替換。
由一組 過程 組成,每一個過程對應一個 非終結符 。
從文法開始符號S開始,遞歸調用文法中的其他非終結符,最終掃描整個輸入串,完成分析。
如果其間有不唯一的產生式,就可能需要退回上一步重新嘗試的情況,稱為 回溯 。
預測分析 是 遞歸下降分析 技術的一個特例,通過輸入中向前看固定個數的符號選擇正確的產生式。
如果一個文法可以構造出向前看k個符號的預測分析器,稱為LL(k)文法 。
預測分析不需要回溯,具有確定性。
含有 形式產生式的文法稱為是 直接左遞歸 的。
如果一個文法中有一個非終結符A使得對某個串存在推導 ,那麼這個文法是 左遞歸 的。其中,經過兩步或以上推導產生的左遞歸,稱為 間接左遞歸 的。
左遞歸會使遞歸下降分析器陷入無限循環。
文法
即
該文法是直接左遞歸的,會陷入無限循環。
將以上文法轉換為:
即可消除左遞歸。事實上,這個過程把左遞歸轉換成了右遞歸。
消除直接左遞歸的一般形式
使用代入法。
對於一個文法,通過改寫產生式來 推遲決定 ,等獲得足夠多的輸入信息再做正確的決定。
例:文法:
可以改寫為:
從文法的開始符號S開始,每一步推導根據當前句型的最左非終結符A和當前輸入符號α,選擇正確的A-產生式。為保證分析的確定性,選出的候選式必須是唯一的。
S_文法(簡單的確定型文法)
可能在某個舉行中緊跟在A後面的終結符a的集合,記為 FOLLOW(A) 。
如果A是某個句型的最右符號,則將結束符「 $ 」添加到FOLLOW(A)中。
例:文法:
中,FOLLOW(B) = {a, c}
產生式 的可選集是指可以選用該產生式進行推導時對應的輸入符號的集合,記為 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)
q_文法
文法符號串α串首終結符的集合,記作 FIRST(A) 。
8. 編譯原理中語法分析的作用是什麼
語法分析是搞清楚語言含義的必要條件,只有語法搞清楚了,語句表達的意思才能得到准確理解,才能得到正確實現。
9. 編譯原理
編譯原理是計算機專業的一門重要專業課,旨在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。 編譯原理是計算機專業設置的一門重要的專業課程。編譯原理課程是計算機相關專業學生的必修課程和高等學校培養計算機專業人才的基礎及核心課程,同時也是計算機專業課程中最難及最挑戰學習能力的課程之一。編譯原理課程內容主要是原理性質,高度抽象[1]。
中文名
編譯原理[1]
外文名
Compilers: Principles, Techniques, and Tools[1]
領域
計算機專業的一門重要專業課[1]
快速
導航
編譯器
編譯原理課程
編譯技術的發展
編譯的基本流程
編譯過程概述
基本概念
編譯原理即是對高級程序語言進行翻譯的一門科學技術, 我們都知道計算機程序由程序語言編寫而成, 在早期計算機程序語言發展較為緩慢, 因為計算機存儲的數據和執行的程序都是由0、1代碼組合而成的, 那麼在早期程序員編寫計算機程序時必須十分了解計算機的底層指令代碼通過將這些微程序指令組合排列從而完成一個特定功能的程序, 這就對程序員的要求非常高了。人們一直在研究如何如何高效的開發計算機程序, 使編程的門檻降低。[2]
編譯器
C語言編譯器是一種現代化的設備, 其需要藉助計算機編譯程序, C語言編譯器的設計是一項專業性比較強的工作, 設計人員需要考慮計算機程序繁瑣的設計流程, 還要考慮計算機用戶的需求。計算機的種類在不斷增加, 所以, 在對C語言編譯器進行設計時, 一定要增加其適用性。C語言具有較強的處理能力, 其屬於結構化語言, 而且在計算機系統維護中應用比較多, C語言具有高效率的優點, 在其不同類型的計算機中應用比較多。[3]
C語言編譯器前端設計
編譯過程一般是在計算機系統中實現的, 是將源代碼轉化為計算機通用語言的過程。編譯器中包含入口點的地址、名稱以及機器代碼。編譯器是計算機程序中應用比較多的工具, 在對編譯器進行前端設計時, 一定要充分考慮影響因素, 還要對詞法、語法、語義進行分析。[3]
1 詞法分析[3]
詞法分析是編譯器前端設計的基礎階段, 在這一階段, 編譯器會根據設定的語法規則, 對源程序進行標記, 在標記的過程中, 每一處記號都代表著一類單詞, 在做記號的過程中, 主要有標識符、關鍵字、特殊符號等類型, 編譯器中包含詞法分析器、輸入源程序、輸出識別記號符, 利用這些功能可以將字型大小轉化為熟悉的單詞。[3]
2 語法分析[3]
語法分析是指利用設定的語法規則, 對記號中的結構進行標識, 這包括句子、短語等方式, 在標識的過程中, 可以形成特殊的結構語法樹。語法分析對編譯器功能的發揮有著重要影響, 在設計的過程中, 一定要保證標識的准確性。[3]
3 語義分析[3]
語義分析也需要藉助語法規則, 在對語法單元的靜態語義進行檢查時, 要保證語法規則設定的准確性。在對詞法或者語法進行轉化時, 一定要保證語法結構設置的合法性。在對語法、詞法進行檢查時, 語法結構設定不合理, 則會出現編譯錯誤的問題。前端設計對精確性要求比較好, 設計人員能夠要做好校對工作, 這會影響到編譯的准確性, 如果前端設計存在失誤, 則會影響C語言編譯的效果。[3]
10. 如何通俗易懂地解釋編譯原理中語法分析的過程
分成詞法分析,語法分析(LL演算法,遞歸下降演算法,LR演算法),語義分析,運行時環境,中間代碼,代碼生成,代碼優化這些部分。其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的,所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式,包括國內的教材也是如此。一般來說,大學裡面的本科教學是不可能把上面的所有部分都認真講完的,而是比較偏重於前面幾個部分。像代碼優化那部分東西,就像個無底洞一樣,如果要認真講,就是單獨開一個學期的課也不可能講得清楚。所以,一般對於本科生,對詞法分析和語法分析掌握要求就相對要高一點了。
詞法分析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧,很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的時候,重點把正則表達式和自動機原理加了進來,然後以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯,就是要讓詞法分析從程序上升到理論的地步。
語法分析部分就比較麻煩一點了。現在一般有兩種語法分析演算法,LL自頂向下演算法和LR自底向上演算法。LL演算法還好說,到了LR演算法的時候,困難就來了。很多自學編譯原理的都是遇到LR演算法的理解成問題後就放棄了自學。其實這些東西都是只要大家理解就可以了,又不是像詞法分析那樣非得自己寫出來才算真正的會。像LR演算法的語法分析器,一般都是用工具Yacc來生成,實踐中完全沒有比較自己來實現。對於LL演算法中特殊的遞歸下降演算法,因為其實踐十分簡單,那麼就應該要求每個學生都能自己寫。當然,現在也有不少好的LL演算法的語法分析器,不過要是換在非C平台,比如Java,Delphi,你不能運用YACC工具了,那麼你就只有自己來寫語法分析器。