表的读写和BNF

在前面两节引入ExpDesc并对现有语法分析进行改造之后，本节实现表的读写。

Lua中表的索引支持两种方式，分别举例如下：t["k"]和t.k，其中后者是前者的特殊形式。表的读写操作都需要用到表的索引。需要在ExpDesc中增加表索引的类型。

表的读写操作本身并不复杂，但会使得其他语句突然变得复杂起来：

• 表的读操作可能有连续多级，比如t.x.y，那么在解析表达式时无法立即判断结束，而需要peek下一个Token来判断。

• 表的写操作，即赋值语句。现在的赋值语句只支持“变量”的赋值，即左值只支持一个Token::Name。如要增加表索引的支持，对左值的处理要重新实现。只解析一个Token不行，而是要解析完一个左值才行。那怎么才算一个完整的左值？比如并不是所有的表达式都可以作为左值，比如函数调用或者表构造都不行。

• 之前区分赋值语句和函数调用语句，是根据第2个Token，如果是等号=就是赋值语句。现在要支持表的写操作，比如t.k = 123，那么第2个Token是点.，而不是等号=，但仍然是赋值语句。之前的判断方法就失效了。那有什么新的办法来区分赋值语句和函数调用语句呢？

第一个读操作问题好解决。后面两个写操作相关的问题就很难了，我们现在无法准确地回答，只能猜测答案。这就引申出一个更大的问题，就是之前的语法分析都是靠猜的！比如局部变量的定义语句的格式等，都是根据使用Lua语言的经验猜测的，而不能保证其是否准确、完整。但之前都比较简单，可以猜个大概。另外为了不打断整个项目的节奏，也就没有深究这个问题。现在要引入表的读写，语句变得复杂了，靠猜不能继续混下去了，有必要引入形式化的语法描述了。

BNF

Lua手册的最后一章名字就叫：Lua的完整语法，内容主要是一套BNF描述。我们并不需要知道BNF这个术语的含义，只需要知道这是一种形式化的语法描述方式，在这里就可以完整且准确地描述Lua语法。BNF本身的语法规则也很简单，大部分一目了然，这里只列两个：

• {A} 代表0个或多个A
• [A] 代表可选的1个A

Lua的代码段称为chunk，所以以chunk的定义为入口，列出几条描述：

chunk ::= block

block ::= {stat} [retstat]

stat ::=  ‘;’ | 
	 varlist ‘=’ explist | 
	 functioncall | 
	 label | 
	 break | 
	 goto Name | 
	 do block end | 
     while exp do block end | 
	 repeat block until exp | 
	 if exp then block {elseif exp then block} [else block] end | 
	 for Name ‘=’ exp ‘,’ exp [‘,’ exp] do block end | 
	 for namelist in explist do block end | 
	 function funcname funcbody | 
	 local function Name funcbody | 
	 local attnamelist [‘=’ explist] 

由这些规则可以得到：一个chunk包含一个block。一个block包含0个或多个stat和一个可选的retstat。一个stat有很多种类型的语句。这其中我们已经实现了functioncall和local两个语句，后续把剩下的类型逐个实现就完成了Lua的全部语法（虽然离完整的Lua语言还差很远）。

我不太理解这里chunk和block的区别是什么？为什么要单独列两个？

就是说，我们后续就按照这套规范来实现解释器，再也不用靠猜的了!挑几条跟我们之前的对比下，比如局部变量定义语句，就可以发现应该要支持多变量，多初始化表达式，甚至没有初始化表达式。这就看出来我们之前的语句解析是非常不完善的。这节后面会根据BNF来完善我们已经支持的语句。当下先从中找出跟表索引相关的规则：

var ::=  Name | prefixexp ‘[’ exp ‘]’ | prefixexp ‘.’ Name 

exp ::=  nil | false | true | Numeral | LiteralString | ‘...’ | functiondef | 
	 prefixexp | tableconstructor | exp binop exp | unop exp 

prefixexp ::= var | functioncall | ‘(’ exp ‘)’

functioncall ::=  prefixexp args | prefixexp ‘:’ Name args 

一眼看上去有些复杂。以var为例分析下。这里var推导出3种情况，第一个Name是简单变量，后面两个就是表索引，分别是通用方式和字符串索引语法糖。涉及到了prefixexp和exp。其中exp跟我们目前实现的exp()函数很类似了，只是我们还缺少了一些情况，也是需要后续补上的。另外Name是直接在exp()函数里的，现在要挪到var里。

消除左递归

这里有个大问题，上述3条规则是有递归引用的。比如：

• var引用了prefixexp而后者又引用了var；
• exp引用了prefixexp而后者又引用了exp。

但这两个例子又有本质区别。

对于第一个例子，带入var后展开下，就是

prefixexp ::= Name | prefixexp ‘[’ exp ‘]’ | prefixexp ‘.’ Name | prefixexp args | prefixexp ‘:’ Name args | ‘(’ exp ‘)’

问题在于推导规则的第2和第3项也是prefixexp开头的。那在语法分析时，比如读到一个Name，即可以匹配第1项，也可以匹配第2和第3项，这就无法判断应该选择哪条规则了。这就很头疼，我当时花了两天时间在这个问题上，想了各种土办法也没有解决。后来上网搜索发现了“消除左递归”这个概念，才隐约回忆起来这是编译原理课程上的必考题目。而且消除是有标准方法的：对于包含左递归的规则，都可以表达为如下形式：

A := Aα | β

然后就可以改写为如下形式：

A := βA’
A’ := αA’ | ε

其中ε是未匹配。这样就消除了左递归。拿上面的prefixexp举例，先套用上述标准形式，可得：

α = ‘[’ exp ‘]’ | ‘.’ Name | args | ‘:’ Name args
β = Name | ‘(’ exp ‘)’

然后再带入上述改写公式，可得：

prefixexp := ( Name | ‘(’ exp ‘)’ ) A’
A’ := ( ‘[’ exp ‘]’ | ‘.’ Name | args | ‘:’ Name args ) A’ |  ε

这样我们就得到了没有左递归的规则。

而本小节最开始的第二个例子，关于exp的，虽然也有递归引用，但不是“左”递归，所以没有这个问题。

表的读操作和prefixexp

使用BNF规则的好处是，不需要想着Lua的语法，只需要照着规则实现即可。

得到上述BNF规则后，就可以完成prefixexp的解析：

    fn prefixexp(&mut self, ahead: Token) -> ExpDesc {
        let sp0 = self.sp;

        // beta
        let mut desc = match ahead {
            Token::Name(name) => self.simple_name(name),
            Token::ParL => { // `(` exp `)`
                let desc = self.exp();
                self.lex.expect(Token::ParR);
                desc
            }
            t => panic!("invalid prefixexp {t:?}"),
        };

        // A' = alpha A'
        loop {
            match self.lex.peek() {
                Token::SqurL => { // `[` exp `]`
                    self.lex.next();
                    let itable = self.discharge_if_need(sp0, desc);
                    desc = match self.exp() {
                        ExpDesc::String(s) => ExpDesc::IndexField(itable, self.add_const(s)),
                        ExpDesc::Integer(i) if u8::try_from(i).is_ok() => ExpDesc::IndexInt(itable, u8::try_from(i).unwrap()),
                        key => ExpDesc::Index(itable, self.discharge_top(key)),
                    };

                    self.lex.expect(Token::SqurR);
                }
                Token::Dot => { // .Name
                    self.lex.next();
                    let name = self.read_name();
                    let itable = self.discharge_if_need(sp0, desc);
                    desc = ExpDesc::IndexField(itable, self.add_const(name));
                }
                Token::Colon => todo!("args"), // :Name args
                Token::ParL | Token::CurlyL | Token::String(_) => { // args
                    self.discharge(sp0, desc);
                    desc = self.args();
                }
                _ => { // Epsilon
                    return desc;
                }
            }
        }
    }

代码第一段对应上述的β，即Name | ‘(’ exp ‘)’。

第二段的循环对应的是上述的A’ := αA’ | ε，如果匹配的是α部分即‘[’ exp ‘]’ | ‘.’ Name | args | ‘:’ Name args，那么解析完后循环继续；如果没有匹配，则对应ε，就退出循环。这里这个循环支持了很多连续的操作，比如t.f()，就是一个表索引接一个函数调用。或者更多的连续操作如t.t.t.k和f()()()。如果按照之前章节的土方法，想到一个功能就做一个功能，要支持这种连续操作就很难了，很难实现也很难想到。但按照BNF来，就可以正确且完整地实现。

对应表的构造时的3类字节码，即key为栈上变量、字符串常量和小整型，这里也新增3个ExpDesc的类型，分别为Index、IndexField和IndexInt。在discharge时，新增3个对应的字节码，GetTable、GetField和GetInt。这样自然而然就解决了本节开头的第一个问题，也就是实现了表的读操作，而且是正确且完整地实现！

依照BNF规则来编码的另一个特点是，就只能看懂每个匹配分支内部的处理逻辑了，而看不清楚每个分支间的整体关系了。这就像解物理应用题，首先分析物理原理，列出方程，其中的每一项都有对应的物理含义；但是之后在求解方程时，具体求解步骤就已经完全脱离了物理对应关系，就是一个数学工具。

上面列出了prefixexp()函数，另外exp()函数的实现也类似，这里省略。

表的写操作和赋值语句

在按照BNF实现了prefixexp和exp后，就可以解决本节开头的关于表的写操作的问题。按照BNF重新实现赋值语句，即可解决问题。这次要实现的是“完整的赋值语句”，终于不用再强调是“变量赋值语句”了。

赋值语句虽然看上去跟局部变量定义语句很像，但实际完全不一样，要复杂的多。BNF中赋值语句定义如下：

varlist ‘=’ explist
varlist ::= var {‘,’ var}
var ::=  Name | prefixexp ‘[’ exp ‘]’ | prefixexp ‘.’ Name 

赋值符=左边是var列表。var展开为3个种类。第一个Name是变量，目前支持局部变量和全局变量，后续引入闭包后还会支持upvalue。后面两个都是表索引。由此可以看到赋值只支持这几种，而其他类型比如函数调用就不支持赋值。再看=右边，是表达式列表，直接使用已经完成的exp()函数解析。

看完赋值语句的BNF语法规则，还有3个语义规则。

首先，=左右两边的变量数跟表达式数不相等时的做法：

• 如果两者相等，则逐一赋值；
• 如果变量数小于表达式数，则变量列表跟对应的表达式列表逐一赋值，而额外多出的表达式忽略；
• 如果变量数大于表达式数，则表达式列表跟对应的变量列表逐一赋值，而额外多出的变量被赋值为nil。

其次，如果=右边最后一个表达式有多个值（比如函数调用和可变参数），则会尽量展开。不过我们现在还不支持这两个类型，所以暂时忽略这种情况。

最后，先对=右边的所有表达式求值，然后再赋值。而不是边求值边赋值。比如下面Lua语句，应该先对右边两个表达式b和a求值得到2和1，然后再分别赋值给左边的a和b。于是完成了两个变量的交换。但是如果边求值边赋值，就是先对右边的b求值，得到2，赋值给a。然后再对右边的a求值，得到刚被赋值的2，再赋值给b。最终结果就是两个变量都会为2。

local a, b = 1, 2
a, b = b, a  -- swap 2 variables !!!

下面的图描述了错误的执行过程：

            +-------+
    /--(1)--|   a   |<------\
    |       +-------+       |
    \------>|   b   |--(2)--/
            +-------+
            |       |

既然要先全部求值，那求得的值就要先存到一个地方，自然就是栈顶，作为临时变量。下面的图描述了正确的执行过程：

             +-------+
    /---(1)--|   a   |<-------\
    |        +-------+        |
    |  /-(2)-|   b   |<----\  |
    |  |     +-------+     |  |
    \------->|  tmp1 |-(3)-/  |
       |     +-------+        |
       \---->|  tmp2 |--(4)---/
             +-------+
             |       |            

图中，(1)和(2)是对表达式求值，放到栈顶临时位置；(3)和(4)是赋值，把栈顶临时位置的值赋给变量。

这种做法的功能是正确的，但性能比较差。因为每个赋值都需要2次操作，先求值再赋值，也就需要2条字节码。但是大部分情况下本来只需要1次操作即可，比如把一个局部变量赋值给另外一个局部变量，本来只需要一条Move字节码即可。尤其是程序中最常见的赋值语句是单个变量的赋值，单个变量就无所谓顺序了，也就不用先求值到临时变量了。所以上述这种先求值到栈顶然后再赋值的做法，就是为了少数情况的正确性，而牺牲了多数情况的性能。这种情况在编程中是比较常见的。通用的解决办法是，对多数情况增加一个quick path，比如我们现在的情况可以用如下逻辑：

if 单个变量 then
    var = exp  // 直接赋值，quick path
else // 多个变量
    tmp_vars = exp_list  // 先全部求值到临时变量 
    var_list = tmp_vars  // 再统一赋值

不过，对于这个具体问题，有更优雅的解决办法。这里的关键是，在多重赋值的情况里，最后一个变量的赋值是不依赖其他变量的赋值的，就可以直接赋值而无需先求值到临时变量的。所以新的方案是：对最后这个变量做特殊处理（直接赋值），其他变量仍然先求值再赋值。这样对于单个变量的赋值语句（单个变量自然就是最后一个变量）这种情况，就退变为直接赋值。这样即保证了多个变量的正确性，也保证了大多数情况（单个变量）的性能。漂亮！

下图描述了这种方案：对于前面的变量a先求值到栈顶临时变量，对于最后一个变量b直接赋值，然后依次把栈顶临时变量赋值给对应变量。

             +-------+
    /---(1)--|   a   |<------\
    |        +-------+       |
    |        |   b   |--(2)--/
    |        +-------+ <-------\
    \------->|  tmp1 |--(3)----/
             +-------+
             |       |

既然我们是最先执行的最后一个表达式的赋值，那么将错就错，前面的表达式也按照倒序来赋值。这样全部表达式就都是按照倒序赋值了。

至此，介绍完了赋值语句的语法和语义规则。接下来就是重写assignment()函数。函数主体逻辑如下：

1. 调用prefixexp()读取左值列表，保存为ExpDesc；
2. 调用exp()读取右值表达式列表，最后一个表达式保留ExpDesc，剩余表达式均discharge到栈顶；
3. 对齐左值和右值的数量；
4. 赋值，先把最后一个表达式赋值给最后一个左值，然后把栈顶的临时变量依次赋值给对应的左值。

具体代码这里省略。下面只详细介绍第4步，赋值。

执行赋值

赋值语句由左值和右值组成：

• 每个左值由prefixexp()函数读取，返回ExpDesc类型。但由BNF可知赋值语句只支持变量和表索引，其中变量包括局部变量和全局变量，分别对应Local和Global这2个ExpDesc类型，表索引又有Index、IndexField和IndexInt这3个ExpDesc类型，加起来一共5种类型。

• 每个右值由exp()函数读取，也返回ExpDesc类型，并且支持任意的ExpDesc类型。

综上，左边5种类型，右边N种类型（N是ExpDesc的全部类型数量），一共就有5N个组合。有点多，需要梳理下。

首先，对于左值是局部变量的情况，赋值就相当于是把表达式discharge到局部变量的栈位置。调用discharge()函数即可。这个函数已经处理了ExpDesc的全部N种类型。

剩下的4种左值类型就有些复杂了，不过这4种情况是类似的，下面先用全局变量Global类型为例介绍。

在之前的赋值小节中介绍了赋值的几种组合。对于左值是全局变量的情况，右值支持了3种表达式类型：常量、局部变量、和全局变量，当时为了简单起见，分别直接生成SetGlobalConst、SetGlobal、SetGlobalGlobal这3个字节码。现在可以预见后面会有更多类型的表达式，比如本节增加的表的读取（如t.k），还有后续要增加的如UpValue、运算（如a+b）等。如果每新增一种类型就新加一个字节码，会变得很复杂。

而且表索引和运算这种表达式需要2个参数来表示，而这系列全局变量的赋值字节码，塞不进2个参数来表示赋值的源表达式（一个字节码最多支持3个u8类型的参数，这系列字节码需要1个参数来表示目的地址，看上去是可以用2个参数来表示源表达式的。但通过luac的输出可以看到Lua官方的全局变量赋值字节码SETTABUP是有3个参数，除了表示源和目的地址的2个参数外，还有1个额外参数。虽然现在还不清楚多出的那个参数的作用，但先假设后续我们也会用上那个参数，于是我们这系列字节码留给源表达式的也就只有1个参数位置了）。那么对这种复杂的表达式该如何处理？答案是先把这些复杂表达式求值到栈顶，作为临时变量，就是Local类型了，然后再使用SetGlobal来完成赋值。

这就出现了两个极端：

• 之前的做法是对每种源表达式类型都定义一个字节码；
• 刚才讨论的方案是把所有类型都先discharge到栈上，然后只用一个SetGlobal字节码。

在这两个极端中间，我们参考Lua官方实现的选择，即为常量类型（ExpDesc的String、Float等类型）定义一个字节码，而其他类型都先discharge到栈上，转换为Local类型。虽然常量类型实际上不是一种具体的类型（包括了String、Float等多个类型），但处理方式是一样的，通过add_const()函数加到常量表中，并用常量表索引来表示，所以在处理赋值语句时，可以看着是一个类型。于是，我们的右值表达式就简化为了两种类型：常量和栈上变量Local！Lua的官方实现中，全局变量赋值的SETTABUP字节码是通过1个bit来表示源表达式是常量还是栈上变量。我们的字节码的生成不方便精确操作bit，所以新增一个字节码SetGlobalConst来表示常量。

Lua官方实现为什么对常量特殊对待，而对其他类型（如全局变量、UpValue、表索引等）却没有优化？个人猜测有两个原因：

• 如果一个全局变量或UpValue或表索引被频繁访问以至于有优化的必要，那么可以简单的创建一个局部变量来优化，比如local print = print。而对常量来说，很多时候赋值给局部变量是不合适的，比如把一条赋值语句g = 100修改为local h = 100; g = a就显得很别扭，多此一举。

• 访问全局变量是根据变量名查表的，是相对比较耗时的操作，相比而言增加一条字节码的代价就不明显。访问其他类型也类似。而访问常量是通过索引直接引用的，增加一条字节码的代价相对就很大了。

至此，介绍完了全局变量的赋值，而表索引的赋值（即表的写操作）是类似的，对于3种类型Index、IndexField和IndexInt，分别定义SetTable、SetField、SetInt和SetTableConst、SetFieldConst、SetIntConst共6个字节码。

最终，赋值的代码如下：

    // process assignment: var = value
    fn assign_var(&mut self, var: ExpDesc, value: ExpDesc) {
        if let ExpDesc::Local(i) = var {
            // self.sp will be set to i+1 in self.discharge(), which is
            // NOT expected, but it's ok because self.sp will not be used
            // before next statement.
            self.discharge(i, value);
        } else {
            match self.discharge_const(value) {
                ConstStack::Const(i) => self.assign_from_const(var, i),
                ConstStack::Stack(i) => self.assign_from_stack(var, i),
            }
        }
    }

    fn assign_from_stack(&mut self, var: ExpDesc, value: usize) {
        let code = match var {
            ExpDesc::Local(i) => ByteCode::Move(i as u8, value as u8),
            ExpDesc::Global(name) => ByteCode::SetGlobal(name as u8, value as u8),
            ExpDesc::Index(t, key) => ByteCode::SetTable(t as u8, key as u8, value as u8),
            ExpDesc::IndexField(t, key) => ByteCode::SetField(t as u8, key as u8, value as u8),
            ExpDesc::IndexInt(t, key) => ByteCode::SetInt(t as u8, key, value as u8),
            _ => panic!("assign from stack"),
        };
        self.byte_codes.push(code);
    }

    fn assign_from_const(&mut self, var: ExpDesc, value: usize) {
        let code = match var {
            ExpDesc::Global(name) => ByteCode::SetGlobalConst(name as u8, value as u8),
            ExpDesc::Index(t, key) => ByteCode::SetTableConst(t as u8, key as u8, value as u8),
            ExpDesc::IndexField(t, key) => ByteCode::SetFieldConst(t as u8, key as u8, value as u8),
            ExpDesc::IndexInt(t, key) => ByteCode::SetIntConst(t as u8, key, value as u8),
            _ => panic!("assign from const"),
        };
        self.byte_codes.push(code);
    }

至此，按照BNF重新了赋值语句，自然也就支持了表的读写操作。

赋值语句和函数调用语句

现在回过头来看本节最开始提出的3个问题的最后一个问题，即语法分析时如何区分赋值语句和函数调用语句。

先来开赋值语句的BNF表示：

varlist ‘=’ explist
varlist ::= var {‘,’ var}
var ::=  Name | prefixexp ‘[’ exp ‘]’ | prefixexp ‘.’ Name 

语句开头是varlist，展开后是变量var，再展开是Name和prefixexp。Name对应Token::Name，但prefixexp还需要继续展开。下面是其定义：

prefixexp ::= var | functioncall | ‘(’ exp ‘)’
functioncall ::=  prefixexp args | prefixexp ‘:’ Name args 

其中第一个var又回到刚才赋值语句的开头，循环引用了，忽略。最后一个是(开头，也很简单。中间的functioncall展开后也是prefixexp开头，也是循环引用，但这次不能忽略，因为functioncall本身也是一条完整的语句，就是说如果一个语句以prefixexp开头，那既可能是赋值语句，也可能是函数调用语句。这两个语句如何区分？在上一节里说明了，赋值语句的左值只能是变量和表索引这两种类型，而函数调用不能作为左值。这就是区分的关键！

综上，最终的解析逻辑是：如果是Name或(开头，则按照prefixexp解析，并判断解析结果：

• 如果是函数调用，则认为是一个完整的functioncall语句；
• 否则，就认为是赋值语句，而本次解析结果只是赋值语句的第一个var。

为此，在ExpDesc中新增函数调用类型Call并让函数调用语句args()返回。在load()函数里，这部分的代码如下：

            match self.lex.next() {
                Token::SemiColon => (),
                t@Token::Name(_) | t@Token::ParL => {
                    // functioncall and var-assignment both begin with
                    // `prefixexp` which begins with `Name` or `(`.
                    let desc = self.prefixexp(t);
                    if desc == ExpDesc::Call {
                        // prefixexp() matches the whole functioncall
                        // statement, so nothing more to do
                    } else {
                        // prefixexp() matches only the first variable, so we
                        // continue the statement
                        self.assignment(desc);
                    }
                }

总结

本节通过BNF重新了赋值语句的解析，最终实现了表的读写操作。另外还有局部变量定义的语句，也需要按照BNF重新，相对很简单，这里省略介绍。

至此，本章完成了表的定义、构造和读写这些基本操作。并为此引入了非常重要的ExpDesc概念和BNF规则。