38

このウィキペディアのページから：

文脈自由文法と構文解析式文法の根本的な違いは、PEG の選択演算子が順序付けられていることです。最初の選択肢が成功した場合、2 番目の選択肢は無視されます。したがって、文脈自由文法や正規表現のような順序付けられていない選択とは異なり、順序付けられた選択は交換可能ではありません。順序付き選択は、一部のロジック プログラミング言語で使用できるソフト カット演算子に似ています。

PEG の選択演算子がマッチングを短絡させるのはなぜですか? （メモ化による）メモリ使用量を最小限に抑えるためですか？

正規表現での選択演算子が何であるかはわかりませんが、これが/[aeiou]/母音に一致すると仮定しましょう。したがって、この正規表現は可換です。(5 階乗) 母音文字の順列? つまり/[aeiou]/、 と同じように動作し/[eiaou]/ます。それが可換であることの利点は何ですか？(PEG の非可換性を参照)

その結果、CFG が直接 PEG に音訳される場合、前者のあいまいさは、可能な解析から 1 つの解析ツリーを決定論的に選択することによって解決されます。代替文法が指定される順序を慎重に選択することにより、プログラマーは、どの構文木が選択されるかを大幅に制御できます。

これは、PEG の文法が CFG の文法よりも優れているということですか?

4

3 に答える 3

59

CFG 文法は非決定論的です。つまり、一部の入力によって 2 つ以上の解析ツリーが生成される可能性があります。ただし、ほとんどの CFG ベースのパーサー ジェネレーターには、文法の決定可能性に制限があります。選択肢が 2 つ以上ある場合は、警告またはエラーが発生します。

PEG 文法は決定論的です。つまり、入力は一方向にしか解析できません。

古典的な例を挙げると、文法

if_statement := "if" "(" expr ")" statement "else" statement
              | "if" "(" expr ")" statement;

入力に適用される

if (x1) if (x2) y1 else y2

次のように解析できます

if_statement(x1, if_statement(x2, y1, y2))

また

if_statement(x1, if_statement(x2, y1), y2)

CFG パーサーは、「else」キーワードに到達したときにシフト (別のトークンを読み取る) か、削減 (ノードを完了する) かを決定できないため、Shift/Reduce 競合を生成します。もちろん、この問題を回避する方法はあります。

PEG パーサーは、常に最初の選択肢を選択します。

どちらが良いかは、あなたが決めることです。私の意見では、多くの場合、PEG 文法は書きやすく、CFG 文法は分析しやすいということです。

于 2011-03-31T14:57:46.910 に答える
4

CFG と LR およびあいまいさを混同していると思います。パーサーはそうかもしれませんが、文法は決定論的/非決定論的ではありません。あいまいな文法は、定義に準拠している場合でも CFG であり、PEG が行うことを行う決定論的パーサーを構築できます。

于 2012-11-17T14:48:24.527 に答える