Problem
问题
Loglan is a synthetic speakable language designed to test some of the fundamental problems of linguistics, such as the Sapir Whorf hypothesis. It is syntactically unambiguous, culturally neutral and metaphysically parsimonious. What follows is a gross over-simplification of an already very small grammar of some 200 rules.
Loglan是一种综合型可发音的语言，设计它是用来验证语言学上的一些原则性问题，比如萨皮尔—沃尔夫假说。它的句法精确明了，在文化上趋于中立，它的哲学是能省则省。该语言的语法集已经被过份的简化——只有200条语法规则。
Loglan sentences consist of a series of words and names, separated by spaces, and are terminated by a period (.). Loglan words all end with a vowel; names, which are derived extra-linguistically, end with a consonant. Loglan words are divided into two classes--little words which specify the structure of a sentence, and predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel (see examples later).
Loglan的语句由一系列的单词和名称组成，中间由空格隔开，并由一个点号（.）表示结束。Loglan的单词均以元音结束；名称来自于该语言之外，由辅音结束。Loglan的单词分为两类——小单词和谓词。小单词指定了句子的结构；谓词的形式为“CCVCV”或“CVCCV”，其中C代表一个辅音，V代表一个元音。（见下面的例子）
The subset of Loglan that we are considering uses the following grammar:
我们考虑使用Loglan语言的一个子集，具有以下语法定义：
A → a | e | i | o | u
MOD → ga | ge | gi | go | gu
BA → ba | be | bi | bo | bu
DA → da | de | di | do | du
LA → la | le | li | lo | lu
NAM → {all names}
PREDA → {all predicates}
<sentence> → <statement> | <predclaim>
<predclaim> → <predname> BA <preds> | DA <preds>
<preds> → <predstring> | <preds> A <predstring>
<predname> → LA <predstring> | NAM
<predstring> → PREDA | <predstring> PREDA
<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>
<verbpred> → MOD <predstring>
Write a program that will read a succession of strings and determine whether or not they are correctly formed Loglan sentences.
写一个程序，读入一组字符串并确定它们是不是正确的Loglan语句。
Input and Output
输入与输出
Each Loglan sentence will start on a new line and will be terminated by a period (.). The sentence may occupy more than one line and words may be separated by more than one whitespace character. The input will be terminated by a line containing a single `#'. You can assume that all words will be correctly formed.
每个Loglan语句均从新的一行开始，并以句点（.）结束。一条语句可能占用多行，且单词之间可能会多于一个空格。所有的输入由一个独占一行的#号表示结束。你可以认为所有单词的格式都是正确的。
Output will consist of one line for each sentence containing either 'Good' or 'Bad!'.
对于每一个输入的语句，应输出"Good"或"Bad!"。
Sample input
输入示例
la mutce bunbo mrenu bi ditca.
la fumna bi le mrenu.
djan ga vedma le negro ketpi.
#
Sample output
输出示例
Good
Bad!
Good
Analysis
分析
对于没学过编译原理的同学来说，这道题的难度比较大。题目中的语法定义由“产生式”给出，这里面用到了正则表达式的一些基本符号。一个产生式定义一个构造（推导）规则，前面是可推导出的符号，箭头后面指向的是符号序列，竖线“|”表示“或着”。举例而言：
A → a | e | i | o | u
上式的义意是a、e、i、o、u中任意一个符号都可以用符号A来表示（推导出A）。
<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>
上式的义意是：<predname> <verbpred> <predname>三个符号从左至右依次排列，可以用符号<statement>来表示，<predname> <verbpred>也可以用<statement>来表示，具体选用哪一种，就要看制定的推导策略了。题目要求判断任意给定的句子的语法是否正确，也就是要用该文法来推导句子，如果能推出sentence符号就算是正确的。
通过对产生式进行语法分析可知，该文法不存在二义性，但它并不是一个正则文法，需要对其进行转换。文法中PREDA是终结符号（除了谓词或名称外，没有其它符号可以推导出它们），它可以推导出predstring，而predstring又可以作为PREDA的前缀推导出predstring，那么predstring的正则表达式应该为：
PREDA+
上式中“+”号的意思是一个或多个PREDA连起来形成的串。我们还可以看到，predstring除了在它自身的产生式之外，其它地方都是用于后缀，因此多个连续的predstring可以直接合并，不会造成二义性问题。那么产生应改写为：
PREDA → PREDA PREDA
这样所有连续的多个PREDA都生成为单个PREDA，再转为predstring即可：
<predstring> → PREDA
NAM、DA和BA也是终结符，但它们的产生式没有自循环，不用变了。具体要说明什么是自循环，则要扯出有限自动机（DNF）、闭包、状态图等一大堆概念了，这些不是本文的重点，恕不赘述！
还要需要处理的是A，predstring可以直接推导出preds，而preds又可以作为A的前缀推导出preds自己，那么preds的产生式可以改写为：
<predstring> → <predstring> A <predstring>
<preds> → <predstring>
画个状态图，一看便知。最后一个要处理的是：
<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>
显然predname和verbpred可以作为一个整体，为了简化产生式，我们另设一个符号predverb：
<predverb> → <predname> <verbpred>
这样statement的产生式就可改写为正则文法：
<statement> → <predverb> <predname> | <predverb>
下面是处理好的正则文法：
A → a | e | i | o | u
MOD → ga | ge | gi | go | gu
BA → ba | be | bi | bo | bu
DA → da | de | di | do | du
LA → la | le | li | lo | lu
NAM → {all names}
PREDA → {all predicates} | PREDA PREDA
<sentence> → <statement> | <predclaim>
<predclaim> → <predname> BA <preds> | DA <preds>
<preds> → <predstring>
<predname> → LA <predstring> | NAM
<predstring> → PREDA | <predstring> A <predstring>
<predverb> → <predname> <verbpred>
<statement> → <predverb> <predname> | <predverb>
<verbpred> → MOD <predstring>
根据这个文法就可以快速的判断语句的正确性了。先将输入的所有字符串转换为单词（包括谓词和小单词）或名称，可根据最后一个字母是否元音来判断是单词还是名称，如果是名称就直接转为NAM，如果是单词则需按上面的文法查表（有不用查表的小技巧，详见代码）。整个句子都转换完成后，就要按照顺序对符号进行推导，过程如下：
PREDA → PREDA PREDA
<predstring> → <predstring> PREDA
<predstring> → PREDA
<predname> → NAM
<predname> → LA <predstring>
<verbpred> → MOD <predstring>
<preds> → <predstring> A <predstring>
<preds> → <predstring>
<predclaim> → <predname> BA <preds> | DA <preds>
<predverb> → <predname> <verbpred>
<statement> → <predverb> <predname> | <predverb>
<predclaim> → <sentence>
<statement> → <sentence>
如果最后能推得sentence，说明句法是正确的，否则就是错误的。推导的方法其实就是对动态数组进行插入和删除的操作：如果一个符号可以直接推导出另一个符号，则直接改写为推导出的符号；如果一个符号和前缀一起能推导出另一个符号，就将前缀删除，当前符号改写为推导出的符号；后缀的情况还有前后缀一起推导的情况也是一样。具体算法详见代码的注释，非常详细。
程序中状态转换表的顺序与上述推导顺序相同（某些次序可以颠导，不影响结果的正确性，可能程序中略有不同）。符号枚举类型中的符号名为符号的缩写，对应如下：
UN: 未知/出错
PS: predstring
P: preds
PN: predname
SE: sentence
VP: verbpred
PV: predverb
PC: predclaim
ST: statement
其它符号名与题目给出的相同。
Solution
解答
view sourceprint?01 #include <iostream>
02 #include <string>
03 #include <vector>
04 using namespace std;
05 //各种符号的枚举，后面的注释为题目中对应的符号
06 enum SYMBOL{A, MOD, LA, BA, DA, PREDA, NAM, SE, PC, P, PN, PS, ST, VP, PV, UN};
07 bool aVowel[] = {1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0}; //元音表
08 static SYMBOL aConvTbl[14][4] = { //状态转换表
09 {PREDA, UN, PREDA, PREDA}, {PREDA, UN, UN, PS}, {NAM, UN, UN, PN},
10 {LA, UN, PS, PN}, {MOD, UN, PS, VP}, {A, PS, PS, PS}, {PS, UN, UN, P},
11 {DA, UN, P, PC}, {BA, PN, P, PC}, {VP, PN, UN, PV}, {PV, UN, PN, ST},
12 {PV, UN, UN, ST}, {PC, UN, UN, SE}, {ST, UN, UN, SE},
13 };
14 //判断是否元音字母的函数
15 inline bool isvowel(char c) {
16 return islower(c) && aVowel[c - 'a'];
17 }
18 //将输入的字符串转为状态
19 SYMBOL Token2Status(const string &str) {
20 int nNum = str.length();
21 if (!isvowel(str[nNum - 1])) {
22 return NAM; //末尾不是元音的为NAM
23 }
24 switch (nNum) {
25 case 1: return A; //只有一位元音的只能是A
26 case 5: //用位运算快速判断谓词是否符合规则CCVCV或CVCCV
27 nNum = isvowel(str[4]);
28 nNum |= ((isvowel(str[0]) << 4) | (isvowel(str[1]) << 3));
29 nNum |= ((isvowel(str[2]) << 2) | (isvowel(str[3]) << 1));
30 return (nNum == 5 || nNum == 9) ? PREDA : UN;
31 case 2: //两位的单词
32 switch (str[0]) { //根据第一位判断是哪一组
33 case 'g': return MOD;
34 case 'b': return BA;
35 case 'd': return DA;
36 case 'l': return LA;
37 }
38 }
39 return UN; //未能识别的错误符号
40 }
41 //词法分析函数，算法过程详见相关文档
42 bool ParseSentence(vector<SYMBOL> &Set) {
43 for (int i = 0; i < 14; ++i) { //依次处理每一种状态
44 SYMBOL *pTbl = aConvTbl[i]; //为加快运算，节省代码，设临时变量
45 for (vector<SYMBOL>::iterator j = Set.begin(); j != Set.end();) {
46 if (*j != pTbl[0]) {
47 ++j; //不是指定符号，遍例下一个
48 continue;
49 } //如果指定了前面或后面相邻的符号则验证其是否存在
50 if (pTbl[1] != UN && (j == Set.begin() || *(j - 1) != pTbl[1])) {
51 ++j; //存在的符号与指定的不符，结果错误
52 continue;
53 }
54 if (pTbl[2] != UN && (j == Set.end() - 1 || *(j + 1) != pTbl[2])) {
55 ++j; //存在的符号与指定的不符，结果错误
56 continue;
57 } //删除前后的符号(如果指定)
58 j = pTbl[1] != UN ? Set.erase(j - 1) : j;
59 j = pTbl[2] != UN ? Set.erase(j + 1) - 1 : j;
60 *j = pTbl[3]; //当前符号变更为指定的目标符号
61 }
62 }
63 return (Set.size() == 1 && Set.front() == SE); //返回结果
64 }
65 //主函数
66 int main(void) {
67 vector<SYMBOL> Set;
68 for (string str; cin >> str && str != "#";) { //循环读入每个单词
69 int nDot = str.find('.'); //如果单词中发现句点，则认为句子结束
70 if (nDot == str.npos) { //没有发现句点
71 Set.push_back(Token2Status(str)); //将单词转为符号后存入语句
72 continue;
73 } //以下为发现句点，即遇到句子结束
74 str.erase(str.length() - 1); //删除句点
75 if (!str.empty()) { //单词不为空则加入语句
76 Set.push_back(Token2Status(str));
77 } //以下进行词法分析并输出结果
78 cout << (ParseSentence(Set) ? "Good" : "Bad!") << endl;
79 Set.clear(); //清空语句，准备处理下一条语句
80 }
81 return 0;
82 }<BR>
