Loglan邏輯綜合可發(fā)音語(yǔ)言

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是一種綜合型可發(fā)音的語(yǔ)言，設(shè)計(jì)它是用來驗(yàn)證語(yǔ)言學(xué)上的一些原則性問題，比如薩皮爾—沃爾夫假說。它的句法精確明了，在文化上趨于中立，它的哲學(xué)是能省則省。該語(yǔ)言的語(yǔ)法集已經(jīng)被過份的簡(jiǎn)化——只有200條語(yǔ)法規(guī)則。

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的語(yǔ)句由一系列的單詞和名稱組成，中間由空格隔開，并由一個(gè)點(diǎn)號(hào)（.）表示結(jié)束。Loglan的單詞均以元音結(jié)束；名稱來自于該語(yǔ)言之外，由輔音結(jié)束。Loglan的單詞分為兩類——小單詞和謂詞。小單詞指定了句子的結(jié)構(gòu)；謂詞的形式為“CCVCV”或“CVCCV”，其中C代表一個(gè)輔音，V代表一個(gè)元音。（見下面的例子）

The subset of Loglan that we are considering uses the following grammar:
我們考慮使用Loglan語(yǔ)言的一個(gè)子集，具有以下語(yǔ)法定義：

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.
寫一個(gè)程序，讀入一組字符串并確定它們是不是正確的Loglan語(yǔ)句。

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.
每個(gè)Loglan語(yǔ)句均從新的一行開始，并以句點(diǎn)（.）結(jié)束。一條語(yǔ)句可能占用多行，且單詞之間可能會(huì)多于一個(gè)空格。所有的輸入由一個(gè)獨(dú)占一行的#號(hào)表示結(jié)束。你可以認(rèn)為所有單詞的格式都是正確的。

Output will consist of one line for each sentence containing either 'Good' or 'Bad!'.
對(duì)于每一個(gè)輸入的語(yǔ)句，應(yīng)輸出"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
分析
對(duì)于沒學(xué)過編譯原理的同學(xué)來說，這道題的難度比較大。題目中的語(yǔ)法定義由“產(chǎn)生式”給出，這里面用到了正則表達(dá)式的一些基本符號(hào)。一個(gè)產(chǎn)生式定義一個(gè)構(gòu)造（推導(dǎo)）規(guī)則，前面是可推導(dǎo)出的符號(hào)，箭頭后面指向的是符號(hào)序列，豎線“|”表示“或著”。舉例而言：

A → a | e | i | o | u

上式的義意是a、e、i、o、u中任意一個(gè)符號(hào)都可以用符號(hào)A來表示（推導(dǎo)出A）。

<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>

上式的義意是：<predname> <verbpred> <predname>三個(gè)符號(hào)從左至右依次排列，可以用符號(hào)<statement>來表示，<predname> <verbpred>也可以用<statement>來表示，具體選用哪一種，就要看制定的推導(dǎo)策略了。題目要求判斷任意給定的句子的語(yǔ)法是否正確，也就是要用該文法來推導(dǎo)句子，如果能推出sentence符號(hào)就算是正確的。

通過對(duì)產(chǎn)生式進(jìn)行語(yǔ)法分析可知，該文法不存在二義性，但它并不是一個(gè)正則文法，需要對(duì)其進(jìn)行轉(zhuǎn)換。文法中PREDA是終結(jié)符號(hào)（除了謂詞或名稱外，沒有其它符號(hào)可以推導(dǎo)出它們），它可以推導(dǎo)出predstring，而predstring又可以作為PREDA的前綴推導(dǎo)出predstring，那么predstring的正則表達(dá)式應(yīng)該為：

PREDA+

上式中“+”號(hào)的意思是一個(gè)或多個(gè)PREDA連起來形成的串。我們還可以看到，predstring除了在它自身的產(chǎn)生式之外，其它地方都是用于后綴，因此多個(gè)連續(xù)的predstring可以直接合并，不會(huì)造成二義性問題。那么產(chǎn)生應(yīng)改寫為：

PREDA → PREDA PREDA

這樣所有連續(xù)的多個(gè)PREDA都生成為單個(gè)PREDA，再轉(zhuǎn)為predstring即可：

<predstring> → PREDA

NAM、DA和BA也是終結(jié)符，但它們的產(chǎn)生式?jīng)]有自循環(huán)，不用變了。具體要說明什么是自循環(huán)，則要扯出有限自動(dòng)機(jī)（DNF）、閉包、狀態(tài)圖等一大堆概念了，這些不是本文的重點(diǎn)，恕不贅述！

還要需要處理的是A，predstring可以直接推導(dǎo)出preds，而preds又可以作為A的前綴推導(dǎo)出preds自己，那么preds的產(chǎn)生式可以改寫為：

<predstring> → <predstring> A <predstring>
<preds> → <predstring>

畫個(gè)狀態(tài)圖，一看便知。最后一個(gè)要處理的是：

<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>

顯然predname和verbpred可以作為一個(gè)整體，為了簡(jiǎn)化產(chǎn)生式，我們另設(shè)一個(gè)符號(hào)predverb：

<predverb> → <predname> <verbpred>

這樣statement的產(chǎn)生式就可改寫為正則文法：

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

根據(jù)這個(gè)文法就可以快速的判斷語(yǔ)句的正確性了。先將輸入的所有字符串轉(zhuǎn)換為單詞（包括謂詞和小單詞）或名稱，可根據(jù)最后一個(gè)字母是否元音來判斷是單詞還是名稱，如果是名稱就直接轉(zhuǎn)為NAM，如果是單詞則需按上面的文法查表（有不用查表的小技巧，詳見代碼）。整個(gè)句子都轉(zhuǎn)換完成后，就要按照順序?qū)Ψ��?hào)進(jìn)行推導(dǎo)，過程如下：

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，說明句法是正確的，否則就是錯(cuò)誤的。推導(dǎo)的方法其實(shí)就是對(duì)動(dòng)態(tài)數(shù)組進(jìn)行插入和刪除的操作：如果一個(gè)符號(hào)可以直接推導(dǎo)出另一個(gè)符號(hào)，則直接改寫為推導(dǎo)出的符號(hào)；如果一個(gè)符號(hào)和前綴一起能推導(dǎo)出另一個(gè)符號(hào)，就將前綴刪除，當(dāng)前符號(hào)改寫為推導(dǎo)出的符號(hào)；后綴的情況還有前后綴一起推導(dǎo)的情況也是一樣。具體算法詳見代碼的注釋，非常詳細(xì)。

程序中狀態(tài)轉(zhuǎn)換表的順序與上述推導(dǎo)順序相同（某些次序可以顛導(dǎo)，不影響結(jié)果的正確性，可能程序中略有不同）。符號(hào)枚舉類型中的符號(hào)名為符號(hào)的縮寫，對(duì)應(yīng)如下：

UN: 未知/出錯(cuò)
PS: predstring
P: preds
PN: predname
SE: sentence
VP: verbpred
PV: predverb
PC: predclaim
ST: statement

其它符號(hào)名與題目給出的相同。

Solution
解答
view sourceprint?01 #include <iostream>

02 #include <string>

03 #include <vector>

04 using namespace std;

05 //各種符號(hào)的枚舉，后面的注釋為題目中對(duì)應(yīng)的符號(hào)

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] = { //狀態(tài)轉(zhuǎn)換表

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 //判斷是否元音字母的函數(shù)

15 inline bool isvowel(char c) {

16 return islower(c) && aVowel[c - 'a'];

17 }

18 //將輸入的字符串轉(zhuǎn)為狀態(tài)

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: //用位運(yùn)算快速判斷謂詞是否符合規(guī)則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]) { //根據(jù)第一位判斷是哪一組

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; //未能識(shí)別的錯(cuò)誤符號(hào)

40 }

41 //詞法分析函數(shù)，算法過程詳見相關(guān)文檔

42 bool ParseSentence(vector<SYMBOL> &Set) {

43 for (int i = 0; i < 14; ++i) { //依次處理每一種狀態(tài)

44 SYMBOL *pTbl = aConvTbl[i]; //為加快運(yùn)算，節(jié)省代碼，設(shè)臨時(shí)變量

45 for (vector<SYMBOL>::iterator j = Set.begin(); j != Set.end();) {

46 if (*j != pTbl[0]) {

47 ++j; //不是指定符號(hào)，遍例下一個(gè)

48 continue;

49 } //如果指定了前面或后面相鄰的符號(hào)則驗(yàn)證其是否存在

50 if (pTbl[1] != UN && (j == Set.begin() || *(j - 1) != pTbl[1])) {

51 ++j; //存在的符號(hào)與指定的不符，結(jié)果錯(cuò)誤

52 continue;

53 }

54 if (pTbl[2] != UN && (j == Set.end() - 1 || *(j + 1) != pTbl[2])) {

55 ++j; //存在的符號(hào)與指定的不符，結(jié)果錯(cuò)誤

56 continue;

57 } //刪除前后的符號(hào)(如果指定)

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]; //當(dāng)前符號(hào)變更為指定的目標(biāo)符號(hào)

61 }

62 }

63 return (Set.size() == 1 && Set.front() == SE); //返回結(jié)果

64 }

65 //主函數(shù)

66 int main(void) {

67 vector<SYMBOL> Set;

68 for (string str; cin >> str && str != "#";) { //循環(huán)讀入每個(gè)單詞

69 int nDot = str.find('.'); //如果單詞中發(fā)現(xiàn)句點(diǎn)，則認(rèn)為句子結(jié)束

70 if (nDot == str.npos) { //沒有發(fā)現(xiàn)句點(diǎn)

71 Set.push_back(Token2Status(str)); //將單詞轉(zhuǎn)為符號(hào)后存入語(yǔ)句

72 continue;

73 } //以下為發(fā)現(xiàn)句點(diǎn)，即遇到句子結(jié)束

74 str.erase(str.length() - 1); //刪除句點(diǎn)

75 if (!str.empty()) { //單詞不為空則加入語(yǔ)句

76 Set.push_back(Token2Status(str));

77 } //以下進(jìn)行詞法分析并輸出結(jié)果

78 cout << (ParseSentence(Set) ? "Good" : "Bad!") << endl;

79 Set.clear(); //清空語(yǔ)句，準(zhǔn)備處理下一條語(yǔ)句

80 }

81 return 0;

82 }<BR>