関数型言語でパーサーを作成する LL パーサーが明らかに不足していることに気付きました。成功せずに探していたものの理想的な発見は、ANTLR スタイルの LL(*) 文法 (文法のモジュロ マイナーな再フォーマット) 用の Haskell パーサーを生成するものであり、最後のすべてのパーサー ジェネレーターが関数型であることに驚きました。私が見つけた言語ターゲットはある種の LR パーサーでした。
私が取り組んでいるこの言語のパーサーを、ANTLR から言語自体の自己ホストへの関数機能を備えているものに移行したいと考えています。別の関数型言語でほぼ確実に正しいものを自分の言語に移植できれば、大いに役立ちます。 (できれば私がよく知っているもの、Haskell と Scala) をゼロから完全に書き直す必要はありませんが、コア言語は小さいため、最終的にはこれを行う可能性があります。
この時点で、これに対する解決策以上のものは、なぜそのような LL(*) や LL(k) パーサー ジェネレーターさえないのに、多くの LR ジェネレーターがあるのかについて非常に興味があります。
この主な理由は、関数型言語で記述されたほとんどの LL(k) パーサーがパーサー コンビネーターを使用して実装されているだけであるためです。パーサー コンビネーター ライブラリを生成する最も簡単な方法は再帰降下です。
Haskell のparsec、attoparsec、およびpolyparseと Scala のストック パーサー コンビネータはすべて、実質的に LL(*) パーサーを生成します。
parsec と attoparsec の両方で、明示的な try コンビネータを使用してバックトラッキングを取得する必要がありますが、これは効率のためだけに行われ、scalaパーサー コンビネータはpackrat 解析も処理できます。
Brent Yorgey の最近のアンバウンドパッケージの発表からの次の断片を考えてみてください。
parseAtom = parens parseTerm
<|> var <$> ident
<|> lam <$> brackets ident <*> parseTerm
元の文法を見るのはとても簡単です。
LRパーサーを効率的に実行するには、テーブルを生成するためにはるかに複雑な前処理が必要です。
パーサー コンビネーターを外部ツールではなく EDSL として実装することにより、プログラミング言語の高度な機能をより活用できるようになります。文法の一部を高次にする、レクサー ハックをパーサーに直接組み込むなどのことができます。典型的な LR パーサー ジェネレーターは、これらのことを行うことができないか、必要があるため、限られたコンテキストでアドホックな方法でしか提供できません。最後にテーブルを発行できます。
古い趣味のプロジェクトをhttps://github.com/nrnrnr/ebnfに投稿するきっかけになりました。標準 ML の LL(1) パーサー生成をサポートします。Icon を理解している人を見つけることができれば、Haskell に適応することは難しくありません。
人々は構文解析にコンビネータを好む傾向があるという Edward のコメントは非常に正しいですが、FIRST および FOLLOW セットを検出し、あいまいさについて文句を言うツールには利点があります。
EBNF の主な利点はその表記法です。シーケンス、Maybe型、予約語はすべてネイティブでサポートされており、余計な手間はかかりません。
SML には、数年前から ml-antlr があります。
http://www.classes.cs.uchicago.edu/archive/2007/winter/22610-1/docs/lpt-manual.pdf
また、Scheme 用の sllgen もあります。
LL パーサー ジェネレーターよりも多くの LR パーサー ジェネレーターが存在する理由については、手動で LR パーサーを記述するのは難しいため、ジェネレーターが本当に必要です。LL パーサーを使用すると、手作業でコーディングした実装でも文法に一致するため、ジェネレーターの必要性ははるかに少なくなります。
Scala を使用すると、既存のすべての Java ツールをオーバーヘッドなしで使用できます。JavaCC は LL(k) パーサー ジェネレーターです。これを使用して、具体的な構文ツリーを自動的に作成し、その他すべてを Scala で行うことができます。JavaCC文法がすでに存在していたという理由だけで、私は実際に小さなプロジェクトのためにそれをしました。
開発中の LL(k) ソリューションについて説明する前に、私が知っている他の利用可能なオプションを使用しなかった理由を説明します。
パーサー コンビネーター ライブラリ、つまり再帰降下パーサーは、次のことを行いません。
コンテキストの自由の欠如は、構文のあいまいさとして表れます。たとえば、ソース コード行の先頭 (セミコロンで送信されなかった行に続く行) の演算子が、式の右側の単項接頭辞であるかどうか、または、前のソース コード行の末尾にある式の中置二項演算子。
JavaCC には次の欠点があります。
Scala に出力する LL(k) パーサー ジェネレーターを作成しようとしています。うまくいけば、開発中の言語 (Scala にコンパイルされる Copute) を出力するためにブートストラップします。
私の現在の試みは、SLK 文法構文のサブセットを使用しているため、SLK ツールを使用して文法がコンテキストフリーであることを確認できます。
Java で LL* パーサーを (とりわけ) 生成するANTLRを使用できるため、 .classresp.jarファイルを使用できます。