鸚鵡虛擬機器/鸚鵡語法引擎
鸚鵡語法引擎 (PGE) 是在鸚鵡上實現 Perl 6 正則表示式語法的引擎。Perl 6 正則表示式語法比 Perl 5 中的正則表示式語法強大得多，也更具表現力。由於許多其他語言中的正則表示式實現都基於 Perl 5 實現，因此 Perl 6 比它們也更強大。Perl 6 的正則表示式和語法與 Perl 5 模組“Parse::RecDescent”或解析器生成器程式 Yacc 和 Bison 等解析器生成器非常相似。然而，與 Yacc/Bison 不同的是，Perl 6 語法引擎使用遞迴下降演算法而不是 LALR 演算法。對於普通讀者來說，這些差異並不重要，但我們將在後面更詳細地討論它們。
Perl 6 語法是詞法分析器（將原始碼分解為標記）和解析器（將標記組合成模式）的組合。語法的詞法分析部分是正則表示式引擎。語法的解析部分是我們將在這裡描述的規則系統。
 | 本章的前半部分將介紹一些關於解析器和解析演算法的背景知識。如果您已經熟悉解析器，您可以跳到關於規則和操作的部分。 |
在我們進一步討論 PGE 之前，我們需要討論一些更多術語，我們還需要快速瞭解解析器使用的演算法。透過理解演算法和這些演算法的侷限性，您作為編譯器設計者應該能夠更有效地使用這些工具。
編譯器的輸入是一個原始碼檔案，用特定的高階語言編寫，它包含各種元件。考慮 C 程式語言中的以下語句
int x = add_both(5, 4);
這條語句需要被分解成更小的塊，這些塊代表各個元件。正如我們已經看到的那樣，一個塊被稱為“標記”。正則表示式引擎，即詞法分析器，用於透過將輸入迭代地與已知正則表示式匹配來將輸入分解為標記。使用這種方法，上面的語句可以分解成以下標記
KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"int" "x" "=" "add_both" "(" "5" "," "4" ")"
請注意，空格已從列表中刪除，因此只有“重要”的內容被轉換為標記。每個標記包含兩條重要的資訊：型別（“關鍵字”、“識別符號”等）和值（“int”、“x”等）。解析器可以將標記型別排列成一個模式，而操作可以使用標記值來構造 PAST 解析樹。
如果一個標記的有序組與解析器的給定輸入模式匹配，則稱為字串。對於編譯器來說，所有有效的字串集合稱為語言。指定這種語言的規則稱為語法。
編譯器的第三部分是後端。後端，也稱為目的碼生成器，將輸入源的中間資料表示（解析樹）轉換為目標語言。在我們的例子中，目標語言是 PIR 或 PBC。所有編譯器都是由這三個關鍵元件組成的：詞法分析器、解析器和後端。鸚鵡為詞法分析器提供了正則表示式，並處理所有目標語言生成。作為編譯器設計者，您唯一需要設計的是解析器。但是，關於解析器，我們還需要了解很多資訊。
解析輸入標記字串有兩種方法。首先，我們可以進行自頂向下解析，從最高級別的標記開始嘗試匹配。其次，我們可以進行自底向上解析，從小的標記開始嘗試將它們組合成越來越大的標記，直到我們得到最高級別。兩種解析方法的最終目標都是將輸入標記字串縮減為單個匹配標記。
yacc 或 Bison 等解析器生成器會生成自底向上的解析器。
作為一個簡單的自底向上解析示例，我們將從標記字串的左側開始，嘗試將小的標記組合成更大的標記。最終，我們想要的是一個代表整個輸入的標記。我們透過利用兩個基本操作來實現這一點：移進和歸約。移進操作意味著我們將一個新的輸入標記讀入解析器。歸約操作意味著我們將匹配的從小標記組成的模式轉換為單個更大的標記。讓我們將此方法應用到下面的實踐中。
KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"int" "x" "=" "add_both" "(" "5" "," "4" ")"
如果我們意識到標記“int”和“x”是一個變數宣告，那麼上面的字串將變成下面的字串。我們將前兩個標記歸約為一個變數宣告標記
DECLARATION OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"=" "add_both" "(" "5" "," "4" ")"
現在，我們從左到右移動，將標記移進解析器。在我們到達括號之前，我們無法看到可以歸約的任何內容。我們可以將開括號和閉括號，以及它們中間的所有標記歸約為一個引數列表，如下所示
DECLARATION OPERATOR IDENTIFIER ARGUMENT_LIST
"=" "add_both"
現在，我們知道，當我們有一個識別符號後面跟著一個引數列表時，它是一個函式呼叫。我們將這兩個標記歸約為一個函式呼叫標記
DECLARATION OPERATOR FUNCTION_CALL
"="
最後，透過跳過一些步驟，我們可以將其轉換為賦值語句
ASSIGNMENT_STATEMENT
每次我們將一組小的標記歸約為一個更大的標記時，我們都會將它們新增到樹中。我們將小的標記新增為更大標記的子節點。我們在這裡討論的這種型別的解析器稱為“移進-歸約”解析器，因為這些是解析器執行的操作。移進-歸約解析器的一個子集，對於算術表示式很有用，稱為運算子優先順序解析器，我們將在下面進一步討論。
- 注意
- 移進-歸約解析器容易出現一種稱為移進-歸約衝突的特定型別的錯誤。移進-歸約衝突是由新的輸入標記導致解析器移進或歸約造成的。換句話說，解析器對於輸入標記有多個選項。包含可能出現移進-歸約衝突的語法稱為二義語法。雖然有一些方法可以糾正這種衝突，但通常最好重新設計語言語法以完全避免它們。有關這方面的更多資訊，請參見頁面底部的資源部分。
自頂向下解析器與自底向上解析器略有不同。我們從最高級別的標記開始，嘗試透過測試更小的模式來進行匹配。這個過程可能效率低下，因為我們經常必須測試許多不同的模式才能找到一個匹配的模式。但是，我們獲得了一種避免移進-歸約衝突的能力，也獲得了一定的魯棒性，因為我們的解析器在放棄之前會嘗試多個選項。假設我們有一個標記字串和一個用於 STATEMENT 標記的頂層定義。以下是用上下文無關語法表示的定義
STATEMENT := ASSIGNMENT | FUNCTION_CALL | DECLARATION
當然，這是一個簡單的示例，不足以滿足像 C 這樣的語言。“:=” 符號類似於“由…組成”這句話。豎線“|”等同於“或”。因此，上面的語句表示“語句由賦值或函式呼叫或宣告組成”。
我們有這條語法規則，它告訴我們語句是什麼，我們也有我們的輸入標記字串
KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"int" "x" "=" "add_both" "(" "5" "," "4" ")"
自頂向下解析器將嘗試 STATEMENT 定義中的每個備選方案，以檢視它是否匹配。如果一個不匹配，它將移動到下一個備選方案，然後再次嘗試。因此，我們先嚐試 ASSIGNMENT 規則，而 ASSIGNMENT 定義如下
ASSIGNMENT := (VARIABLE_NAME | DECLARATION) '=' (EXPRESSION | FUNCTION_CALL)
圓括號用於將事物組合在一起。用英語來說，這條語句表示“賦值是一個變數名或一個宣告，後面跟著一個‘=’，後面跟著一個表示式或一個函式呼叫”。因此，為了滿足 ASSIGNMENT，我們先嚐試 VARIABLE_NAME，然後嘗試 DECLARATION。字串“int x”是一個宣告而不是一個簡單的變數名，因此 VARIABLE_NAME 失敗，而 DECLARATION 成功。接下來，‘=’ 匹配。為了滿足最後一段，我們先嚐試 EXPRESSION，它失敗了，然後我們嘗試 FUNCTION_CALL，它成功了。我們以此類推，嘗試備選方案，逐漸從更大和更小的標記移動到更小的標記，直到我們匹配了整個輸入字串。一旦我們匹配了最後一個輸入標記，如果我們也滿足了頂層匹配，那麼解析器就會成功。
這種型別的解析器稱為“遞迴下降”解析器，因為我們遞迴到每個子規則中，然後從解析樹的頂部逐漸下降到底部。一旦最後一個子規則成功，整個匹配就成功，解析器返回。
在這個過程中，當一個規則匹配時，我們在 PAST 樹中建立一個節點。因為我們在一個規則成功之前先測試所有子規則，所以所有子節點在更高層節點建立之前就已經建立好了。這使得解析樹從底部向上建立，即使我們是從樹的頂部開始向下移動的。
自頂向下解析器可能效率低下，因為解析器會嘗試匹配顯然無法成功的模式。但是，我們有一些技巧可以用來“修剪”可能性樹，透過將解析器引導到特定路徑或阻止它沿著不會匹配的分支進行移動。我們還可以阻止解析器從子規則回溯到更大的規則，這有助於減少不必要的重複。
像 PGE 中使用的遞迴下降解析器一樣，是一種自頂向下的解析器。這意味著它試圖從最高級別的定義開始，並逐步向下匹配給定的輸入。頂級規則始終稱為 TOP。之後，我們可以根據需要建立更多其他規則來指定我們的整個語法。讓我們從建立一個非常簡單的遞迴下降解析器開始，嘗試解析我們之前給出的輸入
int x = add_both(5, 4);
以下是我們基本解析器的一部分
rule TOP {
<assignment> | <function_call> | <declaration>
}
rule assignment {
<lvalue> '=' <rvalue>
}
rule lvalue {
<variable_name> | <variable_declaration>
}
rule rvalue {
<expression> | <function_call>
}
rule function_call {
<identifier> '(' <arguments> ')'
}
rule variable_declaration {
'int' <identifier>
}
這只是解析器的一部分，但思路應該很清楚。我們用常量或其他規則來定義每個規則。尖括號“<”和“>”表示我們需要匹配子規則。單引號用於表示字面字串常量。
規則有一些我們可以使用的基本運算子，其中一些已經討論過。熟悉正則表示式的人會認識大多數運算子。
| 運算子 | 含義 | 示例 | 解釋 |
|---|---|---|---|
* |
"零個或多個" | <number>* '.' <number> |
接受一個字串，其中包含零個或多個數字，後面跟著一個點，最後跟著一個數字。例如：1234.5 |
+ |
"一個或多個" | <letter>+ <number> |
一個或多個字母，後面跟著一個數字。例如：abcde5，或 ghij6 |
? |
"一個或零" | <number>? '.' <number>+ |
一個可選的數字，後面跟著一個點和一個一個或多個數字的字串。例如：1.234 或 .234 |
[] |
分組 | <letter> [<letter> | <number>]* |
一個字母，後面跟著任意數量的字母或數字。例如：a123、ident、wiki2txt |
我們已經討論過或運算子“|”。以下是一些示例。
- 十進位制數
rule decimal_numbers {
<digit>* '.' <digit>+
|<digit>+ '.' <digit>*
}
- 函式引數
rule function_parameters {
'(' [ <identifier> [ ',' <identifier> ]* ]? ')'
}
當 PGE 成功匹配規則時，它會建立一個特殊的“匹配物件”，其中包含有關匹配的資訊。此匹配物件可以傳送到用 PIR 或 NQP 編寫的函式進行處理。接收匹配物件的處理函式稱為 **操作**。語法中的每個規則都具有一個名稱相同的關聯操作函式。
當我們完成成功匹配後，我們需要將匹配物件傳送到操作方法。我們使用特殊符號 `{*}` 來執行此操作。`{*}` 傳送當前匹配物件，不一定是完整的物件。如果需要，您可以在規則中多次呼叫 `{*}` 以多次呼叫操作方法。以下是一個示例
rule k_r {
{*} #Calls the action method with an empty match object
'hello'
{*} #calls the action method after matching 'hello'
'world'
{*} #Calls the action method after matching 'hello' 'world'
}
關於操作方法有兩點需要記住
- 解析器從左到右，從上到下移動。在上面的 k_r 示例中，如果輸入是“hello johnny”，則操作方法將被呼叫前兩次，但該規則將無法匹配單詞“world”，並且操作方法將不會被呼叫第三次。
- 即使還有更多嘗試的可能性，解析器也會在成功匹配後返回。考慮以下示例，其中只有一個操作方法可以根據備選方案的結果被呼叫。在這個例子中，如果輸入是“hello franky”，則操作方法只會被呼叫 `{*}` 後的 'franky'。在匹配後，解析器返回，不再嘗試匹配 'johnny'。
rule say_hello {
'hello'
[
| 'tommy' {*}
| 'franky' {*}
| 'johnny' {*}
]
}
有時指定哪個操作方法被呼叫非常有用，當有一系列可能性時。這是因為我們希望以不同的方式對待某些匹配。為了以不同的方式對待操作方法，我們使用一個特殊的註釋語法
rule say_hello {
'hello'
[
| 'tommy' {*} #= tommy
| 'franky' {*} #= franky
| 'johnny' {*} #= johnny
]
}
特殊的 “#=” 符號不是常規註釋。相反，它是操作方法的第二個引數，稱為“鍵”。如果您使用 “#=” ，則操作方法將接收兩個引數：匹配物件和鍵。然後，您可以測試鍵的值來確定如何處理匹配物件。我們將在下一章關於 NQP 的內容中詳細討論。