文章目錄

• 第三章 上下文無關文法
• • 3.1 引言
  • 3.2 文法與語言
  • • 定義
    • 各個符號的意義
    • 習慣記號
    • 推導與語言
  • 3.3 語法樹與二義性
  • • 語法樹
    • 二義性
  • 參考資料

第三章 上下文無關文法

目的：

對語言的語法結構進行形式描述

從形式描述中，研究語法分析器的構造（分析法遞歸子程序和算符優先分析法）

3.1 引言

文法：是描述語言的語法結構的形式規則（即語法規則），是為了解決語言的有窮說明問題，包含對語法的描述，但是不表達任何語義

文法的描述應該達到以下要求：形式上嚴格，準確；易于理解；描述能力強；有利于句子的分析和翻譯，構造語法分析器

文法的分類：分為四類(0,1,2,3型文法)；與程序語言語法有關的是上下文無關文法

上下文無關文法的特點：它所定義的語法范疇（或語法單位）完全獨立于這種范疇可能出現的環境。

上寫文無關文法只能描述一部分語言，但是已經足夠描述現今的程序設計語言

自然語言要用別的描述方法

3.2 文法與語言

定義

一個上下文無關文法G是一個四元式$(V_T,V_N,S,P)$

$V_N$：是非空有限集合，它的每個元素是非終結符號

$V_T$：是非空有限集合，它的每個元素是終結符號

$V_N\cap V_N=?V_T\cup V_N=V$

$S$：$S\in V_N$，稱為開始符號（相當于有限自動機的初態）

$\mathcal{P}$：產生式集合（有限），每個產生式是

$\{P\to \alpha |P\in V_N,\alpha \in (V_T\cup V_N{)}^{?},S至少一次為P\}$,S即要在左邊至少出現一次

“$\to$" 相當于$isdefinedas$

舉例：考慮以下算數表達式的文法以及語言

$V_T$： id + - * / ↑ ( )
$V_N$：表達式、運算符
$S$： 表達式
$\mathcal{P}$： 表達式->表達式 運算符 表達式
表達式->（表達式）
表達式->— 表達式
表達式-> id
運算符->+|-|*|/|↑

得到文法G1(E) : E->EAE|(E)|-E|id A->+|-|*|/|↑

由此可見，文法G1(E)所定義的語言是算術表達式，如id+id,id*(id+id)等

它表達了簡單算術表達式由id用A連接起來

該文法的:

1?? $V_N$是出現在P的左部所有符號集合

2?? V是$\mathcal{P}$的所有符號：$V_T=V/V_N$

3?? S是該文法所定義的句子名字

4?? 寫出了$\mathcal{P}$，就能找出其它三元素

各個符號的意義

1?? 終結符：是用以組成語言中的串的基本符號，與程序語言中的“單詞”是同義語

如表達式 $id+(id{)}^{?}(?id)$中，+、-、*、/、id均為終結符

2?? 非終結符：非終結符號(也稱語法變量)用來代表語法范疇。例如,“算術表達式”“布爾表達式”“賦值句”“分程序”“過程”等,它們都是現今程序語言常見的語法范疇。我們也可以說，一個非終結符代表一個一定的語法概念。因此，一個非終結符是一個類(或集合)記號,而不是一個個體記號。例如，算術表達式"這個非終結符乃代表一定算術式組成的類。因而,也可以說,每個非終結符號表示一定符號串的集合(由終結號和非終結符號組成的符號串）。

3?? 開始符號：一個特殊的非終結符，標記最終感興趣的語法范疇（句子），其他非終結符用以定義其他的串集，這有助于定義該語言，也有助于為它處理的語言提供一個分層的結構

4?? 產生式：規定由終結符和別的語法范疇組成一個新的語法范疇的辦法

結構：非終結符->一串非終結符和終結符

如：A->α，A是左部符號$V_N$，α是右部候選式，$\alpha =X_1{X}_2{X}_3...X_N,X_i\in V$

舉例

語法規則如下：

<句子> → <主語> <謂語> <間接賓語> <直接賓語>
<主語> → <代詞>
<謂語> → <動詞>
<間接賓語> → <代詞>
<直接賓語> → <冠詞> < 名詞>
<代詞> → He
<代詞> → me
<名詞> → book
<冠詞> → a
<動詞> → gave

比如He gave me a book是一個語法正確的句子

👉 該語法范疇叫"句子"，在程序語言中叫“ 程序”

👉 語言的句子是由一串$V_N$定義，到最后才是一串$V_T$

習慣記號

$V_N$：大寫字母A、B、C、S等

$V_T$：小寫字母，0~9，+，-等運算符，標點，分界符，黑體字母串，id，if

X、Y、Z：文法符號，或$V_N$或$V_T$一個符號

u、v、w……z：$V_T$中的串

α、β、γ：文法符號串$\in (V_T\cup V_N{)}^{?}$

S：開始符號，第一個產生式中出現

->：定義為(元語言符號)

|：或(元語言符號)

推導與語言

? 問題：用文法如何定義一個語言？

思路：從S出發，反復使用$\mathcal{P}$，對非終結符替換展開，最后得到全部由終結符串組成的一個串

涉及到：替換、推導、句型、句子、語言

1?? 直接推出：是兩個文法符號串之間的一種關系$\mathcal{R}$

如：$(\alpha A\beta )\mathcal{R}(\alpha \gamma \beta )$

它表示，若$A\to \gamma \in \mathcal{P},\alpha ,\beta \in V^{?}$，則$\mathcal{R}$就是直接推出，$\mathcal{R}$記作$?$

則有：$(\alpha A\beta )?(\alpha \gamma \beta )$

---

2?? 推導：如果兩個串$u_0,u_n$，存在一個串序列
$$u_0?u_1?...?u_n$$
則$u_0{\mathcal{R}}_1{u}_n{\mathcal{R}}_1記作\stackrel{+}{?}或\stackrel{?}{?}$

+：至少一步推導。*：可以0步推導

---

3?? 如何從推導引出語言

? $u_0\stackrel{+}{?}{u}_n$ $u_0\stackrel{?}{?}{u}_n$

🌵如果令$u_0$為S，即推導要從開始符號開始，那么$S\stackrel{?}{?}\alpha ,\alpha \in V^{?}$，則稱α為G的句型

🌵 如果再要求$\alpha \in V_T^{?}$，則稱$\alpha$為G的句子

🌵 文法G產生的句子的全體是一個語言，記作L(G)
$$L(G)=\{\alpha |S\stackrel{+}{?}\alpha \&\alpha \in V_T^{?}\}$$
說明

① 由文法G定義語言L需依賴一種運算，即關系$\stackrel{+}{?}$

當V*中有許多串，只有那些(S, u) (S,v)存在$\stackrel{+}{?}$關系的u,v才是語言中的句子。

② α , β是句型，表示(S， α) (S， β)有$\stackrel{?}{?}$的關系，但它們的構成是不全屬于$V^T$的字符。

③ G的句型集，是指存在$S\stackrel{?}{?}\alpha$關系的所有α,該集的子集是L(G)。

④$L(G)?句型集?V^{?}$

題目

關于句型、句型集、句子、語言等概念，下面哪些說法是不正確的?

A 終結符串是句子（句子是終結符串）

B 終結符與非終結符的混合串是句型

C 終結符集合的閉包是語言

D 全體符合集合的閉包是甸句集

ABCD

舉例：根據文法G： E->E+E|E*E|(E)|i，句子$i_1?(i_2+i_3)$的推導過程如下

1?? $E=>E?E=>i_1?E=>i_1(E)=>i_1?(E+E)=>i_1?(i_2+E)=>i_1?(i_2+i_3)$

最左推導

2?? $E=>E?E=>E?(E)=>E?(E+E)=>E?(E+i_3)=>E?(i_2+i_3)=>i_1?(i_2+i_3)$

最右推導

從一個句型到另一個句型的推導過程并不唯一，但是通常只考慮最左推導和最右推導

最左推導是指，任何一步a=> β都是對a中的最左非終結符進行替換。

最右推導是指，任何一步a=> β都是對a中的最右非終結符進行替換。

3.3 語法樹與二義性

語法樹

目的：為了理解句子的語法，即理解句子如何從開始符號推導得到，因此引入“圖”。

定義：句型推導的圖形表示，與替換順序的選取無關。

作用：明顯地形成文法所暗含句子的分層語法結構，為語法分析提供一些新的途徑。

樹的內結點：非終結符A標記，若A->XYZ，則該產生式的一棵子樹為

語法樹與文法概念的對應關系如下

語法樹文法概念

內結點A	VN
葉	文法符號
子樹	直接推導
根結點	S
任意一次全剪	句型
葉子∈VT時，將葉子順序排列	句子

有的文法，對于同一句子，應用不同規則進行推導得到不同的語法樹

沒有區分優先級

舉例 $E\stackrel{+}{?}?(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\in V_N$，必須都有用處，即$?s\stackrel{?}{?}\alpha P\beta$，P在句型中出現

$?\gamma \in V_T^{?},P\stackrel{+}{?}\gamma$，即對P不存在不終結的回路

題目

關于文法二義性、語言二義性，下面哪些說法是正確的？

1?? 只要存在某個句子有兩棵不同的語法樹,文法就是二義的。

2?? 無法判定所有句子均沒有兩棵不同的語法樹，即無法判定文法是否無二義。

3?? 對于語言來說只要存在無二義的文法它就不是二義的。

4?? 對于語言來說,無法判定其不存在無二義的文法,即無法判定語言是否二義。

ABCD

參考資料

[1] 西安交通大學軟件工程專業編譯原理 吳曉軍 2022春

[2] 陳火旺，劉春林，譚慶平，趙克佳，劉越. 程序設計語言編譯原理（第3版）. 北京：國防工業出版社，2010/20132017

總結

以上是生活随笔為你收集整理的[XJTUSE编译原理] 第三章 上下文无关文法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。