写解析器是解决这个编程挑战的正确方法吗？

Question

看看这个编程挑战吧。

https://gist.github.com/1083219

我们已经建立了一个严格语法将消息发送新的通信协议。 我们需要编写一个函数来确定给定的消息是否在语法上有效。

下面是规则：

1. 有在协议15个有效性状：小写字母“a”到“J” 和大写字符“Z”，“M”，' K'，'P'和'Q'。
2. 孤立的每个小写字符都是一个有效的消息，例如'a'是一个有效的消息。
3. 如果σ是一个有效的消息，那么Zσ也是如此。
4. 如果σ和τ是有效消息，那么Mστ，Kστ，Pστ和Qστ也是如此。
5. 其他所有消息均无效。

用您选择的语言编写函数来检查消息是否有效。 输入由一系列由空格分隔的潜在消息组成，并且只包含上述15个字符，其中包含 。

输出包含每条潜在消息一行，如果消息有效，则后跟'有效'，如果消息无效，则输出'无效'。

下面是一些输出示例。

Input Output 
Qa Zj Qa INVALID 
MZca  Zj VALID 
Khfa  MZca VALID 
     Khfa INVALID 

有很多方法来解决这个问题，包括正则表达式，由性格解析字符。我想知道别人怎么看待如何解决这个问题。

我认为一个简单的解析器可能是最好的方法。首先编写语法，然后实现解析器。

Answer 1

我想你应该能够以相当简单的递归字符串函数f做到这一点：

1. 看串
2. 如果它是一个小写字母的第一个字符，返回剩下的字符串的
3. 如果是Z，返回f(the rest of the string)
4. 如果是M, K, P, or Q，然后返回f(f(the rest of the string))
5. 否则，返回整个字符串

然后在功能g如果f返回空字符串，否则为假，则返回true这个包起来。为每条消息执行此操作。

这工作，因为你描述的语法是一个简单的树形结构：有两个子女的所有节点都M, K, P, or Q，有一个孩子的任何节点Z，任何叶子是一个小写字母。 f总是消耗树上的一个节点，并返回树的其余部分（包括兄弟），并在格式错误的树上返回一个非空字符串。