Lispでの公式言語パーサの作成

Question

私の会社は新しいドメイン固有のスクリプト言語を設計しています。私は、新しいプログラミング言語を共通のスクリプト言語に翻訳し、それを制定できるようにするパーサーを実装する必要があります。

これを行う通常の方法は、翻訳者のC/C++コードを生成するツールBisonとFlexを使用する方法です。

ほとんどの主流プログラミング言語では他のツールが見つかりましたが、Lispではありません。

Lispはこれまで使用されていませんか？ Lispのパーサーを書く普通の方法は何ですか？

注：私にとっては、Lispの実装/方言は大丈夫ですが、私は好みがありません。

人々はしばしばパーサを書いて、それを行うには多くの方法があります：それのRacket一部を覆うように

Answer 1

• が手動で再帰下降パーサを書きます。
• ラケットにはparser-toolsというライブラリがあります。これはlex/yacc形式です。
• ASNジェネレータジェネレータを使用すると、BNFを書き込むことができます。
• HaskellのParsecに似たモナディーパーザコンビネータライブラリであるParsackを使用してください。
• 私は多分、少なくとも6つのオプションを見落としています（例えば、少なくとも1つのラケット用のPEGスタイルのlibがあることはわかっています）。

Answer 2

まあ、Common Lispでこれを行う "通常の"方法は、Lispでそれをすることです。

多くのドメイン特有の言語（そしてこの目的のためにLispはかなり有名になっています！）は、単にマクロ機能を使ってLisp自身への拡張として書かれています。それは、DSLを書くのは簡単なことです。欠点は、彼らはしばしば "見た目のように"見える傾向があることです。

Common Lisp標準のDSLには、LOOPマクロ独自のサブ言語とFORMAT指定子のサブ言語があります。

Lispのs式の表記法は、名目上は抽象構文木の書いた書式なので、あなた自身のレクサーやパーサをあまり使わない方法の1つです。 READを使用することができます。

これらのことはすべて、GRAYLEXまたはCL-LEXERなどの共通パッケージを使用することができます。あなたに似た構文を持つ他の言語のパーサを見てみると助けになるかもしれません。 Quicklispで、私は参照してください：

CL-USER> (ql:system-apropos "parse") 
#<SYSTEM cl-arff-parser/cl-arff-parser-20130421-git/quicklisp 2013-08-13>                                                 
#<SYSTEM cl-date-time-parser/cl-date-time-parser-20130813-git/quicklisp 2013-08-13>                                               
#<SYSTEM cl-html-parse/cl-html-parse-20130813-git/quicklisp 2013-08-13>                                                  
#<SYSTEM cl-html5-parser/cl-html5-parser-20130615-git/quicklisp 2013-08-13>                                                 
#<SYSTEM cl-html5-parser-tests/cl-html5-parser-20130615-git/quicklisp 2013-08-13>                                               
#<SYSTEM cl-pdf-parser/cl-pdf-20130420-git/quicklisp 2013-08-13>                                                    
#<SYSTEM cli-parser/cl-cli-parser-20120305-cvs/quicklisp 2013-08-13>                                                   
#<SYSTEM clpython.parser/clpython-20130615-git/quicklisp 2013-08-13>                                                   
#<SYSTEM com.gigamonkeys.parser/monkeylib-parser-20120208-git/quicklisp 2013-08-13>                                               
#<SYSTEM com.informatimago.common-lisp.html-parser/com.informatimago-20130813-git/quicklisp 2013-08-13>                                          
#<SYSTEM com.informatimago.common-lisp.parser/com.informatimago-20130813-git/quicklisp 2013-08-13>                                           
#<SYSTEM csv-parser/csv-parser-20111001-git/quicklisp 2013-08-13>                                                   
#<SYSTEM fucc-parser/fucc_0.2.1/quicklisp 2013-08-13>                                                      
#<SYSTEM http-parse/http-parse-20130615-git/quicklisp 2013-08-13>                                                   
#<SYSTEM http-parse-test/http-parse-20130615-git/quicklisp 2013-08-13>                                                  
#<SYSTEM js-parser/js-parser-20120909-git/quicklisp 2013-08-13>                                                    
#<SYSTEM parse-declarations-1.0/parse-declarations-20101006-darcs/quicklisp 2013-08-13>                                              
#<SYSTEM parse-float/parse-float-20121125-git/quicklisp 2013-08-13>                                                   
#<SYSTEM parse-float-tests/parse-float-20121125-git/quicklisp 2013-08-13>                                                 
#<SYSTEM parse-js/parse-js-20120305-git/quicklisp 2013-08-13>                                                    
#<SYSTEM parse-number/parse-number-1.3/quicklisp 2013-08-13>                                                     
#<SYSTEM parse-number-range/parse-number-range-1.0/quicklisp 2013-08-13>                                                  
#<SYSTEM parse-number-tests/parse-number-1.3/quicklisp 2013-08-13>                                                   
#<SYSTEM parse-rgb/cl-tcod-20130615-hg/quicklisp 2013-08-13>                                                     
#<SYSTEM parseltongue/parseltongue-20130312-git/quicklisp 2013-08-13>                                                  
#<SYSTEM parser-combinators/cl-parser-combinators-20121125-git/quicklisp 2013-08-13>                                               
#<SYSTEM parser-combinators-cl-ppcre/cl-parser-combinators-20121125-git/quicklisp 2013-08-13>                                            
#<SYSTEM parser-combinators-tests/cl-parser-combinators-20121125-git/quicklisp 2013-08-13>                                             
#<SYSTEM py-configparser/py-configparser-20101006-svn/quicklisp 2013-08-13>         

Answer 3

共通lispでnon-lispy言語を解析する2つの方法があります。

1）読み取り専用を使用します。これは古典的な方法です：lispリーダアルゴリズムは、文字ベースのディスパッチをサポートする単純な再帰的な構文解析ツールです。これは便宜です。here

2）解析ライブラリを使用してください。私は、packrap解析を行うための良いユーティリティとしてesrapを推奨し、モナド解析を行うためのまともなものとしてお勧めします。両方ともquicklispで利用可能です