Re: An easy-to-miss error

>>>>> In <m2cywp3k6i.fsf@saxonica.com> 
>>>>>	Norm Tovey-Walsh <norm@saxonica.com> wrote:
Norm> [1  <text/plain; utf-8 (quoted-printable)>]
Norm> Good morning.

Norm> Consider the following grammar for an odd little iXML-like language:

Norm>       S = s, alts.
Norm>    alts = alt++(';', s).
Norm>     alt = term**(',', s).
Norm>    term = ('a' ; 'b'), s.
Norm>      -s = (-' '|comment)*.
Norm> comment = -'{', ~[{}]*, -'}'.

Norm> This comes from a unit test. (I can¢t actually recall what I was
Norm> testing, but this was some minimal subset of iXML that demonstrated a
Norm> bug.)

Norm> That¢s not the interesting part. The interesting part is the
Norm> easy-to-overlook error. I¢ll give you a moment to see if you can spot
Norm> it.

I witnessed that given the following input

a, {foo} {bar } b

There are two ambiguous parsing due to how space and comment
are specified.

<S xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous">
   <alts>
      <alt>
         <term>a</term>,<comment>foo</comment>
         <comment>bar </comment>
         <term>b</term>
      </alt>
   </alts>
</S>
<S xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous">
   <alts>
      <alt>
         <term>a</term>,<comment>foo} {bar </comment>
         <term>b</term>
      </alt>
   </alts>
</S>

If the intended fix is applied:

comment = -'{', ~["{}"]*, -'}'.

then the ambiguous parse disappeared.


Norm>                   S P O I L E R  B R E A K

And I didn't see the answer before found the ambiguous parse. So
I consider I won the challenge.
---
ldb

Received on Saturday, 4 November 2023 14:58:38 UTC