Re: A tricky grammar

Norm Tovey-Walsh writes:

> This grammar (derived from one of the King's College grammars that
> Michael pointed us to; thank you again, Michael):

Thank you very much for exploring them.  (All I did was put them on my
to-look-at list ...)

> S: A .
> A: 'a', B ; 'x' .
> B: 'b', A ; LDOE, A .
> LDOE: M; 'l' .
> M: 'm'; LDOE .

> when presented with this input

> amalx

> Crashes both my parser and Steven's (sorry Steven!). Mine goes into an
> infinite loop trying to work out the ambiguity of the forest. I imagine
> something similar happens to Steven's as it never returns a result.

Wow.  That seems worth exploring.  It was with some trepidation that I
submitted this to Aparecium, but in a couple of seconds it came back with:

      <S xmlns:ixml="http://invisiblexml.org/NS" ixml:state="ambiguous">
        <A>a<B>
            <LDOE>
              <M>m</M>
            </LDOE>
            <A>a<B>
                <LDOE>l</LDOE>
                <A>x</A>
              </B>
            </A>
          </B>
        </A>
      </S>

> I'm not quite sure how this grammar differs from any of the other
> ambiguities in the test suite, but it clearly does.

Hmm.  I wonder if the parse forest grammar might help.  Here is a hand
translation from the XML (given below in case my hands screw up):

  {Parse-forest grammar generated  2022-03-17T15:24:41.163-06:00}
  Goal·0·5 = S·0·5.
  S·0·5 = A·0·5.
  A·0·5 = "a", B·1·5.
  B·1·5 = LDOE·1·2, A·2·5.
  LDOE·1·2 = M·1·2.
  A·2·5 = "a", B·3·5.
  M·1·2 = "m";
          LDOE·1·2.
  B·3·5 = LDOE·3·4, A·4·5.
  LDOE·3·4 = M·3·4;
             "l".
  A·4·5 = "x".
  M·3·4 = LDOE·3·4.

What strikes my eye first here is that there are only two ambiguities --
where a node has two right-hand sides (and is thus ambiguous), I've
written them on different lines.  What strikes my eye second is that
they are both infinite ambiguities because of the LDOE / M loop in the
grammar.

One difference between this and most (all?) of the ambiguity tests in
ixml/tests may be that loop.  But there are similar loops in the
grammars of ixml-tests/tests-straw/wisps/wisps-001-020-catalog.xml, so
if you're passing those and not this, there must be something different.

-Michael

And just in case, here is the XML of the parse-forest grammar.

      <ixml>
        <comment>Parse-forest grammar generated  2022-03-17T15:24:41.163-06:00</comment>
        <rule name="Goal·0·5">
          <alt>
            <nonterminal name="S·0·5"/>
          </alt>
        </rule>
        <rule name="S·0·5">
          <alt>
            <nonterminal name="A·0·5"/>
          </alt>
        </rule>
        <rule name="A·0·5">
          <alt>
            <literal tmark="" string="a"/>
            <nonterminal name="B·1·5"/>
          </alt>
        </rule>
        <rule name="B·1·5">
          <alt>
            <nonterminal name="LDOE·1·2"/>
            <nonterminal name="A·2·5"/>
          </alt>
        </rule>
        <rule name="LDOE·1·2">
          <alt>
            <nonterminal name="M·1·2"/>
          </alt>
        </rule>
        <rule name="A·2·5">
          <alt>
            <literal tmark="" string="a"/>
            <nonterminal name="B·3·5"/>
          </alt>
        </rule>
        <rule name="M·1·2">
          <alt>
            <literal tmark="" string="m"/>
          </alt>
          <alt>
            <nonterminal name="LDOE·1·2"/>
          </alt>
        </rule>
        <rule name="B·3·5">
          <alt>
            <nonterminal name="LDOE·3·4"/>
            <nonterminal name="A·4·5"/>
          </alt>
        </rule>
        <rule name="LDOE·3·4">
          <alt>
            <nonterminal name="M·3·4"/>
          </alt>
          <alt>
            <literal tmark="" string="l"/>
          </alt>
        </rule>
        <rule name="A·4·5">
          <alt>
            <literal tmark="" string="x"/>
          </alt>
        </rule>
        <rule name="M·3·4">
          <alt>
            <nonterminal name="LDOE·3·4"/>
          </alt>
        </rule>
      </ixml>
      
-- 
C. M. Sperberg-McQueen
Black Mesa Technologies LLC
http://blackmesatech.com

Received on Thursday, 17 March 2022 21:39:44 UTC