問題タブ [parser-generator]

以前、インクリメンタル パーサーを生成する SLR パーサー ジェネレーターを実装したことがあります。パーサーはテキストの一部を最初から最後まで解析できますが、テキストを削除または挿入するときは、すべてを最初から再解析するのではなく、トークン ストリームと構文ツリーで最小限の作業と最小限の変更を行います。問題は、これの用途を見つけることができなかったことですか? パーサーは、通常のパーサーよりも少し多くの作業を行います。そんな使い道あるの？PS。方法を知りたい場合は、「コンパイラ設計の基本」をグーグルで検索してください。これは無料の本です。その後、アルゴリズムを少し変更して、パーサーの状態をどこにでも保存できるようにするだけで済みました。これは余分な作業です。上で述べました。

まず最初に。

私は C# で少し LUA-Ide を書いています。コードの実行は、LuaInterface というアセンブリによって行われます。コード編集は Scintilla-Port によって行われ、RAD / UI インターフェイスは拡張可能な IDesignSurfaceExt Visual Studio (一方向のコード生成) を介して行われます。ファイル処理は、プロジェクト パッケージ ファイルとして使用される小さな sql-lite-db によって提供されます。

というわけで、必要なものはすべてそろっています...

未解決の唯一の問題は、lua のパーサー/レクサーです。コードを読み込んで実行したくない! Lua コードを含む文字列を解析し、関数やグローバル変数などの情報を取得したいだけです。私はパーサーを完全に自分で書きたくありません... (私は正規表現が嫌いです - 私はいつも間違っています ^^)

.net lua パーサーへのリンクを見つけた人はいますか?

明確にするために-この時点でコードを分析したいだけです-実行したくありません！

前もって感謝します！

コーレルゴット

この質問をした後、以前は手動で記述していたパーサー ジェネレーターを使用することに自信が持てるようになりました。

しかし、C++ コードを生成するパーサーも、Unicode を正しく処理するパーサーも見つけることができないようです。(私の入力は UCS-2 にあることに注意してください -- パーサーの構築がより困難になる場合、基本多言語面の外側のビットをサポートすることは気にしません)

C を生成できるパーサーがいくつかありますが、そのようなパーサーはすべて、窓の外に例外安全性をスローしているように見えます。これにより、セマンティック アクション内で C++ を使用できなくなります。

これら 2 つの原則を満たすパーサー ジェネレーターは存在しますか?

編集:ああ、私のプロジェクトはBSLライセンスなので、パーサージェネレーター自体の出力の使用に多くの制限はありません。

C＃ベースのプログラミング言語コンパイラを手動のレクサー/パーサーからAntlrに移行しています。

Antlrは、通常はほとんど機能するため、深刻な頭痛の種になっていますが、機能しない小さな部分があり、解決するのが非常に困難です。

私の頭痛のほとんどは、パーサーではなく、Antlrのレクサー部分が原因であることがわかりました。次にparser grammar X;、手動で記述したレクサーと、Antlrで生成されたパーサーを使用できる可能性があることに気づきました。

だから私はこのトピックに関するより多くのドキュメントを探しています。カスタムITokenStreamが機能する可能性があると思いますが、このトピックに関するオンラインドキュメントは事実上ないようです...

私の質問はScalaパーサーについてです：

• （標準ライブラリ内および外部で）利用可能なものはどれですか、
• それらの違いは何ですか、
• それらは共通のAPIを共有していますか
• 異なるパーサーを組み合わせて1つの入力文字列を解析できますか？

私は少なくともこれらを見つけました：

• Scalaの「標準」パーサー（LLパーサーのようです）
• ScalaのPackratパーサー（2.8以降はLALRパーサーです）
• パーボイルドパーサー（PEGパーサー？）
• SpiewakのGLLパーサーコンビネーター

文法パーサーについては、賛否両論があるBisonで「遊んで」いました。

先週、SqLiteサイトでエンジンが別の文法パーサーであることに気付きました: Lemon

薄いドキュメントを読んだ後は素晴らしいですね。
このパーサーについてフィードバックはありますか?

Google やウィキペディアで適切な情報を実際に見ることができない (ほんの数例、同じチュートリアル) あまり人気がないようです。(スタック オーバーフローにはレモンタグはありません [編集: 現在 :P があります])

約6年前、私はOCamlで自分のパーサーコンビネーターのベンチマークを行い、当時提供されていたパーサージェネレーターよりも約5倍遅いことがわかりました。私は最近、このテーマを再検討し、HaskellのParsecと、F＃で記述された単純な手巻きの優先順位クライミングパーサーのベンチマークを行いました。F＃がHaskellより25倍高速であることに驚きました。

これが私がファイルから大きな数式を読み取り、それを解析して評価するために使用したHaskellコードです：

これが、F＃の自己完結型の優先順位クライミングパーサーです。

私の印象では、最先端のパーサーコンビネーターでさえ、バックトラッキングに多くの時間を浪費しています。あれは正しいですか？もしそうなら、競争力のあるパフォーマンスを得るためにステートマシンを生成するパーサーコンビネーターを書くことは可能ですか、それともコード生成を使用する必要がありますか？

編集：

ベンチマーク用に〜2Mbの式を生成するために使用したOCamlスクリプトは次のとおりです。

次の入力があります

RecDescent パーサー ジェネレーターの文法を書かなければなりません。出力時のデータは、xml 構造に合わせて変更する必要があり、次のようになります。

追加の繰り返しフィールドはエラーとして報告する必要があります (行番号を含む適切なメッセージで、それ以上の解析は行われません)。私はこのようなものから始めようとしました：

しかし、それが正しい方法であるかどうかさえわかりません。助けてください。

もう 1 つ小さな問題があります。入力時のタグは特定の順序ではない場合がありますが、各タグは一度しか表示できません。(著者、タイトル、年、発行者) のすべての順列に対してサブルールを作成する必要がありますか? 私が思いついたので：

しかし、明らかにタグの繰り返しを妨げません。

私はコンパイラの世界に不慣れで、最近、パーサー ジェネレーターと呼ばれるものについて耳にしました。私が理解した (と思う) ことから、パーサー ジェネレーターは構文ファイルを取り込み、指定された構文でファイルを解析できるソース コード ファイルを出力します。

いくつかの質問：

1. 私はそれを正しく理解しましたか？

2. もしそうなら、ラゲルはそのようなツールですか？

3. そうである場合、Ragel は D パーサーを D ソース コードに出力できますか?

ありがとうございました！

タグのようなxmlを含む小さなテキスト文字列があります：

このテキストを解析し、タグに基づいてアクションを実行する必要があります。したがって、上記のテキストは、ターゲットアプリケーションでは_A B ^Cのようになります（MS Excel-この文字列を貼り付けるとExcelで解析およびフォーマットできますが、セルに入力するだけではできません）。

パフォーマンスの観点から、このタイプのタグベースのテキストを解析するための最良の方法は何ですか。フォーマットコードは非常に頻繁に呼び出されるため、オーバーヘッドを可能な限り最小限に抑えたいと思います。私は次のオプションを考えることができます：

1. タグがいつ開始/終了したかを追跡するインデクサーを使用して、文字ごとに解析します
2. 正規表現を使用する
3. それをいくつかのXML/HTML DOMパーサーにロードし、ノードを反復処理します

パフォーマンスへの影響が最も少ないのはどれだと思いますか？タスクを完了する他の方法はありますか？