Writing a formal language parser with Lisp

Question

My company is designing a new domain specific scripting language; I have to implement a parser that translates our brand new programming language into a common scripting language so as to be able to enact it.

The usual way I do this is by means of Bison and Flex tools that generate the C/C++ code of the translator.

I found other tools, for most of the mainstream programming languages, but none for Lisp.

Hasn't Lisp ever been used for that? What is the usual way to write a parser with Lisp?

Note: to me, any Lisp implementation / dialect that could help is ok, I do not have any preference.

Intubate

See the parsing section of the Clojure Toolbox for some options for that dialect. – Larynx

Answer 1

To cover the Racket part of it:

People often write parsers and there are many ways to do so:

• Write a recursive descent parser manually.
• Use the parser-tools library in Racket, which is lex/yacc style.
• Use Ragg, an AST generator generator letting you write BNF.
• Use Parsack, a monadic parser combinator library similar to Haskell's Parsec.
• I'm probably overlooking at least a half-dozen other options (e.g. I know there's at least one PEG style lib for Racket).

Hump

And if the DSL is S-expression based, you can just use read (along with, if warranted, macro-expansion). ;-) – Opheliaophelie

Matthew Flatt also has a relevant article in ACM Queue which is about going from zero to a mini-DSL with its own syntax in Racket: queue.acm.org/detail.cfm?id=2068896 – Pettit

Can Lisp macros parse non-lispy syntax? As in imagine parsing Haskell like syntax in Lisp? – Nysa

@CMCDragonkai, no, but the parser tools mentioned above serve the sole purpose of converting a non-lispy syntax into a lispy syntax. Here's an example of bf: github.com/expede/fainbracket – Minica

Answer 2

Well, "the usual" way to do this in Common Lisp is … to do it in Lisp.

A lot of domain-specific languages (and Lisp is pretty much notoriously specialized for this purpose!) are simply written as extensions to Lisp itself, using the macro facility. The upside is, it's trivial to write a DSL. The downside is, they often tend to "look like" lisp.

Some examples of DSL's within the Common Lisp standard include the LOOP macro's own sub-language and the sub-language of the FORMAT specifiers.

Since Lisp's s-expression notation is nominally a written form of an Abstract Syntax Tree, it's one way to avoid having much of your own lexer or parser; you can just use READ.

That all being said, you can use some common packages that might be found in GRAYLEX or CL-LEXER or so forth; looking at the parsers for some other language with a similar syntax to yours might help. In Quicklisp, I see:

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>                                   

Shall

As pointed out most eloquently at programmers.stackexchange.com/a/163246/41788 … “Yes, Lisp is a meta-language. And the best way of using it is implementing compilers for the domain-specific languages. Every little macro in Lisp is essentially a compiler.” – Shall

Answer 3

There are two ways to parse non-lispy languages in common-lisp.

1) Use readtables. this is the classic way: the lisp reader algorithm is a simple recursive-decent parser already, which supports character-based dispatch. Vacietis does this here

2) Use a parsing library. I can recommend esrap as a good utility for doing packrat parsing, and smug as a decent one for doing monadic parsing. Both are available in quicklisp

Grigri