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>
本文导航
- 第1页: 首页
- 第2页: Loglan 语言分析
- 第3页: 下面是处理好的正则文法
- 第4页: Loglan问题解决方案
