問題タブ [peg]

PEG.jsを使用して、左結合演算子の AST ( Abstract Syntax Tree ) をどのように構築しますか?

インターネットで見つけた情報に基づいてコードを記述しようとしましたが、間違いを犯したようです。

私が書いたコードは、ほとんどの式に対して間違った AST を生成します。

表現

予想AST

生成された AST

コード

左結合演算子と右結合演算子の両方の AST を構築する方法について、ヘルプやサンプル コードをいただければ幸いです。

編集: @Bergi が指摘したように、問題は、の代わりに残りの演算子リストの式としてE2使用されることでした。しかし、Bergi が書いたコードは私のものよりずっと単純です。E1Value

vCard 形式を解析するパーサーを作成することで、パセリを学んでいます。私の問題は、vCard 形式の一部の行が複数の行に分割される可能性があることです。RFC 822 の「折りたたみ」技術を使用した複数行の表現。つまり、線形の空白が存在する可能性がある場合は、CRLF の直後に少なくとも 1 つの LWSP-char が続きます。私の解決策は、最初に生のテキストを解析することです。改行の後にスペースが続き、その行を結合できます。しかし、私はそれを動作させることができません:私の最新の試みがあります:コードは最後にエラーを返します: TypeError: +: 'bool' および 'str のサポートされていないオペランド型(s)

これがすでに尋ねられている場合は、事前にお詫び申し上げます。私は文法によって定義された言語を持っており、人々が独自の文法に Intellisense を実装する方法を知りたいと思っています。これは私には機械的に思えます。ユーザーが何かを入力すると、それが生成されたパーサーに渡され、キーワードの提案が提供されます。解析は、1 回限りのもの、つまり生成されたパーサーではなくインクリメンタルになるように変更する必要があると思います。

私はこの分野に慣れていないので、ヒントは大歓迎です。

http://pegjs.majda.cz/を使用するつもりですが、何でも構いません。

音楽プログラミング言語を設計し、その構文を PEG 文法として実装しています。構文解析プロセスはかなり複雑になりました。そのため、最も単純なアプローチのように見えたのは、いくつかの個別の文法を定義し、それらを順番に適用することでした。これまでのところ、3 つの文法があります。

1. ソース ファイルの内容全体を取得し、コメントを削除します。
2. ソース ファイル (コメントを削除) を取得し、楽器ごとに分けます。これにより、楽器の名前/定義と、その楽器によって「演奏される」「音楽コード」のペアが作成されます。
3. 実際に音楽コードを解析し、音楽の「イベント」の解析ツリーを返します。

3 つのパーサーのうち、#3 は群を抜いて最も複雑です。#1 と #2 は比較すると単純で、それぞれ約 10 行しか使用しません。一方、#3 は、実装する構文が増えるほど複雑になり、現在 33 行に増えています。

3 つの文法を 1 つに凝縮できるのではないかという考えが頭に浮かびました。これにより、文法の繰り返しが少し減るかもしれませんし、プログラム自体のコードの行数も減るかもしれませんが、物事が過度に複雑になるかどうかはわかりません。私はそれらを組み合わせることに大雑把に突き刺しましたが、すべてのルール内でコメントが発生する可能性に対処する必要があるように思われるため、すぐに難しいことがわかりました（間違っていたら訂正してください！）。現状では、オプションの空白の規則が既にあり、ほとんどの音楽の「イベント」の定義に含めて、構文で空白をある程度柔軟に使用できるようにしています。複数のパスでの解析に固執し、タスクごとに 1 つずつ、複数の個別のパーサーを用意する方が理にかなっているのかどうか、私には判断できません。

私の質問は次のとおりです。PEG 文法を作成した経験のある方は、大きな文法を小さなサブ文法に分割し、入力に対して複数のパスを作成することがよくありますか? すべてを 1 つの文法にまとめることの利点 (パフォーマンスまたはその他) はありますか?

次の最小限の Peg.js 文法を定義しました。

サンドボックスで試すことができます。

「A1」と「A123」が一致すると予想していました (バックトラッキングの仕組みに関する私の考えによると)。しかし、そうではありません: 文法は "A1" を認識しますが、"A123" は認識しません。

注:関連する質問How to transform a simple grammar into something that works in PEG.js (expected "a" but "a" found) のように、「用語の順序を逆にする」というアドバイスは探していません。むしろ、私が見ている動作と、この場合に Peg.js のバックトラッキングが適用されない理由を理解しようとしています。用語の順序を逆にしても効果がない理由については、以下のより現実的な例を参照してください。

より現実的な例として、単位の解析を考えてみましょう。文法は、メートル法単位 (「m」、「mol」など) を、「mm」、「mm​​ol」などのオプションの接頭辞とともに認識し、「yr」、「week」、または「mo」などの非メートル法単位も認識する必要があります。

次の Peg.js 文法は、「mo」を消費してつまずいてバックトラックしないため、「mol」を認識しません。(用語の順序を変更しても意味がありません。むしろ、「mol」または「mmol」を犠牲にして「mo」が認識されるようになります。)

私はAntlrで同様のことをうまくやることができます:

話は以下。私はpeg/leg parser generatorで遊んでいます。これは、PEG 文法を定義するための優れた構文を持ち、非常に使いやすいです。生成されたパーサーで不可解なセグメンテーション違反が発生するまで、私はそれに完全に満足していました。一部の調査では、生成されたヘルパー関数の 1 つに問題があることが明らかになりました。

この関数は常にcount<0 で呼び出されます。C 配列で負のインデックスを使用することは、未定義の動作です。私が理解しているように、配列の先頭から後方を指すと、他の配列で正しいポインターが得られるように、メモリがペグ/レッグによって割り当てられます。これは実際には非常に悪いコードですが、ほとんどの場合は問題なく動作します。ただし、プログラムの他の部分での割り当てにより、メモリチャンクとすべてのセグメンテーションフォールトに別の場所が強制されます。

この問題は、peg/leg が malloc を使用し、私のプログラムが new を使用していることが原因であると思われますが、malloc を使用するようにコードを変更できず、peg/leg を修正できません (複雑でわかりにくい)。

したがって、干渉を避けるために、パーサーが使用するメモリをプログラムの残りの部分から分離する必要があります。

C++でこれを行う方法はありますか? パーサーコードを「サンドボックス」に入れる可能性はありますか?

私はこのpegjs文法を持っています。左再帰を削除するにはどうすればよいですか?