parsing - 曖昧さのない文法

Question

算術式の曖昧さのない文法を作りたい。これで、べき乗の優先順位が高くなり、右側に関連付けられるはずです。他のすべての操作は左側に関連付けられています。これは私がこれまでに持っているものですが、べき乗が正しいかどうかはわかりません

E -> E+T | E-T | T
T -> T*F | T/F | L
L ->  F^ L|F
F -> i | (E)

Answer 1

これは recursive-descent とタグ付けされているため、LL と思われるので、興味があります。

LL パーサーの文法を作成するときは、次の規則を覚えておいてください。

繰り返しは左結合性のために使用されます:

Foo -> Bar (op Bar)*

末尾再帰は、右結合性のために使用されます。

Foo -> Bar (op Foo)?

再帰が残っているため、LL パーサーに適した文法はありません。

E -> E+T

一方、LL の場合、累乗は末尾再帰を使用するため、機能します。

wikipedia のTop Down ParsingとLeft-Recursion の記事をお勧めします (これらはLL パーサーの記事よりも読みやすいです)。また、 LR パーサーの動作が異なり、左結合と右結合の文法が異なることに注意してください。

ああ、あなたのルールの順序は、LLパーサーが優先するために必要なものに対して正しいです。優先順位の低い演算子ルールが、プロダクション ルール チェーンの最初に来ます。

Answer 2

あなたの文法に基づいて、ここにあなたが望むもののより読みやすいバージョンがあります. これは明確で、結合性を正しく捉えます。

expr -> term | expr add term
term -> factor | term mult factor
factor -> number | - factor | ( expr )
add -> + | -
mult -> * | /

この例は、宿題に適用できるように、はるかに読みやすいはずです。演算子を省略し^ましたが、例から理解できるはずです。[別の] 教科書を購入したい場合は、Programming Language Pragmaticsが大いに役立ちます。