編譯原理語言和文法-有解無憂

文章目錄

- 一、語言
- - 1、形式語言
  - 2、符號和符號串
- 二、文法
- - 1、推導
  - 2、語言的定義
  - 3、文法等價
  - 4、語法樹
  - 5、句型分析
  - 6、文法二義性
  - 7、文法分類

一、語言

語言是其句子的集合，

漢語–所有符合漢語語法的句子的全體
英語–所有符合英語語法的句子的全體
程式設計語言–所有該語言的程式的全體

研究語言 = { 每個句子構成的規律每個句子的含義每個句子和使用者的關系研究語言=\left\{ \begin{aligned} 每個句子構成的規律 \\ 每個句子的含義\\ 每個句子和使用者的關系 \\ \end{aligned} \right. 研究語言=??????每個句子構成的規律每個句子的含義每個句子和使用者的關系?

三個方面：

語法 Syntax
表示構成語言句子的各個記號之間的組合規律
語意 Semantics
表示各個記號及其組合的特定含義（各個記號和記號所表示物件之間的關系）
語用 Pragmatics
表示在各個記號所出現的行為中，它們的來源、使用和影響

1、形式語言

可用于形式化地描述程式設計語言，包括它由哪些符號串構成，這些符號串的表示、結構和特性

2、符號和符號串

任何一種語言都是由該語言的基本符號組成的符號串集合

一些基本概念：

符號:
一個抽象物體,我們不再形式地定義它(就象幾何中的”點”一樣).例如字母是符號,數字也是符號，
字母表:
字母表是元素的非空有窮集合，我們把字母表中的元素稱為符號，因此字母表也稱為符號集，不同的語言可以有不同的字母表，例如：漢語的字母表中包括漢字、數字及標點符號等，PASCAL語言的字母表是由字母、數字、若干專用符號及BEGIN、IF之類的保留字組成，
符號串:
- 由字母表中的符號組成的任何有窮序列稱為符號串，例如00 11 10 是字母表 ∑ =｛0，1｝上的符號串，
- 字母表A=｛a,b,c｝上的一些符號串有：a,b,c,ab,aaca，在符號串中，符號的順序是很重要的，符號串ab就不同于ba,abca和aabc也不同，
- 可以使用字母表示符號串，如x=STR表示 x 是由符號S、T和R，并按此順序組成的符號串，
符號串的長度:
如果某符號串x中有m個符號，則稱其長度為m，表示為｜x｜=m，如001110的長度是6，
空符號串：
即不包含任何符號的符號串，用ε表示，其長度為0，即｜ε｜=0，
符號串的頭、尾，固有頭和固有尾：
- 如果z=xy是一符號串，那么x是z的頭，y是z的尾；
- 如果x是非空的，那么y是固有尾；
- 如果y非空，那么x是固有頭，

例如：設z=abc，那么z的頭是ε,a,ab,abc，除abc外，其它都是固有頭；z的尾是ε,c,bc,abc,z的固有尾是
ε,c,bc，

當對符號串z=xy的頭感興趣而對其余部分不感興趣時，采用省略寫法：z=x…；
如果只是為了強調x在符號串z中的某處出現，則可表示為：z=…x…；符號t是符號串z的第一個符號，則表示為z=t…，

符號串的連接：
設x和y是符號串，它們的連接xy 是把y的符號寫在x的符號之后得到的符號串. 由于ε的含義，顯然有ε x=x，x ε =x
例如：x=ST，y=abu，則它們的連接xy=STabu，看出
｜x｜=2，｜y｜=3，｜xy｜=5
符號串的方冪：
符號串自身連接n次得到的符號串，an 定義為 aa…aa n個a，a1=a, a2=aa且a0=ε
- 例：若x=AB，則:
  x0 = ε
  x1 =AB
  x2 = ABAB
  x3 = ABABAB
  xⁿ = xx^n-1 = x^n-1 x (n>0)
符號串集合：
若集合A中所有元素都是某字母表 ∑ 上的符號串，則稱A為字母表?上的符號串集合，
兩個符號串集合A和B的乘積：
定義為 AB = {xy|x∈A且y∈B}
若集合A={ab,cde} 集合B = {0,1}，則
AB ={ab1,ab0,cde0,cde1}

使用 ∑^* 表示 ∑ 上的一切符號串（包括 ε ）組成的集合，Σ^* 稱為 Σ 的閉包，

∑ 上的除ε外的所有符號串組成的集合記為∑⁺， ∑⁺稱為Σ的正閉包，

編譯原理的閉包：

V是一個符號集合，假設V指的是三個符號a, b, c的集合，記為 V = {a, b, c } V*
讀作“V的閉包”，它的數學定義是V自身的任意多次自身連接（乘法）運算的積，也是一個集合，
也就是說，用V中的任意符號進行任意多次（包括0次）連接，得到的符號串，都是V*這個集合中的元素， 0次連接的結果是不含任何符號的空串，記為
ε 1次連接就是只有一個符號的符號串，比如，a，b， c 2次連接是兩個符號構成的符號串，比如，aa, ab, ac, ba, bb,
bc,等等

二、文法

符號 ? > -> ?>符號串 ? > -> ?>句子 ? > -> ?>語言

并非所有符號串都能形成句子

文法G定義為一個四元組 ( V N ， V T ， P ， S ) (V_N，V_T，P，S ) (VN?，VT?，P，S)，其中：

V N V_N VN?為非終結符號(或語法物體，或變數)集；

非終結符(nonterminal) 是用來表示語法成分的符號，有時也稱為語法變數

例: V N = { < 句子 > , < 名詞短語 > , < 動詞短語 > , < 名詞 > , … } V_N = \{ <句子>, <名詞短語>, <動詞短語>,<名詞>, … \} VN?={<句子>,<名詞短語>,<動詞短語>,<名詞>,…}
V T V_T VT?為終結符號集；

終結符（terminal symbol）是文法所定義的語言的基本符號，有時也稱為 t o k e n token token

例: V T = { a p p l e , b o y , e a t , l i t t l e } V_T=\{ apple, boy, eat, little\} VT?={apple,boy,eat,little}
P P P為產生式(也稱規則)的集合； V N V_N VN?， V T V_T VT?和 P P P是非空有窮集；

產生式（production）描述了將終結符和非終結符組合成串的方法產生式的一般形式：

α→β 讀作：α定義為β
- α ∈ ( V T ∪ V N ) + α∈(V_T∪V_N)^+ α∈(VT?∪VN?)+，且α中至少包含 V N V_N VN?中的一個元素：稱為產生式的頭(head)或左部(left side)
- β ∈ ( V T ∪ V N ) ? β∈(V_T∪V_N)^* β∈(VT?∪VN?)?：稱為產生式的體(body)或右部(right side)
  
  例：
  
  P = { < 句子 > → < 名詞短語 > → < 動詞短 > ， < 名詞短語 > → < 形容詞 > → < 名詞短語 > ， … P=\left\{ \begin{aligned} <句子>\rightarrow<名詞短語>\rightarrow<動詞短>， \\ <名詞短語>\rightarrow<形容詞>\rightarrow<名詞短語>， \\ …\end{aligned} \right. P=??????<句子>→<名詞短語>→<動詞短>，<名詞短語>→<形容詞>→<名詞短語>，…?
S S S為識別符號或開始符號，它是一個非終結符，

S ∈ V N S∈V_N S∈VN?，開始符號(start symbol ) 表示的是該文法中最大的語法成分

?例： S = < 句子 > S = <句子> S=<句子>

V N V_N VN?和 V T V_T VT?不含公共的元素，即 V N V_N VN? ∩ V T V_T VT? = φ φ φ

用 V V V表示 V N V_N VN? ∪ V T V_T VT? ，稱為文法 G G G的字母表或字匯表規則，也稱重寫規則、產生式或生成式，
是形如α→β或α∷=β的 ( α ， β ) (α，β) (α，β)有序對，其中 α 是字母表 V V V的正閉包 V + V^+ V+中的一個符號，β 是 V ? V^* V?中的一個符號，
α 稱為規則的左部，β稱作規則的右部，

1、推導

直接推導：“ = > => =>”

α→β 是文法G的產生式，若有 δ1, δ2 滿足：δ1 =γ1αγ2, δ2 = γ1βγ2, 其中γ1,γ2∈V

? - 則稱δ1直接推導到δ2,記作δ1 = > => =>δ2

? - 也稱δ2直接歸約到δ1

例：

G：S→0S1， S→01

0S1 => 00S11
00S11 => 000S111
000S111 => 00001111
S => 0S1

規范推導：最右推導

中間為規范推導

句型、句子的定義

句型：
有文法G，若S =>* x，則稱x是文法G的句型，
句子：
有文法G，若S =>*x，且x∈ V T {V_T} VT?*，則稱x是文法G的句子，

例：

G： S→0S1， S→01

S = > => => 0S1 = > => => 00S11 = > => => 000S111 = > => => 00001111
G的句型S, 0S1, 00S11,000S111, 00001111
G的句子00001111, 01

2、語言的定義

由文法G生成的語言記為L(G),它是文法G的一切句子的集合：

L ( G ) = { x ∣ S = > ? x ，其中 S 為文法的開始符號，且 x ∈ V ? } L(G)=\{x|S =>^*x，其中S為文法的開始符號，且x ∈V*\} L(G)={x∣S=>?x，其中S為文法的開始符號，且x∈V?}

例：G： S→0S1， S→01

L ( G ) = { 0 n 1 n ∣ n ≥ 1 } L(G)=\{0^n1^n|n≥1\} L(G)={0n1n∣n≥1}

3、文法等價

若 L ( G 1 ) = L ( G 2 ) L(G1)=L(G2) L(G1)=L(G2), 則稱文法 G 1 G1 G1和 G 2 G2 G2是等價的，

如文法 G 1 [ A ] ： A → 0 R G1[A]：A→0R G1[A]：A→0R 與 G 2 [ S ] ： S → 0 S 1 G2[S]：S→0S1 G2[S]：S→0S1 等價
A→01 S→01 R→A1

4、語法樹

文法G[Z]的語法樹：

每個結點都是G的符號
樹根是文法的開始符號
若某個結點至少有一個從它出來的分支，則該結點一定是非終結符
若某個結點A有n個分支，假設其分支結點為B1,B2,…Bn，則A::=B1B2B3…Bn一定是文法的一條規則

語法樹可以從推導程序產生，

凡使用一條規則推導，則可以從規則左部符號結點長出若干分支，

5、句型分析

句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構造程序，

在語言的編譯實作中，把完成句型分析的程式稱為分析程式或識別程式，分析演算法又稱識別演算法，

從左到右的分析演算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結束，

句型分析分析演算法可分為：

自上而下分析法：
從文法的開始符號出發，反復使用文法的產生式，尋找與輸入符號串匹配的推導，
自下而上分析法：
從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號，

兩種方法反映了兩種語法樹的構造程序:

自上而下方法是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結果正好是輸入符號串
自下而上方法則是從輸入符號串開始，以它做為語法樹的結果，自底向上地構造語法樹

句型分析的有關問題

1）在自上而下的分析方法中如何選擇使用哪個產生式進行推導？
假定要被代換的最左非終結符號是A，且有n條規則：A→B1|B2|…|Bn，那么如何確定用哪個右部去替代A？
2）在自下而上的分析方法中如何識別可歸約的串？
在分析程式作業的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結符號，該子串稱為“可歸約串”

刻畫“可歸約串”

短語是句型中某非終結符號通過若干步推導出的子串
歸約：如果每次都從當前句型的句柄進行歸約，則可以歸約到文法的開始符號

6、文法二義性

文法二義性：兩棵語法樹對應同一句子
根據語法樹，可以發現文法的二義性二義文法

若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的或者，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的，

判定任給的一個背景關系無關文法是否二義，或它是否產生一個先天二義的背景關系無關語言，
這兩個問題是遞回不可解的，但可以為無二義性尋找一組充分條件，

文法的二義性和語言的二義性是兩個不同的概念：
可能有兩個不同的文法G和G′，其中G是二義的，但是卻有：L(G)=L(G′)，
即，這兩個文法所產生的語言是相同的，

7、文法分類

通過對產生式施加不同的限制，Chomsky將文法分為四種型別：

0型文法：對任一產生式 α → β α→β α→β，都有 α ∈ ( V N ∪ V T ) + α∈(V_N∪V_T)^+ α∈(VN?∪VT?)+， β ∈ ( V N ∪ V T ) ? β∈(V_N∪V_T)^* β∈(VN?∪VT?)?
1型文法：對任一產生式 α → β α→β α→β，都有 ∣ β ∣ ≥ ∣ α ∣ |β|≥|α| ∣β∣≥∣α∣ ，僅 S → ε S→ε S→ε 除外, S為文法初始符號且不出現在任何產生式右邊
2型文法：對任一產生式 α → β α→β α→β，都有 α ∈ V N α∈V_N α∈VN?， β ∈ ( V N ∪ V T ) ? β∈(V_N∪V_T)^* β∈(VN?∪VT?)?
3型文法：任一產生式 α → β α→β α→β的形式都為 A → a B A→aB A→aB或 A → a A→a A→a，其中 A ∈ V N A∈V_N A∈VN?， B ∈ V N B∈V_N B∈VN?， a ∈ V T a∈V_T a∈VT?