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

parrt@lonewolf.parr-research.com (Terence John Parr)
10 May 1996 01:44:33 -0400

          From comp.compilers

Related articles
splitting grammars in LL / LR / Backtrack / ... koens@natlab.research.philips.com (Michiel Koens) (1996-04-29)
Re: splitting grammars in LL / LR / Backtrack / ... solution@gate.net (1996-04-30)
Re: splitting grammars in LL / LR / Backtrack / ... k3is@unb.ca (1996-04-30)
Re: splitting grammars in LL / LR / Backtrack / ... clark@zk3.dec.com (Chris Clark USG) (1996-05-01)
Re: splitting grammars in LL / LR / Backtrack / ... dodd@csl.sri.com (1996-05-01)
Re: splitting grammars in LL / LR / Backtrack / ... parrt@lonewolf.parr-research.com (1996-05-10)
Re: splitting grammars in LL / LR / Backtrack / ... jlilley@ix.netcom.com (1996-05-19)
| List of all articles for this month |

From: parrt@lonewolf.parr-research.com (Terence John Parr)
Newsgroups: comp.compilers
Date: 10 May 1996 01:44:33 -0400
Organization: Compilers Central
References: 96-04-147
Keywords: parse, tools

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
--


Post a followup to this message

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