Natural Language Processing

Currently I've only implemented a chart parser that can create multiple parse trees from ambiguous sentences. The algorithm for the chart parser can be found in chapter 23 of "Artificial Intelligence: A Modern Approach (AIMA)" by Stuart Russell and Peter Norvig. I extended it so the different parse trees can be used separately.

What was implemented:
  • The Chart Parser
  • Lexicon and Grammar can be read from file
Remarks
  • I added a lexicon and a grammar because without them the parse is not of much use. Both are lacking but will at least give you an idea. The grammar generates way too much ambiguous sentences and is thus not very useful. The lexicon lacks even a lot of basic words.
  • Implementing the chart parsing took a lot of time. First it was hard to understand the notation used in the book AIMA. Secondly, there is a small, but annoying error in the algorithm: the first line
    chart[0] <- [0, 0, S' -> *S]
    should read
    ADD-EDGE( [0, 0, S' -> *S] )
    Finally, and this has taken most of the time, the algorithm is meant to find out if a sentence is legal or not. It creates internally only a combined parse tree. It proved quite hard and in demand of a thorough understanding of the algorithm (which I gained in time) to pull the separate parse trees from the combined tree.

Sample use
void PrintParseTrees(CNLPParseForest &ParseForest)
{
	for (int Index=0; Index<ParseForest.GetParseTreeCount(); Index++)
	{
		CNLPParseTree *ParseTree = ParseForest.GetParseTree(Index);
		printf("%s\n\n", ParseTree->ToString().GetBuffer());
	}
}

void Parse(void)
{
	CNLPModel Model;
	CNLPParseForest ParseForest;

	// load a grammar
	Model.AddGrammarRules("resources/grammar_english_thoughtreasure.txt");

	// load a lexicon
	Model.AddLexicalEntries("resources/lexicon_english_nouns.txt", "Noun");
	Model.AddLexicalEntries("resources/lexicon_english_articles.txt", "Article");
	Model.AddLexicalEntries("resources/lexicon_english_pronouns.txt", "Pronoun");
	Model.AddLexicalEntries("resources/lexicon_english_verbs.txt", "Verb");
	Model.AddLexicalEntries("resources/lexicon_english_adverbs.txt", "Adverb");
	Model.AddLexicalEntries("resources/lexicon_english_adjectives.txt", "Adjective");
	Model.AddLexicalEntries("resources/lexicon_english_determiners.txt", "Det");
	Model.AddLexicalEntries("resources/lexicon_english_conjunctions.txt", "Conjunction");

	// parse sentences and create and print the parse trees
	Model.Parse("I feel a breeze.", ParseForest);
	PrintParseTrees(ParseForest);

	Model.Parse("fall leaves fall and spring leaves spring.", ParseForest);
	PrintParseTrees(ParseForest);

	Model.Parse("I think therefore I am.", ParseForest);
	PrintParseTrees(ParseForest);
}
Links