LALR-1 剖析器產生器

一個用於 Erlang 的 LALR-1 剖析器產生器，類似於 yacc。它將 BNF 文法定義作為輸入，並產生 Erlang 程式碼以供剖析器使用。

要理解此文字，您還必須查看 UNIX(TM) 手冊中的 yacc 文件。這很可能是為了理解剖析器產生器的概念，以及使用有限的前瞻進行 LALR 剖析的原理和問題所必需的。

Brian W. Kernighan 和 Rob Pike 的《The UNIX Programming Environment》一書的第 8 章中有一個關於 yacc 的不錯介紹。

預設 Yecc 選項

（主機作業系統）環境變數 ERL_COMPILER_OPTIONS 可用於提供預設的 Yecc 選項。其值必須為有效的 Erlang 項。如果該值是列表，則會照原樣使用。如果不是列表，則會將其放入列表中。

該列表會附加到傳遞給 file/2 的任何選項。

可以使用 compile:env_compiler_options/0 檢索該列表。

前處理

yecc 模組中未提供用於預處理要剖析的文字（程式）的 掃描器。掃描器充當一種詞彙查詢常式。可以編寫一個僅使用字元符號作為終端符號的文法，從而消除對掃描器的需求，但這會使剖析器更大且更慢。

使用者應實作一個掃描器，該掃描器分割輸入文字，並將其轉換為一個或多個符號列表。每個符號都應該是一個元組，其中包含有關語法類別、文字中的位置（例如行號）以及在文字中找到的實際終端符號的資訊：{Category, Position, Symbol}。

如果終端符號是類別的唯一成員，並且符號名稱與類別名稱相同，則符號格式可以是 {Symbol, Position}。

掃描器產生的符號列表應以一個特殊的 end_of_input 元組結束，剖析器正在尋找該元組。此元組的格式應為 {Endsymbol, EndPosition}，其中 Endsymbol 是一個與語法規則的所有終端和非終端類別區分的識別符號。Endsymbol 可以在文法檔案中宣告。

最簡單的情況是將輸入字串分割為識別符號（原子）列表，並將這些原子同時用作類別和符號的值。例如，輸入字串 aaa bbb 777, X 可以掃描（符號化）為

[{aaa, 1}, {bbb, 1}, {777, 1}, {',' , 1}, {'X', 1},
 {'$end', 1}].

這假設這是輸入文字的第一行，並且 '$end' 是區分的 end_of_input 符號。

當編寫新的掃描器時，可以使用 io 模組中的 Erlang 掃描器作為起點。研究 yeccscan.erl，以了解如何在 io:scan_erl_form/3 的頂部新增篩選器，以提供一個 Yecc 掃描器，該掃描器會在使用 Yecc 剖析器剖析文法檔案之前對其進行符號化。更通用的掃描器實作方法是使用掃描器產生器，例如 leex。

文法定義格式

文法檔案中允許使用以 '%' 開頭的 Erlang 樣式 註解。

每個 宣告 或 規則 都以句點（字元 '.'）結尾。

文法以一個可選的 標頭 區段開始。標頭會放在產生的檔案中的第一個位置，位於模組宣告之前。標頭的目的是提供一種使 EDoc 產生的文件看起來更美觀的方法。每個標頭行都應以雙引號括起來，並且會在行之間插入換行符。例如

Header "%% Copyright (C)"
"%% @private"
"%% @Author John".

接下來是宣告規則中要使用的 非終端類別。例如

Nonterminals sentence nounphrase verbphrase.

非終端類別可以用於文法規則的左側（= lhs 或 head）。它也可以出現在規則的右側。

接下來是宣告 終端類別，這些類別是掃描器產生的符號類別。例如

Terminals article adjective noun verb.

終端類別只能出現在文法規則的右側（= rhs）中。

接下來是宣告 根符號，或文法的起始類別。例如

Rootsymbol sentence.

此符號應出現在至少一個文法規則的 lhs 中。這是最通用的語法類別，剖析器最終會將每個輸入字串剖析為該類別。

在根符號宣告之後，是一個可選的 end_of_input 符號宣告，您的掃描器應該使用該符號。例如

Endsymbol '$end'.

接下來是一個或多個 運算子優先順序 的宣告（如果需要）。它們用於解決移位/歸約衝突（請參閱 yacc 文件）。

運算子宣告的範例

Right 100 '='.
Nonassoc 200 '==' '=/='.
Left 300 '+'.
Left 400 '*'.
Unary 500 '-'.

這些宣告表示 '=' 被定義為優先順序為 100 的 右結合二元 運算子，'==' 和 '=/=' 是 不具結合性 的運算子，'+' 和 '*' 是 左結合二元 運算子，其中 '*' 的優先順序高於 '+'（一般情況），而 '-' 是優先順序高於 '*' 的 一元 運算子。'==' 不具結合性的事實表示像 a == b == c 這樣的運算式被視為語法錯誤。

某些規則會被指派優先順序：每個規則都會從規則右側提到的最後一個終端符號取得其優先順序。也可以宣告非終端符號的優先順序，即「向上一個層級」。當運算子重載時，這很實用（另請參閱下面的範例 3）。

接下來是 文法規則。每個規則都具有一般形式

Left_hand_side -> Right_hand_side : Associated_code.

左側是非終端類別。右側是一個或多個非終端或終端符號的序列，它們之間有空格。相關的程式碼是零個或多個 Erlang 運算式（以逗號 ',' 作為分隔符號）。如果相關的程式碼為空，則會省略分隔冒號 ':'。最後一個句點表示規則的結束。

諸如 '{'、'.' 等符號在用作文法規則中的終端或非終端符號時，必須用單引號括起來。應避免使用符號 '$empty'、'$end' 和 '$undefined'。

文法檔案的最後一部分是一個可選的 Erlang 程式碼區段（= 函數定義），該區段會「按原樣」包含在產生的剖析器檔案中。此區段必須以虛擬宣告或關鍵字開始

Erlang code.

在此區段之後，不得有任何語法規則定義或其他宣告。為了避免與內部變數衝突，請勿在此區段的 Erlang 程式碼中，或在與個別語法規則相關的程式碼中使用以兩個底線字元 ('__') 開頭的變數名稱。

可選的 expect 宣告可以放置在最後一個可選的 Erlang 程式碼區段之前的任何位置。它用於抑制關於文法模糊時通常會發出的衝突警告。一個範例

Expect 2.

如果移位/歸約衝突的數量與 2 不同，或者存在歸約/歸約衝突，則會發出警告。

範例

一個用於剖析清單運算式（具有空相關程式碼）的文法

Nonterminals list elements element.
Terminals atom '(' ')'.
Rootsymbol list.
list -> '(' ')'.
list -> '(' elements ')'.
elements -> element.
elements -> element elements.
element -> atom.
element -> list.

此文法可用於產生一個剖析器，該剖析器剖析清單運算式，例如 (), (a), (peter charles), (a (b c) d (())), ...，前提是您的掃描器會將例如輸入 (peter charles) 符號化為如下形式

[{'(', 1} , {atom, 1, peter}, {atom, 1, charles}, {')', 1},
 {'$end', 1}]

當剖析器使用文法規則來剖析輸入字串的（部分）作為文法詞組時，會評估相關的程式碼，並且最後一個運算式的值會成為剖析詞組的值。剖析器稍後可以使用此值來建構結構，這些結構是目前詞組所屬的較高詞組的值。最初與終端類別詞組（即輸入符號）相關的值是符號元組本身。

以下是上面文法的範例，其中新增了結構建構程式碼

list -> '(' ')' : nil.
list -> '(' elements ')' : '$2'.
elements -> element : {cons, '$1', nil}.
elements -> element elements : {cons, '$1', '$2'}.
element -> atom : '$1'.
element -> list : '$1'.

將此程式碼新增到文法規則後，剖析器會在剖析輸入字串 (a b c). 時產生以下值（結構）。這仍然假設這是掃描器符號化的第一個輸入行

{cons, {atom, 1, a}, {cons, {atom, 1, b},
                            {cons, {atom, 1, c}, nil}}}

相關的程式碼包含 虛擬變數 '$1'、'$2'、'$3' 等，這些變數是指（繫結到）剖析器先前與規則右側的符號相關聯的值。當這些符號是終端類別時，這些值是輸入字串的符號元組（請參閱上文）。

相關的程式碼不僅可以用於建構與詞組相關的結構，還可以在剖析過程中用於語法和語義測試、列印輸出動作（例如用於追蹤）等等。由於符號包含位置（行號）資訊，因此可以產生包含行號的錯誤訊息。如果規則右側之後沒有相關的程式碼，則會將值 '$undefined' 與詞組相關聯。

文法規則的右側可以為空。這通過使用特殊符號 '$empty' 作為 rhs 來指示。那麼，上面的清單文法可以簡化為

list -> '(' elements ')' : '$2'.
elements -> element elements : {cons, '$1', '$2'}.
elements -> '$empty' : nil.
element -> atom : '$1'.
element -> list : '$1'.

產生剖析器

要呼叫剖析器產生器，請使用以下命令

yecc:file(Grammarfile).

如果語法不是 LALR 類型（例如，過於模糊），Yecc 會顯示錯誤訊息。如果沒有運算子優先權宣告，則移位/歸約衝突會優先選擇移位。關於運算子優先權的使用，請參閱 yacc 文件。

輸出檔案包含一個解析器模組的 Erlang 原始碼，模組名稱等於 Parserfile 參數。編譯後，可以如下方式呼叫解析器（假設模組名稱為 myparser）：

myparser:parse(myscanner:scan(Inport))

如果生成解析器時包含自訂的序言檔，而不是預設檔案 lib/parsetools/include/yeccpre.hrl，則呼叫格式可能會有所不同。

使用標準序言時，此呼叫會返回 {ok, Result}，其中 Result 是語法檔案的 Erlang 程式碼所建立的結構，或者，如果輸入中有語法錯誤，則返回 {error, {Position, Module, Message}}。

Message 可以透過呼叫 Module:format_error(Message) 轉換為字串，並使用 io:format/3 列印。

注意

預設情況下，生成的解析器不會將錯誤訊息列印到螢幕上。使用者必須透過列印返回的錯誤訊息，或者在與語法檔案的語法規則相關聯的 Erlang 程式碼中插入測試和列印指令來完成此操作。

如果使用以下呼叫格式，也可以使解析器在需要時要求更多的輸入 token：

myparser:parse_and_scan({Function, Args})
myparser:parse_and_scan({Mod, Tokenizer, Args})

tokenizer Function 可以是一個 fun 或一個 tuple {Mod, Tokenizer}。每當需要新的 token 時，就會執行呼叫 apply(Function, Args) 或 apply({Mod, Tokenizer}, Args)。例如，這使得從檔案逐個 token 解析成為可能。

上面使用的 tokenizer 必須實作為返回以下其中之一：

{ok, Tokens, EndPosition}
{eof, EndPosition}
{error, Error_description, EndPosition}

這符合 Erlang io 函式庫模組中掃描器使用的格式。

如果立即返回 {eof, EndPosition}，則對 parse_and_scan/1 的呼叫會返回 {ok, eof}。如果在解析器預期輸入結束之前返回 {eof, EndPosition}，則 parse_and_scan/1 當然會返回錯誤訊息（請參閱上文）。否則，會返回 {ok, Result}。

更多範例

1. 一個將中綴算術表達式解析為前綴表示法的語法，沒有運算子優先權

Nonterminals E T F.
Terminals '+' '*' '(' ')' number.
Rootsymbol E.
E -> E '+' T: {'$2', '$1', '$3'}.
E -> T : '$1'.
T -> T '*' F: {'$2', '$1', '$3'}.
T -> F : '$1'.
F -> '(' E ')' : '$2'.
F -> number : '$1'.

2. 具有運算子優先權的相同語法會更簡單

Nonterminals E.
Terminals '+' '*' '(' ')' number.
Rootsymbol E.
Left 100 '+'.
Left 200 '*'.
E -> E '+' E : {'$2', '$1', '$3'}.
E -> E '*' E : {'$2', '$1', '$3'}.
E -> '(' E ')' : '$2'.
E -> number : '$1'.

3. 一個重載的減號運算子

Nonterminals E uminus.
Terminals '*' '-' number.
Rootsymbol E.

Left 100 '-'.
Left 200 '*'.
Unary 300 uminus.

E -> E '-' E.
E -> E '*' E.
E -> uminus.
E -> number.

uminus -> '-' E.

4. 用於解析語法檔案的 Yecc 語法，包括它自己

Nonterminals
grammar declaration rule head symbol symbols attached_code
token tokens.
Terminals
atom float integer reserved_symbol reserved_word string char var
'->' ':' dot.
Rootsymbol grammar.
Endsymbol '$end'.
grammar -> declaration : '$1'.
grammar -> rule : '$1'.
declaration -> symbol symbols dot: {'$1', '$2'}.
rule -> head '->' symbols attached_code dot: {rule, ['$1' | '$3'],
        '$4'}.
head -> symbol : '$1'.
symbols -> symbol : ['$1'].
symbols -> symbol symbols : ['$1' | '$2'].
attached_code -> ':' tokens : {erlang_code, '$2'}.
attached_code -> '$empty' : {erlang_code,
                 [{atom, 0, '$undefined'}]}.
tokens -> token : ['$1'].
tokens -> token tokens : ['$1' | '$2'].
symbol -> var : value_of('$1').
symbol -> atom : value_of('$1').
symbol -> integer : value_of('$1').
symbol -> reserved_word : value_of('$1').
token -> var : '$1'.
token -> atom : '$1'.
token -> float : '$1'.
token -> integer : '$1'.
token -> string : '$1'.
token -> char : '$1'.
token -> reserved_symbol : {value_of('$1'), line_of('$1')}.
token -> reserved_word : {value_of('$1'), line_of('$1')}.
token -> '->' : {'->', line_of('$1')}.
token -> ':' : {':', line_of('$1')}.
Erlang code.
value_of(Token) ->
    element(3, Token).
line_of(Token) ->
    element(2, Token).

注意

符號 '->' 和 ':' 必須以特殊方式處理，因為它們既是語法表示法的元符號，又是 Yecc 語法的終端符號。

5. lib/stdlib/src 目錄中的檔案 erl_parse.yrl 包含 Erlang 的語法。

注意

語法測試用於與某些規則相關聯的程式碼中，當測試失敗時，會拋出錯誤（並由生成的解析器捕獲以產生錯誤訊息）。使用對 return_error(ErrorPosition, Message_string) 的呼叫可以實現相同的效果，該呼叫在 yeccpre.hrl 預設標頭檔案中定義。

檔案

lib/parsetools/include/yeccpre.hrl

參見

• Aho & Johnson: 'LR Parsing', ACM Computing Surveys, vol. 6:2, 1974.

• Kernighan & Pike: The UNIX programming environment, 1984.