[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Is Ruby grammar context free?

Peter Suk

4/26/2005 8:56:00 PM

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.
12 Answers

B. K. Oxley (binkley)

4/26/2005 9:00:00 PM

0

Peter Suk wrote:
> 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

4/26/2005 9:26:00 PM

0

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.

Jon A. Lambert

4/26/2005 9:27:00 PM

0

Peter Suk wrote:
> 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

4/26/2005 9:41:00 PM

0

Peter Suk <peter.kwangjun.suk@mac.com> writes:
> 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
--
Come to think of it, there are already a million monkeys on a million
typewriters, and Usenet is NOTHING like Shakespeare.
-- Blair Houghton.

Peter Suk

4/26/2005 10:19:00 PM

0


On Apr 26, 2005, at 4:44 PM, Eric Schwartz wrote:

> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>> 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:

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

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

Nikolai Weibull

4/26/2005 10:41:00 PM

0

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

--
Nikolai Weibull: now available free of charge at http:/...!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

Jim Weirich

4/27/2005 2:50:00 AM

0

On Tuesday 26 April 2005 05:26 pm, Jon A. Lambert wrote:
> 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"

--
-- Jim Weirich jim@weirichhouse.org http://onest...
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

Jon A. Lambert

4/27/2005 7:21:00 AM

0

Jim Weirich wrote:
> On Tuesday 26 April 2005 05:26 pm, Jon A. Lambert wrote:
>> I just noticed it also breaks operator continuation.
> 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

--
J. Lambert

Eric Schwartz

4/27/2005 4:56:00 PM

0

Peter Suk <peter.kwangjun.suk@mac.com> writes:
> On Apr 26, 2005, at 4:44 PM, Eric Schwartz wrote:
>> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>>> 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:
>
> 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
--
Come to think of it, there are already a million monkeys on a million
typewriters, and Usenet is NOTHING like Shakespeare.
-- Blair Houghton.

Peter Suk

4/27/2005 6:43:00 PM

0


On Apr 27, 2005, at 12:04 PM, Eric Schwartz wrote:

> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>> On Apr 26, 2005, at 4:44 PM, Eric Schwartz wrote:
>>> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>>>> 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:
>>
>> 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?

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.

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