1

次の再帰 BNF ルールを見てください。

(1) X = Xa | b

これは次のような文を生成します

X = b
X = ba
X = baa
X = baaa
...

これは次のように記述できます。

(2) X = b a*

右辺が再帰的でない場合

次の再帰的 BNF ルールを見てみましょう。

(3) X = { X } | b

これは次のような文を生成します

X = b
X = {b}
X = {{b}}
X = {{{b}}}
...

ルール (1) をルール (2) に書き直したときと同様に、ルール (3) を非再帰的な方法で書き直す方法はありますか。

括弧のバランスをとる必要があるため、X = {* b }* は良くないことに注意してください。

4

1 に答える 1

0

上記の質問に答えられるかどうかわかりません。上記の質問の理由は、パーサー (Java で作成) で無限ループを回避したかったからです。1 つの方法は、BNF ルールが再帰的でないことを確認することでした。そのため、私の質問です。しかし、別の方法は、再帰規則を使用することですが、(Java) プログラム内の無限ループを回避します。遅延インスタンス化によってループを回避できることがわかりました。

たとえば、次のルールを見てください。

expression = term ('+' term)*;
term       = factor ('*' factor)*;
factor     = '(' expression ')' | Num;

expression() が term() を呼び出し、それが factor() を呼び出し、それが expression() を呼び出すため、無限ループに陥る可能性があります。それを避けるために、遅延インスタンス化を使用できるので、次のように書く代わりに:

public Parser expression() {
    expression = new ...
    return expression;
}

代わりに次のように書きます。

public Parser expression() {
    if (expression == null) {
        expression = new ...
    }
    return expression;
}

これを機能させるには、式をインスタンス変数として宣言する必要があることに注意してください。

于 2015-04-21T10:48:02.760 に答える