アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

128

4

章 能力を高める

字句解析器は最長マッチの規則を選ぶことで、うまく変数名を扱っています。さもないと以

下の

2

番目の例は、ブール値として誤認識されてしまうでしょう。

>>

LexicalAnalyzer.new('x = false').analyze

=> ["v", "=", "b"]

>>

LexicalAnalyzer.new('x = falsehood').analyze

=> ["v", "=", "v"]

この問題を扱う方法にはもう

1

つあります。それは規則にもっと限定した正規表現を書くこと

です。ブール値の規則に

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

というパターンを使うことで、文字列

'falsehood'

にはマッチしなくなります。

4.3.2

　構文解析

文字列をトークンに変換するという簡単な作業ができたら、次に、それらのトークンが構文的に有効

なSIMPLEプログラムを表現しているか判断する、という難しい問題があります。これには正規表現

やNFAは使えません。SIMPLEの構文は好きなだけ括弧をネストするのを許しています。もうおわか

りのように、有限オートマトンにはそのような言語を認識するだけの能力がありません。有効なトーク

ンのシーケンスを認識するには、プッシュダウン・オートマトンが使えます。どうやって構築するか見

ていきましょう。

まずは、トークンをどのように組み合わせてプログラムを作るかを記述した構文文法が必要になりま

す。SIMPLEのための文法の一部を以下に示します。