Subj : Re: Parsing regular languages
To   : comp.programming
From : Omri Barel
Date : Thu Aug 04 2005 05:59 pm

Flavius Vespasianus wrote:
> Omri Barel <spammer@p2z.com> wrote in news:brbIe.87498$Pf3.36361
> @fe2.news.blueyonder.co.uk:
> 
> 
>>However, what happens if I have something that looks like a context free 
>>grammar, but the language it describes is regular? In my case it's even 
>>easier - the grammar is not recursive. So I have something like:
> 
> Done all the time
> 
>>As you can see, I can simply expand the entire thing, because it's not 
>>recursive:
>>Note that although there's no left-recursion problem (it's not 
>>recursive), I'm trying to avoid any left-factoring, due to memory 
>>requirements and processing time. So, if my grammar is:
> 
> 
> Right recursion causes more wasted memory in an LR parser. LL parsers can't 
> handle it.

I'm not sure I follow. You say "Done all the time". Does that mean you 
have an efficient algorithm to parse regular grammars given as 
context-free grammars without transforming the grammar or using too much 
memory?

Also, you say that right recursion causes wasted memory in an LR parser, 
and that LL parsers can't handle it. I wasn't talking about recursive 
grammars. I said that the grammar is not recursive. However, if it *is* 
right recursive, an LL parser can definitely handle it.

I'd appreciate any references or links to an algorithm that can do it. 
Thanks.

.