Home » forums » LtU Forum

An "adaptive" LALR(1) parser I've been toying with

Hello LtUers,

I've been toying with this little project during my daily commute (only today learning that it's an area that's been explored off and on since the 60s under the name "adaptive parsers" -- I'll have to update the readme):

https://github.com/kthielen/ww

Some things that I think are interesting about this experiment are:

* lexing/parsing are handled by the same underlying LALR(1) parser-generator algorithm
* the active lexer/parser are dynamically determined (reading input can affect the grammar being used)
* lexemes and "non-terminals" have associated types (and named binding syntax rather than $0,$1,...)
* lexers/parsers are constructed incrementally, so it's easy to point to the first rule that introduces ambiguity (and "nice" error messages are split out to illustrate where these conflicts come from)

The basic idea here is that you feed this thing some basic axioms (your primitive functions, which can be used in subsequent lexer/parser reductions), then you can feed it input to parse and/or extend the syntax of what can be parsed. I have been thinking about using this to allow syntax extension in modules supported by a compiler I've been working on. A simple (working) example from the project page:


syntax lexeme w = '//[^\n]*\n' -> null.

// now that we can write comments -- extend this grammar to accept arithmetic expressions
syntax {
  assocl p.
  lexeme p = "+".

  assocl t before p.
  lexeme t = "*".

  assocl e before t.
  lexeme e = "^".

  lexeme int = x:'[0-9]+' -> toInt x.
  rule expr = x:int -> x.
  rule expr = x:expr p y:expr -> plus x y.
  rule expr = x:expr t y:expr -> times x y.
  rule expr = x:expr e y:expr -> power x y.
  rule statement = e:expr -> e.
}

// with that out of the way, let us now do a little arithmetic
1 + 3^2*2

FWIW, I'm not working in an academic setting, just your average compiler project in a large non-technology company. I'm curious to know if others have thoughts/warnings about this approach, or maybe interesting recent research/discussions I should read (I did turn up this old thread from several years back).

By Kalani at 2013-10-09 19:35 | LtU Forum | previous forum topic | next forum topic | other blogs | 3965 reads