編譯器構造/描述程式語言
多年來，人們發現使用自然語言（例如英語）來描述程式語言是不令人滿意的，因為可能存在遺漏、矛盾、歧義和模糊性。一個重要的里程碑是 Algol 60 報告的出版，該報告使用形式語法（BNF）來描述語言的語法。語義（含義）使用英語仔細描述。擴充套件 BNF（EBNF）的變體將用於本書，如本節後面所述。
已經進行了幾次嘗試來形式化語義，包括用於定義 Algol 68 的語法生成器，以及維也納定義語言，該語言曾在某一階段用於定義 PL/1 的含義。雖然理論上足夠，但這些嘗試非常複雜，以至於證明對實際應用幾乎沒有用處。
1956 年，喬姆斯基（一位語言學家）開發了一個形式語法層次結構（型別 0 到 3）用於研究英語和其他自然語言。型別 0 能力最強，型別 3 能力最弱。事實證明，型別 3 正則語法正是描述詞法分析要求所需的，而型別 2 上下文無關語法正是描述許多程式語言的語法所需的。但即使是型別 0 語法也無法充分描述英語。
已經開發了可以接受語法描述作為輸入，並生成使用該語法進行分析的程式碼的程式設計工具。請注意，可能存在幾種不同的語法可以用來描述特定的程式語言，並且並非所有這些語法都能被這些工具使用。
使用正則語法進行詞法分析的程式碼可以由諸如 lex、flex 和 JavaCC 之類的工具生成。
使用上下文無關語法進行語法分析的程式碼可以由諸如 yacc、bison 和 JavaCC 之類的工具生成。
即使你有一個合適的語法，這些工具也只能自動化編寫編譯器或直譯器工作的相對較小的一部分。實際上，簡單的詞法和語法分析程式碼可以用手工編寫，而不會造成過多的努力。我們將在後面的章節中看到一些例子。良好的手工編寫程式碼可能比工具生成的程式碼更快。
用斜體（例如WholeNumber）中的詞語來命名語法概念。選擇這些概念的名稱，這些名稱在語義上對人類讀者有意義，可以使內容更容易閱讀和理解。Algol 60 報告使用菱形括號 '<' 和 '>' 而不是斜體來標記語法概念。
垂直線 | 用於分隔備選方案。
單引號用於指示按原樣使用的字元。
複合符號 ::= 用於表示“定義為”，分號 ; 用於結束定義。
方括號 [ ] 用於指示選項和/或重複。
[ xxx ] xxx is optional. [ yyy ]* yyy may be repeated zero or more times. [ zzz ]+ zzz may be repeated one or more times.
我們將從一些滿足正則語法規則的簡單示例開始。
以下定義了一個十進位制Digit，它可以是 '0' 到 '9' 之間的任何一個字元。
Digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
理解為
Digit is defined as: '0' OR '1' OR '2' OR '3' OR '4' OR '5' OR '6' OR '7' OR '8' OR '9'.
可以為Letter給出類似（有點繁瑣）的定義，以涵蓋 'a' 到 'z' 和 'A' 到 'Z'。
一個WholeNumber 是一個或多個十進位制數字的序列，可以用以下兩種方式之一表示
第一種方式
WholeNumber ::= [ Digit ]+ ;
理解為
WholeNumber is defined as: Digit may be repeated one or more times
第二種方式
WholeNumber ::= Digit [ Digit ]* ;
理解為
WholeNumber is defined as: Digit AND Digit repeated zero or more times.
這些定義允許諸如 007 之類的整數。有些人不喜歡允許整數有前導零。我們可以透過使用以下定義來處理這種看法，但我們必須將數字零（僅為 0）作為特殊情況包含在內。
NonZeroDigit ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ; Digit ::= '0' | NonZeroDigit ; WholeNumber ::= '0' | NonZeroDigit [ Digit ]* ;
理解為
NonZeroDigit is defined as: '1' OR '2' OR '3' OR '4' OR '5' OR '6' OR '7' OR '8' OR '9'.
Digit is defined as: 0 OR NonZeroDigit.
WholeNumber is defined as: 0 OR as NonZeroDigit AND Digit repeated zero or more times.
最後一個定義是正式地說，一個整數要麼是 0，要麼以一個非零數字開頭，並且這個非零數字後面可以跟著任意數量的數字（包括沒有）。
在大多數程式語言中，一個Identifier 是任何以字母開頭的字母和數字的序列。一些程式語言可能還允許一些特殊字元（例如下劃線 _ 或井號 #）。Identifier 的長度也可能有一些限制，但這些限制通常被指定為以自然語言（如英語）表達的語義約束，而不是作為形式語法的一部分（例如，直到 Fortran 77，Fortran 中的Identifier 限制為最多 6 個字元）。
我們現在來看一些示例，這些示例結合在一起滿足上下文無關語法的規則。
考慮一個算術表示式，如 3 + 4 * 5。通常的約定是乘法和除法先於加法和減法，因此 3 + 4 * 5 的值為 23。如果我們希望在本例中加法先進行，則會使用括號，以便 (3 + 4) * 5 的值為 35。
我們可以用以下方式表達這些關於括號和運算子優先順序的約定。這些定義還指定具有相同優先順序的運算子是從左到右應用的。
AddSub ::= '+' | '-' ;
MulDiv ::= '*' | '/' ;
Expression ::= Secondary [ AddSub Secondary ]* ;
Secondary ::= Primary [ MulDiv Primary ]* ;
Primary ::= '(' Expression ')' | Secondary | WholeNumber | Identifier ;
有一些非常簡單的表示式沒有被上述語法覆蓋。你能在閱讀下面第三段之前找出它們可能是什麼嗎？
請注意，這是一個相對簡單的例子，運算子只有兩個優先順序級別。像 C/C++/Java 這樣的語言有十多個優先順序級別。
使它成為上下文無關而不是正則的特定方面是Expression 可以是Secondary 的方式，Secondary 可以是Primary，Primary 可以是帶括號的Expression，即Expression 可以部分地用它自己來定義；這就是所謂的遞迴定義。
未被覆蓋的表示式包括 -5 或 +4 之類的東西。為了處理這些，我們需要更改一個定義
Expression ::= [AddSub] Secondary [ AddSub Secondary ]* ;
此語法規則允許 -(+(-4))，但不允許 -+-4。