Re: Grammars are not Regexps

Tom Hillman writes:

> Looks interesting!

> I await the results with interest.

> In the meantime, if you can share the grammar, I might have time to
> try out the parses in JayParser in the morning (these look short
> enough that they might actually finish parsing!)

I think the challenge Steven has given the other members of the group
is to find a grammar that accepts these as comments, and doesn't accept
... well, ideally I would like to have some negative test cases, too --
otherwise we could just write

    S = ~[]*.

and accept all of the cases.


Michael

> On 3 Feb 2022, 21:06 +0000, Steven Pemberton <steven.pemberton@cwi.nl>, wrote:
>> I was working on some grammars this week, and tripped up a couple of times,
>> getting ambiguous grammars, I think because I was thinking in regexp terms,
>> and grammars are not regexps.
>> The place where this was obvious was with repetition. Regexps are greedy,
>> grammars aren't. So "x"* with a regexp will match a maximal number of x's,
>> but not necessarily with a grammar.
>>
>> I reduced it to a small example in order to work on it more, and I
>> thought maybe some of you would like to try it out too, before I give an
>> example answer. I found it quite instructional.
>>
>> It's Pascal-style comments (XML comments would work similarly), comments
>> surrounded by (* and *).
>>
>> Here is a test set:
>>
>> (**)
>> (***)
>> (****)
>> (*****)
>> (*abc*)
>> (**abc*)
>> (*abc**)
>> (*abc*abc*)
>> (**abc*abc*)
>> (*abc**abc*)
>> (*abc*abc**)
>> (*abc* )(*abc*)
>> (*abc*)(*abc*)
>>
>> (The last line contains two comments; the line before has a space before
>> the first closing bracket).
>>
>> It was trickier than I expected at first, because as I said, although I was
>> parsing the comments OK, the results were ambiguous.
>>
>> Steven
>>


-- 
C. M. Sperberg-McQueen
Black Mesa Technologies LLC
http://blackmesatech.com

Received on Thursday, 3 February 2022 23:15:25 UTC