編譯原理中浮點數的文法
A. 編譯原理-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(α) 包括空串ε,那麼這個產生式是不是間接左遞歸。
B. 編譯原理的,要詳細的
^\d+\.\d+E[-+]?\d+$
C. 編譯原理-文法定義
文法定義公式如下:
Chomsky 文法分類將文法分為四種,0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。
又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法(Phrase Structure Grammar)
定義: 對於產生式 α→β , α 至少包含一個非終結符。
為什麼要叫無限制文法,明明它要求產生式的左部必須包含一個非終結符。
又被稱為上下文有關文法(Context-Sensitive Grammar)
定義:對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外
為什麼叫做上下文有關文法?
一般情況下,這種產生式的形式為 α1Aα2→α1βα2
又被稱為上下文無關文法(Context-Free Grammar)
定義:對任一產生式 α→β ,都有 α∈VN,β∈(VN∪VT)*
為什麼叫上下文無關文法?
又被稱為正則文法(Regular Grammar,RG),分為右線性(Right Linear)文法和左線性(Left Linear)文法。
定義: 對任一產生式 α→β ,都有 α∈VN,β最多兩個字元元素,如果有二個字元必須是(終結符+非終結符)的格式,如果是一個字元,那麼必須是終結符。
根據產生式右部非終結符位置不同,分為右線性文法和左線性文法。
可以看出,不同文法就是對產生式進行逐層的限制,所以各個文法是包含關系,即0型文法包含1型文法;1型文法又包含2型文法;2型文法最後包含3型文法。
D. 編譯原理文法
編譯原理文法的概念為:每一種自然語言或者是編程語言都需要文法來描述,文法相當於語言學的語義分析,即分析每一句話所表示的含義,編譯器需要利用文法來完成其語法分析和語義分析。
字母表是元素的非空有窮集合,字母表中的元素稱之為符號,因此,字母表也稱之為符號集。例如C語言中的字母表由字母、數字、關鍵字等組成。
符號串,就是由符號集中的元素組成的序列。例如,給定符號集a、b、c,那麼abc、abb、ac就是由該符號集組成的符號串。一個文法中,含有一個,或多個產生式,產生式,描述了將終結符集合和非終結符集合組合成串的方法。
E. 【編譯原理】第二章:語言和文法
上述文法 表示,該文法由終結符集合 ,非終結符集合 ,產生式集合 ,以及開始符號 構成。
而產生式 表示,一個表達式(Expression) ,可以由一個標識符(Identifier) 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹( )構成。
約定 :在不引起歧義的情況下,可以只寫產生式。如以上文法可以簡寫為:
產生式
可以簡寫為:
如上例中,
可以簡寫為:
給定文法 ,如果有 ,那麼可以將符號串 重寫 為 ,記作 ,這個過程稱為 推導 。
如上例中, 可以推導出 或 或 等等。
如果 ,
可以記作 ,則稱為 經過n步推導出 ,記作 。
推導的反過程稱為 歸約 。
如果 ,則稱 是 的一個 句型(sentential form )。
由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ,記作 。
即:
例
文法
表示什麼呢?
代表小寫字母;
代表數字;
表示若干個字母和數字構成的字元串;
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是,以字母開頭的、非空的字元串,即標識符的構成方式。
並、連接、冪、克林閉包、正閉包。
如上例表示為:
中必須包含一個 非終結符 。
產生式一般形式:
即上式中只有當上下文滿足 與 時,才能進行從 到 的推導。
上下文有關文法不包含空產生式( )。
產生式的一般形式:
即產生式左邊都是非終結符。
右線性文法 :
左線性文法 :
以上都成為正則文法。
即產生式的右側只能有一個終結符,且所有終結符只能在同一側。
例:(右線性文法)
以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串(標識符)。
以上文法等價於 上下文無關文法 :
正則文法能描述程序設計語言中的多數單詞。
正則文法能描述程序設計語言中的多數單詞,但不能表示句子構造,所以用到最多的是CFG。
根節點 表示文法開始符號S;
內部節點 表示對產生式 的應用;該節點的標號是產生式左部,子節點從左到右表示了產生式的右部;
葉節點 (又稱邊緣)既可以是非終結符也可以是終結符。
給定一個句型,其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2,那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。
直接短語一定是某產生式的右部,但反之不一定。
如果一個文法可以為某個句子生成 多棵分析樹 ,則稱這個文法是 二義性的 。
二義性原因:多個if只有一個else;
消岐規則:每個else只與最近的if匹配。
F. 編譯原理文法分析
改完了,能文法分析出來了!!
大概 跟你說下 你的錯誤吧:
出錯地點:
1.聲明的stack[50]沒有初始化;
2.stack的入棧是錯誤的,按照你的方式,如果原來有TM,再加入T->FN,則M就被擠出來了.(這里很關鍵,你對照我給你改的再看看)
3.s指針在你入棧操作以後並沒有指向棧頂,而是保持了不變,這肯定是有問題的.(傳入push函數的時候直接傳參數s就好了.)
4.if(*s==*p){***}else{}的else的右括弧管轄的范圍 有錯誤
不嫌棄的話,可以去http://blog.csdn.net/fangguanya,我的BLOG,不怎麼充實,呵呵,有這個程序的運行結果的. 謝謝 呵呵.
總之你對照我給你改的再看看吧. 我把我的測試輸出 也給保留了.你好對照點.
(PS.我用的vs2005,用的時候你改下頭申明,其他一樣)
// grammar.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
char * spush(char *stack,char *pt);
bool analyse(char *p);
void main()
{
//將分析串存放在二維數組中
char input[5][10]={"i+i#",
"i*(i+i)#",
"i*i+i#",
"i+*#",
"+i*i#"};
bool flag; //定義一個布爾型的標記量
for(int h=0;h<5;++h)
{
flag=analyse(input[h]);
if(flag) cout<<"恭喜你!"<<input[h]<<"語法分析成功,合法!"<<endl;
else cout<<"對不起!"<<input[h]<<"語法分析失敗,非法!"<<endl;
}
int aaa;
cin>>aaa;
}
//定義各一將串逆序入棧的函數
char * spush(char *stack,char *pt)
{
int l=0;
//while循環的作用是將指針指向字元串的末尾,然後再由後向前入棧,從而實現逆序
while(*pt!='\0')
{
pt++;
l++;
}
if (*stack == '#')
{
stack++;
}
while(l)
{
pt--;
char cTempIntoStack = (*pt);
*stack=cTempIntoStack;
stack++;
l--;
}
stack--; //由於前面向前加了一位,要返回
////////////////
return stack;
///////////////////////////////////
}
/*LL(1)分析表
i + * ( ) #
E TM +TM
F i (E)
M TM e e
N e *FN e e
T FN FN
*/
//分析函數
bool analyse(char *p){
char analyseTable[5][6][4]={
"TM", "", "", "TM", "", "",
"i", "", "", "(E)", "", "",
"", "+TM", "", "", "e", "e",
"", "e", "*FN", "", "e", "e",
"FN", "", "", "TN", "", ""
};
char *stack = new char[50]; //定義一個棧空間
for (int iStack = 0;iStack<50 ;iStack++)
{
stack[iStack] = 0;
}
char *s=stack; //用指針*s指向棧的起始地址
*s='#'; //將「#」入棧
s++; //指針加1
*s='E'; //將「E」入棧
//下面的while循環實現字元串的詞法分析操作
int count = 0;
while(*s!='#' || *p!='#'){
count++;
char * temp = s;
cout<<"NO."<<count<<endl;
cout<<"STACK"<<endl;
while (*temp != '#')
{
cout<<*temp<<" ";
temp--;
}
cout<<endl;
int x,y;
//若果棧頂數據和分析串的字元匹配,則將符號棧的棧頂數據出棧(即將棧頂指針減1)
if(*s==*p){
cout<<"Before :"<<*s<<endl;
s--;
p++;
cout<<"After :"<<*s<<endl;
}
//當符號棧和分析串的字元不匹配時,查分析表
else {
switch(*s){
case 'E':x=0;break;
case 'F':x=1;break;
case 'M':x=2;break;
case 'N':x=3;break;
case 'T':x=4;break;
default:return false;
}
switch(*p){
case 'i':y=0;break;
case '+':y=1;break;
case '*':y=2;break;
case '(':y=3;break;
case ')':y=4;break;
case '#':y=5;break;
default:return false;
}
//若果對應的為空,則分析串非法,退出
if(analyseTable[x][y][0]=='\0') return false;
//若查表所對應的為'e',則將符號棧的棧頂數據出棧
else if(analyseTable[x][y][0]=='e') s--;
//其它,這時將查表所得的項逆序入符號棧
else {
s=spush(s,analyseTable[x][y]);
}
}
}
return true; //分析成功,返回
}
G. 四種文法的類型(編譯原理)
喬姆斯基(Chomsky)按產生式的類型把文法分為四種類型:0、1、2、3型文法。
*在下文中的產生式中,箭頭左邊的大寫字母為嚴格的非終結符,而其左邊的小寫字母不嚴格要求為非終結符,如[0型文法]中的第2條產生式。
【0型文法】
產生式形式:α→β
要求:箭頭左邊的α 至少 含有 一個非終結符 , 其餘 不加任何限制
例如,G:C→AaB
aA→a
B→b|Bb
【1型文法】
產生式形式:α→β
要求: |α|≤|β| (產生式左端的長度<=右端的長度),S→ε除外。
例如G: C→aAB
aA→aBa
B→b|Bb
【2型文法】(上下文無關文法)
產生式形式:A→β,A∈VN(終結符) ,β∈V *(VN∪VT,即可為終結符也可為非終結符)
說明:當以β替換A時,與A的上下文環境無關;
大部分程序設計語言近似於2型文法。
【3型文法】(正規文法 / 右線性文法)
產生式形式:A→a,A→aB,
說明:a∈VT(終結符) , A,B∈VN(非終結符),即產生式右端的第一個符號必須為 終結符
例如 G:A→aB
B→b|bB
【其他說明】對於這四種類型的文法:
*包含關系:0 > 1 > 2 > 3 (以'>'代替包含符,'A>B'譯為A包含B)
*嚴格程度:3 > 2 > 1 > 0
*判斷文法所屬類型的順序:3 → 2 → 1 → 0
H. 編譯原理的文法是什麼
文法是描述語言規則的形式規則。實際上就是用一個四元組G=(VT,VN,S,P)定義的一個推理方式。其中VT是終結符,VN是非終結符,S是開始符號,P是一組產生規則。
I. 編譯原理 文法類型
0型文法(Type-0 Grammar)
1型文法(Type-1 Grammar)
2型文法(Type-2 Grammar)
3型文法(Type-3 Grammar)
無限制文法(Unrestricted Grammar) /短語結構文法(Phrase Structure Grammar, PSG )
∀α → β∈P, α中至少包含1個非終結符
0型語言
由0型文法G生成的語言L(G )
上下文有關文法(Context-Sensitive Grammar , CSG )
∀α → β∈P,|α|≤|β|
產生式的一般形式: α1Aα2 → α1βα2 ( β≠ε )
上下文有關語言(1型語言)
由上下文有關文法(1型文法) G生成的語言L(G )
上下文無關文法(Context-Free Grammar, CFG )
∀α → β∈P,α ∈ VN
產生式的一般形式:A→β
上下文無關語言(2型語言)
由上下文無關文法(2型文法) G生成的語言L(G )
正則文法(Regular Grammar, RG )
右線性(Right Linear)文法: A→wB 或 A→w
左線性(Left Linear) 文法: A→Bw 或 A→w
左線性文法和右線性文法都稱為正則文法
0型文法:α中至少包含1個非終結符
1型文法(CSG) :|α|≤|β|
2型文法(CFG) :α ∈ VN
3型文法(RG):A→wB 或 A→w (A→Bw 或A→w)
0型文法包含1型文法,1型文法包含2型文法,2型文法包含3型文法