0

Whttleを使用して文法を解析していますが、古典的なLALR のあいまいさの問題に直面しています。私の文法は次のようになります（簡略化）：

<comment> ::= '{' <string> '}'           # string enclosed in braces
<tag> ::= '[' <name> <quoted-string> ']' # [tagname "tag value"]
<name> ::= /[A-Za-z_]+/                  # subset of all printable chars
<quoted-string> ::= '"' <string> '"'     # string enclosed in quotes
<string> ::= /[:print:]/                 # regex for all printable chars

もちろん、問題は<string>. すべての印刷可能な文字が含まれているため、非常に貪欲です。<name>これは LALR パーサーであるため、a を aとして解析しようとする<string>と、すべてが壊れます。文法は、さまざまなものにさまざまな文字列区切り文字を使用するため、物事を複雑にします。そのため<string>、最初にルールを作成しようとしました。

可能であれば、この文法を正規化して LALR に準拠させる標準的な方法はありますか?

4

1 に答える 1

1

これは、「古典的な LALR のあいまいさの問題」ではありません。これは単に、言語の字句仕様のエラーです。

Whittle の readme をざっと見ましたが、OP の文法とは似ていませんでした。したがって、OPのテキストは文字通りではなく概念的なものであり、明らかに間違ったものが含まれているという事実を想定しています

<string> ::= /[:print:]/                 # regex for all printable chars

は単なるタイプミスです。

/[:print:]*/Ruby が Posix 標準では[:print:]なく[[:print:]].

しかし、字句解析は (通常) 可能な限り長い文字列に一致するため、これも正しくありません。その結果、最後の引用符とそれに続くテキストをむさぼり食います。

したがって、 の正しい解決策quoted-stringは、正しく書き出すことです。

<quoted-string> ::= /"[^"]*"/

あるいは

<quoted-string> :: /"([^\\"]|\\.)*"/
# any number of characters other than quote or escape, or escaped pairs

内部二重引用符をエスケープする方法について、他のアイデアがあるかもしれません。これらは単なる例です。どちらの場合も、(少なくとも) 二重引用符を取り除き、エスケープ シーケンスを解釈できるようにするために、トークンを後処理する必要があります。それはちょうどそれが行く方法です。

{This comment {with this} ends here}ネストされたブレース構文は規則的ではないため、正規表現と一致できないため、コメントにネストされたブレース (例: ) が含まれる可能性があることを意図していたと仮定すると、コメントシーケンスはより困難な問題を提示します。もちろん、最近では本当に規則的な「正規表現」ライブラリはほとんどありません。たとえば、Lua のパターン構文のように、Ruby にある種の中かっこを数える拡張機能が含まれているかどうかはわかりません。{...}ネストされたブレース構文は確かに文脈自由ですが、実際に解析するには、プログラムの残りの部分とは異なる方法でアウターの内容を字句解析する必要があります。

LALRアルゴリズムの弱点ではなく、この後者の観察があなたを悩ませているのです。これは、ホイットルの（ほとんど文書化されていない）字句解析セクションの弱点だと思います。たとえば、flex によって生成されたレクサーでは、開始条件を使用してレキシカル環境 (プログラム / 引用符で囲まれた文字列 / 中括弧付きコメント) を分離するのが普通であり、パーサーはあいまいさを持ちません。

それが役立つことを願っています。

于 2014-03-06T18:27:01.997 に答える