導航:首頁 > 源碼編譯 > 編譯原理輸入文法

編譯原理輸入文法

發布時間:2023-03-31 04:20:17

A. 編譯原理

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

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

(1)編譯原理輸入文法擴展閱讀:

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

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

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

B. 編譯原理文法

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

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

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

C. 編譯原理實驗報告

#include<stdio.h>
void main()
{

int m=0,n=0,n1=0,n2=0,n3=0,zg,fzg,flag;
int bz[7]=;/*狀態改變控制,1 表示可以改變狀態zt值,0 表示不可以*/
int zt[7]=;/*狀態值,2表示未定狀態,1表示 是,0表示 否*/

char temp[100]="\0";/*用於求first集*/
char z[7];/*非總結符*/
char z1[7];/*總結符*/
char z2[7]="\0";/*gs[]文法中出現的標記個數的輔助字元 01234*/
char gs[100]="\0";/*文法,按順序排成字元串*/

printf("請依次輸入非終結符(不超過7個):");
gets(z);
while(z[m]!='\0')

fzg=m;//zg是非終結符個數

while(n<m)
//生成01234輔助字元
printf("您輸入了:");
puts(z);
fflush(stdin);

printf("請依次輸入終結符(不超過7個):");
gets(z1);
while(z1[n1]!='\0')

zg=n1;
printf("您輸入了:");
puts(z1);
fflush(stdin);

printf("按照正確格式輸入所有文法(總長度不超過100格式如下):");
printf("如果文法為(字元'k'表示空):\n");
printf("S-->AB S-->bC A-->k A-->b\n");
printf("輸入:0SAB0SbC1Ak1Ab\n");
printf(" (注:數字01234表示第一二三四個非終結符)\n");

gets(gs);
fflush(stdin);
printf("您輸入了:");
puts(gs);
m=0;
//對於輸入文法字元串的轉換,將每個文法式左部去除
while(gs[m]!='\0')
{
n=m;
if(gs[m]>='0'&&gs[m]<='9')
{
m++;
while(gs[m]!='\0')
{
gs[m]=gs[m+1];
m++;
}
//gs[m-1]='\0';
}
m=++n;
}

m=0;

//puts(gs);

/*情況一,直接判定是 形如: (A-->k) */
while(gs[m]!='\0')
{
if(gs[m]=='k')
{
zt[gs[m-1]-48]=1;
bz[gs[m-1]-48]=0;
}
m++;
}

/*情況二,直接判定--否 形如: (D-->aS ,D-->c) */
for(n=0;n<fzg;n++)
{
if(bz[n]==1)
{
m=0;
n2=0;
while(gs[m]!='\0')
{
if(z2[n]==gs[m])
{
if(gs[m+1]>=z1[0]&&gs[m+1]<=z1[n1-1])
zt[n]=0;
else //gs[m+1] 是非終結符n2做標記
}
//跳出循環,無法解決該情況,推到下面情況三
m++;
}
if(n2!=99) //完成所有掃描,未出現非終結符,得出結論zt[n]=0.bz[n]=0不允許再改變zt[n]
}
}

/*情況三,最終判定*/
do
{
flag=0;
for(n=0;n<fzg;n++)
{
if(bz[n]==1) //未得到判定
{ m=0;
while(gs[m]!='\0')
{
if(gs[m]==z2[n]) //判定gs[m]是輔助字元0123
{
m++;
while(gs[m]>='A'&&gs[m]<='Z')
{

n1=0;
for(n2=0;n2<fzg;n2++) //循環查找是gs[m]哪個非終結符
{
if(gs[m]==z[n2])
{
if(zt[n2]==1) //這個非終結符能推出空
zt[n]=1;
else if(bz[n2]==1) //這個非終結符 現在 不能推出空,但它的狀態可改即它最終結果還未判定

else
//設 m1 做標記供下一if參考
break; //找到gs[m]是哪個非終結符,for循環完成任務,可以結束
}

}
if(n1==99) break;
m++;
}
}
m++;
}
if(zt[n]==1) bz[n]=0;
if(bz[n]==0) flag=1;//對應for下的第一個if(zt[n]==2)
}

}
}while(flag);

printf("結果是:\n");

for(m=0;m<5;m++)
{
switch(zt[m])
{
case 0:printf("%c---否\n",z[m]);break;
case 1:printf("%c---是\n",z[m]);break;
case 2:printf("%c---未定\n",z[m]);break;
}

}
/*
puts(gs);
puts(zt);
puts(z);
puts(z1);
puts(z2);
printf("%d,,,%d",fzg,zg);
*/

//下面求first集
//下面求first集

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

m=0;n=0;n1=0;n2=0;
while(gs[n]>='0'&&gs[n]<='9')
{
for(;m<fzg;m++)
{
if(n2!=m)
n1=0; //m=n2用於第二次以後的for循環中還原上次m的值

if(gs[n]==z2[m])
{
while(gs[n+1]>'9')
{
if(n1==0)
//如果是第一個直接保存

//不是第一個,先與字元數組中其它字元比較,沒相同的才保存
else if(gs[n]>='a'&&gs[n]<='z'&&gs[n+1]>='A'&&gs[n+1]<='Z') //gs[n]是終結符 且 gs[n+1]是非終結符
;//什麼也不做,程序繼續n++,掃描下一個gs[n]

else
{
for(n3=0;n3<=n1;n3++)
{
if(temp[m*13+n3]==gs[n+1])
break;
}

if(n3>n1) //for循環結束是因為n3而不是break

}
n++;
}
break; //break位於if(gs[n]==z2[m]),對於gs[n]已找到z2[m]完成任務跳出for循環
}
}
n2=m; //存放該for循環中m的值
n++;
}
//進一步處理集除去非終結符
m=0;n=0;n1=0;n2=0;
for(m=0;m<fzg;m++)
{
if(flag!=m)
n1=0; //m=flag用於第二次以後的for循環中還原上次m的值

while(temp[m*13+n1]!='\0')
{
while(temp[m*13+n1]>='A'&&temp[m*13+n1]<='Z') //搜索非終結符
{
for(n=0;n<fzg;n++) //確定是哪個非終結符
{if(temp[m*13+n1]==z[n])
break;
}
while(temp[m*13+n1]!='\0') //從temp[n*13+n1]開始每個字元依次往前移動一

n1--;
while(temp[n*13+n2]!='\0') //把z[n]對應的first加入temp[m*13+n1]這個first中,每個字元依次加在最後
{
for(n3=0;n3<n1;n3++) //循環判定是否有相同的字元
{
if(temp[m*13+n3]==temp[n*13+n2])
break;
}
if(temp[n*13+n2]=='k'&&zt[m]==0) //那些不能推出 空,但是因為要加入 其他非終結符的first集 而可能含有 空
n2++;
else if(n3>=n1) //for循環結束是因為n3而不是break ,即無相同字元

else n2++;
}

n1=0;
n2=0;
}

n1++;
}
flag=m; //存放該for循環中m的值
}

//非終結符的first集輸出
m=0;n1=0;
for(m=0;m<fzg;m++)
{
n1=0;
printf("非終結符 %c 的first集是: ",z[m]);
while(temp[m*13+n1]!='\0')
{
printf("%c",temp[m*13+n1]);
n1++;
}
printf("\n");
}

}

D. 編譯原理中如何用c語言來編寫程序判斷輸入的字元串是否符合文法規則

scanf()有返回值,若返回值是0,則不正握符合文法規則
一般情況下,scanf()返回值是扮頃輸廳清陸入的字元數

E. 編譯原理 文法類型

    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型文法

F. 編譯原理:FIRST(A) 集合與FOLLOW(A)集合

1.設計一個演示窗口,包括幾本的操作按鈕和顯示窗口; 2.設計first集合和follow集合生成演算法 3.輸入文法,按要求顯示first集合和follow集合

G. 編譯原理-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(α) 包括空串ε,那麼這個產生式是不是間接左遞歸。

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

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

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

(8)編譯原理輸入文法擴展閱讀

詞法分析器的作用:

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

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

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

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


I. 【編譯原理】第四章:語法分析

從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號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)

J. 編譯原理 LR0文法的判定

設G1、G2是兩個文法,若L(G1)=L(G2)
,則稱G1與G2等價,記作G1≡G2。
即:文法的等價性是指他們所定義的語言是一樣的。
文法的化簡是指消除如下無用產生式:

刪除
A->A
形式數橡的產生式(自定己);

刪除不能從其推導出終結符串的產生式(不終結差旦);

刪除在推導中永不使用的產生式(不可用虛畢擾)。

閱讀全文

與編譯原理輸入文法相關的資料

熱點內容
文件夾圖標如何改成公會logo 瀏覽:973
怎樣創建job文件夾 瀏覽:831
介紹單片機外設的書籍推薦 瀏覽:56
通達信雙柱擒牛指標源碼 瀏覽:467
內存太大解壓失敗怎麼辦 瀏覽:441
linuxmakefile解析 瀏覽:777
單片機原理與應用李林功 瀏覽:39
pythonorm框架有哪些 瀏覽:431
indesign轉pdf 瀏覽:483
javaweb找源碼 瀏覽:26
浪潮物理伺服器如何重啟 瀏覽:602
aes加密性能下降 瀏覽:449
linux驅動結構 瀏覽:868
psv安裝壓縮包 瀏覽:613
錦州聯通DNS伺服器地址 瀏覽:115
伺服器佔用太多的網路怎麼辦 瀏覽:936
設置ftp共享文件夾win10 瀏覽:793
伺服器和主機是什麼意思 瀏覽:638
自製透明收納文件夾 瀏覽:164
testflight怎麼下載安卓軟體 瀏覽:180