我正在编写一个非常基本的解析器(主要是为了更好地理解它们是如何工作的),它使用户输入选择的几个单词,检测句子结构是否正常,并输出结果.语法是:
句子:Noun Verb
文章句子
句子连词句
连词:"和""或""但是"
名词:"鸟""鱼""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"
所以有我非常邋ps的伪代码.我有一些关于实施它的问题.
对于单词函数(名词,动词等),我该如何检查它们是否属实？(如检查用户的输入是否有鸟类,鱼类,苍蝇,游泳等)
我该如何处理联合呼叫和输出？
我应该处理主函数或调用函数的输出吗？
如果我的伪代码完全错误,上述问题都不重要.基础知识有什么问题吗？
作为补充说明,我正在进行第6章编程练习:使用C++实践和原理,所以我更喜欢使用我已经学过的语言语法,所以属于高级编程类别的任何东西都可能不是非常有帮助.(该练习明确表示不使用令牌,因此请将其计算在内.)
提前致谢
最后编辑:在该书的公共小组中,我问了同样的问题,Bjarne Stroustrup回复说他把运动解决方案放在网上.他基本上把输入读入了句子函数,并使用if语句返回true或false.但是,他没有使用文章,所以我的文章要复杂得多.我想如果我从这个练习中学到了什么,那么在处理大量用户输入时,标记化是关键(从目前为止我所知道的.)这是我现在的代码.我可能会在以后回到它,因为它仍然是非常错误的,并且基本上只有在句子没问题且不能处理(名词,连词,句子)之类的东西时才返回,但是现在我继续前进.
#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(); }
好.如果你真的想手工做:-(
这个问题有两个部分:
首先,您将输入流标记为合理的令牌.单词将是一个obvios选择,但这将为句法阶段留下很多工作.所以我会把你的单词分成以下类型(Conjunction,Noun,Verb,Article),然后写一个词法分析器来返回正确的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
}
所以现在你可以根据简化的令牌流来学习你的语法分析器了.
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;
}
我对这个问题很感兴趣.我要帮助OP,Alex,做些什么,但由于我不太了解C++,它将使用伪C++.它也不会使用lex/yacc,因为Alex想要了解它们是如何制作的.如果你使用它们,lex和yacc等工具就会成为"黑盒子".我现在没有时间把它们放在一起,但我可以在几个小时内一块一块地完成它.我只是想现在就开始吧.
我们需要做的第一件事就是清理语法.你有一个这样定义的句子:
sentence : noun verb
| article sentence
| sentence conjunction sentence
这个语法有缺陷.诸如"游泳鱼"之类的句子是有效的,因为句子是根据其自身来定义的.递归是语法的正常部分,但需要正确处理.我打算猜测你不希望连续出现两篇或多篇文章.
更好的句子语法可以是:
sentence : clause conjunction clause
| clause
clause : nounphrase verbphrase
nounphrase : noun
| article noun
这消除了无约束的递归,这可能导致无限循环.
现在我们已经准备好解决解析器本身了.由于这是C++,我们不妨使它面向对象.我现在必须用scoot,但我会给你一个提示:每个生产规则都会有一个类.
大多数解析（如程序文本解析）是使用形式语法解析器完成的。英语和大多数口语都不是正式的语法，你将很难解析它们。这个问题困扰了博士们数十年，但并没有取得多大成功。