语法：如何添加优先级

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不会使用总和运算符解析表达式。 （它确实解析括号内的任何内容。但是这些都是括号内的内容。）

这就是语法中隐含关联性和优先级的意义。