2014-01-17 39 views
9

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

我这样做的通常方法是通过BisonFlex工具生成翻译器的C/C++代码。

我发现了大多数主流编程语言的其他工具,但没有一个用于Lisp

还没有Lisp曾经用过吗?用Lisp编写解析器的常用方法是什么?

请注意:对于我来说,任何Lisp实现/方言可以帮助确定,我没有任何偏好。

+0

请参阅[Clojure Toolbox](http://www.clojure-toolbox.com/)的解析部分,了解该方言的一些选项。 –

回答

14

为了掩饰它的Racket部分:

人们经常写解析器,有很多方法可以做到这一点:

  • 手工编写一个递归下降解析器。
  • 在Racket中使用parser-tools库,这是lex/yacc风格。
  • 使用Ragg,AST发电机发电机让你写BNF。
  • 使用Parsack,这是一个类似于Haskell的Parsec的monadic解析器组合器库。
  • 我可能会忽略至少6个其他选项(例如我知道至少有一个适用于Racket的PEG样式库)。
+2

如果DSL是基于S表达式的,您可以使用'read'(以及,如果有保证的话,宏扩展)。 ;-) –

+4

Matthew Flatt在ACM队列中也有相关的文章,这篇文章讲述了从零到一个mini-DSL,在Racket中有自己的语法:http://queue.acm.org/detail.cfm?id=2068896 –

+0

Can Lisp宏可以解析非lispy语法吗?像在Lisp中解析Haskell一样的语法? – CMCDragonkai

10

那么,在Common Lisp中执行此操作的“常用”方法是......在Lisp中执行此操作。

很多领域特定的语言(和Lisp是非常出名的专门为此目的!)简单地写作Lisp本身的扩展,使用宏设施。好处在于,编写DSL是微不足道的。缺点是,他们往往倾向于“看起来像”lisp。

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

由于Lisp的s表达式符号名义上是抽象语法树的书面形式,它是避免拥有大量自己的词法分析器或分析器的一种方法;你可以使用READ

就这么说,你可以使用一些常见的包,可以在GRAYLEXCL-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>         
+3

正如http://programmers.stackexchange.com/a/163246/41788最能说明的那样......“是的,Lisp是一种元语言。使用它的最好方法是实现特定领域语言的编译器。 Lisp中的每一个小宏本质上都是一个编译器。“ – BRFennPocock

3

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

1)使用readtables。这是一种经典的方式:lisp读取器算法已经是一个简单的递归正确的解析器,它支持基于字符的调度。Vacietis是否这样here

2)使用解析库。我可以推荐esrap作为进行packrat解析的一个很好的实用工具,并且作为一个体面的monadic解析工具而得意。两者都可以在quicklisp