二元运算
二元运算相对于上一节的一元运算，虽然只是多了一个操作数，但引入了很多问题，主要包括BNF左递归，优先级，操作数类型、和求值顺序等。
BNF左递归
Lua中二元运算语句的完整语法如下：
exp ::= nil | false | true | Numeral | LiteralString | ‘...’ | functiondef |
prefixexp | tableconstructor | exp binop exp | unop exp
简单起见，其他部分简化为OTHERS，得到：
exp ::= exp binop exp | OTHERS
是左递归规则，需要按照之前介绍的方法来消除左递归，得到：
exp ::= OTHERS A'
A' := binop exp A' | Epsilon
之前的exp()函数只是实现了上面第一行的OTHERS部分，现在要加上第二行的A'部分，也是递归引用，使用循环来实现。修改exp()函数结构如下：
fn exp(&mut self) -> ExpDesc {
// OTHERS
let mut desc = match self.lex.next() {
// 这里省略原有的各种OTHERS类型处理
};
// A' := binop exp A' | Epsilon
while is_binop(self.lex.peek()) {
let binop = self.lex.next(); // 运算符
let right_desc = self.exp(); // 第二个操作数
desc = self.process_binop(binop, desc, right_desc);
}
desc
}
其中对第二个操作数right_desc也是递归调用exp()函数来读取，这就导致一个问题：优先级。
优先级
上一节的一元运算语句中，也是递归调用exp()函数来读取操作数，但因为只有一个操作数，所以并不需要优先级，或者说所有一元运算符的优先级都相等。并且一元运算符都是右结合的。比如下面两个连续一元运算的例子，都是按照从右向左的顺序执行，而跟具体运算符无关：
~ -10，先取负，再按位取反，- ~10，先按位取反，再取负。
但对于二元运算语句，就要考虑优先级了。比如下面两个语句：
a + b - c，先执行前面的加法，再执行后面的减法，a + b * c，先执行后面的乘法，再执行前面的加法。
对应到上面的exp()函数代码中，开头的OTHERS部分读取到第一个操作数a；然后while循环内读取到运算符+；再然后递归调用exp()函数读取右操作数，此时就需要计较下。还以上面两个语句为例：
a + b - c，读到b就结束并作为右操作数；然后执行加法a + b；然后再次循环处理后面的- c部分；a + b * c，读到b之后还要继续往下，读取并执行整个b * c并将执行结果作为右操作数；然后执行加法；并结束循环。
- +
/ \ / \
+ c a *
/ \ / \
a b b c
那么在语法分析时，如何判断是上述哪种情况？读到b后，是停止解析先算加法，还是继续解析？这取决于下一个运算符和当前运算符的优先级：
- 下一个运算符优先级不大于当前运算符时，就是第一种情况，停止解析，而先完成当前的运算；
- 下一个运算符优先级大于当前运算符时，就是第二种情况，需要继续解析。
为此，参考Lua语言中给所有运算符优先级列表：
or
and
< > <= >= ~= ==
|
~
&
<< >>
..
+ -
* / // %
unary operators (not # - ~)
^
由上往下，优先级依次变高。其中连接符..和求幂^都是右结合，其他运算符都是左结合。上面列出的判断规则里，对于相等优先级的情况是停止解析（而非继续解析），所以默认是左结合。于是对于2个右结合的运算符需要特殊处理，即给他们向左和向右定义不同的优先级，向左的更高，这样就会变成右结合。
综上，定义优先级函数：
fn binop_pri(binop: &Token) -> (i32, i32) {
match binop {
Token::Pow => (14, 13), // right associative
Token::Mul | Token::Mod | Token::Div | Token::Idiv => (11, 11),
Token::Add | Token::Sub => (10, 10),
Token::Concat => (9, 8), // right associative
Token::ShiftL | Token::ShiftR => (7, 7),
Token::BitAnd => (6, 6),
Token::BitNot => (5, 5),
Token::BitOr => (4, 4),
Token::Equal | Token::NotEq | Token::Less | Token::Greater | Token::LesEq | Token::GreEq => (3, 3),
Token::And => (2, 2),
Token::Or => (1, 1),
_ => (-1, -1)
}
}
对于不是二元运算符的Token，则返回-1，即最低的优先级，无论当前运算符是什么，都可以停止解析。按照Rust的习惯做法，这个函数应该返回Option<(i32, i32)>类型，然后不是二元运算符的Token就返回None。但是返回-1在调用的地方更简单，不需要多一次Option的处理。
这个函数看上去是Token类型的属性，所以貌似适合定义为Token的方法。但Token类型是在lex.rs中定义的；而优先级是语法分析的概念，应该在parse.rs中实现。Rust语言不允许在类型的非定义的文件中添加方法。所以上述函数就在parse.rs文件中定义为个普通函数（而非其他函数那样是ParseProto的方法）。
现在，按照优先级，再次修改exp()函数：
fn exp(&mut self) -> ExpDesc {
self.exp_limit(0)
}
fn exp_limit(&mut self, limit: i32) -> ExpDesc {
// OTHERS
let mut desc = match self.lex.next() {
// 这里省略原有的各种OTHERS类型处理
};
// A' := binop exp A' | Epsilon
loop {
let (left_pri, right_pri) = binop_pri(self.lex.peek());
if left_pri <= limit {
return desc; // 停止解析
}
// 继续解析
let binop = self.lex.next();
let right_desc = self.exp_limit(right_pri);
desc = self.process_binop(binop, desc, right_desc);
}
}
首先为exp()增加一个limit参数，作为当前运算符的优先级，限制后续的解析范围。但这个参数属于语句内部概念，对于此函数的调用者而言，无需知晓此参数；所以增加exp_limit()这个实际处理函数，而把exp()变成一个外层封装函数，用limit=0来调用前者。初始调用之所以使用limit=0，是因为0小于binop_pri()函数中定义的任何二元运算符优先级，所以第一个运算符都会被继续解析（而不是return退出循环）；但0又大于非运算符的优先级-1，所以如果后面紧跟非运算符，也会正常退出。
上述解析代码结合了循环和递归调用，对于不熟悉算法的人来说难度很大，很难直接写出完整代码。但是依照消除左递归后的BNF规范，就可以完成循环和递归，再根据优先级加上条件退出，就可以很轻松完成这个函数。
另外，需要注意到上面运算符优先级表单中也列出了一元运算符，所以上一节解析一元运算语句时，读取操作数的表达式时，就不能使用exp()函数（初始优先级0），而应该指定初始优先级为12：
fn exp_unop(&mut self) -> ExpDesc {
self.exp_limit(12) // 12 is all unary operators' priority
}
求幂运算^的优先级居然高于一元运算符，所以语句-a^10的执行顺序是：先求幂，再取负。
求值顺序
上述解析代码有个非常隐晦的bug，是关于操作数求值的顺序。
每个操作数的处理需要2步：首先调用exp()函数读取操作数并返回ExpDesc，然后调用discharge()函数把操作数discharge到栈上以便字节码操作。二元运算有2个操作数，就一共需要4步。现在讨论下这4步的顺序。
按照当前版本的exp()函数中对二元运算的处理逻辑：
- 先读取第一个操作数，
desc； - 然后判断是二元运算后，递归调用
exp_limit()，读取第二个操作数，right_desc； - 然后在
process_binop()函数中把上述两个操作数的ExpDesc一起discharge到栈上。
简化下就是：
- 解析第一个操作数；
- 解析第二个操作数；
- discharge第一个操作数；
- discharge第二个操作数。
在解析和discharge阶段，都可能生成字节码。所以按照这个顺序，两个操作数相关的字节码是可能穿插的。比如下面的例子：
local a = -g1 + -g2
忽略前面的局部变量定义，也忽略未定义全局变量的运算会抛异常，这里重点只看后面的加法语句。用当前版本的解释器生成如下字节码序列：
constants: ['g1', 'g2']
byte_codes:
GetGlobal(0, 0) # 解析第一个操作数
GetGlobal(1, 1) # 解析第二个操作数
Neg(2, 0) # discharge第一个操作数
Neg(3, 1) # discharge第二个操作数
Add(0, 2, 3)
可以看到这里两个操作数相关的字节码是穿插的。在这个例子里，穿插并没什么问题。但有的情况下，解析第二个操作数是会影响第一个操作数的求值的，这时穿插就会造成问题。比如下面的例子：
local t = { k = 1 }
local function f(t) t.k = 100; return 2 end -- 修改t.k的值
local r = t.k + f(t)*3
对于最后一句，我们预期是1 + 2*3，但是如果按照现在的求值顺序：
- 先解析左操作数
t.k，生成ExpDesc::IndexField，但并不discharge； - 然后解析右操作数
f(t)*2，在解析过程中会执行f(t)，从而修改t.k的值； - 然后discharge左操作数，生成
GetField字节码，但此时t.k已经被上一步修改了！这里就出现了错误。实际执行的就是100 + 2*3。
综上，我们要确保两个操作数的字节码不能穿插！那么改造exp_limit()函数如下：
fn exp_limit(&mut self, limit: i32) -> ExpDesc {
// 这里省略原有的各种OTHERS类型处理
loop {
// 省略判断优先级的处理
// discharge第一个操作数！！！
if !matches!(desc, ExpDesc::Integer(_) | ExpDesc::Float(_) | ExpDesc::String(_)) {
desc = ExpDesc::Local(self.discharge_top(desc));
}
// 继续解析
let binop = self.lex.next();
let right_desc = self.exp_limit(right_pri); // 解析第二个操作数
desc = self.process_binop(binop, desc, right_desc);
}
}
在解析第二个操作数前，先把第一个操作数discharge到栈上。不过对于常量类型则无需这么处理，因为：
- 常量不会像上面的例子那样，被第二个操作数影响；
- 常量还要在后续尝试直接折叠。
至此完成二元运算语法分析的exp_limit()函数改造。至于二元运算的具体处理process_binop()函数，下面介绍。
字节码
上一节介绍的一元运算只有1个操作数，分2种情况：常量和变量，常量就直接求值，变量就生成字节码。所以每个一元运算都只有一个字节码。二元运算因为涉及2个操作数，所以复杂些。
首先，二元运算符虽然大部分都是数值计算，但因为Lua的元表功能，类似运算符重载，所以其他类型常量（比如字符串、bool等）都可能是合法的操作数。在解析一元运算时，这些类型的常量是直接报错，但对于二元运算需要到执行阶段才能判断是否合法。
其次，如果两个操作数都是数字类型常量（整数和浮点数），那么就可以在语法分析时直接计算出结果，称之为常量折叠。
否则，就生成字节码，由虚拟机执行。类似之前已经支持的读取全局变量和读表操作，每个二元运算符也都设置3个字节码，分别处理右操作数的3种类型：栈上变量、常量、小整数。
而左操作数统一discharge到栈上，因为左操作数是常量的情况并不多见。如果也为常量和小整数类型增加对应的字节码，比如10-a这种语句，那字节码类型就太多了。
最后，对于满足交换律的加法和乘法，如果左操作是常量，那么可以交换，比如10+a可以先转换为a+10，由于右操作数10是小整数，就可以使用AddInt字节码。
ExpDesc
类似上一节介绍的一元运算引入的新ExpDesc类型，二元运算因为多了一个操作数，所以也需要一个新的类型：
enum ExpDesc {
UnaryOp(fn(u8,u8)->ByteCode, usize), // (opcode, operand)
BinaryOp(fn(u8,u8,u8)->ByteCode, usize, usize), // (opcode, left-operand, right-operand)
语法分析
至此介绍完二元运算语句的基本要求。下面看代码实现，即exp()函数中调用的process_binop()函数：
fn process_binop(&mut self, binop: Token, left: ExpDesc, right: ExpDesc) -> ExpDesc {
if let Some(r) = fold_const(&binop, &left, &right) { // 常量折叠
return r;
}
match binop {
Token::Add => self.do_binop(left, right, ByteCode::Add, ByteCode::AddInt, ByteCode::AddConst),
Token::Sub => self.do_binop(left, right, ByteCode::Sub, ByteCode::SubInt, ByteCode::SubConst),
Token::Mul => self.do_binop(left, right, ByteCode::Mul, ByteCode::MulInt, ByteCode::MulConst),
// 省略更多类型
}
}
首先尝试常量折叠。这部分功能因为涉及整数和浮点数类型的处理，所以在下一节介绍。因为两个操作数并不一定是常量，并不一定能够折叠，如果没有成功折叠，那么后续还要使用操作符和两个操作数，所以这里fold_const()函数只能传入引用。
如果不是常量，不能折叠，那么调用do_binop()函数来返回ExpDesc。这里把enum的tag作为函数来使用，在之前已经介绍过了，这里不再介绍。
下面来看do_binop()函数：
fn do_binop(&mut self, mut left: ExpDesc, mut right: ExpDesc, opr: fn(u8,u8,u8)->ByteCode,
opi: fn(u8,u8,u8)->ByteCode, opk: fn(u8,u8,u8)->ByteCode) -> ExpDesc {
if opr == ByteCode::Add || opr == ByteCode::Mul { // commutative
if matches!(left, ExpDesc::Integer(_) | ExpDesc::Float(_)) {
// swap the left-const-operand to right, in order to use opi/opk
(left, right) = (right, left);
}
}
let left = self.discharge_top(left);
let (op, right) = match right {
ExpDesc::Integer(i) =>
if let Ok(i) = u8::try_from(i) {
(opi, i as usize)
} else {
(opk, self.add_const(i))
}
ExpDesc::Float(f) => (opk, self.add_const(f)),
_ => (opr, self.discharge_top(right)),
};
ExpDesc::BinaryOp(op, left, right)
}
首先，判断如果是加法或乘法，并且左操作数是数字常量，则交换两个操作数，为了后续能够生成xxCoust或者xxInt的字节码。
然后，把左操作数discharge到栈上；
然后，再判断右操作数类型是否为数字常量，否则也discharge到栈上。
最后，生成ExpDesc::BinaryOp。
至此，二元运算语句的语法分析基本完成。
整数和浮点数
至此，我们介绍了二元运算的大致解析过程，但还有一个细节，即对整数和浮点数类型的不同处理规则。由于这方面内容也不少，而且跟上述主要的解析过程相对独立，所以在下一节中单独介绍。