[XJTUSE编译原理] 第三章 上下文无关文法
文章目錄
- 第三章 上下文無關文法
- 3.1 引言
- 3.2 文法與語言
- 定義
- 各個符號的意義
- 習慣記號
- 推導與語言
- 3.3 語法樹與二義性
- 語法樹
- 二義性
- 參考資料
第三章 上下文無關文法
目的:
對語言的語法結構進行形式描述
從形式描述中,研究語法分析器的構造(分析法遞歸子程序和算符優先分析法)
3.1 引言
文法:是描述語言的語法結構的形式規則(即語法規則),是為了解決語言的有窮說明問題,包含對語法的描述,但是不表達任何語義
文法的描述應該達到以下要求:形式上嚴格,準確;易于理解;描述能力強;有利于句子的分析和翻譯,構造語法分析器
文法的分類:分為四類(0,1,2,3型文法);與程序語言語法有關的是上下文無關文法
上下文無關文法的特點:它所定義的語法范疇(或語法單位)完全獨立于這種范疇可能出現的環境。
上寫文無關文法只能描述一部分語言,但是已經足夠描述現今的程序設計語言
自然語言要用別的描述方法
3.2 文法與語言
定義
一個上下文無關文法G是一個四元式(VT,VN,S,P)(V_T,V_N,S,P)(VT?,VN?,S,P)
VNV_NVN?:是非空有限集合,它的每個元素是非終結符號
VTV_TVT?:是非空有限集合,它的每個元素是終結符號
VN∩VN=?VT∪VN=VV_N\cap V_N=\empty\qquad V_T\cup V_N=VVN?∩VN?=?VT?∪VN?=V
SSS:S∈VNS\in V_NS∈VN?,稱為開始符號(相當于有限自動機的初態)
P\mathscr{P}P:產生式集合(有限),每個產生式是
{P→α∣P∈VN,α∈(VT∪VN)?,S至少一次為P}\{P\rightarrow \alpha|P\in V_N,\alpha \in (V_T\cup V_N)^* ,S至少一次為P\}{P→α∣P∈VN?,α∈(VT?∪VN?)?,S至少一次為P},S即要在左邊至少出現一次
“→\rightarrow→" 相當于isdefinedasis\ defined \ asis?defined?as
舉例:考慮以下算數表達式的文法以及語言
VTV_TVT?: id + - * / ↑ ( )
VNV_NVN?:表達式、運算符
SSS: 表達式
P\mathscr{P}P: 表達式->表達式 運算符 表達式
表達式->(表達式)
表達式->— 表達式
表達式-> id
運算符->+|-|*|/|↑
得到文法G1(E) : E->EAE|(E)|-E|id A->+|-|*|/|↑
由此可見,文法G1(E)所定義的語言是算術表達式,如id+id,id*(id+id)等
它表達了簡單算術表達式由id用A連接起來
該文法的:
1?? VNV_NVN?是出現在P的左部所有符號集合
2?? V是P\mathscr{P}P的所有符號:VT=V/VNV_T=V/V_NVT?=V/VN?
3?? S是該文法所定義的句子名字
4?? 寫出了P\mathscr{P}P,就能找出其它三元素
各個符號的意義
1?? 終結符:是用以組成語言中的串的基本符號,與程序語言中的“單詞”是同義語
如表達式 id+(id)?(?id)id+(id)^*(-id)id+(id)?(?id)中,+、-、*、/、id均為終結符
2?? 非終結符:非終結符號(也稱語法變量)用來代表語法范疇。例如,“算術表達式”“布爾表達式”“賦值句”“分程序”“過程”等,它們都是現今程序語言常見的語法范疇。我們也可以說,一個非終結符代表一個一定的語法概念。因此,一個非終結符是一個類(或集合)記號,而不是一個個體記號。例如,算術表達式"這個非終結符乃代表一定算術式組成的類。因而,也可以說,每個非終結符號表示一定符號串的集合(由終結號和非終結符號組成的符號串)。
3?? 開始符號:一個特殊的非終結符,標記最終感興趣的語法范疇(句子),其他非終結符用以定義其他的串集,這有助于定義該語言,也有助于為它處理的語言提供一個分層的結構
4?? 產生式:規定由終結符和別的語法范疇組成一個新的語法范疇的辦法
結構:非終結符->一串非終結符和終結符
如:A->α,A是左部符號VNV_NVN?,α是右部候選式,α=X1X2X3...XN,Xi∈V\alpha=X_1X_2X_3...X_N,X_i\in Vα=X1?X2?X3?...XN?,Xi?∈V
舉例
語法規則如下:
<句子> → <主語> <謂語> <間接賓語> <直接賓語>
<主語> → <代詞>
<謂語> → <動詞>
<間接賓語> → <代詞>
<直接賓語> → <冠詞> < 名詞>
<代詞> → He
<代詞> → me
<名詞> → book
<冠詞> → a
<動詞> → gave
比如He gave me a book是一個語法正確的句子
👉 該語法范疇叫"句子",在程序語言中叫“ 程序”
👉 語言的句子是由一串VNV_NVN?定義,到最后才是一串VTV_TVT?
習慣記號
VNV_NVN?:大寫字母A、B、C、S等
VTV_TVT?:小寫字母,0~9,+,-等運算符,標點,分界符,黑體字母串,id,if
X、Y、Z:文法符號,或VNV_NVN?或VTV_TVT?一個符號
u、v、w……z:VTV_TVT?中的串
α、β、γ:文法符號串∈(VT∪VN)?\in (V_T\cup V_N)^*∈(VT?∪VN?)?
S:開始符號,第一個產生式中出現
->:定義為(元語言符號)
|:或(元語言符號)
推導與語言
? 問題:用文法如何定義一個語言?
思路:從S出發,反復使用P\mathscr{P}P,對非終結符替換展開,最后得到全部由終結符串組成的一個串
涉及到:替換、推導、句型、句子、語言
1?? 直接推出:是兩個文法符號串之間的一種關系R\mathscr{R}R
如:(αAβ)R(αγβ)(\alpha \ A \ \beta)\ \mathscr{R}\ (\alpha \ γ \ \beta)(α?A?β)?R?(α?γ?β)
它表示,若A→γ∈P,α,β∈V?A\rightarrow γ \in \mathscr{P},\ \alpha,\beta \in V^*A→γ∈P,?α,β∈V?,則R\mathscr{R}R就是直接推出,R\mathscr{R}R記作?\Rightarrow?
則有:(αAβ)?(αγβ)(\alpha \ A \ \beta)\ \Rightarrow (\alpha \ γ \ \beta)(α?A?β)??(α?γ?β)
2?? 推導:如果兩個串u0,unu_0,u_nu0?,un?,存在一個串序列
u0?u1?...?unu_0\Rightarrow u_1 \Rightarrow ... \Rightarrow u_n u0??u1??...?un?
則u0R1unR1記作?+或??u_0\ \mathscr{R}_1\ u_n\quad \mathscr{R}_1記作\mathop\Rightarrow\limits ^+或\mathop\Rightarrow\limits ^*u0??R1??un?R1?記作?+或??
+:至少一步推導。*:可以0步推導
3?? 如何從推導引出語言
? u0?+unu_0\mathop\Rightarrow\limits ^+ u_nu0??+un? u0??unu_0\mathop\Rightarrow\limits ^* u_nu0???un?
🌵如果令u0u_0u0?為S,即推導要從開始符號開始,那么S??α,α∈V?S\mathop\Rightarrow\limits ^* \alpha,\alpha\in V^*S??α,α∈V?,則稱α為G的句型
🌵 如果再要求α∈VT?\alpha \in V_T^*α∈VT??,則稱α\alphaα為G的句子
🌵 文法G產生的句子的全體是一個語言,記作L(G)
L(G)={α∣S?+α&α∈VT?}L(G)=\{\alpha |S \mathop\Rightarrow\limits ^+ \alpha \ \&\ \alpha \in V_T ^*\} L(G)={α∣S?+α?&?α∈VT??}
說明
① 由文法G定義語言L需依賴一種運算,即關系?+\mathop\Rightarrow\limits ^+?+
當V*中有許多串,只有那些(S, u) (S,v)存在?+\mathop\Rightarrow\limits ^+?+關系的u,v才是語言中的句子。
② α , β是句型,表示(S, α) (S, β)有??\mathop\Rightarrow\limits ^*??的關系,但它們的構成是不全屬于VTV^TVT的字符。
③ G的句型集,是指存在S??αS\mathop\Rightarrow\limits ^* \alphaS??α關系的所有α,該集的子集是L(G)。
④L(G)?句型集?V?L(G)\subset 句型集 \subset V^*L(G)?句型集?V?
題目
關于句型、句型集、句子、語言等概念,下面哪些說法是不正確的?
A 終結符串是句子(句子是終結符串)
B 終結符與非終結符的混合串是句型
C 終結符集合的閉包是語言
D 全體符合集合的閉包是甸句集
ABCD
舉例:根據文法G: E->E+E|E*E|(E)|i,句子i1?(i2+i3)i_1*(i_2+i_3)i1??(i2?+i3?)的推導過程如下
1?? E=>E?E=>i1?E=>i1(E)=>i1?(E+E)=>i1?(i2+E)=>i1?(i2+i3)E=>E*E=>i_1*E=>i_1(E)=>i_1*(E+E)=>i_1*(i_2+E)=>i_1*(i_2+i_3)E=>E?E=>i1??E=>i1?(E)=>i1??(E+E)=>i1??(i2?+E)=>i1??(i2?+i3?)
最左推導
2?? E=>E?E=>E?(E)=>E?(E+E)=>E?(E+i3)=>E?(i2+i3)=>i1?(i2+i3)E=>E*E=>E*(E)=>E*(E+E)=>E*(E+i_3)=>E*(i_2+i_3)=>i_1*(i_2+i_3)E=>E?E=>E?(E)=>E?(E+E)=>E?(E+i3?)=>E?(i2?+i3?)=>i1??(i2?+i3?)
最右推導
從一個句型到另一個句型的推導過程并不唯一,但是通常只考慮最左推導和最右推導
最左推導是指,任何一步a=> β都是對a中的最左非終結符進行替換。
最右推導是指,任何一步a=> β都是對a中的最右非終結符進行替換。
3.3 語法樹與二義性
語法樹
目的:為了理解句子的語法,即理解句子如何從開始符號推導得到,因此引入“圖”。
定義:句型推導的圖形表示,與替換順序的選取無關。
作用:明顯地形成文法所暗含句子的分層語法結構,為語法分析提供一些新的途徑。
樹的內結點:非終結符A標記,若A->XYZ,則該產生式的一棵子樹為
語法樹與文法概念的對應關系如下
| 內結點A | VN |
| 葉 | 文法符號 |
| 子樹 | 直接推導 |
| 根結點 | S |
| 任意一次全剪 | 句型 |
| 葉子∈VT時,將葉子順序排列 | 句子 |
有的文法,對于同一句子,應用不同規則進行推導得到不同的語法樹
沒有區分優先級
舉例 E?+?(id+id)E\mathop\Rightarrow\limits^+ -(id+id)E?+?(id+id)的語法樹
最左推導:E=>-E=>-(E)=>- (E+E) =>-(id+E) =>- (id+id)
最右推導:E=>-E=>-(E) =>- (E+E) =>-(E+id)=>- (id+id)
每一個中間過程,句型很容易獲取
樹忽略了符號的替換順序的不同,不同的推導過程得到相同的語法樹
有的文法,對于同一句子,應用不同規則進行推導會得到不同的語法樹
舉例:根據文法G對句子id+id*id進行推導
文法G:E->E+E|E*E|(E)|i
推導1
E=>E+E=>id+E=>id+E*E=>id+id*E=>id+id*id
推導2
E=>E*E=>E+E*E=>id+E*E=>id+id*E=>id+id*id
二義性
文法G的某一個句子有兩棵不同的樹,則G為二義的
作為描述程序語言的上下文無關文法,有以下限制
1?? G不含以下產生式:P->P
2?? 每一P∈VNP∈V_NP∈VN?,必須都有用處,即?s??αPβ\exists s\mathop\Rightarrow\limits^* \alpha P \beta?s??αPβ,P在句型中出現
?γ∈VT?,P?+γ\exists γ\in V_T^*,P\mathop\Rightarrow\limits^+γ?γ∈VT??,P?+γ,即對P不存在不終結的回路
題目
關于文法二義性、語言二義性,下面哪些說法是正確的?
1?? 只要存在某個句子有兩棵不同的語法樹,文法就是二義的。
2?? 無法判定所有句子均沒有兩棵不同的語法樹,即無法判定文法是否無二義。
3?? 對于語言來說只要存在無二義的文法它就不是二義的。
4?? 對于語言來說,無法判定其不存在無二義的文法,即無法判定語言是否二義。
ABCD
參考資料
[1] 西安交通大學軟件工程專業編譯原理 吳曉軍 2022春
[2] 陳火旺,劉春林,譚慶平,趙克佳,劉越. 程序設計語言編譯原理(第3版). 北京:國防工業出版社,2010/20132017
總結
以上是生活随笔為你收集整理的[XJTUSE编译原理] 第三章 上下文无关文法的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 计算机硬件性能指标参考
- 下一篇: kafka 命令重新启动_命令行基础知识