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

solution@gate.net (Ken Walter)
30 Apr 1996 23:53:20 -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: solution@gate.net (Ken Walter)
Newsgroups: comp.compilers
Date: 30 Apr 1996 23:53:20 -0400
Organization: Solution Technology
References: 96-04-147
Keywords: parse, theory

Michiel Koens <koens@natlab.research.philips.com> writes:
:>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?


I know it was done in a thesis many years ago. A FSM was extracted
(much like a lexical scanner). This was repeated on the resulting
grammar until no more FSMs could be extracted. This usually resulted
in two or three layers to create the equivalent lexical scanner. This
handled floating point numbers and things like "..".


Then the simplest parser was extracted (I don't remember the details)
and repeated. One of the side branches that was explored was to do a
parse from right to left and drop "non-terminal symbols into the
stream. Then the next left to right parse had a "context free
lookahead" when it encounterd the non-terminal. (This was all before
LR(k)).




Ken Walter
--


Post a followup to this message

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