From: Peter Suk <peter.kwangjun.suk@...>
Date: 2005-04-27T05:56:18+09:00
Subject: Is Ruby grammar context free?

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

Also, from the Ruby 1.4 docs, it would appear that heredoc can be 
interleaved.  This also seems like it breaks Context Free.



def myfunc(this, num, that)
         print this
         print num
         print that
end

myfunc(<<"THIS", 23, <<'THAT')
Here's a line
or two.
THIS
and here's another.
THAT



--Peter


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