语法 : How to add a level of precedence

Question

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

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

可以看出 * 和/比 + 和 - 具有更高的优先级。但是，如何添加另一个优先级？例如指数，^，(例如:3^2 = 9)或其他东西？请解释您的程序和您如何到达那里的推理，以便我可以为其他运营商做这件事。

Answer 1

这是一个更具可读性的语法:

expr: sum

sum : sum add_op term
    | term

term: term mul_op factor
    | factor

factor: ID
      | '(' expr ')'

add_op: '+' | '-'
mul_op: '*' | '/'

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

expr: bool

bool: bool or_op conj
    | conj

conj: conj and_op comp
    | comp

/* This one doesn't allow associativity. No a < b < c in this language */ 
comp: sum comp_op sum

sum : sum add_op term
    | term

term: term mul_op factor
    | factor

/* Here we'll add an even higher precedence operators */
/* Unlike the other operators, though, this one is right associative */
factor: atom exp_op factor
    | atom

atom: ID
    | '(' expr ')'

/* I left out the operator definitions. I hope they are obvious. If not,
 * let me know and I'll put them back in
 */

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

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

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

foo: foo foo_op bar
   | bar

然后我们翻转它，使它是正确的关联:

foo: bar foo_op foo
   | bar

(如果运算符最初是右结合的，就像上面的求幂一样，则不需要这一步。)

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

foo : bar foo'
foo': foo_op foo
    | ε

对上面的每个递归产生式(即，除了 expr、comp 和 atom 之外的所有递归产生式)都将产生一个语法这看起来像您开始时使用的那个，只是运算符更多。

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

term: term mul_op factor
    | factor

它的意思是 term(或乘积，如果您愿意)不能是乘法的右手参数，但它可以是左手参数。这也意味着，如果您正处于产品有效的阶段，那么您实际上并不需要乘法运算符；您可以改用 factor。但显然您不能使用求和，因为 factor 不使用求和运算符解析表达式。 (它确实解析括号内的任何内容。但那些是括号内的内容。)

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