|
I'm on my way to being able to create parser generators that can parse natural language
I'm using GLR parsing which is a form of LR parsing that uses a non-deterministic approach to running one of the existing LR algorithms (usually LALR(1))
Basically the GLR algorithm uses almost exactly the same tables as the LALR(1) algorithm but it uses with with 1+n stacks instead of 1 stack where n is the number of alternate parses it is finding in the input (GLR can return multiple parse trees for the same input)
Now this is cool. However, my LALR(1) algorithm is clearly broken.
I taught myself how to do it using what I could find on the web, and 90% of it works. The 10% are the blasted epsilon rules. The issue is when I was "taught" LALR(1) by the web it only showed me monotonic grammars - no epsilon rules. Now, any grammar can be converted to monotonic, and it's the approach Chomsky suggests so a lot of eggheads do it that way, and then work on the monotonic form. It's not as practical when making a parser generator though because it significantly changes what the resulting parse tree looks like.
Most (all?) real world algorithms can handle epsilons but since I was only shown how to do this by some undergrads with free time and such I have never learned this.
LALR(1) is very difficult to understand. I understand most of it now, but do i understand enough to modify the algorithm to do what I need?
I hope so. I've been smashing away at it all morning, getting close, but never quite there.
Real programmers use butterflies
|
|
|
|
|
"parse natural language": I'm keen on to see an approach.
I assume you will try it first in english. If you can do it that would be great! The next step will be translate the translation from other languages.
Very cool challenge anyway 
It does not solve my Problem, but it answers my question
modified 19-Jan-21 21:04pm.
|
|
|
|
|
For most natural language constructs it will probably return multiple parse trees because natural language can be ambiguous.
Parsing English involves creating a grammar for it which would be daunting to do in its entirety and probably run the computer out of memory.
But you could do a subset.
Real programmers use butterflies
|
|
|
|
|
English grammar is ridiculously simple, with no more than about 130 rules, which could be learned to perfection in a couple of hours.
Style rules, distinctions of the various ways to phrase things, and idioms, however...
How many centuries can you pencil in to work on it?
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
Right. And if just programmers would learn to write correct programs adhering to all rules, compilers could be ridiculously simple.
But I assume that you meant to be sarcastic.
|
|
|
|
|
Member 7989122 wrote: But I assume that you meant to be sarcastic.
No, English grammar is ridiculously simple, with about 130 rules.
As I said, I believe quite clearly, it's the ridiculous number of non-rules that is the problem -- "non-rules" being idiomatic speech, old sayings/proverbs/etc, and ridiculous "rules" of style that hundreds of people have documented as being That-Which-Must-Be-Obeyed, but which are no more than personal preferences.
Using a computer language well is a piece of piss, by comparison, and the readership is computers, which don't come in a multitude of flavours and levels of understanding -- case in point my having to repeat my perfectly clear statements here.
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
Lots of grammar exceptions, and vocabulary is the real killer.
Real programmers use butterflies
|
|
|
|
|
LALR is not hard at all. The difference between SLR and LALR is that in LALR the context is taken into account in computing the lookahead. Couple of months ago I looked into your code and it seemed to me that you computed SLR rather than LALR.
|
|
|
|
|
I know the difference.
And I disagree that it's not difficult. Were it I could make the comments make sense. =)
Real programmers use butterflies
|
|
|
|
|
According to the person whose website instructed me it's lalr by way of SLR
You compute the SLR itemsets and such then you create an extended grammar out of it and use that to resolve additional look ahead
At least that's what I think i understand of it.
The reason i can (i think?) verify that it's lalr is it generates exactly the same tables as Gold Parser, even for complicated stuff like Javascript grammars - either that or i got lucky.
Oh I have a grammar now that is Lalr(1) but not SLR(1). I should probably try it now that i have it.
Real programmers use butterflies
modified 15-Feb-20 15:17pm.
|
|
|
|
|
honey the codewitch wrote: I'm on my way to being able to create parser generators that can parse natural language
I'd love to see an article on this subject! When I was studying for my MS(CS) degree in the early 80s, I had the good fortune of sitting in a lecture by Naomi Sager @ NYU who worked in the area of natural language parsing. Attendees of the lecture received a copy of her recent book on the grammar of English. I still have it and will have to dig it out to relive the joys of NLP. 
/ravi
|
|
|
|
|
cool!. And yeah if i ever finish it. I'll be honest i'm punching outside my weight class with this project
Real programmers use butterflies
|
|
|
|
|
Natural language parsing has come a long way since the text commands in this game[^], which busied out our PDP-10 for a while when I was in third-year CS.
|
|
|
|
|
But can it run DOOM?
Real programmers use butterflies
|
|
|
|
|
What's DOOM?
I had to look it up. I'll take the original ADVENT, thanks.
I think there's a PDP-10 emulator available online somewhere. When parsing eventually fills you with ennui, porting DOOM would make for quite the article!
|
|
|
|
|
There's a fad of porting doom to smart-appliance and peripheral devices like printers. Also graphing calculators.
"But can it run doom?" is almost an internetism at this point.
Real programmers use butterflies
|
|
|
|
|
A first-person shooter game with hi-res graphics?! 
|
|
|
|
|
Hi-res on PC at the time meant 320x200 8-bit color
On other devices obj they were different
Real programmers use butterflies
|
|
|
|
|
I didn't know which version of DOOM was being ported. But still!
|
|
|
|
|
I'm envisioning DOOM running across a 19.2K RS-232 interface to a VT220 terminal or suitable emulation  .
I'm sure there's someone out there who's done a text-mode version of DOOM.
Software Zen: delete this;
|
|
|
|
|
Contemporaneous with ADVENT on the PDP-10 was a Star Trek game, written by a classmate, for which the interface was a DecWriter (dot-matrix printer/terminal) on which a map would be displayed.
|
|
|
|
|
I played an IBM 370 version of the Colossal Cave Adventure, somewhere around 1981 or so. The various Star Trek text-mode games I played were all MS-DOS BASIC games.
Software Zen: delete this;
|
|
|
|
|
Quote: I played an IBM 370 version of the Colossal Cave Adventure, somewhere around 1981 or so.
Time to relive your youth, Mr Wheeler!
A hollow voice says, "PLUGH".
/ravi
|
|
|
|
|
Now that brings back memories! Clickety
/ravi
|
|
|
|
|
When my hubby and I raid the stores for half priced valentines day chocolate.
It's not really about the money, but about the hunt.
Real programmers use butterflies
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
