形式語言與剖析

形式語言是一組定義於某個字母表上的有限字串。文法定義能在該集合中推導出字串的產生式。編譯器前端使用此模型，將區域性的記號辨識與遞迴的程式結構分離。

Chomsky 類別 #

Chomsky 階層依產生式限制分類文法：

第 3 型、正規文法描述由有限自動機辨識的正規語言。正規表示式與詞法分析器在此層運作。
第 2 型、上下文無關文法（CFG）每個產生式左側有一個非終結符，並由下推自動機辨識。
第 1 型、上下文相關文法限制產生式不得縮短句型，但定義的開始符號情況除外。
第 0 型、無限制文法不施加可相提並論的產生式限制。

平衡分隔符號說明了這個界線。有限自動機無法記住無界的巢狀深度，而 CFG 可以使用如下的遞迴：Group → '(' Group ')' Group | ε。

推導、樹與歧義 #

推導會將產生式從開始符號套用至終結符。剖析樹記錄該推導的階層結構。字串具有多棵剖析樹或等價的最左推導時，文法即具有歧義。

text

Expr → Expr '-' Expr | number

在該文法下，輸入 number - number - number 具有互相競爭的分組方式。請重寫文法以編碼結合律，例如使用左遞迴的 Expr → Expr '-' Term | Term；或者在其衝突解決原則有意設計時，使用剖析器產生器的優先順序宣告。當產生的樹必須直接表示語言語意時，文法結構較為理想。

由上而下與由下而上剖析 #

LL(\(k\)) 剖析器由左至右讀取，建立最左推導，並根據有限的前瞻選擇產生式。遞迴下降剖析器會直接實作此風格；預測文法必須消除左遞迴，並讓替代項在決策點可區分。

LR 剖析器由左至右讀取，透過移入記號與歸約已辨識的句柄，建立最右推導的反向結果。LR 系列剖析器能處理左遞迴的運算式文法與更廣泛的決定性 CFG，但剖析器產生器衝突表示存在歧義或優先順序原則的規格不足。

前端邊界與錯誤設計 #

詞法分析器將字元分組為記號，例如識別碼、常值、運算子與原始碼位置。剖析器依據文法產生式消費這些記號，並產生語法樹或語意動作。當註解、跳脫、數字拼寫不影響巢狀或結構時，請將詞法關注事項留在產生式之外。

將錯誤設計為文法介面的一部分。詞法分析器必須識別無效字元序列並安全前進。剖析器應回報非預期記號與位置，然後在選定的分隔符號（例如陳述式終止符或右大括號）處同步。復原規則必須保證進度；接受任意記號只會隱藏後續錯誤，並破壞產生的樹。