Re: A tricky grammar

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.