我想设计一个组合器以解析命题逻辑。这是一个简单的BNF：
<sentence> ::= <atomic-sentence> | <complex-sentence>
<atomic-sentence> ::= True | False | P | Q | R
<complex-sentence> ::= (<sentence>)
| <sentence> <connective> <sentence>
| ¬<sentence>
<connective> ::= ∧ | ∨ | ⇒ | ⇔
问题是语法是左记录，这导致了无限的循环：句子可以是一个复杂的句子，可以从句子开始，这可以是一个复杂的句子，……永远。这是导致此问题的示例句子：
P∧Q
是否有一种简单的方法来修复语法，以便适用于解析器组合器？谢谢。
fwiw，我在F＃中使用FPARSEC，但我认为任何解析器组合库都会有相同的问题。
fparsec可以使用OperatorPrecedenceParser类处理Infix运算符，您只需要指定与哪些关联性和优先级的运算符，而无需为您的infix表达式编写语法。其余的答案将解释如何在不适用的情况下，对于没有同等课程的解析器组合者，或者如果您只是普通不想使用它或至少对没有问题的问题感兴趣。
解析器组合者倾向于不支持左记录，但它们确实倾向于支持重复。幸运的是，可以使用*重复运算符将表格的左征询规则重写为<a> ::= <c> <b>*。如果您然后在结果列表上左转，则可以构造一棵看起来像是从原始语法中获得的解析树。
因此，如果我们首先将<complex-sentence>内联CC_5进入<sentence>，然后应用上述模式，我们将获得<a> = <sentence>，<b> = <connective> <sentence>和<c> = <atomic-sentence> | '(' <sentence> ')' | ¬<sentence>，从而在转换后产生以下规则：
<sentence> ::= ( <atomic-sentence>
| '(' <sentence> ')'
| ¬<sentence>
)* <connective> <sentence>
为提高可读性，我们将把括号的部分放入其自身的规则中：
<operand> ::= <atomic-sentence>
| '(' <sentence ')'
| ¬<sentence>
<sentence> ::= <operand> (<connective> <sentence>)*
现在，如果您尝试此语法，您会注意到一些奇怪的东西：*创建的列表只会包含一个元素(或无(。这是因为，如果有两个以上的操作数，则对<sentence>的右手调用将吞噬所有操作数，从而形成右求和解析树。
因此，上面的语法实际上等同于此(或者语法是模棱两可的，但是解析器组合者会将其视为等同于此(：
<sentence> ::= <operand> <connective> <sentence>
这是因为原始语法是模棱两可的。模棱两可的定义<s> ::= <s> <c> <s> | <o>可以解释为左获取的<s> ::= <s> <c> <o> | <o>(将创建左求和解析树(或右回收<s> ::= <o> <c> <s> | <o>(Right-sysociative Parse Tree(。因此，我们应该首先选择其中一种形式来消除歧义，然后在适用的情况下应用转换。
因此，如果我们选择左记录表格，我们最终以：
<sentence> ::= <operand> (<connective> <operand>)*
确实会创建具有多个元素的列表。另外，如果我们选择正确的恢复规则，我们可以将其作为IS(无需重复运算符(，因为没有左记录可以消除。
正如我所说，我们现在可以通过从左获取版本中获取列表，并通过获取右回复版来获得左求的树，或者左转。但是，这两种选项都将使我们拥有一棵树，将所有操作员视为具有相同优先级的树。
要修复优先级，您可以将分流码算法之类的内容应用于列表，也可以首先重写语法以考虑优先级，然后应用转换。