程式語言/語法簡介
< 程式語言簡介
一種程式語言由其語義及其語法的組合來描述。語義告訴我們該程式語言中所有可能構造的含義。語法告訴我們它的結構。描述程式語言語義有很多不同的方法；但是，經過數十年的研究，描述其語法的方法大多隻有一種。我們稱這種形式化方法為上下文無關文法。
請注意，上下文無關文法不是計算機用來識別語言的唯一一種文法。實際上，存在一整套形式文法，這些文法最初是由諾姆·喬姆斯基研究的，今天我們通常稱之為喬姆斯基層次結構。該層次結構中的一些成員，如正則文法非常簡單，並且識別相對較少的語言。然而，這些文法仍然非常有用。例如，正則文法是編譯器詞法分析的核心。其他型別的文法非常強大。例如，無限制文法的計算能力與圖靈機一樣強大。然而，在這本書中，我們將重點關注上下文無關文法，因為它們是編譯器用來將程式轉換為易於處理的格式的主要工具。
文法使我們能夠將程式（通常表示為ASCII字元的線性序列）轉換為語法樹。只有語法上有效的程式才能以這種方式轉換。這棵樹將是編譯器或直譯器用來處理程式的主要資料結構。透過遍歷這棵樹，編譯器可以生成機器程式碼，或者可以對程式進行型別檢查。透過遍歷這棵樹，直譯器可以模擬程式的執行。
用來表示文法的主要符號是巴克斯-諾爾正規化（簡稱BNF）。這種符號是由約翰·巴克斯發明，並由彼得·諾爾進一步改進的，最初用於描述ALGOL程式語言的語法。BNF文法由一個由(T, N, P, S)表示的四元組定義。這些元素的含義如下：
- T是一組標記。標記構成語言的詞彙表，是語法的最小單位。這些元素是程式設計師在輸入程式碼時看到的符號，例如，while、for、+、( 等。
- N是一組非終結符。非終結符本身並不屬於語言。相反，它們有助於確定可以從文法中推匯出的推導樹的結構。通常，我們將這些符號用尖括號括起來，以區分它們和終結符。
- P是一組產生式規則。每個產生式都由一個左部、一個分隔符和一個右部組成，例如，<非終結符> := <表示式1> ... <表示式N>，其中 ':=' 是分隔符。為了方便起見，左部相同的產生式可以使用符號 '|' 來縮寫。在這種情況下，管道用於分隔不同的備選方案。
- S是一個起始符。任何最終產生語法上有效的程式的推導序列都從這個特殊的非終結符開始。
例如，下面是一個非常簡單的文法，它識別算術表示式。換句話說，這種簡單語言中的任何程式都表示諸如 'a'、'b' 和 'c' 之類的名稱的乘積或總和。
<exp> ::= <exp> "+" <exp>
<exp> ::= <exp> "*" <exp>
<exp> ::= "(" <exp> ")"
<exp> ::= "a"
<exp> ::= "b"
<exp> ::= "c"
這種文法也可以用更方便的方式表示，使用一系列豎線符號，例如：
<exp> ::= <exp> "+" <exp> | <exp> "*" <exp> | "(" <exp> ")" | "a" | "b" | "c"