On Dec 7, 2006, at 1:23 PM, Sylvain Schmitz wrote:
Hi Ter, David and all,
Terence Parr wrote:
I started putting this LL(*) description in the upcoming ANTLR v3
book, but decided it was beyond the scope of the reference guide
so here it is in the lookahead blog:
http://www.antlr.org/blog/antlr3/lookahead.tml
Not sure that it is useful to industry or academia because it is
neither practical, nor complete, nor rigorous. ;) Anyway, there
you go.
I'm glad you took the time to describe the LL(*) algorithm in a
more organized fashion. Most of it seems pretty clear, and seems
to work well. I have only a small question on the termination
conditions: you wrote:
It turns out that the set of decisions for which ANTLR timed
out was the same as the set of non-LL(*) decisions for which ANTLR
would
never be able to succeed anyway due to recursion occurring in more
than
one alternative in a single decision.
What is a "recursion occurring in more than one alternative in a
single decision"?
s : e ';'
| e '!'
;
e : '(' e ')'
| INT
;
I cannot see past the recursive e construct with a DFA. That said,
ANTLR creates a really nice DFA--it actually handles the case where e
is INT and (INT) before it giving up. If you add the auto
backtracking, then it will only backtrack when you have ((INT)) or
more nested parentheses.
Does the absence of this recursion guarantee termination in all
cases, or did you keep a threshold for the (seemingly very rare)
undetected nonterminating cases?
Yes. termination is guaranteed without recursion, because there is a
finite amount of work.
On a different subject, David Mercer wrote:
In your last missive, you mentioned that you have had trouble getting
academic interest in your research. I've been meaning to ask ever
since I
read that -- since I am not myself an academic and have little
experience
publishing -- if anyone on this list knows the reason for this.
I can only talk of my own experience on this matter. I am under
the strong impression---after quite a few negative reviews
recommending to submit elsewhere, wherever elsewhere might be---
that the major issue is to find a conference/journal with people
interested in parsing techniques (for programming languages;
natural languages are a different story).
Yep, per my previous e-mail message, the community seems to be very
small. I'm surprised that your work is not accepted, because it
seems very strong theoretically and most of the people in the parsing
community are very theoretical.
Parsing is simply not a very active area of research any more, and
its small academic community does not weight much in the program
committees and editorial boards of the major conferences and
journals out there.
Yup.
As an alternative, Terence, could you take out a patent on it?
Writing a book has the merit of potentially reaching a much larger
public.
Yeah, I am cranking away. I would expect the book to be available
in finished form via pay-for-PDF in mid-February and printed form by
May 2007. :) Books are easy for me to write because I can be much
looser than an academic paper.
Ter
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
