問題タブ [lalr]

プログラミング言語のパーサーを生成するために GPPG (基本的に C# の bison) を使用しています。本当に厄介な部分を除いて、すべてが順調に進んでいます。私たちが解析している言語には、一種の「暗黙の比較」規則があり、「式式」は「式 == 式」として解釈されます。

たとえば、これは完全に有効なステートメントです。

これにより、パーサーの生成中にあらゆる種類の競合が明らかに発生します。それらを解決するための私の最初の試みは、これらの線に沿ったものでした（簡潔にするために編集しました）。ルールのリファクタリングを試みたところ、もはやあいまいではないように見えますが、明らかな何かが欠けているに違いありません。

これは、私が抱えている競合を示す非常に小さな文法であり、それを解決しようとした方法はうまくいきません

どんな助けでも大歓迎です

Context Free Artと呼ばれる文脈自由言語を解析しようとしています。YACC のような JS LALR(1) パーサー ジェネレーターJSCCを使用して、Javascript でパーサーを作成しました。

次の CFA (Context Free Art) コードの例を見てみましょう。このコードは有効な CFA です。

A上記のとに注意してくださいs。sをスケーリングするコマンドですがCIRCLE、Aこのルールの名前にすぎません。言語の文法では、トークンとして設定sし、トークンの下にSCALEあります(文字列に一致する正規表現があり、すべてのトークンの一番下にあります)。ASTRING

これは問題なく動作しますが、以下の場合は壊れます。

これも完全に有効なコードですが、私のパーサーはs後にruleas SCALEtoken をマークするため、期待していたと言ってエラーになりますSTRING。

私の質問は、これを説明するためにパーサーのプロダクション ルールを書き直す方法があるかどうかです。関連する生産規則は次のとおりです。

私が考えることができる簡単な解決策の 1 つは、上記のルールのコピーを でSTRING置き換えて作成することSCALEですが、これは、そのような修正が必要な多くの同様のルールの 1 つにすぎません。さらに他にもマッチング可能な端末はたくさんありますSTRING。つまり、ルールが多すぎるということです。

いくつかの主要な構文解析アルゴリズム (LL(1)、LR(1)、LR(0)、LALR(1)) の文法を集めたオンラインの優れたリソースはありますか? 私はこれらのファミリーに分類される多くの個々の文法を見つけましたが、誰かが大量の文法例を書き上げた優れたリソースを知りません。

そのようなリソースを知っている人はいますか？

私はしばらくの間これで立ち往生しています。私は次のような単純なものを解析したいと思います：

好きなもの：word1 word2 .. wordN嫌いなもの：word1 word2 .. wordN

Lemon+Flexを使用しています。現時点では、私の文法は次のようになっています。

ただし、これは最初の2単語でのみ機能します。明らかに、おそらく再帰的定義で、私は何か間違ったことをしていますか？どんな頭を上げても大歓迎です:)

C++ で Bison を使用してパーサーを生成しようとしています。文法は問題ありませんが、アクションですぐに問題が発生します。簡単なサンプルを次に示します。

私の知る限り、これはごく普通のことです。私が持っている問題は、どちらが最初に導出されるかです。たとえば、次のような入力がある場合

バイソンは私の行動を

また

ここで呼び出されたルールのリンクされたリストを作成しようとしていますが、リストを入力された順序と同じ順序に保ちたいと考えています。今、私は持っている

編集：わかりましたので、次のようなことができます：

Bisonコードでは、予想されるシフト/リデュースの競合がいくつかあり、通常のC文法は。の競合を生成することを知っていif/elseます。しかし、私は330の他のシフト/削減の競合を生成する文法を持っています。これは私の文法に深刻な問題があることを示していますか？それぞれの対立を追い詰めて、それが正しいかどうかを解決または検証することに時間を費やす必要がありますか？私は通常のLALRパーサーを使用しています。

編集：

これが私の文法です。すべてのアクションとその他のものを取り除きました。

私は少し前進しました。あなたは正しかった-それは何度も同じ対立だった。ルールの内容（具体的にはvarルール）をコメントアウトして文法からキーワードを削除しようとしていたことが判明したため、Bisonがそれを使用していたものに遭遇したときはいつでも、キーワードを減らすかどうかがわかりませんでした。空のルール。現在、シフト/リデュースは3つ、リデュース/リデュースは2つしかありません。

したがって、元の質問に対する私の答えは「はい」だったと思います。330のシフト/削減の競合があることは本当に悪い兆候です。

私はある言語のパーサーを書いていますが、スキャナーは次のように設計されています

1. 不要な端末も返す（例：ホワイトスペース）または
2. そうしないでください

ブールフラグに基づいています。

さて、パーサーでは、これらすべての端末で文法を乱雑にしたくありません。構築している解析ツリーに「自動的に」飲み込まれる必要があります。

この「魔法」を行うには、端末をチェーン化して（単純にリンクされた循環リスト）、削減が行われるときにそれらを繰り返して「空白を埋める」ことができると思いました（LALR（1）パーサジェネレーターを使用しています） 。

問題が1つありますが、それは正気のアイデアのように聞こえます。私が「戻るかどうか」と言ったことを覚えていますか？シナリオ（2）では、次に何が来るか誰が知っているので、端末を解放しますか？そして、メモリリークは必要ありません。

しかし、シナリオ（1）では、ターミナルを解放できません。これに基づいて、「空白を埋める」プロセスを停止する場所をさらに削減することを決定するためです。

同じ理由で、条件付きで解放することもできません。次に何が来るかわかりません。「空白を埋める」プロセスがトリガーされない場合はどうなりますか？それ以上の削減がまったくない場合はどうなりますか？

同様の問題がありましたか？どのようにそれを解決しましたか？

注：これはすべて私の頭の中にあり、十分に明確に説明していない可能性があります。質問してください。質問を編集します。シナリオは実際にはもう少し複雑です。私はこれを最初から書いているのではなく、想像力を使って他の何かに統合しているので、「それはできません。環境の制約のため」。

補遺

私の頭に浮かぶ唯一の本当に良いアイデアは、パーサージェネレーターをフォークして改善することです。これは、私が上で述べた制限のいくつかを克服するために、あちこちのいくつかのマイナーな場所ですでに行っています。

あいまいな文法に問題があります。私はこれを持っています：

これは私の本物の文法のサブセットであり、個別にコンパイルできます。現時点では、ストリームとの間function_callにS/Rの競合が発生します。関数呼び出しと関数定義の文法を統一することで、トークンストリームの後半まで決定を下す必要がないことをBisonに納得させようとしています。言い換えると、呼び出しと定義の両方に共通する何かに遭遇した場合、どちらがどちらであるかを知る必要なしにそれを減らすことができ、他の何かに遭遇した場合、他の何かがどちらを明確にラベル付けします。それも可能ですか？もしそうなら、どうすればそれができますか？可能であれば、入力ストリームの構造を変更する必要はありません。function_definitionidentifier (