2

私は単純な式パーサーに取り組んでいますが、以下のパーサー コンビネーター宣言を考えると、テストに合格できないようで、正しい連想ツリーがポップアップし続けます。

def EXPR:Parser[E] = FACTOR ~ rep(SUM|MINUS) ^^ {case a~b => (a /: b)((acc,f) => f(acc))}
def SUM:Parser[E => E] = "+" ~ EXPR ^^ {case "+" ~ b => Sum(_, b)}
def MINUS:Parser[E => E] = "-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}

私はこれのために何時間もデバッグしてきました。誰かがそれが正しく出ていないことを理解するのを手伝ってくれることを願っています.

"5-4-3" は、予想される -2 ではなく 4 に評価されるツリーを生成します。

上記の文法のどこが間違っていますか?

4

3 に答える 3

4

私は Scala を扱っていませんが、F# パーサー コンビネーターを扱っており、中置演算子との結合性も必要としていました。5-4 または 2+3 を実行できると確信していますが、優先順位と演算子が同じ 2 つ以上の演算子、つまり 5-4-2 または 2+3+5 のシーケンスで問題が発生します。ご存知のように、(2+3)+5 = 2+(3+5) ではなく、(5-4)-2 <> 5-(4-2) のような足し算では問題は発生しません。

参照: Monadic Parser Combinators 4.3 意味のあるセパレーターを使用した繰り返し。注: セパレーターは「+」や「*」などの演算子であり、空白やコンマではありません。

参照:関数パーサーセクション 7 の chainl および chainr パーサーを探してください。その他のパーサー コンビネータ。

たとえば、算術式では、部分式を区切る演算子が解析ツリーの一部である必要があります。この場合、関数 chainr と chainl を開発します。これらの関数は、セパレーターのパーサーが関数 (!) を生成することを想定しています。

関数 f は、それぞれが演算子と要素を含む要素とタプルのリストで動作する必要があります。たとえば、f(e0; [(1; e1); (2; e2); (3; e3)]) は ((eo 1 e1) 2 e2) 3 e3 を返す必要があります。これには、リストからのタプル (; y) と中間結果 x が x y を適用して結合される (カリー化されていないものではありますが)、foldl のバージョンがあることがわかります。

fold functionセマンティックパーサー、つまり構文パーサーからのトークンをパーサーの出力に変換する部分が必要です。あなたのコードでは、この部分だと思います。

{case a~b => (a /: b)((acc,f) => f(acc))}

Scala を使用していないため、これ以上のことはできません。

于 2013-12-01T13:28:52.960 に答える
1 
"-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}

5-4-3 の場合、次のように展開されます。

Diff(5, 4-3)

これは

Diff(5, Diff(4, 3))

ただし、必要なものは次のとおりです。

Diff(Diff(5, 4), 3))

// for 5 + 4 - 3 it should be

Diff(Sum(5, 4), 3)

スタックを含める必要があります。

于 2013-12-01T11:33:57.010 に答える
0

「+」を使用しているようです〜EXPRは答えを間違っていました。代わりにFACTORであるべきでした。

于 2013-12-01T13:07:07.253 に答える