語法分析組合子

在計算機編程中 語法分析組合子 是一個 高階函數 ，它接受幾個的語法分析器作為輸入，並返回一個新的語法分析函器作為其輸出。 在這個上下文中， 語法分析器 是一個函數，它接受字符串作為輸入，返回的一些結構作為輸出，通常為 分析樹 或一組索引表示在字符串中成功停止分析的位置。 分析器組合子使用 遞歸下降分析 戰略，提倡模塊式建造和測試。 這種分析技術是所謂的 組合分析。

使用組合子構建的分析器易於構造、可讀、模塊化、結構良好且易於維護它們被廣泛地用於 領域特定語言（如數據庫的自然語言接口）的編譯器和處理器的原型設計中，在這些語言中，複雜多樣的語義操作與語法處理緊密集成。1989年，Richard Frost和John Launchbury演示了使用語法分析組合子構造的自然語言解釋器。Graham Hutton在1992年也使用了高階函數進行基本解析。S.D. Swierstra在2001年還展示了解析器組合器的實用方面。在2008年，Frost、Hafiz和Callaghan用Haskell中描述了一組語法分析組合子，它們解決了長期存在的通用左遞歸的問題，它也是一個完整的，只需要多項式時間、空間的自頂向下解析工具。

基本想法

在任何一種編程語言，擁有 頭等函數，分析器組合子可以用基本的分析器構造用於更複雜的規則的分析程序。 例如，上下文無關文法 (CFG)的產生式可能有一個或多個備選推導方案，每個備選方案可以由一系列的 非終結符 和/或 終結符，或者推導方案可以由一個單一的非終結符或終結符端或空串組成。如果一個簡單的分析程序適用於這些推導方案，語法分析組合子可以用來組合這些分析器，返回一個新的分析器，這可以識別出的任何推導方案。

在支持 運算符重載 的語言中，一個語法分析組合子可以使用 中綴 操作符形式，用於將不同的分析器膠合成一個完整的規則。語法分析組合子使得分析程序能以一個嵌入式的風格編寫，這使得程序結構上類似於正則文法的規則。 因此，實現方式可以被認作為可執行的規格並有所有的相關優點。 (值得注意的是：可讀性)

組合子

為了保持討論比較簡單，我們只討論語法分析組合子作為 識別器 的情況。 如果輸入串的長 #input ，其成員通過一個索引 j，一個 識別器 是一個語法分析器，它返回一組索引，表示分析器在位置 j成功地識別出了一個序列的標記。一個空的結果表明在索引 j識別器沒有識別到任何序列的開始。

• empty 識別器識別出空串。 這種分析器總是成功，在返回一個包含目前位置的單元素集合：

$empty(j)=\{j\}$

• 一個識別器 term x 識別出終結符 x。如果 j 位置上的token是 x，這種分析器返回元素為 j＋1的單元素集合 否則，返回空集。

$term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ element of }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}$

注意可能有多個不同的方法來分析一個字符串，同時在相同的索引處結束：這表明一個 二義性文法 。簡單的識別器不承認這些二義性；每個可能的結束索引在結果集中只出現一次。 對於更完整的結果集合，必須返回一個更複雜的對象，例如 分析樹。

下面的定義的兩個基本的識別器 p 和 q，我們可以界定兩個主要的語法分析組合子，用於選擇和順序：

• '選擇'的語法分析組合子, ⊕，在相同的輸入位置 j 應用兩個的識別器並返回兩者結果的和。它是作為一個 p 和 q 之間的一個中綴操作符：

$(p\oplus q)(j)=p(j)\cup q(j)$

• 順序識別器是使用⊛語法分析組合子完成的。像⊕一樣它是作為 p 和 q 之間的中綴運算符。它在輸入位置 j應用第一個識別器 p ，然後第二個識別器 q 應用於第一識別器返回的每個結果。⊛最終返回q的結果的併集。

$(p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}$

例

考慮一個有高度二義性的 上下文無關文法, s ::= 'x' s s|ε. 使用上面定義的組合子，我們可以模塊化的定義可執行的符號，這種語法在一個現代化的函數式語言(例如 Haskell)作為 s = term 'x' <*> s <*> s <+> empty。當識別器 s 在一個輸入序列 ..... 的位置 1上被應用，根據上述定義，它將返回的結果集合 {5,4,3,2}.