Re: incremental LL(k)-parser

Arnd Russmann writes:


> Request for references on extensions of LL(k)-grammars.


ANTLR 1.10 has both semantic and syntactic predicates where the former
indicates the semantic validity of applying a production and the latter
describes the syntactic validity of applying a production (i.e., specify a
syntactic structure that must be visible on the input stream for a
production to be attempted).


The semantic predicates allow you to specify ambiguous CFGs and then to
disambiguate them with semantics such as the old Fortran array ref versus
function call ambiguity (only the symbol table can differentiate them).


Syntactic predicates provide a form of selective nondeterminism or
backtracking. For example, in C++, statements can be recognized via:


stat : ( declaration )? declaration
          | expression
          ;


or in short form:


stat : ( declaration )?
          | expression
          ;


which indicates that the construct defies LL(k) analysis and the parser
should (at run time) simply see if a declaration is visible. This is well
known to be powerful (==CFLs), but terribly expensive in the worst case
runtime (although ANTLR parsers are mostly deterministic and the user
indicates when to backtrack--leading to very good performance).


> especially on those dealing with incremental parser generation.


I'm thinking about making a version of ANTLR that dumps the user's grammar
in some form to the output C file and then tries to do lookahead analysis
at parse time.


You might want to look at the following paper in TOPLAS that dealt with
computing LR(k) parse tables at parse time:


.IP [ADG91] 10n
M. Ancona, G. Dodero, V. Gianuzzi, and M. Morgavi, \*QEfficient
Construction of $LR(k)$ States and Tables,\*U ACM TOPLAS Vol. 13, No.
1, January 1991, pp 150-178.


Terence Parr
U of MN
--

Return to the comp.compilers page.
Search the comp.compilers archives again.