Mailing List Archive


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [tlug] presentation wish list



On 13 October 2014 13:04, Travis Cardwell
<travis.cardwell@example.com> wrote:
>
> These days, I prefer PEG/packrat over LL(n)

For the sake of correctness, ANTLR uses what Terence Parr dubbed LL(*)
which is LL(n) for arbitrary values of n. This uses memoisation to
avoid costly backtracking and for all practical purposes it is
functionally equivalent to PEG.

However, for a discussion of RD parsing it is best to introduce the
concept on the basis of LL(1) then expand from that towards values of
n > 1 and show how this impacts the parsing algorithm and its
complexity as it requires techniques such as memoisation or
backtracking.

There are other techniques that can enhance LL grammars in ways that
would otherwise require more complex grammars such as LR and GLR. For
example, we wanted to use one symbol both as a reserved word and as an
identifier depending on context. Usually this would require a much
more complex grammar but we found a paper for a technique called
"Schroedinger's Token" which allows the decision whether a given token
is one of two (or more) things from the lexer to the parser where the
parser usually has the context information to resolve the ambiguity.
This can be implemented with astonishingly little effort.

>
>> 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.
>
> That does indeed sound like it would be a bit much for one meeting!

Indeed. Thus if there is somebody who likes to do a session on LR
parsing and flex/bison, that would be sufficient material for one
meeting. A presentation covering LL parsing, RD and ANTLR would be
material for another.

Should there be interest and a presenter to go even further, a
presentation covering PEG and packrat would expand on the LL RD/ANTLR
presentation and be material enough for a third meeting.

However, I am not sure whether it is desirable when out of a total of
six technical meetings per year, three of them are about parsing.
There will be folks who are not all that interested in parsing.


Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links