Building evaluative dialects


#1

@rgchris asked the question in the rebol chat room “Has anyone written anything on building dialects with some evaluative behaviour?”

Don’t know of a document but it would be useful. Espeically on design considerations.

Some possible evaluation strategies I’ve used:

  • Obviously Parse, but it doesn’t offer much more than recognising tokens. It’s awkward to manage the evaluation.
  • In rowsets.r I wanted a SQL like dialect for series. I selectively bind the SQLish keywords in a block then just DO the block. The keywords when used together with their arguments form a chained expression.
  • In math.reb I used a Top Down Operator Precedence Parser (Pratt Parser). This is the go to example for Pratt parsing. Pratt parsing can be arbitrarily more complex. I think there is a good fit for Pratt parsing in Rebol dialects. However, all the work @hostilefork has put into evaluation in the DO dialect (enfix, etc), takes quite a bit of territory that Pratt parsing covers, so it makes sense to seek to leverage Ren-c’s Do where possible before resorting to Pratt.
  • I have used expression rewriting in a number of places including rewriting parse rules. It’s a good trick to keep up one’s sleeve. Rewrite was written by Gabriele for pattern rewriting blocks, I’ve modified it heavily. Only problem with it is if you’ve rewritten the expression and have an error then reporting back to the user where the error occurred could be a problem (you rewrote it!).

I’ve spent quite a bit of time trying to get varied articles on Pratt parsing so I’m just going to dump them here for posterity:

Top Down Operator Precedence (Vaughan R. Pratt)

Top-Down operator precedence parsing (Eli Bendersky)

Pratt Parsers: Expression Parsing Made Easy (Bob Nystrom)

Top Down Operator Precedence (Douglas Crockford)

A Monadic Pratt Parser (Matthew Manela) - see discussion of someFunction.

A number of good articles by the one author on Pratt (Andy Chu)

Top Down Operator Precedence Parsing in Go (Cristian Dima)

CGOL - An algebraic notation for MACLISP users (Vaughan R. Pratt)


#2

Thanks Brett, no shortage of material here for sure!


#3

Perhaps the links should be here instead of in chat.

https://chat.stackoverflow.com/transcript/message/37872603#37872603