関数型言語の勉強にSICPを読もう - (57) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう5
最近、字句解析とか構文解析をしていましたが、その試行錯誤のサマリです。
前提
なぜ構文解析が必要か
Schemeインタプリタ(以後インタプリタ)をScheme(以後Gauche)で実装する場合と入力の扱いが違うからです。
インタプリタでは入力を受け付けますが、実際にはGaucheが入力を受け取り、Gaucheが手続き eval にそのまま渡します。
この際、Gaucheが受け取る入力はS式ですが、Gaucheはそれ自体S式をS式として認識しているので特に難しい作業は必要ありません。
一方、C++で実装する場合、入力は"(+ a b)"のように文字列で与えられ、C++はS式を解釈しません。
単語がどこで切れるか?、(にどのような意味があるか?などには一切関知しないのです。
そのためC++では字句解析と構文解析が必要となります。
字句解析
字句解析は文字列を、いくつかのトークンに分類します。
トークンはS式に登場するいくつかの人物です。
具体的には識別子、文字列、数値、(、)、クォートです。
enum
{
IDENTIFIER,
STRING,
NUMBER,
LEFT_PAREN,
RIGHT_PAREN,
QUOTE,
};
今回は文字列から次々とトークンを返す toknize()を実装しました。
その結果、入力された文字列に含まれる文字は上のいずれかに分類されるようになりました。
構文解析
次に、トークンの並びを解析し、構文木を構築します。
構文木ではNodeの定義が重要です。（後から気づきました。）
(+ 1 3)
という式は + の左の葉が1で右の葉が3となっているイメージです。
二文木で最初実装を試みましたが、その後多分木に変更しました。
たとえば
(sum 1 3 4 5)
は
擬似コードで
Node {
Nodes nodes = new Array("sum", 1, 3, 4, 5);
};というノードとして格納されます。
このフェーズでは、手続きとその引数の意味の違いを解釈していません。
構文木構築後の処理
((lambda (a) a) "b")
を解析すると以下の構文木が作られます。
NODES NODES SYMBOL[lambda] NODES SYMBOL[a] SYMBOL[a] STRING["b"]
ここからいよいよ各ノードとC++のオブジェクトをマッピングしていきます。
たとえば nodes[0] が Stringのノードで "if" という文字列であれば、特殊形式if をあらわすオブジェクト
SpecialIf(Object* predicate, Object* consequent, Object* alternative);
を new します。
このように入力をオブジェクトにマッピング後にトップレベルのオブジェクトを eval してやればインタプリタが動作するというわけです。
現状の問題点
define/if/condなどは動いているが!。
lambdaが動かない。
たとえば
((lambda (a) a) "b")
は nodes->[0]が更に (lambda (a) a)のように手続き呼び出しになっており、オブジェクトの型をうまく決められないのではと考えて悩んでいます。（続く）
計算機プログラムの構造と解釈
posted with amazlet on 06.05.31
