Re: [tlug] presentation wish list

[Benjamin Kowarsch <trijezdci@example.com>]

>> Travis Cardwell writes:
>>
>> >   flex & bison
>>
>> I've written a parser-generator in Lisp, but it kinda sucked.  Maybe
>> someday...
>
> Yoshi brought up flex and bison, saying that he would be happy to present.
> If there is interest in the topic, perhaps we could have a parsing-theme
> meeting where different methods of parsing are explored.

Over the last five years I worked on a pet project for which teamed up
with a scholar at a Canadian university to modernise and revise an old
systems programming language that goes all the way back to Xerox PARC
in the early 1970s.

Our aim was to produce a quality language report and specification
first, then build an open source reference compiler front end for LLVM
from the specification.

However, during the design phase in such a project it is desirable to
have an experimental parser to test one's ideas and design.

We therefore tried several lexer and parser generating tools to build
experimental parsers but found that most if not all fail on their
promise of quick and easy prototyping.

There is an immense learning curve with all of these tools. There is
also a steeper learning curve for the underlying parsing method that
bison is using.

In our case, it turned out far less trouble and effort to write a
lexer and parser from scratch by hand using recursive descent.
However, our grammar is rather compact (85 productions in total) which
lends itself to RD parsing. A large language with hundreds of
productions would take significantly more effort and there comes a
point where a parsing tool will safe time despite the learning curve.

Even so, there are other parsing tools that are easier to use than
flex/bison and have other features that are helpful to language
designers/experimenters.

We maintained our grammar in an EBNF notation used by the ANTLR lexer
and parser tool by Terence Parr and we verified the correctness of our
grammar with it before we applied any changes in our specification and
hand coded parser.

ANTLR is open source and it has an optional graphical user interface
called ANTLRworks which is a great tool for visualisation of grammar
rules, their dependencies and any conflicts.

Anyway, I could give a presentation that covers:

(1) the concept of recursive descent parsing
(2) how to craft an LL(n) grammar that can be parsed using RD
(3) how to translate an LL(n) grammar directly into code
(4) how to use ANTLR to visualise and verify a grammar and visualise conflicts
(5) summarise the benefits of LL parsing in general and ANTLR as a
prototyping tool

However, parsing is a fairly complex subject matter. I doubt that it
would be a good idea to cover a presentation for LR parsing and
flex/bison as well as LL parsing and RD/ANTLR on a single day. It is
probably better to do this on two separate meetings.

Anyone who is interested in the work in progress pet project I was
talking about, the language report/specification is available online
and it includes the EBNF grammar and nicely drawn railroad diagrams
at:

https://bitbucket.org/trijezdci/m2r10/downloads/M2R10.2014-01-31.tracked.pdf

ANTLR and ANTLRworks can be found at:

http://www.antlr.org/