c++ - 非常基础的英语语法解析器

Question

我正在编写一个非常基本的解析器(主要是为了更好地理解它们的工作原理)，它接受用户输入的几个单词，检测句子结构是否正常，并输出结果。语法是:

句子: 名词动词

文章句

连词句

连词: “和” “或者” “但是”

名词: “鸟类” “鱼” “C++”

动词: “规则” “飞” “游泳”

文章: “那个”

编写语法很简单。它正在实现给我带来麻烦的代码。我的伪代码是:

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"

所以这是我非常草率的伪代码。我有几个关于实现的问题。

1. 对于单词函数(名词、动词等)，我应该如何检查它们是否为真？ (如检查用户的输入是否有鸟、鱼、苍蝇、游泳等)

2. 应该如何处理连词调用和输出？

3. 我应该处理主函数的输出还是调用函数？

4. 如果我的伪代码完全错误，上述问题都不重要。基础有什么问题吗？

作为补充说明，我正在进行第 6 章的编程练习:使用 C++ 的实践和原则，所以我更喜欢使用我已经学过的语言语法，所以任何属于高级编程类别的东西可能不是很有帮助。 (练习中明确指出不要使用 token ，所以把它们算出来。)

提前致谢

最后编辑:在本书的公共(public)小组中，我问了同样的问题，Bjarne Stroustrup 回复说他将练习解决方案放到了网上。他基本上将输入读入语句函数并使用 if 语句返回真或假。但是，他没有使用文章，所以我的文章要复杂得多。我想如果我从这个练习中学到了什么，那就是在处理大量用户输入时，标记化是关键(据我目前所知)。这是我现在的代码。稍后我可能会回到它，因为它仍然有很多错误，并且基本上只有在句子正常并且无法处理(名词，连词，句子)之类的事情时才会返回，但现在我要继续前进。

#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

好的。如果你真的想手工做:-(

这个问题有两个部分:

• 词法分析
• 句法分析。
• 我们可以忽略 Symantic 分析，因为这就是上面的原因。

首先，您将输入流标记为合理的标记。单词将是一个明显的选择，但这会给句法阶段留下很多工作。所以我会把你的话分成以下类型(连词、名词、动词、文章)，然后写一个词法分析器来返回正确的词组。

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
}

所以现在您可以根据简化的标记流来编写句法解析器。

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

句法分析的另一个选择是建立一个状态表。但这涉及手工分析语法和确定状态。这应该只用最简单的语法来尝试，任何比你这里更大的东西都应该留给可以自动生成状态表的工具。

所以假设我在下面的原始帖子中定义的语法:
并希望我能做对，因为我不是充气工具 :-)

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;
}