インタープリタパターン

質問

インタープリタパターンでたとえば以下のような文法を解釈したい場合、どう書けばいいのでしょう。

・再帰
<statement_list> ::= <statement> | <statement> <statement_list>
・分岐
<statement> ::= <assign> ";" | <formula> ";"

例えば、
<formula> ::= <term> | <term> "+" <formula>
であれば

interface Context {
　/* 現在のtokenを取得 */
　public String currentToken();
　/* tokenを次に進める */
　public String nextToken();
}
/* 構文木におけるノード */
abstract class Node {
　/* 解析 */
　public abstract void parse(Context ctx);
}
/* 式を表すノード */
class Formula extends Node {
　Node term;
　Node formula;
　public void parse(Context ctx) {
　　// <term>部分の解析
　　term = new Term();
　　term.parse(ctx);
　　// "+" が続けば、<formula>部分の解析を進める
　　if (ctx.equals("+")) {
　　　ctx.nextToken();
　　　formula = new Formula();
　　　formula.parse(ctx);
　　}
　}
}

という風に "+" があるか無いかで分岐の判断ができるのですが，

<statement> ::= <assign> ";" | <formula> ";"
<statement_list> ::= <statement> | <statement> <statement_list>

のように、どちらにするか（解析を進めるか）判断する記号がない場合はどのように対処すればよいのでしょうか？

回答No.2

noocyte · ベストアンサー

デザインパターンのインタープリタパターンのことは知りませんが，
自分で構文解析器を作った経験からコメントします．

> 構文をチェックしているうちに
> １．下位のノードでnextToken()を呼び出してしまった
> ２．でも実を言うとこの構文規則じゃありませんよ
> ３．上に戻ったはいいけどトークンが進められちゃってますから。残念！
> ってことになって、トークンを戻さなければいけない気がします。
> 多分例外をキャッチした際に戻る処理を書けばよいのだと思うのですが、
> まだ試してはいませんし、戻さないでかけないものかなーと格闘中です。

普通，手書きの構文解析器が扱うのは LL(1) と呼ばれる文法です．
大雑把に言うと，LL(1) とは１トークン先読みしながら左から順に解析すればいい文法です．
LL(k) (k≧2) 文法の場合は構文解析が大変なので，文法を見直した方がよい．
先読みしないでいい LL(0) というのは聞いたことがないけど，一つの解釈としては
「何もかもが固定長」とか，非常に制限された文法ということになると思います．

LL法
http://ja.wikipedia.org/wiki/LL%E6%B3%95

したがって構文解析器では１トークン (字句解析器ならば１文字) 先読みし，
解析に失敗すればそれを元に戻すのはごくあたりまえの処理です．
Ｃ言語の標準ライブラリには，入力ストリームから先読みした１文字を戻すための
関数 ungetc() が用意されています．Java はあまり使ってないのでよく知りませんが，
↓によると PushBackInputStream や PushBackReader クラスがその機能を提供しているようです．

ungetc ってどう使う？
http://www.nurs.or.jp/~sug/soft/super/ungetch.htm
字句解析
http://www.tokumaru.org/yacc/yacc04.htm

もっともこれらのクラスは文字レベルの先読みの話なので，トークンの先読みについては
必要ならば自分で PushBackTokenStream のようなクラスを作る必要があるかも．

> 実を言うと現在も例外処理で何とか対処しています。

Java ではどうか知りませんが，一般には例外処理は重い処理だし，
そもそも「例外」的な状況に対処するのが目的なので，
構文解析のバックトラッキングのように当たり前に発生する処理に用いるのは不適当です．
(構文エラーの場合は例外処理がいいと思いますが．)

> <statement> ::= <assign> ";" | <formula> ";"
>
> のように、どちらにするか（解析を進めるか）判断する記号がない場合は
> どのように対処すればよいのでしょうか？

普通は <assign> と <formula> の定義をさらに展開し，両者を区別できる
終端記号 (トークン) が出現するまでそれを繰り返します．
そして，その結果をもとに構文解析プログラムを書くことになります．
(この方法はバックトラッキングなしで効率良く構文解析を行うためには
　当然の方法ですが，それぞれの非終端記号 (::= の左辺) の構文定義
　(::= の右辺) をカプセル化できないので，「オブジェクト指向」や
　「デザインパターン」から入った人は嫌がるかもしれませんね．(笑))

また，parse メソッドは void 型じゃなく Node 型 (またはそのサブクラス) にして，
・目的の構文要素を読んだとき，その構文木の Node を返す．
・その構文要素以外のものが現れたとき，先読みしたトークンを
　ストリームに戻して null を返す．
・構文エラーの場合は例外を投げる．
ようにするのがいいと思います．

このようにすると，

> <statement_list> ::= <statement> | <statement> <statement_list>

は，大まかには

class StatementList extends Node {
　　List statementList;

　　public boolean parse(Context ctx) {
　　　　Statement statement;
　　　　int count = 0; // 読まれた <statement> の個数

　　　　while((statement = Statement.parse(ctx)) != null) {
　　　　　　statementList.add(statement);
　　　　　　count++;
　　　　}
　　　　return count > 0;
　　}
}

のような感じになると思います．

お礼

なるほど、例外の乱用はよくないのですね。
承知いたしました。
たしかに提示していただいたnullを返す方法でうまくいきそうです。

また、LL(1)やLR(1)等、聞き覚えがあります。
というより、お話を聞いて思い出しました。

> 終端記号 (トークン) が出現するまでそれを繰り返します
これも承知しました。
構文規則をちゃんと吟味してみます。
（複雑になったらjavaccやjfrex+jayを使おうと思いますが、こういうのを自分で実装するのは面白いですね！）

経験者の方からのご回答ということもあって大変勉強になりました。
ご回答ありがとうございました。

回答No.3

noocyte

#2 です．StatementList の定義を訂正します．

class StatementList extends Node {
　　List statements;

　　public static StatementList parse(Context ctx) {
　　　　StatementList statementList = new StatementList();
　　　　Statement statement;
　　　　while((statement = Statement.parse(ctx)) != null) {
　　　　　　statementList.statements.add(statement);
　　　　}
　　　　return statementList.statements.isEmpty() ? null : statementList;
　　}
}

お礼

訂正ありがとうございました。

また申し遅れましたが、お礼が遅くなり申し訳ありませんでした。

回答No.1

PED02744

回答がなかなか付かないようなので、構文図やBNFではなく通常のインタプリタの考え方でお話しますと（だからロジックは回答できないのです。ごめんなさい）

再帰的な処理は、進んだ先で終了判定を行います。
「ステートメントリスト」は「ステートメント１つか、ステートメントとステートメントリスト」
なわけですから、右辺にステートメントリストが空っぽになるまで分解して再帰処理をすればよいことになります。
例を挙げますと
tokenが"a = 1; b = 1; c = a + b;"だった場合
１．→[statement = "a = 1;"] + [token = "b = 1; c = a + b;"]
残ったtoken"b = 1; c = a + b;"をステートメントリストで再帰処理
２．→[statement = "b = 1;"] + [token = "c = a + b;"]
残ったtoken"c = a + b;"をステートメントリストで再帰処理
３．→[statement = "c = a + b;"] + [token = ""]
残ったtoken""をステートメントリストで再帰処理
４．→tokenが""(null)で処理不要なので戻る

再帰処理ではなく、<statement>の様に単純分岐の場合は、ロジックでがちがちに固めるしかないかと思います。
もし<assgin>としてチェックしてエラーならば<formula>として再チェック
もし、<assign>であり<formula>でもある　というような場合が考えられるのであれば、分割単位にミスがあるので、もっと細かくしなくてはいけないということかと思います。

お礼

ご回答ありがとうございます。
頭が「再帰」に慣れていないので、稚拙な質問かもしれませんが、
上に加えて、

<block> ::= "{" <statement_list> "}"

という構文規則があった場合で
"program { a = 1; b = 1; c = a + b ; }"

１．(略)
２．(略)
３．→[statement = "c = a + b;"] + [token = "}"]
残ったtoken""をステートメントリストで再帰処理
４．→tokenが""(null)で処理不要

の４．が適用できない気がします。
"}"をチェックすれば解決しますが、上位の構文ノードを意識している点でインタープリタパターンの流儀に反するような気も・・。

> 再帰処理ではなく、<statement>の様に単純分岐の場合は、
> ロジックでがちがちに固めるしかないかと思います。
やはり、そうでしたか。
実を言うと現在も例外処理で何とか対処しています。
がしかし、構文をチェックしているうちに
１．下位のノードでnextToken()を呼び出してしまった
２．でも実を言うとこの構文規則じゃありませんよ
３．上に戻ったはいいけどトークンが進められちゃってますから。残念！
ってことになって、トークンを戻さなければいけない気がします。
多分例外をキャッチした際に戻る処理を書けばよいのだと思うのですが、まだ試してはいませんし、戻さないでかけないものかなーと格闘中です。

>もし、<assign>であり<formula>でもある　というような場合が考えられるのであれば、分割単位にミスがあるので、もっと細かくしなくてはいけないということかと思います。

もしかしたらおっしゃるとおりあいまいな部分があるかもしれません。
調べてみます。