From: Peter Suk <peter.kwangjun.suk@...>
Date: 2005-04-27T06:26:13+09:00
Subject: Re: Is Ruby grammar context free?

On Apr 26, 2005, at 3:56 PM, Peter Suk wrote:

> Something that came up while discussing Ruby parsing brought this to 
> my attention.
>
>
> "#{print <<foo}"
> This is not context free.
> foo
>
>
> Something like this runs under Ruby 1.8.  I believe this construction 
> is not context free, if the language requires heredoc beginning and 
> ending delimiters to be paired.  (Which Ruby seems to.  It throws a 
> syntax error if I leave out the second foo.)  Note that you can nest 
> the beginning of the heredoc arbitrarily.
>
> I believe that a context free grammar cannot generate a language like 
> this.  I think that a CFG can generate a superset language where the 
> beginning delimiter of a heredoc may appear, but the ending delimiter 
> may never appear.  (But I can't think of a disproof using the pumping 
> lemma for CFG yet.)

Okay, this part is probably context free.  I can come up with a context 
free grammar for something analogous:

	X -> S1 d | S2
	S1 -> a S1 b | c
	S2 -> a S2 b | <empty>

This produces the language { a^n c b^n d } where x ^ n denotes x 
repeated n times.


I may have something for 2nd heredoc construction.

--Peter


--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.