Is Ruby grammar context free?

[Peter Suk]

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

 

[B. K. Oxley (binkley)]

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

Ye, gods--it's Perl!


Cheers,
--binkley

 

[Peter Suk]

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

 

[Jon A. Lambert]

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 just noticed it also breaks operator continuation.
Assuming your myfunc returned a string..

This is a syntax error.

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

This is okay.

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

 

[Eric Schwartz]

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.

Actually, the c and d are optional:

X -> S2
X -> a S2 b
X -> a b

and by implication

X -> a^n b^n

I'm not sure how that affects your attempt to replicate heredocs in a
CFG.

-=Eric

 

[Peter Suk]

Actually, the c and d are optional:

No they're not! The whole point is to show that you can have a
language where c is matched with a d, even though it is nested in an
arbitrary number of ab pairs.

--Peter

 

[Nikolai Weibull]

Peter Suk, April 27:

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

C isn't context-free either,
nikolai

 

[Jim Weirich]

I just noticed it also breaks operator continuation.
Assuming your myfunc returned a string..

This is a syntax error.

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

Try this:

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

 

[Jon A. Lambert]

Try this:

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

Oh it is actually consistent then.
It makes even recognition difficult.

Thanks

 

[Eric Schwartz]

No they're not! The whole point is to show that you can have a
language where c is matched with a d, even though it is nested in an
arbitrary number of ab pairs.

Okay, I freely confess to maybe just being pig-ignorant here, but if I
can generate { a^n b^n } from your grammar, and I don't see how that's
precluded from what you said above, then how are c and d required?

-=Eric

 

[Peter Suk]

Okay, I freely confess to maybe just being pig-ignorant here, but if I
can generate { a^n b^n } from your grammar, and I don't see how that's
precluded from what you said above, then how are c and d required?

c is matched with d. If there is no c, there is no d, and vice versa.
But if there is a c, there is a d.

 

[Eric Schwartz]

c is matched with d. If there is no c, there is no d, and vice versa.
But if there is a c, there is a d.

But they're both optional-- you can generate the string 'aa bb' from
your grammar, which is all I was saying. It's probably irrelevant,
but then again, I mentioned that in the first place.

-=Eric

 

[Peter Suk]

But they're both optional-- you can generate the string 'aa bb' from
your grammar, which is all I was saying. It's probably irrelevant,
but then again, I mentioned that in the first place.

Oh, I thought you were saying, it was *only* that language.

--Peter