Shift-Reduce 解析を使用した解析ツリーの構築

StackOverflow https://stackoverflow.com//questions/21064599

質問

私は自由時間に解析を実験していて、非常に単純な文法用の shift-reduce パーサーを実装したいと考えていました。多くのオンライン記事を読みましたが、解析ツリーの作成方法がまだわかりません。これが私がやりたいことの例です:

文法：

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

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

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

役に立ちましたか？

解決

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

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

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

ターミナル ノードの「シフト」を、(ターミナルを構成する文字の) ターミナル ノードへの縮小と考えると、ターミナル ノードのシフトがぴったり当てはまります。ターミナルのノードを作成し、スタックにプッシュします。

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

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

CST を生成する場合、ツリーから「不要な」ノードを削除するのは概念的には簡単です。私たちのツールでそれを行います。結果は AST によく似ており、手続き的な添付ファイルをすべて手動で記述する必要はありません。

他のヒント

あなたのトラブルの理由は、あなたがあなたの文法に競合をシフト/減らすことです：

expr: expr OP expr
    | number
.

これを2つの方法で解決することができます：

expr: expr OP number
    | number
.

左連想演算子または

expr: number OP expr
    | number
. 右連想のための

。これはあなたの木の形状も決定する必要があります。

縮小は通常1節が完了したときに行われます。右連想の場合は、数字を想定している状態1で始まり、それを値スタックにプッシュし、状態2に移行します.State 2では、トークンがOPでない場合は、EXPRへの数値を減らすことができます。 。それ以外の場合は、オペレータを押して状態への移行1.状態1が完了すると、数値、演算子、および式を別の式に縮小できます。注意、削減後に「戻る」にメカニズムが必要です。その後、全体のパーサーは状態0で始まり、これは直ちに状態1に進み、減少後に受け入れます。

yaccやバイソンのようなツールは、すべての低レベルの機械類とスタックを持ってくるので、この種のものをはるかに簡単にします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top