编译器:如何定义这个语法？

Question

我必须为我正在创建的某个编译器编写语法:二元运算符&&和||，以及一元运算符#和*，其方式如下：

I)优先于&&的||

II) &&向左关联:A && B && C表示((a&&b)&&c)

III) ||与右侧关联

IV)一元运算符具有相同的优先级，并且多于二元运算符

我是这样想的：

E -> E || T | E && T | T
T -> T # F | T * F
F -> (E) | Numbers
Numbers -> 0 | 1 | 2 | 3 | ... | 9

这会是错的吗？有什么想法吗？

Answer 1

对于像这样的简单表达式，您总是可以从最低优先级开始。

所以你想要有一堆&&ed表达式，每个表达式都是同样有先例的一元运算符的||ed表达式。

在写下这一点之前，先看看这两条规则：

E -> E + T

和

E -> T + E

第一条规则使+向左关联，而第二条规则使其向右关联(想想看)。所以你希望你的&&是左关联的，||是右关联的：

E -> E '&&' T | T         # left associative &&
T -> F '||' T | F         # right associative ||

一元运算符的规则相当简单：

F -> '#' F | '*' F | N    # apply unary operators without precedence from right to left

最后，最有先例的是圆括号，就好像你有一个牢不可破的令牌。除了，在括号内你可以有任何表达式：

N -> '(' E ')' | number

number本身可以由正则表达式表示，如'[1-9][0-9]*'