Re: A tricky grammar

We do mention GLR, but Earley can parse your example too:


time flies like an arrow.


<!-- AMBIGUOUS
     The input from line.pos 1.1 to 1.25 can be interpreted as 'sentence' in 3 different ways:
     1: sentence[1.1:]:  command[:1.25] 
     2: sentence[1.1:]:  subject[:1.5] s[:1.6] verb[:1.11] (s, comparison)[:1.25] 
     3: sentence[1.1:]:  subject[:1.11] s[:1.12] verb[:1.16] s[:1.17] object[:1.25] 
-->


<sentence ixml:state="ambiguous" xmlns:ixml="http://invisiblexml.org/NS">
   <command>
      <verb>time</verb>
      <object>
         <noun>flies</noun>
      </object>
      <comparison>like
         <noun>an arrow</noun>
      </comparison>
   </command>
</sentence>


Best wishes,


Steven

On Thursday 17 March 2022 16:37:37 (+01:00), Dimitre Novatchev 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.