Re: splitting grammars in LL / LR / Backtrack / ...

On 04/29/96, Michiel Koens wrote:
> I wonder if it is possible to split a grammar into seperately parsable
> parts to 'isolate' the parts that are not parsable with an LL(1) or
> LR(1) parser. This way, a parse-function could parse a grammar mainly
> using a cheap parsing strategy and call more general (=expensive)
> parse-functions only for those parts that need the more general
> techniques. Are there any tools for this?


If you're asking if there is a tool that uses a cheap parsing strategy
unless it runs into something complicated, the answer is yes: ANTLR (the
parser generator of PCCTS). ANTLR uses LL(1) where it can. If the
decision is not LL(1), it tries LL(k>1) up to some user-defined
maximum. Failing that, the tool looks for semantic predicates to
see if semantic information is enough to resolve the nondeterminism.
If it still is not deterministic, the programmer can specify a
syntactic predicate--selective backtracking. For example,


stat : (declaration)?
          | expression
          ;


says "if it looks like a declaration, it is; else it's an expression."
This resolves an infamous grammatical ambiguity of C++:


T (*g); // is this a function-style type cast of *g to T?
T (*g); // or, is this a decl of g to a pointer to T?


> I know that several tools generate C or C++ functions that parse a
> part of a grammar and that different tools use different parse
> strategies, but probably functions generated by different tools are
> hard to combine. Does anyone know more about this? Or are there any
> helpful links to pages/articles/books?


See ftp.parr-research.com in pub/pccts/*
and http://www.igs.net/~mtr/software-development/pccts.htm


Best regards,
Terence
--

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