Analysis
分析
對于沒學(xué)過編譯原理的同學(xué)來說，這道題的難度比較大。題目中的語法定義由“產(chǎn)生式”給出，這里面用到了正則表達(dá)式的一些基本符號。一個產(chǎn)生式定義一個構(gòu)造（推導(dǎo)）規(guī)則，前面是可推導(dǎo)出的符號，箭頭后面指向的是符號序列，豎線“|”表示“或著”。舉例而言：
A → a | e | i | o | u
上式的義意是a、e、i、o、u中任意一個符號都可以用符號A來表示（推導(dǎo)出A）。
<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>
上式的義意是：<predname> <verbpred> <predname>三個符號從左至右依次排列，可以用符號<statement>來表示，<predname> <verbpred>也可以用<statement>來表示，具體選用哪一種，就要看制定的推導(dǎo)策略了。題目要求判斷任意給定的句子的語法是否正確，也就是要用該文法來推導(dǎo)句子，如果能推出sentence符號就算是正確的。
通過對產(chǎn)生式進(jìn)行語法分析可知，該文法不存在二義性，但它并不是一個正則文法，需要對其進(jìn)行轉(zhuǎn)換。文法中PREDA是終結(jié)符號（除了謂詞或名稱外，沒有其它符號可以推導(dǎo)出它們），它可以推導(dǎo)出predstring，而predstring又可以作為PREDA的前綴推導(dǎo)出predstring，那么predstring的正則表達(dá)式應(yīng)該為：
PREDA+
上式中“+”號的意思是一個或多個PREDA連起來形成的串。我們還可以看到，predstring除了在它自身的產(chǎn)生式之外，其它地方都是用于后綴，因此多個連續(xù)的predstring可以直接合并，不會造成二義性問題。那么產(chǎn)生應(yīng)改寫為：
PREDA → PREDA PREDA
這樣所有連續(xù)的多個PREDA都生成為單個PREDA，再轉(zhuǎn)為predstring即可：
<predstring> → PREDA
NAM、DA和BA也是終結(jié)符，但它們的產(chǎn)生式?jīng)]有自循環(huán)，不用變了。具體要說明什么是自循環(huán)，則要扯出有限自動機(jī)（DNF）、閉包、狀態(tài)圖等一大堆概念了，這些不是本文的重點，恕不贅述！
還要需要處理的是A，predstring可以直接推導(dǎo)出preds，而preds又可以作為A的前綴推導(dǎo)出preds自己，那么preds的產(chǎn)生式可以改寫為：
<predstring> → <predstring> A <predstring>
<preds> → <predstring>
畫個狀態(tài)圖，一看便知。最后一個要處理的是：
<statement> → <predname> <verbpred> <predname> | <predname> <verbpred>
顯然predname和verbpred可以作為一個整體，為了簡化產(chǎn)生式，我們另設(shè)一個符號predverb：
<predverb> → <predname> <verbpred>
這樣statement的產(chǎn)生式就可改寫為正則文法：
<statement> → <predverb> <predname> | <predverb>
本文導(dǎo)航
- 第1頁: 首頁
- 第2頁: Loglan 語言分析
- 第3頁: 下面是處理好的正則文法
- 第4頁: Loglan問題解決方案
喜歡 
頂
難過
囧
圍觀
無聊
