3

アトミック要素と単項および二項演算子のみで構成される言語がある場合:

atomic elements: a b c
unary operators: ! ~ + -
binary operators: + - / *

次に、文法を定義できます。

ATOM := a | b | c
UNOP := ! | ~ | + | -
BINOP := + | - | / | *
EXPR := ATOM | UNOP EXPR | EXPR BINOP EXPR

ただし、この文法はあいまいな解析ツリー (および左再帰による再帰降下パーサーでの無限ループ) につながります。

そこで、優先テーブルを追加します。

Precendence 1: unary+ unary- ~ ! (Right to Left)
Precendence 2: * / (Left to Right)
Precendence 3: binary+ binary- (Left to Right)

私の質問は、どのアルゴリズムまたは手順によって優先順位テーブルを取得し、再帰降下パーサー (左再帰ではない) に適した文法を生成できるかということです。

優先度テーブルは、演算子グループと関連する方向 (L->R または R<-L) の順序付きリストです。答えは、これを入力として受け取り、文法を出力として生成するものです。

4

2 に答える 2

3

任意の優先順位を記述する一般的な文法は、テーブルベースで yacc を使用して生成できる LALR パーサーを使用して解析できます。しかし、これは、再帰降下パーサーを使用したい場合にすべてが失われるという意味ではありません。

再帰降下パーサーは、構文が正しいかどうかのみを検証できます。構文ツリーの構築は別の問題であり、ツリー構築レベルで優先順位を処理する必要があります。

したがって、中置式を解析できる左再帰を使用しない次の文法を考えてみましょう。優先順位の兆候はありません:

Expr := Term (InfixOp Term)*
InfixOp := '+' | '-' | '*' | '/'
Term := '(' Expr ')'
Term := identifier

(右側で使用される表記は正規表現のようなもので、大きなキャメル ケースを使用して記述された置換を持つルール、トークンは小さなキャメル ケースを使用して引用または記述されます)。

構文ツリーを構築するとき、新しいノードを追加する現在のノードがあります。

ほとんどの場合、ルールを解析するときに、現在のノードに新しい子ノードを作成し、その子を現在のノードにします。解析が終了したら、親ノードにステップアップします。

これは、InfixOpルールを解析するときに別の方法で行う必要があることです。関連するノードに優先順位の強さを割り当てる必要があります。ノードのExpr優先順位は最も低く、他のすべての演算子は優先順位が高くなります。

中置優先順位の処理

ルールを解析するときInfixOpは、次のようにします。

  1. 現在のノードの優先順位が着信ノードの優先順位よりも強い間、1 レベル上げ続けます (親ノードを現在のノードにします)。

  2. 次に、着信ノードのノードを現在のノードの最後の子の親として挿入し、現在のノードにします。

Exprノードは優先順位が最も低いと宣言されているため、最終的に上昇を停止します。

例を見てみましょう：A+B*C

現在のノードは!、現在のトークンを消費した後、常に でマークされます。

Parsed: none

Expr!

Parsed: A

Expr!
|
A

Parsed: A+

Expr
|
+!
|
A

Parsed: A+B

  Expr
  |
  +!
 / \
A   B

Parsed: A+B*

  Expr
  |
  +
 / \
A   *!
   /
  B

Parsed: A+B*C

  Expr
  |
  +
 / \
A   *!
   / \
  B   C

これをポストオーダー方式でトラバースすると、評価に使用できる式の逆ポーランド記法が得られます。

またはその逆の例:A*B+C

Parsed: none

Expr!

Parsed: A

Expr!
|
A

Parsed: A*

Expr
|
*!
|
A

Parsed: A*B

  Expr
  |
  *!
 / \
A   B

Parsed: A*B+

  Expr
  |
  +!
  |
  *
 / \
A   B

Parsed: A*B+C

    Expr
    |
    +!
   / \
  *   C
 / \
A   B

結合性の処理

左結合の演算子と右結合の演算子があります。たとえば、C 言語ファミリでは、+は左結合ですが、=は右結合です。

実際には、結合性全体は、同じ優先順位レベルでの演算子の処理に要約されます。同じ優先レベルの演算子に遭遇すると、上昇するときの左連想演算子の場合は上昇し続けます。右結合演算子の場合、同じ演算子に遭遇したら停止します。

(すべてのテクニックを説明するにはスペースがかかりすぎます。紙の上で試してみることをお勧めします。)

前置演算子と後置演算子の処理

この場合、文法を少し変更する必要があります。

Expr := PrefixOp* Term PostfixOp* (InfixOp PrefixOp* Term PostfixOp*)*
InfixOp := '+' | '-' | '*' | '/'
Term := '(' Expr ')'
Term := identifier

前置演算子に遭遇したら、それを現在のノードに新しい子として追加し、新しい子を現在のノードにします。優先順位に関係なく、それが強い演算子であっても弱い演算子であっても正しいものになります。中置演算子は正確性を保証します。

後置演算子の場合、中置演算子で説明したのと同じ優先順位の上昇を使用できます。唯一の違いは、後置演算子の右辺がないため、子が 1 つだけになることです。

三項演算子の扱い

C 言語ファミリには、?:三項演算子があります。構文ツリーの構築に関しては、?and:を別の中置演算子として扱うことができます。しかし、トリックがあります。用に作成するノードは?、不完全な 3 項ノードである必要があります。つまり、通常の優先順位の上昇を行って配置しますが、この不完全なノードの優先順位は最も低くなります。これにより、コンマ オペレーターのような弱いオペレーターがそれを乗り越えることができなくなります。に到達し:たら、最初の不完全な 3 項ノードまで登り (見つからない場合は、構文エラーを報告します)、通常の優先順位を持つ完全なノードに変更し、現在のノードにする必要があります。現在の分岐に不完全な 3 項ノードがあるときに式の最後に予期せず到達した場合は、再び構文エラーを報告します。

したがって、a , b ? c : dは と解釈されa , (b ? c : d)ます。

しかし、コンマが ? を超えるのを防いだので、a ? c , d : eは と解釈されます。a ? (c , d) : e

配列インデックスと関数呼び出しの処理

後置のように見えますが、これらは右側に構文的に強制された括弧で囲まれた項を持つ中置演算子です。これは、配列インデックスと関数呼び出しにも当てはまります。

于 2015-05-09T15:37:25.147 に答える
2

演算子の優先順位文法を文法[1]に変換するのは簡単LR(1)ですが、結果の文法は左再帰を使用して左結合演算子を解析します。左再帰を排除するのは簡単です（たとえば、すべての演算子を右連想にする）が、結果の文法は同じ言語を認識しますが、解析ツリーは異なります。

再帰下降パーサーをわずかに変更して、優先順位の関係を処理できるようにすることは難しくありません。この手法はVaughanPrattによって発明され、基本的にコールスタックを使用して、従来の操車場アルゴリズムの明示的なスタックを置き換えます。

プラット構文解析はある種の復活を遂げているようであり、それに関する多くのブログ投稿を見つけることができます。適度に良いものの1つは、EliBenderskyによるものです。プラットは1970年代初頭に手順を考案しました。ほぼ同時に、フランク・デレマーはLR(1)構文解析が実用的であることを証明していました。プラットは、正式な構文解析の実用性と柔軟性の欠如の両方に懐疑的でした。それ以来、議論はかなり煮えたぎっていると思います。プラットパーサーは確かにシンプルで柔軟性がありますが、一方で、それらが正しいことを証明すること（または特定の正式に記述された文法を解析すること）を証明することは非常に難しい場合があります。一方、bison最近GLR解析のサポートを取得しましたが、それを使用するのがはるかに簡単になる可能性があります。bison生成されたパーサーは、実際に解析すると主張する文法を解析しますが、正式な構文解析方法は「アクセスしにくく、使い心地が悪い」というプラットの声明（1973年から）に同意する人はまだたくさんいます。

[1]実際には、すべてのyacc-derivativesおよび他の多くのLRパーサジェネレーターは、曖昧性解消のために優先順位関係を受け入れます。結果として得られる文法テーブルは小さく、単位の削減も少ないため、パーサジェネレータを使用する場合は、この手法を使用しない理由は特にありません。

于 2012-12-20T17:19:42.933 に答える