5

私は自由時間に構文解析を試していて、非常に単純な文法のシフト削減パーサーを実装したいと考えていました。多くのオンライン記事を読みましたが、解析ツリーの作成方法についてはまだ混乱しています。これが私がやりたいことの例です：

文法：

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

入力例を次に示します。

1 + 1 + 1 + 1

トークン化すると、次のようになります。

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

という事は承知しています：

  1. シフトとは、最初の入力トークンをスタックにプッシュし、それを入力から削除することを意味します
  2. 削減とは、スタック上の 1 つ以上の要素を文法要素に置き換えることを意味します。

したがって、基本的には、次のようになります。

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

「何を減らすか」とは別に 間違いなく、解析ツリーを正しく構築する方法がわかりません。ツリーはおそらく次のようになります。

1    +    o
          |
     1    +    o
               |
          1    +    1

リダクションで新しいノードを作成する必要がありますか?

また、新しく作成したノードにいつ子を追加する必要がありますか? / 新しいルート ノードをいつ作成する必要がありますか?

4

2 に答える 2

4

簡単で明白なことは、縮小ごとにツリー ノードを作成し、縮小された文法要素からツリー ノードをそのツリー ノードに追加することです。

これは、生のパーサーが使用する「シフト トークン」スタックと並行して実行されるノード スタックで簡単に管理できます。長さ N のルールの削減ごとに、シフト トークン スタックが N だけ短縮され、非終端トークンがシフト スタックにプッシュされます。同時に、上位 N 個のノードを削除してノード スタックを短くし、非ターミナルのノードを作成し、削除した N 個のノードを子としてアタッチし、そのノードをノード スタックにプッシュします。

このポリシーは、右辺の長さがゼロのルールでも機能します。ツリー ノードを作成し、それに子の空のセットを追加します (たとえば、リーフ ノードを作成します)。

ターミナル ノードの "シフト" を (ターミナルを形成する文字の) ターミナル ノードへの縮小と考える場合、ターミナル ノードのシフトは適切に適合します。ターミナルのノードを作成し、それをスタックにプッシュします。

これを行うと、文法と同形的に一致する「具体的な構文/構文木」が得られます。(これは、私が提供する商用ツールで行います)。このような具象ツリーを好まない人がたくさんいます。キーワードなどのノードが含まれているため、あまり価値がありません。確かにそうですが、文法がツリー構造であるため、そのようなツリーは非常に簡単に構築でき、理解も非常に簡単です。2500 のルールがある場合 (完全な COBOL パーサーの場合と同様)、これは重要です。これは、すべてのメカニズムを解析インフラストラクチャに完全に組み込むことができるため、便利です。文法エンジニアは単純にルールを記述し、パーサーが実行され、ほら、ツリーが実行されます。文法を変更するのも簡単です: それを変更するだけで、ほら、構文木を取得できます。

ただし、具体的なツリーが必要ない場合、たとえば「抽象構文ツリー」が必要な場合は、どのリダクションがノードを生成するかを文法エンジニアに制御させる必要があります。通常、リダクション ステップで実行される各文法規則に手続き上の添付ファイル (コード) を追加します。次に、そのような手続き型アタッチメントがノードを生成する場合、ノード スタックに保持されます。ノードを生成する手続き型アタッチメントは、右側の要素によって生成されたノードをアタッチする必要があります。もしあれば、これは YACC/Bison/... ほとんどの shift-reduce パーサー エンジンが行うことです。Yacc または Bison について読み、文法を調べます。このスキームは、あなたがそのコントロールを取ることを主張するという代償を払って、あなたに多くのコントロールを与えます. (私たちが行っていることについては、文法を構築するためにこれほど多くのエンジニアリング作業を行いたくありません)。

CST を生成する場合、ツリーから「役に立たない」ノードを削除するのは概念的に簡単です。ツールでそれを行います。結果は AST によく似ており、これらすべての手続き型アタッチメントを手動で作成する必要はありません。

于 2014-01-11T18:08:59.633 に答える
2

問題の理由は、文法にシフト/リデュースの競合があることです:

expr: expr OP expr
    | number

これは 2 つの方法で解決できます。

expr: expr OP number
    | number

左結合演算子の場合、または

expr: number OP expr
    | number

右連想の場合。これにより、ツリーの形状も決まります。

リダクションは通常、1 つの節が完了したことが検出されたときに行われます。適切な連想ケースでは、数値を期待する状態 1 で開始し、それを値スタックにプッシュして状態 2 に移行します。状態 2 では、トークンが OP でない場合、数値を expr に減らすことができます。 . それ以外の場合は、演算子を押して状態 1 に移行します。状態 1 が完了すると、数値、演算子、および式を別の式に減らすことができます。削減後に「戻る」メカニズムが必要であることに注意してください。次に、パーサー全体が状態 0 で開始されます。たとえば、状態 0 はすぐに状態 1 になり、縮小後に受け入れます。

yacc や bison などのツールは、すべての低レベルの機械とスタックを提供するため、この種の作業をはるかに簡単にすることに注意してください。

于 2014-01-12T02:11:20.753 に答える