程序語言的語法描述
一、幾個重要概念
字母表和符號串
(1)字母表 alphabet
字母表是元素的非空有窮集合。
【例如】 ∑ = {a,b,c}
∑是字母表，由 a,b,c 三個元素組成。
字母表中至少包含一個元素，字母表中的元素，可以是字母、數字或其他符號。
不同的語言有不同的字母表。
英文的字母表是26個字母、數字和標點符號的集合;C 語言的字母表是字母、數字和若干專用符號組成。
(2)符號(字元)symbol
字母表中的元素稱為符號，或稱為字元。
【例如】 ∑ = {a,b,c}
a,b,c 是字母表 ∑ 中的符號。
(3)符號串(字)string
符號的有窮序列稱為字元串。
【例如】設有字母表 ∑ = {a,b,c}，
則有符號串 a,b,ab,ba,cba,abc,…
(a,b,ab,ba,cba,abc 等都是字母表∑上的符號串)
符號串總是建立在某個特定字母表上的且只能由字母表上的有窮多個符號組成。
符號串中符號的順序是很重要的，如 ab 和 ba 是字母表∑上的兩個不同的符號串。
不包含任何符號的符號串，稱為空符號串，用 ε (epsilon)表示，即空符號串由 0 個符號組成，其長度 |ε| = 0
下面看看符號串的運算：
(1)符號串的連結 catenation
設 x 和 y 是符號串，則串 xy 稱為它們的連結。即 xy 是將 y 符號串寫在 x 符號串之後得到的符號串。
【例如】設 x = abc，y = 10a，
則 xy = abc10a
則 yx = 10aabc
特別，對任意一符號串 x 有：
εx = xε = x
(2)集合的乘積 product
設 A 和 B 是符號串的集合，則 A 和 B 的乘積定義為：
AB = {xy | x ∈ A, y ∈ B}
即集合 AB 中的符號串是由 A 和 B 的符號串連接而成的。
【例如】設 A = {a,b}, B = {c,d}
則 AB = {ac,ad,bc,bd}
因為對任意一符號串 x 有：
εx = xε = x
所以，對任意集合 A，有 {ε}A = A{ε} = A
這裡要說一下 空集 Φ empty set
Φ 表示不含任何元素的空集 { }
Φ = { }
注意： ε是符號串，不是集合
{ ε} 表示由空符號串 ε 所組成的集合，但這樣的集合不是空集Φ， 即Φ不包含空串。 ε ∈ Φ
(3)符號串的冪運算 power
(4)集合的冪運算
(5)集合A的正閉包A+與閉包A*
正閉包：Positive closure
閉包 ：Star closure(星閉包)
二、上下文無關文法
(1)形式語言
序列(字元串)的集合稱為形式語言。
每個形式語言都是某個字母表上按某種規則構成的所有符號串的集合;任何一個字母表上符號串的集合均可定義一個形式語言。
【例如】
C 語言是具有基本符號字母表上的符號串的集合。每個 C 語言程序是基本符號的符號串。
形式語言的描述有兩種方法：
第一種方法是當語言為有窮集合時，用枚舉法來表示語言。
【例】設有字母表 A={a,b,c},則
L1 = {a,b,c}
L2 = {a,aa,ab,ac}
L3 = {c,cc}
均表示字母表 A 上的一個形式語言。
由於這三個語言均是有限符號串的集合，可以枚舉出其全部句子來表示該語言。
第二種是 當語言為無窮集合時，需要設計文法來描述無窮集合的語言。
文法是一種形式規則
(2)文法的形式定義
1、規則
規則的作用是告訴如何用規則中的符號串生成語言中的序列。一組規則規定了一個語言的語法結構。
產生式中的符號
非終結符：非終結符號(也稱語法變數)用來代表語法範疇。例如，「算術表達式」、「布爾表達式」、「賦值句」、「分程序」、「過程」等，它們都是現今程序語言常見的語法範疇。出現在產生式左部能派生出符號或符號串的那些符號，即每個非終結符表示一定符號串的集合。用大寫字母表示或用尖括弧把非終結符括起來。
終結符：是不屬於非終結符的那些符號，它是組成語言的基本符號，是一個語言的不可再分的基本符號，只出現在產生式右部。通常用小寫字母表示。
2、文法
VT 可以理解成一個符號的集合，就像英語的單詞。
VN 可以理解成語法單位的集合 就像英語的語法單位，比如主語、謂語。
S是文法的開始符號。
每一條規則是一條產生式，所有的規則的集合記成P。
產生式(也稱產生規則或簡稱規則)是定義語法範疇的一種書寫規則。
3、語言的形式定義
(1)直接推導
(2)推導
4、廣義推導
直接推導的長度為1，推導的長度大於等於1，廣義推導的長度大於等於0
5、句型和句子
僅含終結符號的句型是一個句子。文法G所產生的句子的全體是一個語言。
6、語言
7、規範推導和規範歸約
文法所定義的任一句型和句子，都可以根據文法推導出來，但同一個句型(句子)可以通過不同的推導序列推導出來，這是因為在推導過程中所選擇非終結符的次序無關。
最左推導是指對於一個推導序列中的每一步直接推導 α=>β，都對 α 中的最左非終結符進行替換。
最右推導是指對於一個推導序列中的每一步直接推導 α=>β，都對 α 中的最右非終結符進行替換。
最右推導也稱為規範推導，用規範推導推導出的句型稱為規範句型。
每個句子都有規範推導，但對句型此結論並不成立。
歸約是推導的逆過程，歸約是與推導相對的概念，推導是把句型中的非終結符用規則的一個右部來替換的過程，而歸約是句型中的某個子串用一個非終結符來替換的過程。
規範推導的逆過程，稱為最左歸約，也稱為規範歸約。
8、遞歸規則與文法的遞歸性
所謂遞歸規則，是指在規則的左部和右部具有相同的非終結符的規則。
如果文法中有規則 A→A… 稱為規則左遞歸。
如果文法中有規則 A→…A 稱為規則右遞歸。
如果文法中有規則 A→…A… 稱為規則遞歸。
文法的遞歸性，是指對文法中任一非終結符，若能建立一個推導過程，在推導所得的符號串中又出現了該非終結符本身，則文法是遞歸的，否則是無遞歸性的。
文法中使用遞歸規則，使得能用有限的規則去定義無窮集合的語言。
下面的情況比較特殊：
文法中使用了遞歸規則，使得可用有限的規則去刻畫無窮集合的語言。
若不用遞歸規則來定義文法，需要用無窮多條規則去表示無窮集合的語言。
當一個語言是無窮集合時，則定義該語言的文法一定是遞歸的。
程序設計語言都是無窮集合，因此描述它們的文法必定是遞歸的。
9、短語、直接短語和句柄
短語、直接短語和句柄 是後面章節的內容，這裡不懂沒關係。
首先看一下短語和直接短語。
短語是句型的一部分。
句柄
一個句型的最左直接短語稱為該句型的句柄。
句柄特徵：
(1)它是直接短語，即某規則右部
(2)它具有最左性。
注意：
短語、直接短語和句柄都是針對某一句型的，特指句型中的哪些符號串能構成短語和直接短語，離開具體的句型來談短語、直接短語和句柄是無意義的。
三、語法樹與文法的二義性
1、推導樹的生成
(1)語法樹的生成
語法樹的構造是從文法的開始符號出發，構造一個推導的過程，因為文法的每一個句型(句子)都存在一個推導，所以文法的每個句型(句子)都有一棵對應的語法樹。
舉個例子：
方法一：
以識別符號作為根結點，從它開始對每一步直接推導向下畫一分支，分支結點的標記是直接推導中被替換的非終結符的名字，按此方法逐步向下，畫出每一步直接推導對應的分支直到對該語法樹再無分支可畫時，構造過程結束。
方法二：
語法樹中從左到右的末端結點構成了有該語法樹所表示的那個推導推出的符號串。
句型 (i+i)*i-i 的最左、最右推導得到的語法樹完全相同，
也就是說，一棵語法樹表示一個句型的種種可能的(但未必是所有的)不同推導過程。
(2)子樹
語法樹的子樹是由某一個結點連同所有分支組成的部分。
(3)簡單子樹
語法樹的簡單子樹是指只有單層分支的子樹。
(4)子樹與短語的關係
根據子樹的概念，句型的短語、直接短語和句柄的直觀解釋如下：
短語：子樹的末端結點形成的符號串是相對於子樹根的短語。
直接短語：簡單子樹的末端結點形成的符號串是相對於簡單子樹根的直接短語。
句柄：最左簡單子樹的末端結點形成的符號串是句柄。
【例】對文法G[E]，用語法樹求句型(T+i)*i-F 的短語、直接短語和句柄。
2、文法的二義性
對應文法 G 中任一句型的推導序列，總能構造一棵語法樹。
文法 G[E]：E→ E + E | E﹡E | (E) | i
該文法的一個句子 i*i+i 有兩個不同的最左推導，對應兩棵不同的語法樹。
如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。也就是說，若一個文法存在某個句子，它有兩個不同的最左推導或有兩個不同的最右推導，則稱這個文法是二義的。
二義性的文法將給編譯程序的執行帶來問題。對於二義性文法的句子，當編譯程序對它的結構進行語法分析時，就會產生兩種甚至多種不同的理解。語法結構上的不確定性，必將導致語義處理上的不確定性。
解決方法之一：利用文法的等價性來消除文法的二義性。
3、文法二義性的消除
(1) 不改變文法中原有的語法規則，僅加進一些語法的非形式規定。
【例】文法 G：E → E + E | E﹡E | (E) |i
不改變已有的四條規則，僅加進運算符的優先順序和結合規則，即 * 優先+，+、* 服從左結合。
這樣，對於文法 G[E] 中的句子 i*i+i 只有唯一的一棵語法樹，從而避免了文法的二義性。
(2) 構造一個等價的無二義性文法;即排除二義性的規則，改寫原有的文法。
例如，文法 G：E → E + E | E﹡E | (E) |i
想要讓一個規則結合性弱;就讓它出現在推導序列前面(語法樹的上層);
想要讓一個規則結合性強;就讓它出現在推導序列後面(語法樹的下層);
具體做法：引入非終結符
語言的二義性是指不存在一個無二義的文法 G，使得L(G)就是語言本身。
注意：文法的二義性和語言的二義性是兩個不同的概念。可能有兩個不同文法的 G 和 G』，其中一個是二義的而另一個是無二義的，但是有 L(G) = L(G』)。
對於一個程序語言來說，常常希望它的文法是無二義的，因為希望對它的每個語句的分析是唯一的。
二義性問題是不可判定的。即不存在一個演算法，能在有限步驟內確切的判定一個文法是否為二義的。
4、文法和語言的分類
Chomsky 於 1956 年建立形式語言的理論，形式語言的理論發展得很快。
對計算機科學有著深刻的影響; 特別是對如下方面有重大的作用：程序語言的設計；編譯方法；計算複雜性。
Chomsky把文法分成四種類型， 即 0型、1型、2型和3型。 這幾類文法的差別在於對產生式的形式施加的限制從 0型到 3型依次增強，但它們表達語言的能力則依次減弱。
0 型文法(無限制文法，短語文法)
由定義可見，α 和 β 均是文法的終結符和非終結符組成的符號串，且 β 可能為空，而 α 不能為空，即允許 |α|>|β|。
由於 0 型文法沒有加任何限制條件，故又稱為無限制文法，相應的語言稱為無限制語言。
非終結符 A 永遠消不掉，不能終結。
1 型文法(上下文有關文法)
在推導過程中，連續 n 個 a 一直是最前面，不能生成連續 n 個 b 和緊跟 n 個 c，但是可以生成相互間隔的 n 個 B 和 c。
使用規則 cB→Bc 可以將所有穿插的 c 中的B 向前移。
然後使用規則 bB→bb 消除掉所有的 B。
aaabbbccc 的推導過程。
最左推導：
規則 cB→cc和 bB→bc 是把 B 換成 c。
規則 cA→Ac 是把穿插的 c 中的 A 向前移。
最終使用規則 bA→bb 消除掉所有的 A，換成 b。
2 型文法(上下文無關文法)
由定義可見，利用規則將 A 替換成 β 時，與 A 的上下文環境無關，即無需考慮 A 在上下文中出現的情況。
故又稱為上下文無關文法，相應的語言稱為上下文無關語言。
通常定義程序設計語言的文法是上下文無關文法，因此，上下文無關文法及相應語言是我們主要的研究對象。
有 a 就有 B
有 b 就有 A
或： S → aB | bA A → a | aS | Sa B → b | bS | Sb
3 型文法(正規文法)
右線形文法和左線形文法都稱為 3 型文法或正規文法， 3型文法描述的語言稱為 3 型語言或正規語言。
通常定義程序設計語言詞法規則的文法是正規文法。
通過幾個特殊的例子來體會語言與文法的關係。
有關文法的使用限制和變換。
作為程序語言的上下文無關文法，對它們限制以下幾點：
第二點限制的解釋
(2』)
每個非終結符 P 必須都有用處。這一方面意味著，必須存在含 P 的句型;也就是從開始符號 S 出發，存在推導 S > αPβ.。
以後所討論的文法均假定滿足上述兩個條件。這種文法稱為化簡了的文法。
若程序設計語言的文法含有多餘規則，其中必定有錯誤存在，因此檢查文法中是否含有多餘規則是很重要的。
以上就是有關程序語言的語法描述的相關介紹，無論是初入程序還是程序的專家，都可以通過學步園進行更深入的了解程序語言的知識。