用Lisp编写正式的语言解析器

Question

我的公司正在设计一种新的特定于域的脚本语言; 我必须实现一个解析器,将我们全新的编程语言转换为通用的脚本语言,以便能够实现它.

我这样做的通常方法是通过生成翻译器代码的工具Bison和Flex工具C/C++.

对于大多数主流编程语言,我找到了其他工具,但没有找到Lisp.

没有Lisp曾经被使用是什么？编写解析器的常用方法是什么Lisp？

注意:对我来说,任何Lisp可能有帮助的实现/方言都可以,我没有任何偏好.

Answer 1

覆盖Racket部分:

人们经常编写解析器,有很多方法可以这样做:

• 手动编写递归下降解析器.
• 使用Racket中的解析器工具库,它是lex/yacc样式.
• 使用Ragg,一个让你编写BNF的AST生成器.
• 使用Parsack,一个类似于Haskell的Parsec的monadic解析器组合库.
• 我可能忽略了至少六个其他选项(例如,我知道至少有一个针对Racket的PEG样式库).

Answer 2

好吧,在Common Lisp中执行此操作的"通常"方法是......在Lisp中执行此操作.

许多特定于域的语言(和Lisp非常出名地专门用于此目的!)只是使用宏工具编写为Lisp本身的扩展.好处是,写一个DSL是微不足道的.缺点是,他们往往"看起来像"口齿不清.

Common Lisp标准中的DSL的一些示例包括LOOP宏自己的子语言和FORMAT说明符的子语言.

由于Lisp的s表达式符号名义上是抽象语法树的书面形式,因此它是避免使用自己的词法分析器或解析器的一种方法; 你可以使用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

在 common-lisp 中有两种解析非 lispy 语言的方法。

1) 使用可读表。这是经典的方式：lisp 阅读器算法已经是一个简单的递归体面的解析器，它支持基于字符的调度。Vacietis在这里做这个

2）使用解析库。我可以推荐 esrap 作为一个很好的工具来进行 Packrat 解析，而 smug 作为一个体面的工具来进行 monadic 解析。两者都可以在 quicklisp 中使用