深入理解運算原理｜從簡單的機器到無所不能的程式

只想加入運算能力

|

133

還有其他能處理這個問題的作法，其中一種是在規則裡編寫限制更多的正

規運算式：如果將布林規則用在範式

/(true|false)(?![a-z])/

裡，那麼它

不會在一開始的地方和字串

'falsehood'

相匹配。

語法分析

只要完成字串轉換成符記的簡單工作，更難的問題就會是從語法的角度決定這些符

記是否代表有效的 SIMPLE 程式。我們無法使用正規運算式或 NFA 來完成這件工作

（SIMPLE 的語法允許任意深度的括號巢狀，而我們也已經知道有限自動機的能力不足

以識別像這樣的語言）。但是我們可以使用下推自動機來識別有效的符記序列，所以讓

我們看看如何構建。

首先，我們需要一個語法的文法，描述如何組合符記而形成程式。以下是以第 61 頁

『實作解析器』Treetop 文法的結構為基礎的部分 SIMPLE 文法：

<statement> ::= <while> | <assign>

<while> ::= 'w' '(' <expression> ')' '{' <statement> '}'

<assign> ::= 'v' '=' <expression>

<expression> ::= <less-than>

<less-than> ::= <multiply> '<' <less-than> | <multiply>

<multiply> ::= <term> '*' <multiply> | <term>

<term> ::= 'n' | 'v'

這稱為

無關脈絡的文法 ...