鸚鵡虛擬機器/Squaak 教程/運算子和優先順序
第一集： 簡介
第二集： 窺探編譯器內部
第三集： Squaak 細節和第一步
第四集： PAST 節點和更多語句
第五集： 變數宣告和作用域
第六集： 作用域和子程式
第七集： 運算子和優先順序
第八集： 雜湊表和陣列
第九集： 總結和結論
到目前為止，我們已經實現了 Squaak 語言的很大一部分。我們已經看到了賦值、控制流語句、變數宣告和作用域、子程式和呼叫。到目前為止，我們的表示式僅限於單個值，例如字串文字和整數常量。在本集中，我們將增強 Squaak 以便它可以處理運算子，這樣你就可以構建更復雜的表示式。
我們首先簡要介紹一下使用遞迴下降解析器（PCT 生成的解析器）解析表示式時遇到的問題。考慮以下迷你語法，它是一個非常基本的計算器。
rule TOP {
<expression>*
}
rule expression {
<term>
}
rule term {
<factor> [ <addop> <factor> ]*
}
token addop { '+' | '-' }
rule factor {
<value> [ <mulop> <value> ]*
}
token mulop { '*' | '/' | '%' }
rule value{
| <number>
| '(' <expression> ')'
}
這種基本的表示式語法透過利用遞迴下降解析器的性質來實現運算子優先順序（如果你還沒有見過這個詞，就在谷歌上搜索一下）。然而，用這種方式解析表示式的最大缺點是，解析樹可能會變得相當大。也許更重要的是，解析過程效率不高。讓我們來看一些示例輸入。我們不會像在 第二集 中那樣顯示解析樹，而只是顯示一個概要。
輸入：42 導致以下解析樹
TOP
expression
term
factor
value
number
42
如你所見，這個單個數字的輸入將在解析實際數字之前呼叫 6 個語法規則。你可能會覺得這還不錯。
輸入："1 + 2" 導致以下解析樹（我們現在忽略運算子）
TOP
expression
term
factor
| value
| number
| 1
factor
value
number
2
只調用了幾個語法規則，這也不是什麼大問題。
輸入："（1 + 2）* 3" 導致以下解析樹
TOP
expression
term
factor
value
| expression
| term
| | factor
| | value
| | number
| | 1
| term
| factor
| value
| number
| 2
value
number
3
正確；僅僅為了解析這個簡單的輸入就呼叫了 16 個語法規則。我認為這有點效率低下。重點是，使用遞迴下降解析器實現運算子優先順序有一些問題，而且考慮到有更好的方法來解析像這樣的表示式，所以這不是最好的方法。檢視 這個很好的解釋 或在谷歌上搜索。
我想向你解釋一下，自底向上解析是如何針對表示式（或者一般意義上的自底向上解析器；Yacc/Bison 是解析器生成器，它們會根據你的語法規範生成自底向上解析器）工作的，同時考慮運算子優先順序。然而，我已經大約 6 年沒有在 CS 課程中學過這個了，我不記得具體的細節。如果你真的想知道，請檢視上一節末尾的連結。實際上值得一看。現在，我假設你知道問題所在，這樣我就可以立即介紹針對基於 PCT 的編譯器的解決方案。在你解析輸入的某個時刻，你可能會遇到一個表示式。在這一點上，我們希望解析器從自頂向下切換到自底向上解析。鸚鵡語法引擎支援這一點，並且可以使用以下方式進行使用
rule expression is optable { ... }
請注意，我們在這裡使用了“表示式”這個詞，但你可以用任何名字來命名它。這聲明瞭，每當你需要一個表示式時，就會啟用自底向上解析器。當然，這個“optable”必須填充一些我們需要才能解析的運算子。這可以透過以下方式宣告運算子來實現
proto 'infix:*' is tighter('infix:+') { ... }
這定義了運算子“*”（“infix:”是一個字首，告訴運算子解析器這個運算子是一箇中綴運算子；還有其他型別，例如字首、字尾和其他）。“is tighter”子句表示“*”運算子的優先順序高於“+”運算子。正如你可能已經猜到的那樣，還有其他子句來宣告等效優先順序（“is equiv”）和較低優先順序（“is looser”）。
正確拼寫所有子句（例如，“is equiv”）非常重要（例如，不要寫成“is equil”），否則你可能會在嘗試執行編譯器時收到一些神秘的錯誤訊息。請檢視參考文獻部分中的運算子表指南，其中包含更多關於此方面的詳細資訊。
當然，表示式解析器不僅僅解析運算子，它還必須解析運算元。那麼，我們如何宣告代表運算元的最基本實體呢？它可以是任何東西，從一個基本的整數常量、一個函式呼叫，甚至是一個函式定義（但是將兩個函式定義加起來並沒有多大意義，對吧？）。運算元以遞迴下降方式解析，因此解析器必須在某個地方從自底向上（表示式解析）切換回自頂向下。為了宣告這個“切換”點，請編寫以下內容
proto 'term:' is tighter('prefix:-')
is parsed(&term) { ... }
名稱“term:”是運算子自底向上解析器的內建名稱；每當需要一個新的運算元時，它都會被呼叫。“is parsed”子句告訴解析器“term”（它意外地看起來像“term:” ，但你也可以給它起任何其他名字）解析運算元。
注意：在“term:”規則的宣告中新增“is tighter”子句非常重要。否則你的表示式解析器將無法工作！我在這方面的知識有限，但我通常將它定義為相對於已定義的最緊運算子的“is tighter”。
我們已經定義了表示式（自底向上）解析器的入口點和出口點，現在是時候新增運算子了。讓我們看一下 Squaak 的運算子及其優先順序。運算子按優先順序遞減的順序列出（以便高優先順序運算子列在頂部）。（我不確定這個優先順序表與其他語言相比是否通用；某些運算子可能與你習慣的運算子相比具有不同的優先順序。至少數學運算子是按照標準數學規則組織的）。
unary "-" unary "not" * / % + - .. < <= >= > != == and or
（“..”是字串連線運算子）。除了為表示式解析器定義入口點和出口點之外，你還需要定義一個運算子作為參考點，以便可以相對於該參考點定義其他運算子的優先順序。我個人更喜歡將優先順序最低的運算子宣告為參考點。這可以透過以下方式實現
proto 'infix:or' is precedence('1') { ... }
現在，可以定義其他運算子
proto 'infix:and' is tighter('infix:or') { ... }
proto 'infix:<' is tighter('infix:and') { ... }
proto 'infix:+' is tighter('infix:<') { ... }
proto 'infix:*' is tighter('infix:+') { ... }
proto 'prefix:not' is tighter('infix:*') { ... }
proto 'prefix:-' is tighter('prefix:not') { ... }
請注意，有些運算子缺失。請檢視練習部分。有關運算子表使用的更多詳細資訊，請檢視鸚鵡儲存庫中的 docs/pct/pct_optable_guide.pod。
Squaak 有兩個邏輯運算子：and 和 or；and 只有當兩個運算元都計算為真時才返回真，而 or 只要至少有一個運算元計算為真就返回真。兩個運算元都是短路計算的，這意味著如果不需要計算兩個運算元，它們就不會計算。例如，如果 and 運算子的第一個運算元計算為假，那麼就沒有必要計算第二個運算元，因為 and 表示式的最終結果不可能再變為真（記住：兩個運算元都必須計算為真）。
讓我們考慮如何實現這一點。在計算 and 表示式時，我們首先計算第一個運算元，如果它是真，只有這時才有意義計算第二個運算元。這種行為看起來很像 if 語句，不是嗎？在 if 語句中，第一個子語句總是被計算的，如果為真，第二個子語句（“then”塊）就會被計算（記住，第三個子語句 -- “else” 子句 -- 是可選的）。如果能使用 PAST::Op( :pasttype('if') ) 節點來實現 and 運算子，那將是件好事。你可以使用 “is pasttype” 子句來做到這一點！以下是方法：
proto 'infix:and' is tighter('infix:or')
is pasttype('if') { ... }
那麼 or 運算子呢？在計算 or 表示式時，會計算第一個運算元。如果它計算為真，則無需計算第二個運算元，因為 or 表示式的結果已經是真！只有當第一個運算元計算為假時，才需要計算第二個子語句。嗯...... 我們的意思是，除非第一個運算元計算為真，否則計算第二個子語句。猜猜你需要什麼 pasttype 來做到這一點！
運算子 PAST 型別和 PIR 指令
[edit | edit source]在上一節中，我們介紹了可以指定的“pasttype”子句。這意味著對於該運算子（例如，我們討論的“and”運算子），將建立一個 PAST::Op( :pasttype('if') ) 節點。如果未指定 pasttype 會發生什麼？
在這種情況下，將建立一個預設的 PAST::Op 節點，預設的 pasttype 為 'call'。換句話說，將建立一個呼叫宣告的運算子的 PAST::Op 節點。例如，“infix:+” 運算子會導致對子例程“infix:+” 的呼叫。這意味著你需要為每個運算子實現子例程。現在，這有點可惜。顯然，一些語言對“+”運算子有非常奇特的語義，但許多語言只想使用 Parrot 的內建加法指令。我們如何實現這一點？不要新增“pasttype”子句，而是指定“pirop”子句。“pirop” 或“PIR 運算子”子句告訴程式碼生成器應該生成哪個運算子。它不會生成具有運算元作為引數的子例程呼叫，而是會生成具有運算子運算元作為引數的指定指令。很酷吧？讓我們看一個例子：
proto 'infix:+' is tighter('infix:<')
is pirop('n_add') { ... }
這指定使用“n_add”指令，它告訴 Parrot 建立一個新的結果物件，而不是更改其中一個運算元。你可能會想，為什麼不直接使用“add”指令（它接受兩個運算元，更新第一個）呢？好吧，如果你省略這個“is pirop”部分，就會生成以下內容：
$P12 = "infix:+"($P10, $P11)
你會看到，涉及到三個暫存器。正如我們之前提到的，PCT 不會進行任何最佳化。因此，它不會生成上面的指令，而是直接發出以下內容：
n_add $P12, $P10, $P11
這意味著暫存器 $P10 和 $P11 中的 PMC 會被相加，並賦值給一個新建立的 PMC，該 PMC 被儲存在暫存器 $P12 中。
是否使用環繞運算子
[edit | edit source]Squaak 支援帶括號的表示式。括號可以用來改變表示式中的計算順序，就像你在其他語言中看到的那樣。除了中綴、字首和字尾運算子之外，你還可以定義環繞運算子，它使用左右分隔符來指定。這是實現帶括號的表示式的理想方式
proto 'circumfix:( )' is looser('infix:+')
is pirop('set') { ... }
預設情況下，將為每個運算子生成一個子例程呼叫，在本例中為對“circumfix:( )”的呼叫。但是，我們只對被括起來的表示式感興趣。子例程只會返回表示式。相反，我們可以使用 pirop 屬性來指定應該生成哪個 PIR 操作；在本例中為“set”操作，它將一個暫存器設定為另一個暫存器的內容。
這個解決方案可以正常工作，但“set”指令有點浪費。發生的事情是，某個暫存器的內容被簡單地複製到另一個暫存器中，然後在後面的程式碼生成中使用。這個“set”指令最好被最佳化掉。目前，PCT 中沒有實現任何最佳化。
新增帶括號的表示式語法規則有一個替代方案，方法是將其作為 term 的替代方案新增。然後，term 語法規則最終將變為：
rule term {
| <float_constant> {*} #= float_constant
| <integer_constant> {*} #= integer_constant
| <string_constant> {*} #= string_constant
| <primary> {*} #= primary
| '(' <expression> ')' {*} #= expression
}
當然，儘管我們節省了一條生成的指令，但解析器效率會略低，原因我們在本節開頭討論過。當然，你可以自由地決定如何實現這一點；本節只是解釋了這兩種方法。在某個時候，PCT 中會實現最佳化。我懷疑“無用”指令（比如我們剛剛看到的“set”指令）會被刪除。
表示式解析器的動作方法
[edit | edit source]對於我們介紹的所有語法規則，我們還介紹了一個動作方法，該方法在語法規則完成匹配後被呼叫。optable 的動作方法是什麼？自然，必須執行一些操作。
嗯，它確實有，但坦白地說，我無法向你解釋。每次需要 optable 的動作方法時，我都會從現有的動作檔案中複製它。當然，動作方法的名稱應該與 optable 的名稱匹配（包含“is optable”子句的規則）。所以，這裡就是：
method expression($/, $key) {
if ($key eq 'end') {
make $($<expr>);
}
else {
my $past := PAST::Op.new(
:name($<type>),
:pasttype($<top><pasttype>),
:pirop($<top><pirop>),
:lvalue($<top><lvalue>),
:node($/) );
for @($/) {
$past.push( $($_) );
}
make $past;
}
}
下一步是什麼？
[edit | edit source]本節介紹了運算子的實現，它允許我們編寫複雜的表示式。到目前為止，我們語言的大部分內容都已實現，只有一件事除外：聚合資料結構。這將是 第 8 節 的主題。我們將介紹兩種聚合資料型別：陣列和雜湊表，並瞭解如何實現它們。我們還將討論在將這些聚合作為子例程引數傳遞時會發生什麼，以及它與基本資料型別的區別。
練習
[edit | edit source]- 問題 1
目前，Squaak 只有整數和字串常量的語法規則，沒有浮點數常量的語法規則。實現這個語法規則。浮點數由零個或多個數字組成，後面跟著一個小數點和至少一位數字，或者至少一位數字後面跟著一個小數點和任意多個數字。例如：42.0、1.、.0001。各個數字和小數點之間不能有空格。確保你理解“規則”和“標記”之間的區別。
- 提示
- 目前，Parrot 語法引擎 (PGE)，即“執行”正則表示式（你的語法規則）的元件，按順序匹配替代子規則。這意味著這將不起作用：
rule term {
| <integer_constant>
| <float_constant>
...
}
因為當給出輸入“42.0”時，“42”將被 <integer_constant> 匹配，而小數點和“0”將保留下來。因此，將 <float_constant> 替代方案放在 <integer_constant> 之前的 term 規則中。在某個時候，PGE 將支援最長標記匹配，因此這個問題將消失。
- 解決方案
token float_constant {
[
| \d+ '.' \d*
| \d* '.' \d+
]
{*}
}
- 問題 2
實現缺失的運算子：（二元）“-”、“<=”、“>=”、“==”、“!=”、“/”、“%”、“or”。
- 解決方案
為了完整起見（方便你複製貼上），以下是為 Squaak 編寫的運算子宣告列表：
rule expression is optable { ... }
proto 'infix:or' is precedence('1')
is pasttype('unless') { ... }
proto 'infix:and' is tighter('infix:or')
is pasttype('if') { ... }
proto 'infix:<' is tighter('infix:and') { ... }
proto 'infix:<=' is equiv('infix:<') { ... }
proto 'infix:>' is equiv('infix:<') { ... }
proto 'infix:>=' is equiv('infix:<') { ... }
proto 'infix:==' is equiv('infix:<') { ... }
proto 'infix:!=' is equiv('infix:<') { ... }
proto 'infix:+' is tighter('infix:<')
is pirop('n_add') { ... }
proto 'infix:-' is equiv('infix:+')
is pirop('n_sub') { ... }
proto 'infix:..' is equiv('infix:+')
is pirop('n_concat') { ... }
proto 'infix:*' is tighter('infix:+')
is pirop('n_mul') { ... }
proto 'infix:%' is equiv('infix:*')
is pirop('n_mod') { ... }
proto 'infix:/' is equiv('infix:*')
is pirop('n_div') { ... }
proto 'prefix:not' is tighter('infix:*')
is pirop('n_not') { ... }
proto 'prefix:-' is tighter('prefix:not')
is pirop('n_neg') { ... }
proto 'term:' is tighter('prefix:-')
is parsed(&term) { ... }
參考資料
[edit | edit source]- docs/pct/pct_optable_guide.pod