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

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

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