Re: A tricky grammar

> New implementations always welcomed, Dimitre! :)

It may well be the case that GLR is much faster (Like just O(N^2) or even
O(N) than Earley's algorithm.

Thanks,
Dimitre


On Thu, Mar 17, 2022 at 8:53 AM Tomos Hillman <yamahito@gmail.com> wrote:

> 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.
>
>
>

-- 
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.