语法：如何添加优先级

Question

假设我有以下用于简单计算器语言的上下文无关语法：

S->TS'
S'->OP1 TE'|e
T->FT'
T'->OP2 FT'|e
F->id|(S)
OP1->+|-
OP2->*|/

可以看到，* 和 / 的优先级高于 + 和 -。但是，如何添加另一级优先级？例如指数、^、（例如：3^2=9）或其他什么？请解释一下您的程序以及如何到达那里的原因，以便我可以为其他操作员做这件事。

Answer 1

这是一个更易读的语法：

\n\n

expr: sum\n\nsum : sum add_op term\n    | term\n\nterm: term mul_op factor\n    | factor\n\nfactor: ID\n      | '(' expr ')'\n\nadd_op: '+' | '-'\nmul_op: '*' | '/'\n

\n\n

这可以使用相同的模式轻松扩展：

\n\n

expr: bool\n\nbool: bool or_op conj\n    | conj\n\nconj: conj and_op comp\n    | comp\n\n/* This one doesn't allow associativity. No a < b < c in this language */ \ncomp: sum comp_op sum\n\nsum : sum add_op term\n    | term\n\nterm: term mul_op factor\n    | factor\n\n/* Here we'll add an even higher precedence operators */\n/* Unlike the other operators, though, this one is right associative */\nfactor: atom exp_op factor\n    | atom\n\natom: ID\n    | '(' expr ')'\n\n/* I left out the operator definitions. I hope they are obvious. If not,\n * let me know and I'll put them back in\n */\n

\n\n

我希望那里的模式或多或少是明显的。

\n\n

这些语法在递归下降解析器中不起作用，因为递归下降解析器会因左递归而阻塞。您所拥有的语法已经通过左递归消除算法运行，您也可以对上面的语法执行此操作。但请注意，消除左递归或多或少会消除左递归和右递归之间的差异，因此在使用递归下降语法识别解析后，您需要根据您对运算符结合性的了解来修复它，因为结合性不再是语法所固有的。

\n\n

对于这些简单的产生式，消除左递归非常简单，只需两个步骤。我们从一些非终结符开始：

\n\n

foo: foo foo_op bar\n   | bar\n

\n\n

我们翻转它，使其成为右结合：

\n\n

foo: bar foo_op foo\n   | bar\n

\n\n

（如果运算符最初是右结合的，如上面的求幂，则不需要此步骤。）

\n\n

然后我们需要左因子，因为 LL 解析要求非终结符的每个替代项都有一个唯一的前缀：

\n\n

foo : bar foo'\nfoo': foo_op foo\n    | \xce\xb5\n

\n\n

对上面的每个递归产生式执行此操作（即，除了expr、comp和 之外的所有递归产生式）atom的所有递归产生式）执行此操作将产生一个与您开始使用的语法类似的语法，只是具有更多运算符。

\n\n

顺便强调一下，这里并没有什么神秘的魔法力量在起作用。例如，当语法说：

\n\n

term: term mul_op factor\n    | factor\n

\n\n

它的意思是，a term（或乘积，如果你愿意的话）不能是乘法的右侧参数，但它可以是左侧参数。它还说，如果您正处于产品有效的阶段，那么您实际上并不需要带有乘法运算符的东西；您可以使用乘法运算符。你可以使用 afactor代替。但显然你不能使用求和，因为factor不使用求和运算符解析表达式。（它确实解析括号内的任何内容。但这些都是括号内的内容。）

\n\n

这就是语法中隐含的结合性和优先级的含义。

\n