This post by Gary caught my attention and I thought I’d reply to it in a less hostile environment than its original thread.

Gary Dubuque - Jul 28, 2011:

What you don’t get yet is the human’s need to be aware of what each other’s thoughts are.  So much so that we project thoughts into animals just by observing their behavior.  Like parrots (dogs for you) can talk and listen to our words. What a conversation they have. Intelligence is an artifact of that modelling in our mind of what is happening in some else’s mind.  And to have a mind is…  (hint: it is not a game or a player or creature in a game)

(emphasis mine)

I really like this idea, Gary. But isn’t modelling the mind of another person one facet of “predictive” behavior? We also attempt to model the behavior of inanimate objects. The fact that we anthropomorphize them in the process says something about the importance of social interaction to humans.

But what of solitary animals? To what degree do they exhibit intelligence? When a cheetah picks its prey and chooses the moment to pursue, how much of this is guided by prediction based on previous experience? How much on instinct?

How does this compare with social animals? Domesticated animals, bred specifically for their ability to interact with humans and read human communication cues? Any thoughts, references, anecdotes?

It’s early days yet, but there does seem to be mounting evidence that animals communicate among themselves far more than we previously gave them credit for. Young cheetahs spend a great deal of time engaged in play activities that prepare them for hunting, and they also receive guidance from their elders.

We only have to look at the lack of capabilities of individuals raised in isolation, whether it is a tame lion in a zoo, or a feral human in the jungle, to see how little individuals can do without the experience of previous generations to draw on.

I’ve formed the opinion that it is not humans that are intelligent, however you care to define that, but our civilization as a whole that is intelligent. The same goes for other species and I think that in time we will come to realise that we are surrounded by intelligence, but have not had the depth of understanding to realise it.

After all, isn’t it to our shame that only a few generations ago there were many white men who thought that non-white men, and women of any race, were their intellectual inferior? I think we still have a lot to learn before we are free of such chauvinism on both the intra- and inter-species levels.

Andrew Smith - Jul 28, 2011:

It’s early days yet, but there does seem to be mounting evidence that animals communicate among themselves far more than we previously gave them credit for. Young cheetahs spend a great deal of time engaged in play activities that prepare them for hunting, and they also receive guidance from their elders.

It seems to me one could do a field study and record how young predators improve their success rate. (In fact, I’m sure it’s been done.) The reason this case interests me particularly is that most predators are solitary animals. Therefore one might suppose they have little reason to develop traits we normally associate with social animals. Watching the behavior of others. Trying to determine their mood. Trying to influence their behavior. But then, perhaps it might be useful to develop these traits to improve hunting? Or perhaps this is unnecessary.

If our interest in predicting outcomes of events is really a bi-product of having some sort of theory of mind, then this would have powerful implications in terms of animal intelligence. But then again, perhaps I’m putting the cart before the horse. One could easily imagine that social intelligence derived from a more general interest in predicting the behavior of our environment.

Andrew Smith - Jul 28, 2011:

We only have to look at the lack of capabilities of individuals raised in isolation, whether it is a tame lion in a zoo, or a feral human in the jungle, to see how little individuals can do without the experience of previous generations to draw on.

So true! I find it very telling that humans raised without language up to a certain age will never develop the capacity fully. And members of cultures that do not have counting terms beyond “1, 2, 3, many” have difficulty in understanding quantity. This must be true for a wide variety of neural function, both cognitive and otherwise. Heck, a baby that is prevented from using one eye at birth can also become permanently blind in that eye.

Makes you wonder about the driving force behind brain evolution. A jump in brain capacity will never result in a sudden jump in mental capability. The “extra” capacity will just be trimmed away during early childhood development. It is all in the way that our environment (including other humans) prods our brain into usefulness.

And yet conversely, that capacity must have increased significantly in our evolutionary past because even our closest relations (chimps, bonobos, and the like) cannot be prodded to anything like a human level of intelligence. Perhaps our brains are a product of nature and environment, tugging eachother along?

Andrew Smith - Jul 28, 2011:

I’ve formed the opinion that it is not humans that are intelligent, however you care to define that, but our civilization as a whole that is intelligent. The same goes for other species and I think that in time we will come to realise that we are surrounded by intelligence, but have not had the depth of understanding to realise it.

Definitely true. The ability of apes/dogs/etc. to pick up on language and develop a library of signs or words that they can interpret is impressive. But they need that supportive environment. (I wonder if anyone has counted the number of “signals” wild wolves or lions, for instance, use to communicate amongst themselves in the wild? And whether any of these signals could be regarded as representative of a concrete object? I imagine none of the latter.)

This can be taken too far however. I saw a preview for a new documentary, Project Nim, that describes an experiment in the 1970’s to raise a chimp as a human child. You can imagine how well that went.

The important takeaway, I think, is that not only do animals have varying levels of intellect, but they have varying types as well. And directed towards varying objectives. One thing Project Nim taught researchers was that although Nim could learn to sign many complex things, he only seemed to use this tool towards one end—getting things he wanted. No conversation for the sake of conversation, as you’d find among humans.

Makes me think the place we should look closest to consider the nature of human intelligence is at autism spectrum individuals. Here you have a group of people with brains functioning at the same—or even more advanced—level as everyone else, except in specific domains like social acuity. What happens to our intellectual whole when you change one/more parts of our behavior? Then again, maybe the answer says more about which aspects of intelligence we value most.

Andrew Smith - Jul 28, 2011:

After all, isn’t it to our shame that only a few generations ago there were many white men who thought that non-white men, and women of any race, were their intellectual inferior? I think we still have a lot to learn before we are free of such chauvinism on both the intra- and inter-species levels.

We’ll get over these prejudices just in time to have the machines lament about humans treating them as intellectually inferior. It never ends.

Studying the humble ant supports the assertions that we are definitely surrounded by intelligence. Not only “in proportion to their size” do they have the largest brain, they have been achieving feats of construction that are quite advance when compared to humans.

For instance an ant nest is a city numbering thousands of occupants, that again if extrapolated to human size would measure kilometers of levels , containing designed and fit for purpose constructions,  air vents, nurseries, food farming (use of fungi) ,birthing chamber for the queen ant , military control and specialized defense mechanisms - all of which is controlled through a language.

Possibly our first steps in creating intelligence we need to celebrate and understand the ‘type’ of intelligence we want to create, and that these may be presented in some type of ontology.

It seems all thinkers here are looking for the meaning of intelligence, it seems to me like to be seeking the holy grail of intelligence itself. Let me try to make some reflection upon this subject.

We are capable of making machines, indeed: very complex ones like computers, this is not new our ancient brothers were able to do many complex stuff too, may be not as complex as today’s hardware and software engineering but close enough to overkill a single normal human mind trying to figure all those crap by himself, alone. So our tech capabilities are collective, not merely individually-human but collectively-social; as we are an advanced technological society by definition.

This machines, (at least the ones we call intelligent) tends to exhibit some behavior, specially bots ans computers when dealing with human-language, this may be happening because our language is a good vehicle to persist and communicate our capabilities and ideas, formerly our collective intelligence. Meanwhile I conclude all the human intelligence is actually sleeping “serialized” by means of a complex language, not only natural but with graphs, pictures and diagrams, as all the books and articles we are used to read during our lifespan, but it needs a trained human to be read and interpreted. This comes as an evidence when the archaeologists find lost cultures and have no clue on reading their scripts and graphics, like the Mayas or older geometric-iconic Sumerian languages, decrypted thanks to the Rosetta Stone (a paralell translated text)

Having given all this hints, and going towards the chatbot’s intelligence evaluation I conclude we are ‘trying’ to make a machine which appearance is to be a smart-ass, but internally it has not a clue on what is happening. The Turing test is exactly such a test, a human’s judges fooling test. ¿Are we measuring intelligence? - In my opinion: no! (we are just measuring the intelligence of the programmer who built a engine capable of fooling the biggest number of judges!

On the point if we ever would get a strong AI being self-aware, and creating stuff like a human, may be! but not until many of the secrets of how our brains (and even the animal ones) figure out and organize themselves to solve strategies to get some thing, to communicate, to have emotions, to collaborate, etc.

Many people are crying tor the moment this will happen, calling it “The Singularity”, I conclude they smoked too much tech-pod. I think all this will evolve like all science, many discoveries here and there will co-operate and build better blocks, and so on, until there will exist semi-smart-ass bots, who will understand (mimic intelligence) very well. Even they will solve many things we actually don’t, because of the faster speed and calculus power, but again, only may be… because the modelling of deductions is not solved actually.

There exist many math and logic theories, from strictly Boolean to Zadeh’s Fuzzy logic, many are appropriate for calculus, modelling and even engine-control but they cannot cope actually with diffuse thinking, and lateral intelligence, may be some new logic operation and schema needs to be discovered… Well here I have reached my point!

My Actual Research Direction
I think there is a ‘different’ kind of operation happening inside our self-organized intelligent minds, which needs to be modeled and simulated, a new kind of representation, difficult to be expressed by means of simple bool logic, or numbers, may be with a combination of both and a little magic from math it will be possible.
This models are actually being built by me, they are still very simple, and involves many hard-coded solutions and many not-so hard coded ones (deducted) but deducted based in the model, not programmed as a if-then-else logic but as a competition, trying to maximize abstract measures, like benefit and loss, or happiness an grief, I am using simple measurements, represented by simple feelings as the guidance for all cognitive processes, even justice is a feeling, inside our brains, the beauty of math or the awkwardness of evil, its all chemical stimulus.

A very interesting theory in sentiment analysis and modelling is the Plutchick’s theory of emotional interrelation, I’ve modeled it as software and are actually using those outcomes as a guidance on the bot’s behavior. - Again only trying to imitate human behavior.

This is (as I think) the direction of my work, actually, and the main ideas are very simple, I am trying to make a simple.. very-simple script, capable of figuring out things on his own, to deduct simple things, modeled only by natural stimulus of self-benefit (or social benefit).

The programming behind this stuff is huge and complex, because I try to model all the perceptions at once: deictic dialog-positions, rooting, ellipsis, anaphora and co-references must be reasonably solved, there must be some kind of common sense and a good representation of the world (in an intelligent way). there is no semantic notation I’ve seen as all the Grammar crap (POS etc.) and semantic is more powerful than grammar.

The last effort (which is now starting to function) involves a simple idea-construction prototype, in which the bot, may construct a complete sens-full sentence, based on many ‘blind’ parts collected during the dialog-act turns, like the following:

user: eat
bot: eat what, and when?
user: tomorrow, here
bot: who?
user: me
bot: what will you eat tomorrow?
user: stones
bot: stones are not edibles, are you joking?
user: yes
bot: ha ha!, but what are you going to eat tomorow?
user: vegetables
bot: ok!

This conversation is fake, but states in English what I am trying to build, or program.

Actually it works (part of it) in Spanish, where the deixis and verb-tenses and inflection are really very complicated (much more than English).

Even this (actually working) stupid routine, handles a verb in infinitive and a particle stating time like “eat” “tomorrow” and the system says correctly ¿what are you willing to eat? (again, in Spanish)
I other words the parser is robust enough to handle an idea and assemble it with multiple passes, even correcting and trying to get the best ‘emotional-score’ out of the final result.

- so here I stop, have to go to dinner!

Bye! for today!

@Andy, are you using your own discourse representation theory (DRT), or are you modifying something like Penn or SDRT/USDRT, or even a semantic version of RST?  I’m just curious.

@C R, I bet you’ve definitely got your own representational language.  How are those symbols going to associate to animals who don’t use symbols to think, but instead “sign to get what they want?”

I vaguely remember hearing about Ayurvedic which suggests knowledge of all human diseases and cures.  5,000 years ago those doctors were concerned that gathering together into communities would bring illness and might become the end of humans.  It upsets the balance of nature.  We have lost the Ayurvedic knowledge and don’t know how to cure all illness anymore.  But we think we are more intelligent and our science is far more advanced.  Even today, what little bits of the knowledge that is left through the broken and damage scripture can cure cancer (scripture was difficult for the culture of Ayurvedic to use, part of the loss of those ancients.)  Like acupuncture, it is hard for the modern world to understand.

Wandering around the internet just now I came across a Wikipedia page about the Analysis of Subjective Logics and it contained the following

Brunetto Latini wrote in the Middle Ages (The Book of Treasure): « Tullius [Marcus Tullius Cicero] said that the highest science of city governing is rhetorics, that is the science of speech ; because if speech did not exist, neither would city exist nor any establishment of justice or of human company ».

Still a dog pack has a sense of justice by establishing the pack leader.  An bee hive has their hierarchy.  I wonder how swarming works…

And I wonder if human justice can be in harmony and balance with nature.

Gary Dubuque - Jul 30, 2011:

@Andy, are you using your own discourse representation theory (DRT), or are you modifying something like Penn or SDRT/USDRT, or even a semantic version of RST?  I’m just curious.
....

@Gary
Not quite exactly, the DRT/SDRT/USDRT and RST are hard theories and they are all linguistically shaped, and well-defined, but there is not much evidence provided to be programmable or detectable by programming, because fulfillment and entailment of inter segmental components is not even clearly defined in any arena (not grammatic nor semantic) They use Tree Adjoining Grammars (TAG) and other eccentricities, for which parsing is not well defined (or even possible), and there are little or even no parsing structure available, only some statistics exists.

My approach is much more simple and even holds as robust (I guess)

I designed a pattern system, much like empty slots. Each one holds a piece of information and there is a semantic+syntactical relation among each part, which also need or claim to be fulfilled.

Each part has a fuzzy-based logic associated, and each part also knows how to claim for fulfillment (even knows how to ask, using all the available information on other slots to compose the query). The compete and the best set, wins, composing the need.

Then the dialog-turn analyzer sees if there is appropriate to make a claim or ask for fulfillment, and takes the decision. Even if the answer renders only a part of the query, this part is fit to the sets, and may be replace for a better scored position, because also a shallow common sense method is evaluated at each scoring fit.

All this sounds complicated, but is exactly how I think it may work in humans heads, so I just are trying to re-create this model and try it out, to see how good or bad it behaves.

And for now I am fully satisfied, the preliminary test gave a good answer schema, the only think not working now is the Turn-Taking analysis, I put a hard value each time, to do the tests (like using mocking objects) because without this I could probably not test each part alone and get results.

The whole sounds like very simple and thus silly, even too simple to work, but I was surprised to see how a simple system turned out very robust and may understand a ill-shaped conversation and even get sense out of nowhere, also composing good natural language for the fulfillment queries (again in Spanish, which is far more difficult than English, sorry for who don’t know why, its a long story..).

Again I had to hard-wire a lot to get some decent verb-flextions because the bot had to infer many elements like the person, the tense, the mode, the gender, the number, the deixis and rooting, etc.

I am plainly satisfied with the outcome, and are planning to incorporate this “silly-pattern-routines-matcher” as a full flagged pattern matching system alternating/competing against the AIML-like pattern matcher and compiler I’ve built into my chatbot framework. As I guess, this black boxes, will for sure give a new kind of behavior to a conversational system, because it may be able to compose a broken conversational intent by re-asking needed parts to get sense out of the user’s intention and then do a correct query against whatever internal information it may have to render to the user, as a query-answer system. all this will happen without directed script intervention (pre-programming)

So put in simple words: You set-up the patterns-types the bot can handle (the queries he may understand), the bot sees if some of them are fulfill-able on each turn, the pattern which has more common sense and fitting-score wins on each round and conduces the re-questioning schema until success or total disappointment, as simple as this!

¿did you understand? (may be my English is not the best.. but I do what I can..)

By fortuitous coincidence I spent the last few days working on this very problem, specifically discourse analysis and sentence splitting. I finally got my GLR parser software working earlier this week (it only took me four years), and I’ve been testing it out by trying to develop a Context Free Grammar in Chomsky Normal Form.

It’s looking really good so far, though it is really just a hint of what will be possible with this approach.

Here’s the grammar definition file: http://asmith.id.au/files/eng.grammar
Here’s the original test input file: http://asmith.id.au/files/the-country-of-the-blind.text
Here’s the marked up output file: http://asmith.id.au/files/the-country-of-the-blind.xml

Some of the productions in the grammar are a little bit hard-coded at the moment, but once I’ve broadened the regression test suite to include many more types of document, I’ll be able to determine what rules to add or modify.

@“C R Hunt”

After reading the short-story that I’ve been using for testing my parsing software, I figured out why Nim didn’t bother talking socially with his human carers: he didn’t think they were intelligent enough to warrant the effort.

Many of us have dogs and know that they are intelligent enough to obey commands and do what they’re told, but I don’t know of anyone who tries to talk about politics with their canine friends. I’ve also noticed that my dogs don’t bother trying to talk to me unless they want something, though they are obviously able to talk to each other on some level.

@Andy, so for creating behavior in your system, you’ll be able to use the pattern types triggered when they are filled in with enough data to make sense.  And I’m guessing you can tie the various types together to build a tree or graph or something like that to support the variations on anaphora and co-referencings so you’ll be able to identify topic and context changes. It’s the behavior between understanding what the discourse is about and what the language generator needs to plan and then realize that fascinates me.  That’s the intelligent behavior?

@Andrew, cool slicing and dicing.  This is neat for story parsing.  My system only finds the sentences so far.  Yours is better.  How now are all these going to be annotated for syntax and semantics? One DRT I’ve run across lately is Penn (PDT) (too expensive to acquire for my shoe string budget - it’s a million word corpus annotated) and I also found a PDF on asking why questions against the tree (that what they call the annotations I guess.)  Are you aiming at using the output xml, after the sentences are parsed, for a reasoning engine?  How does it do intelligent behavior?

When I first encountered a system like AIML, I longed for it to have more behavior than just responding by processing a small template for each input.  With my years of building expert system shells, I decided to add some calculation power into the mix.  Now I have some of that available in my toy.  I am confronted with the huge task of translating many patterns into the “facts” used by the reasoning engine, what the engine should do with those facts, and finally what to pick from what is reasoned for the bot to say.

Folks have talked about goals.  People have goals.  They use goals in conversation.  Perhaps this is the theory of dialog management, since it defines rules to make moves or set goals.  It works ok when a clear business purpose is involved like booking an airplane flight.  Goals for an open discussion shrink to nothing after the other person’s identity has been established.  You could easily have a grab bag full of possible (intelligent) directions for the bot to seek and randomly pick one (unless someone stumbles into a situation that matches a goal) for all that matters.  This is another way of saying the bot has gamuts to play, a la, ChatScript.  That’s where the intelligent behavior leaves me.  Spinning the wheel to talk about something just doesn’t feel like the bot is being intelligent.  That’s not how I see nature working, although evolution could suggest there is a lot of playing with dice in nature.  So is the goal to model the “mind” of the person with whom the bot converses?

Gary Dubuque - Jul 31, 2011:

Are you aiming at using the output xml, after the sentences are parsed, for a reasoning engine?  How does it do intelligent behavior?

The parser driver is implemented as a GNU/C library and you use it much like you would use flex or bison. It is thread safe and you can have parsers for as many different grammars as you like in the one program. Just write the grammar, generate the oracle, compile and link it all together. I’ve written a shell for testing and development and I run that from the Linux command line.

The oracle generator is written in CommonLisp but I hope to write a C version of that as well. As it only took two weeks to do in CommonLisp, I’m confident that I could have the C version up and running by the end of the year if I start working on it right now.

Parsing text is as simple as calling a C function with pointers to a block of text and an oracle. It returns a data structure (parse graph) which can be used directly by the calling C code, or it can print it to a stream as XML. The library is also capable of producing a diagram as SVG (scalable vector graphics), though that is only useful for very simple parses. I’ve posted some example diagrams in my Google+ stream if you want to take a look at that.

Here are links to the generated oracle source files from the grammar definition that I posted earlier. They probably won’t mean much unless you are already very familiar with compiler software, but they will give you an idea of what’s involved.

http://asmith.id.au/files/eng-tables.c
http://asmith.id.au/files/eng-header.h

It’s just a parser, albeit a very powerful one: it doesn’t do “intelligent behaviour” yet.

@Andrew

Andrew Smith - Jul 31, 2011:

By fortuitous coincidence I spent the last few days working on this very problem, specifically discourse analysis and sentence splitting. I finally got my GLR parser software working earlier this week (it only took me four years), and I’ve been testing it out by trying to develop a Context Free Grammar in Chomsky Normal Form.

It’s looking really good so far, though it is really just a hint of what will be possible with this approach.

Here’s the grammar definition file: http://asmith.id.au/files/eng.grammar
Here’s the original test input file: http://asmith.id.au/files/the-country-of-the-blind.text
Here’s the marked up output file: http://asmith.id.au/files/the-country-of-the-blind.xml

Some of the productions in the grammar are a little bit hard-coded at the moment, but once I’ve broadened the regression test suite to include many more types of document, I’ll be able to determine what rules to add or modify.

Congratulations! I see you and me have got several points in common for a bot analysis, this is not uncommon due we all humans, under similar circumstances do think in similar ways!

I’ve got cached by some doubts/questions:
1) About the parser specification: does it includes character recognitions (seems it has no scanner?)
2) About the multiple parse-tree output, is each output weighted in some way?
3) Have you tried Elkhound/Bison or other GNU parser? I’ve got no one of those to work fine for me, also I work in C# so my target is more restricted, so I’ve got to write my own one…

Curious and coinciding, I’ve spent also a long time and some resources and finally got my own GLR parser up and running! specially trimmed to allow combined grammatic and semantic parsing and active early AST tree-trimming.

But when I started to develop the parser & grammar…I got a huge problem along with this, the ambiguity of the grammatic-word-tags and hence the different semantic meanings (called synsets in WordNet).. If I POS-tag the sentence prior to parsing, I will loose the less statistic frequent and may miss the parse! ¿any clue?

I finally wrote my own CFG parser-generator (compiler-compiler) allowing to specify complex actions on each reduction (free code), and even letting it to control the parser internal behavior by means of semantic actions. This finally allowed me to parse almost any kind of ambiguous input text (tokenized) and extract the most “meaningful” parse, instead of the most frequent POS-annotation parse.. which mostly fails when you face wrong typed or poorly written text, specially using highly inflected languages like Spanish.

Anyone who mastered in parsing, would actually ask “if this GLR parser doesn’t explode exponentially or in a NP hard-way? the answer is “I was afraid it would” but the conclusion is that even with complex grammars like Spanish (600 productions) the intelligent and early pruning mechanism embedded inside my parser makes it almost time-linear (about 4mS average parse time for a complete 10-20 word sentence parse, on a normal desktop 3GHz i386 ) I feel somehow proud of it.

But sadly at last I had to throw it all away and change the whole approach specially dealing with broken sentences, poor-grammar specifications, and dialog chunks, they are all not grammatic, so a decent parse is virtually impossible!

So I changed the approach, and using the underlying GLR parser I got a weighting Chunker to work! (a really weired piece of shit!)

Then I built and an active re-assembler system including several dialog turns! It’s like a distributed split-parser where you get no assembled sentence, you only get mixed up pieces on several turns (sentences), and you must see how to fit them together to make sense!

If you ask me if this is solvable? at first glance: NO, because the problem IS NP-hard, but designing a careful weighting algorithm you may find the best arrangement in sub-exponential (polynomial) time, and it works! ant the story continues…
one day at a time!

@Gary

Gary Dubuque - Jul 31, 2011:

@Andy, so for creating behavior in your system, you’ll be able to use the pattern types triggered when they are filled in with enough data to make sense.  And I’m guessing you can tie the various types together to build a tree or graph or something like that to support the variations on anaphora and co-referencings so you’ll be able to identify topic and context changes. It’s the behavior between understanding what the discourse is about and what the language generator needs to plan and then realize that fascinates me.  That’s the intelligent behavior?
....

Yes, I guess this would result in a good intelligent appearance, but still not real intelligence by far!

The real intelligence I guess will be possible when the ‘brain’ could be able to manage the strategy to deal with enough loosely linked data to grab some sense out of this, and even get some decent conclusion after all!

As I see, data-navigation heuristics on loosely bound graphs is still on dippers and there is a lot to create to accomplish some good results, and I’m here… thinking on this.. may be some day…! we’ll see!

AndyHo - Jul 31, 2011:

@Andrew
1) About the parser specification: does it include character recognitions (seems it has no scanner?)
2) About the multiple parse-tree output, is each output weighted in some way?
3) Have you tried Elkhound/Bison or other GNU parser?

Answers to your questions:

1) My GLR parser is scannerless which means that the same mechanism handles both characters and tokens. In the grammar definitions, characters are defined by their code point (the unicode equivalent of ASCII codes but the values can be at least 16 bits in magnitude). Here is the grammar definition file that is concatenated with the others to provide a complete grammar definition http://asmith.id.au/files/common.grammar

2) No.

3) I’ve looked at them all very closely but they are not designed to deal with ambiguity in a robust and efficient manner. They are intended for parsing formal languages and while they are capable of forking to handle local ambiguity, they all rely on the ambiguity being resolved before the completion of the parse, otherwise they fail.

There is another open source GLR parser called D Parser http://dparser.sourceforge.net/ which handles ambiguity in a more robust manner, but it is still targeted towards handling formal languages only.

The simple fact is that if you are going to handle natural languages then you have to treat ambiguous input not as the problem, but as (part of) the solution. Much of our communication is actually enhanced by the vague and ambiguous nature of our language and I’m not just referring to bad puns and double entendre. Creative writers balance and contrast words to convey meanings that cannot be captured by this or that single word. Part of the motivation for the development of WordNet was the need to capture this notion which is why it is organised as sets of synonyms (synsets) which often do not correspond exactly to any particular word or phrase.

The problem of handling the complexity of multiplying ambiguity is easily solved. I even solved it myself when I wrote the first version of my parser based on Earley’s algorithm, and I subsequently found that a description of the method was published in 1984 by Masaru Tomita http://en.wikipedia.org/wiki/GLR_parser

Another of the problems that you encountered also has a solution. I have not implemented this myself yet, but there have been papers published that show how to modify a GLR parser so it can ignore or correct errors in the input (i.e. not defined by the grammar) without slowing down. The modified algorithm is called GLR* and the paper describing it can be downloaded from http://www.cs.cmu.edu/~alavie/papers/IWPT-93.pdf

So Andy, in future I hope you won’t give up so easily!