Re: A tricky grammar

Looks like GLR is already explicitly mentioned as a known algorithm that could be used for an iXML parser: see the list at the end of the "conformance of processors" section of the spec: https://invisiblexml.org/ixml-specification.html#processorconformance

New implementations always welcomed, Dimitre! :)

Thanks,
Tom
On 17 Mar 2022, 15:39 +0000, Dimitre Novatchev <dnovatchev@gmail.com>, wrote:
> Hi Norm,
>
> Sorry to interrupt your group's discussions and probably show lack of understanding.
>
> But 30 years ago I had a post-doc scholarship with Masaru Tomita at CMU and at that time implemented in C his algorithm for NL parsing -- GLR (Generalized LR Parsing).
>
> This parsing algorithm can handle any NL grammar ambiguities, it even produced all possible parses for "Time flies like an arrow", and one of these interpreted "time-flies" as the subject. So, "time-flies" like (love) an arrow :)
>
> Maybe you could consider implementing and using Tomita's GLR?
>
> https://en.wikipedia.org/wiki/GLR_parser
>
> https://www.barnesandnoble.com/w/generalized-lr-parsing-masaru-tomita/1117273215
>
> Thanks,
> Dimitre
>
>
> > On Thu, Mar 17, 2022 at 7:48 AM Norm Tovey-Walsh <norm@saxonica.com> wrote:
> > > Hello,
> > >
> > > [ GitHub seems to be borked at the moment, so I’m sending this to the
> > >   list instead. I’ll make an issue and test in the test suite for it
> > >   when (a) GitHub is back and (b) I have a spare moment. ]
> > >
> > > This grammar (derived from one of the King's College grammars that
> > > Michael pointed us to; thank you again, Michael):
> > >
> > > 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.
> > >
> > > I'm not quite sure how this grammar differs from any of the other
> > > ambiguities in the test suite, but it clearly does.
> > >
> > >                                         Be seeing you,
> > >                                           norm
> > >
> > > --
> > > Norm Tovey-Walsh
> > > Saxonica
>
>
> --
> Cheers,
> Dimitre Novatchev
> ---------------------------------------
> Truly great madness cannot be achieved without significant intelligence.
> ---------------------------------------
> To invent, you need a good imagination and a pile of junk
> -------------------------------------
> Never fight an inanimate object
> -------------------------------------
> To avoid situations in which you might make mistakes may be the
> biggest mistake of all
> ------------------------------------
> Quality means doing it right when no one is looking.
> -------------------------------------
> You've achieved success in your field when you don't know whether what you're doing is work or play
> -------------------------------------
> To achieve the impossible dream, try going to sleep.
> -------------------------------------
> Facts do not cease to exist because they are ignored.
> -------------------------------------
> Typing monkeys will write all Shakespeare's works in 200yrs.Will they write all patents, too? :)
> -------------------------------------
> Sanity is madness put to good use.
> -------------------------------------
> I finally figured out the only reason to be alive is to enjoy it.
>

Received on Thursday, 17 March 2022 15:53:19 UTC