An LALR(1) Dylan Grammar

The Dylan Reference Manual presents the syntax for Dylan as a BNF phrase grammar in Appendix A. The presented version was designed for human readers and not LALR(1) parser generators, so it has a number of conflicts and ambiguities.

dylan-phrases.y is a conflict-free YACC implementation of the Dylan phrase grammar, derived from the presented BNF grammar. It reworked to be free of conflicts and ambiguities, as well as to allow words to serve multiple purposes in the same module -- for example, allowing the same word to be used as both a define word and begin word, as the language requires. I think it is suitable for use in a real implementation of the language.

(On the other hand, ambiguous-dylan-phrases.y is little more than a raw translation of the BNF grammar into YACC; perhaps it's useful for exploration and for purposes of comparison.)

Parsing Dylan requires at least three conceptual layers of processing: lexical analysis (described by the lexical grammar in Appendix A of the DRM), syntactic analysis (the phrase grammar), and macro processing. While lexical analysis of Dylan is easy, macro processing is rather complicated, so do not deceive yourself: writing a Dylan parser is a lot harder than just feeding the grammar I wrote to YACC.


Paul Haahr