6

いくつかのコンパイラの本/記事/論文は、文法の設計とその演算子の結合性の関係について語っています。私はトップダウン、特に再帰降下パーサーの大ファンであり、これまでに書いたほとんどの (すべてではないにしても) コンパイラーは、次の式の文法を使用しています。

Expr   ::= Term { ( "+" | "-" ) Term }
Term   ::= Factor { ( "*" | "/" ) Factor }
Factor ::= INTEGER | "(" Expr ")"

これは、この BNF の EBNF 表現です。

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ε
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ε
Factor = INTEGER | "(" Expr ")"

私が読んだことによると、演算子の結合性 (これらの 4 つの演算子は左から右) の変更により、この文法が「間違っている」と見なす人もいます。これは、解析ツリーが左ではなく右に成長することによって証明されています。属性文法を介して実装されたパーサーの場合、l-attribute 値ではこの値が最初に作成されてから子ノードに渡される必要があるため、これは当てはまります。ただし、通常の再帰降下パーサーで実装する場合、最初にこのノードを構築してから子ノードに渡す (トップダウン) か、最初に子ノードを作成してから、戻り値をこのノードの子として追加する (渡される) かは私次第です。このノードのコンストラクターで) (ボトムアップ)。この文法が「間違っている」という声明に同意しないため、ここで見逃しているものがあるはずです この文法は多くの言語で使用されています。ワーシアンのもの。通常 (またはすべて?) LL ではなく LR 解析を促進するという読み方です。

4

2 に答える 2

1

ここでの問題は、言語が次のような抽象構文を持っていることだと思います。

E ::= E + E | E - E | E * E | E / E | Int | (E)

しかし、これは実際には、結合性と優先順位を指定するために使用される具体的な構文を介して実装されます。したがって、再帰下降構文解析を記述している場合は、具体的な構文を暗黙的に記述していることになります。これは問題ありませんが、句構造文法として正確に指定することもできます。

本格的な具体的な文法である場合、文法にはいくつかの問題があります。まず、「次のレベルに進む」ためにプロダクションを追加する必要があるため、構文を少し緩和します。

Expr ::= Term + Term | Term - Term | Term
Term ::= Factor * Factor | Factor / Factor | Factor
Factor ::= INTEGER | (Expr)

そうしないと、開始記号（この場合はExpr）から始まる有効な文を導出する方法がありません。たとえば、これらの余分なプロダクションなしで「1 * 2」をどのように導き出しますか？

Expr -> Term
     -> Factor * Factor
     -> 1 * Factor
     -> 1 * 2

他の文法が​​これをわずかに異なる方法で処理していることがわかります。

Expr -> Term Expr'
     -> Factor Term' Expr'
     -> 1 Term' Expr'
     -> 1 * Factor Term' Expr'
     -> 1 * 2 Term' Expr'
     -> 1 * 2 ε Expr'
     -> 1 * 2 ε ε
      = 1 * 2

しかし、これは同じ効果を達成します。

パーサーは実際には非結合です。これを確認するには、どのようE + E + Eに解析するかを尋ね、解析できなかったことを確認します。どちら+が最初に消費されても、一方Eと他方になりますが、それから、不可能なものとしてE + E解析しようとしています。同様に、開始記号からその式を導出することを考えてください。これも不可能です。E + ETerm

Expr -> Term + Term
     -> ? (can't get another + in here)

他の文法は左結合性であり、任意の長さの刺し傷をE + E + ... + E導き出すことができます。

とにかく、要約すると、RDPを作成するときに、好きな抽象構文の具体的なバージョンを実装でき、おそらくそれについて私よりも多くのことを知っているはずです。しかし、RDPを正確に説明する文法を作成しようとすると、これらの問題が発生します。お役に立てば幸いです。

于 2012-06-02T09:11:42.137 に答える
1

連想ツリーを取得するには、サブツリー ルート ノードとしてオペレータを使用してツリーを形成し、子が同様のルートを持つようにする必要があります。

実装文法:

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ε
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ε
Factor ::= INTEGER | "(" Expr ")"

それを厄介にする必要があります。これに再帰的降下を実装すると、Expr' ルーチンは「左の子」にアクセスできないため、ツリーを構築できません。ピースを渡すことでいつでもこれを修正できます (この場合、ツリーのパーツを再帰に渡す) が、それは厄介なようです。代わりにこれを文法として選択することもできます。

Expr  ::= Term  ( ("+"|"-") Term )*;
Term  ::= Factor ( ( "*" | "/" ) Factor )* ;
Factor ::= INTEGER | "(" Expr ")"

これは、再帰的な降下法をコーディングするのと同じくらい簡単です (より簡単ですか?) が、必要なツリーを問題なく形成できるようになりました。

これでは結合性が得られません。許可されるようにツリーを形作るだけです。結合性とは、ツリー ( + (+ ab) c) が (+ a (+ bc)) と同じことを意味することを意味します。それは実際にはセマンティックプロパティです（確かに「-」では機能しませんが、提示された文法では区別できません）。

連想性が明示的に表現されるパーサーと用語書き換え (ソースからソースへの変換を使用) を含むツール ( DMS Software Reengineering Toolkit ) があります。私たちはあなたの文法を書きます：

Expr  ::= Term ;
[Associative Commutative] Expr  ::= Expr "+" Term ;
Expr  ::= Expr "-" Term ;
Term  ::= Factor ;
[Associative Commutative] Term  ::= Term "*" Factor ;
Term  ::= Term "/" Factor ;
Factor ::= INTEGER ;
Factor ::= "(" Expr ")" ;

文法はこのように長くて不器用に見えますが、実際には特殊なケースを分解し、必要に応じてマークすることができます. 特に、結合可能な演算子とそうでない演算子を区別し、それに応じてマークを付けることができるようになりました。そのセマンティック マーキングにより、ツリー書き換えエンジンは自動的に結合性と交換性を考慮します。このようなセマンティック プロパティを考慮する必要のない典型的な式の文法に対して明示的な書き換え規則を使用して、高校の代数を記号的に単純化するために使用される DMS 規則の完全な例を見ることができます。それは書き換えエンジンに組み込まれています。

于 2012-06-02T10:48:07.753 に答える