OMeta/JS Parser/Generator DSL

This is a proof of concept s-expression parser in OMeta/JS I just made in about 10 minutes, produces Javascript nested lists as the resulting AST, although I could easily produce output text in a different language like C or C++. OMeta/JS is a Parsing Expression Grammar DSL which uses Javascript as the host language.

ometa SexprParser {
    start      = sexpr*,
    sexpr      = spaces (atom | list),
    atom       = symbol | number,
    list       = "(" sexpr:h sexpr*:t spaces ")"            -> [h].concat(t)
               | "(" sexpr:e spaces ")"                     -> [e]
               | "(" blank ")"                              -> [],
    symbol     = firstAndRest(`letter, `letterOrDigit):s    -> s.join(''),
    digit      = ^digit:d                                   -> d.digitValue(),
    number     = number:n digit:d                           -> (n * 10 + d)
               | digit
}

$> SexprParser.matchAll("""
(print (add 1 2))
(map xarnicate
    (you me TheSussman)
    (100 200 300))
""", `start)

$> [[print, [add, 1, 2]], [map, xarnicate, [you, me, TheSussman], [100, 200, 300]]]

>>3
Thanks, I'll give it a look.

>>4
The generated parser above ended up only being a few dozen lines of code, it's just imperatively specifying a bunch of parse rules/productions which are used to build the underlying state machine at runtime. It inherits most of its functionality from a base class in OMeta/JS library. The library itself looks to be few thousand lines of Javascript which isn't too bad and you can run it in a web browser. I'm just running it from within a V8 shell on the command line.

The cool thing about packrat parsers/pegs is that they unify the lexer, parser, analyzer/optimizer and generator all under the same mechanism, and its easy to chain multiple DSLs/IM processors together that start at a very high-level and output lower-level code such as C or assembly at the final stage.

You can even implement an interpreter. Notice in my SexprParser example, how I'm evaluating the value of integers using the (n * 10 + d) production--you could extend that technique to evaluate all expressions as they're being parsed.

Apparently, the guy who came up with this language used it in a group project where they reimplemented the million LoC Cairo compositing engine using a high-level DSL, and their DSL stack was written using OMeta which generated x86 assembly listings as output. The top-level program and the code for their DSL tool chain was altogether just several LoC, not including the LoC for OMeta itself.

Look here for more if you're interested: http://tinlizzie.org/ometa/