0

簡単な文法があります。実際、私が使用している文法はもっと複雑ですが、これは私の質問を説明する最小のサブセットです。

Expr ::= Value Suffix
       | "(" Expr ")" Suffix

Suffix ::= "->" Expr
         | "<-" Expr
         | Expr
         | epsilon

Value識別子、文字列、数字などに一致します。ルールは、Suffix左再帰を排除するためにあります。これは、次のような式に一致します。

a -> b (c -> (d) (e))

つまり、とのa両方に行き、とに行くグラフ。これらの式の抽象構文ツリーを作成しようとしていますが、すべての演算子が各側で任意の数のオペランドを受け入れることができるため、問題が発生しています。式を抽出するロジックを複製する必要がないため、再帰下降構文解析メソッド内でASTを生成するためのロジックを維持したいと思います。私の現在の戦略は次のとおりです。b(c -> (d) (e))cde

  1. が表示されたら、Valueそれを出力にプッシュします。

  2. Fromまたはが表示された場合To：

    1. セパレータを出力します。

    2. 次を取得しExprます。

    3. ノードを作成しLinkます。

    4. Linkセパレータが表示されるまで、出力からのオペランドの最初のセットをポップします。

    5. 検出されたセパレータを消去します。

    6. オペランドの2番目のセットをLink区切り記号までポップします。

    7. を出力にプッシュしLinkます。

手順2.3〜2.7に従わずにこれを実行すると、値と区切り文字のリストが表示されます。上で引用した式の場合a -> b (c -> (d) (e))、出力は次のようになります。

A sep_1 B sep_2 C sep_3 D E

Toルールを適用すると、次のようになります。

A sep_1 B sep_2 (link from C to {D, E})

そしてその後：

(link from A to {B, (link from C to {D, E})})

注意すべき重要なことsep_2は、2番目の左側のオペランドを区切るために重要なが->表示されないため、パーサーは式が実際に記述されたと信じていることです。

a -> (b c -> (d) (e))

現在の戦略でこれを解決するには、隣接する式の間に区切り文字を作成する方法が必要ですが、現在の式が括弧で囲まれたFromまたは式である場合に限ります。Toそれが可能であれば、私はそれを見ていません。答えは単純なはずです。ただし、これについてもっと良い方法がある場合は、お知らせください。

4

1 に答える 1

1

詳細に分析しようとはしていませんが、「Fromまたは括弧で囲まれたTo式」は、再帰下降が直接処理できない「コンテキスト依存」のように聞こえ始めます。コンテキスト依存を回避するには、括弧内または括弧なしと括弧なしの別々のプロダクションが必要になる可能性があります。FromToFromTo

編集：何か良いことをするのは遅すぎるかもしれませんが、あなたが一致させたいものの私の理解が正しければ、私はそれをもっとこのように書くと思います：

Graph := 
       | List Sep Graph
       ;

Sep := "->"
     | "<-"
     ;

List :=
      | Value List
      ;

Value := Number 
      | Identifier 
      | String 
      | '(' Graph ')'
      ;

確かなことは難しいですが、これは少なくとも必要な入力に（のみ）一致するようになり、入力を正しく反映するASTをかなり簡単に生成できるようになるはずです。

于 2010-09-24T15:22:44.557 に答える