Very basic English grammar parser

Question

I'm writing a very basic parser(mostly just to better understand how they work) that takes a user's input of a select few words, detects whether the sentence structure is OK or Not OK, and outputs the result. The grammar is:

Sentence: Noun Verb

Article Sentence

Sentence Conjunction Sentence

Conjunction: "and" "or" "but"

Noun: "birds" "fish" "C++"

Verb: "rules" "fly" "swim"

Article: "the"

Writing the grammar was simple. It's implementing the code that is giving me some trouble. My psuedocode for it is:

main()
get user input (string words;)
while loop (cin >> words)
call sentence()
end main()

sentence()
call noun()
if noun() call verb() (if verb is true return "OK" ???)(else "not ok"???)
else if not noun() call article()
                if article() call sentence() (if sentence is true "OK"???)(else "not"?)
else if not noun() call conjunction()
                   if sentence() conjunction() sentence() - no idea how to implement
                                                             return "OK"
else "not ok"

So there is my extremely sloppy psuedo code. I have a few questions on implementing it.

1. For the word functions (noun, verb, etc.) how should I go about checking if they are true? (as in checking if the user's input has birds, fish, fly, swim, etc.)

2. How should I handle the conjunction call and the output?

3. Should I handle the output from the main function or the call functions?

4. None of the above questions matter if my psuedo code is completely wrong. Is there anything wrong with the basics?

As an added note, I'm on a Chapter 6 exercise of Programming: Practice and Principles Using C++ so I'd prefer to use language syntax that I've already learned, so anything that falls into the category of advanced programming probably isn't very helpful. (The exercise specifically says not to use tokens, so count those out.)

Thanks in advance

Last Edit: In the book's public group I asked the same question and Bjarne Stroustrup commented back saying he put the exercise solution online. He basically had the input read into the sentence function and used if statements to return true or false. However, he didn't use articles so mine was much more complex. I guess if I've learned anything from this exercise its that when dealing with a lot of user input, tokenization is key (from what I know so far.) Here is my code for now. I may go back to it later because it is still very buggy and basically only returns if the sentence is OK and can't handle things like (noun, conjunction, sentence), but for now I'm moving on.

#include "std_lib_facilities.h"

bool article(string words)
{
               if (words == "the")
               return true;
               else return false;        
}

bool verb(string words)
{
               if (words == "rules" || words == "fly" || words == "swim")
               return true;
               else return false;                   
}

bool noun(string words)
{
               if (words == "birds" || words == "fish" || words == "c++")
               return true;
               else return false;                   
}

bool conjunction(string words)
{
              if (words == "and" || words == "but" || words == "or")
              return true;
              else return false;                  
}

bool sentence()
{
string w1;
string w2;
string w3;
string w4;

cin >> w1;
if (!noun(w1) && !article(w1)) return false; // grammar of IFS!

cin >> w2;
if (noun(w1) && !verb(w2)) return false;
if (article(w1) && !noun(w2)) return false;

cin >> w3;
if (noun(w1) && verb(w2) && (w3 == ".")) return true;
if (verb(w2) && !conjunction(w3)) return false;
if (noun(w2) && !verb(w3)) return false;
if (conjunction(w3)) return sentence();

cin >> w4;
if (article(w1) && noun(w2) && verb(w3) && (w4 == ".")) return true;
if (!conjunction(w4)) return false;
if (conjunction(w4)) return sentence();
}


int main()
{                                   
cout << "Enter sentence. Use space then period to end.\n";
            bool test = sentence();
            if (test)
      cout << "OK\n";
            else
      cout << "not OK\n";

keep_window_open(); }

Answer 1

Hash tables.

Answer 2

Most parsing like program text parsing is done with formal grammar parsers. English and most spoken languages are not formal grammars and you're going to have a very hard time parsing them. This problem has tied up PHDs for decades without a lot of success.

Answer 3

Before you get too far writing a parser, might I suggest learning the pair of lex and yacc or flex and bison? These tools were specifically made for creating parsers and lexers.

They will automatically generated your c/c++ (maybe other) code, so you will not have to worry about all sorts of boundary cases for user arguments. You could whip up the grammar you have above in under 30 minutes.

As for your questions:

For the word functions (noun, verb, etc.) how should I go about checking if they are true? (as in checking if the user's input has birds, fish, fly, swim, etc.)

A generous use of strcasecmp() is called for here, with all sorts of error checking as well.

How should I handle the conjunction call and the output?

I don't really understand too much what you mean here. I'd just return some sort of sentinel value if its valid or not.

Should I handle the output from the main function or the call functions?

Mostly from the call functions, since these have the individual functionality you're concerned with. main() is just glue to hold it together.

None of the above questions matter if my psuedo code is completely wrong. Is there anything wrong with the basics?

It looks doable the way you have, but you will save yourself a huge headache by switching to lex/yacc or flex/bison

Answer 4

Use Flex and Bison:

Grammer Rule in Bison:

%%

English            :   SentenceList

SentenceList       :   Sentence
                   |   Article  Sentence
                   |   Sentence Conjunction Sentence

Sentence           :   Noun Verb


Conjunction        :   TOKEN_WordAnd
                   |   TOKEN_WordOr
                   |   TOKEN_WordBut


Noun               :   TOKEN_WORD_BIRDS
                   |   TOKEN_WORD_FISH
                   |   TOKEN_WORD_CPP

Verb:              :   TOKEN_WORD_RULES
                   |   TOKEN_WORD_FLY
                   |   TOKEN_WRD_SWIM

Article            :   TOKEN_WORD_THE
%%

Answer 5

Okay so... I won't have answers to your specific questions, but I want to point you to some general ideas to think about when working on this. First of all, parsing is hard. You have a simple grammar, but it can STILL be hard. Compiler front-ends are responsible for parsing... just to give some context.

There are two basic types of parsing... top down parsing and bottom up parsing. They are named by how they traverse a syntax tree (Think about what sort of syntax tree is going to be created for possible constructs). Top down parsing is easy, and will probably work for what you want to do. The most common top-down parsing method is Recursive Descent parsing: http://en.wikipedia.org/wiki/Recursive_descent_parser

However, to use recursive descent parsing, your grammar must be in a certain format... for some grammars, it is impossible to recursive descent parse them. You should be able to reform your grammar to fit this though.

Top-down parsers are easy to write... as you will only need a few functions for a small language.

The second way to parse is bottom-up parsing. This is commonly used in compilers as it does not have the restrictions top-down has. It is also easier to do error-reporting if the given string does not fit the language.

Bottom-up parsers are HARD to write... most people use a parser generator to do the work. I've worked with YACC quite a bit. You basically input the grammar (and actions to take when that rule is matched) and it parses the grammer.

Bottom-up parsers use something called shift-reduce parsing. This is the method of processing the input and matching the rules.

Looking at your code again, I'd say it is possible for you to use a top-down parser. Sorry I can't give specific code, but a google of top-down parser examples (or recursive descent parser examples) would probably turn up the code you need.

Answer 6

You could take a loot to Ubiquity, it's a plugin for Firefox that aims to use natural language to do common web tasks (it's written in JavaScript but maybe you can get a general algorithm that would be usefull)

Answer 7

Ok. If you really want to do it by hand :-(

There are two parts to this problem:

• Lexical analysis
• Syntactic Analysis.
• We can ignore the Symantic analysis as this is why up ther.

First you have tokenize the input stream into resonable tokens. Words would be an obvios choice but that would leave a lot of work for the syntactic phase. So I would group up your words into the following types (Conjunction,Noun,Verb,Article) and then write a lexer to return the correct Lexems.

Lexer.cpp
enum Lexeme { END,Conjunction,Noun,Verb,Article };
Lexem getNextLexme(std::istream in)
{
    std::string word;
    in >> word;

    if (!in) {return END;}

         if (word == "and")   return Conjunction;
    else if (word == "birds") return Noun;
    else if (word == "fly")   return Verb;
    else if (word == "the")   return Article;

    ... etc
}

So now you can wrtie your syntactic parser in terms of the simplified token stream.

bool ParseSentence(std::istream in)
{
    Lexeme token = getNextLexme(in);
    switch(token)
    {
        case Noun:    if (!parseVerb(in))
                      {    return false;
                      }
                      return parseConjunctionOrEnd(in);
        case Article: return ParseSentence();
        case END:     return true;
    }
}
bool parseVerb(std::istream in)
{
    Lexeme token = getNextLexeme(in);
    if (token != Verb) { /*ERROR*/ return false;}
    return true;
 }
 // etc

Your other option with syntactic analyasis is to build a state table. But that involves hand analysing the grammer and determing the states. This should only be attepted with the most trivial of grammers, anything bigger than you have here should be left to tools that can generate the state table auto-magically.

So Assuming the grammer I defined in my original post below:
And hoping I get it correct as I am not an inflable tool :-)

State 1:   Start <Nothing Happened>
               Article -> State 2
               Noun -> State 3
               Otherwise Error
State 2:   Seen Article.
               Noun -> State 3
               Otherwise Error
State 3:   Seen Noun  in Sentence.
               Verb -> State 4
               Otherwise Error
State 4:   Seen Noun Verb
               End -> State 5
               Conjunction -> State 1
State 5:   Finished:

State 0:   Error State.


int stateTable[][]    // CurrentState,CurrentObject
           = {/*State 0: Error State:*/{},
                                       // END,Conjunction,Noun,Verb,Article 
              /*State 1: Start*/       {  0,  0,          3,   0,   2},
              /*State 2: Article*/     {  0,  0,          3,   0,   0},
              /*State 3: Noun*/        {  0,  0,          0,   4,   0},
              /*State 4: Noun Verb*/   {  5,  1,          0,   0,   0},
              /*State 5: End*/         {}
             };

bool parseSentence(std::iostream& in)
{
    int currentState = 1;
    while((currentState != 0) && (currentState != 5))
    {
        int token = getNextLexme(in);
        currentState = stateTable[currentState][token];
    }
    return currentState == 5;
}

Answer 8

Parts of Speech

To get parts of speech you will need a dictionary list with parts of speech. Besides a hashtable mapping words to lists of parts of speech, another possible way to check for part(s) of speech is to load each set of words for each part of speech into its own Bloom filter (sort of a compressed hashed map from strings to booleans).

Answer 9

I'm intrigued by this question. I'm going to help the OP, Alex, cook something up, but since I don't know C++ very well, it'll be in pseudo-C++. It won't use lex/yacc, either, because Alex wants to learn how they're made. Tools such as lex and yacc become "black boxes" if you use them. I don't have time to put it all together right now, but I can work on it piece by piece over a few hours. I just wanted to get this started now.

The first thing we need to do is clean up the grammar. You have a sentence defined this way:

sentence : noun verb
         | article sentence
         | sentence conjunction sentence

This grammar is flawed. A sentence such as "a the fish swim" is valid because sentence is defined in terms of itself. Recursion is a normal part of grammars, but it needs to be handled correctly. I'm going to hazard a guess that you don't want two or more articles to appear in a row.

A better grammar for sentence could be:

sentence : clause conjunction clause
         | clause

clause : nounphrase verbphrase

nounphrase : noun
           | article noun

This removes the unconstrained recursion which could cause infinite loops.

Now we're ready to tackle the parser itself. Since this is C++, we might as well make it object-oriented. I gotta scoot for now, but I'll give you a hint: there's going to be a class for each one of the production rules.

Answer 10

One aspect of grammars for natural languages is that they are often ambigious. For example, the english sentance:

I once shot an elephant in my pajamas. How he got in my pajams I'll never know
-- Groucho Marx

The phrase 'in my pajamas' ambigiously describes The subject 'I' or the object 'elephant'. Without semantic context it would be impossible to build an AST correctly.

If you wish to avoid this, you will probably need some way of treating ambiguity in a useful way. One strategy is to produce all possible derivations of ambiguous phrases. One tool that makes this possible is an Earley Parser. Unlike other types of parser, such as recursive descent parsers, Earley parsers generate all derivations in the form of parser state transitions, rather than a simple tree. In practice this isn't any harder to work with.