UVA12423 (Last) Mua(III) - Full Interpreter

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3854 [PDF](https://uva.onlinejudge.org/external/124/p12423.pdf) 

N/A

N/A

## Mua(III) - 完整解释器 在这一系列问题中，你需要实现一个 Lua 语言（5.1 版本）的子集，称为 mini-lua（mua）。这是一个刘汝佳的实验语言，主要用于实现算法，而非真实世界的程序。 这是本系列的第三个（也是最后一个）问题，需要你实现一个完整的解释器。在挑战这个问题之前，请保证你已经解决了前两个问题，否则可能会在理解问题时受到一些阻碍。 ### 代码块（Chunk） 代码块是一个在运行时被看作整体的语句块（Block）。代码块通常为一个完整文件，或者交互模式下的一行输入。 ``` block -> {stat EOL} [laststat EOL] ``` 一个语句块包括多个以换行符结尾的语句，和一个可选的结尾语句。 ``` laststat -> return [expr] | break ``` 结尾语句可以是 `return`（可以不包含返回值）和 `break`。 注意，你只能在一个语句块的结尾使用 `break`。（为了保持简洁，lua 甚至不支持 `continue`！） **致 lua 程序员**：在 Lua 中，你可以将两个语句写在一行，甚至**不需要**分号。在 mini-lua 中，一行不可以包含多条语句。实际上，分号不能作为语句的分隔符。此外，一个语句块只能有一个返回值。 ### 简单语句（Simple Statements） 以下类型的语句很容易理解： - 空语句。`stat ->` - 函数调用，然后丢弃结果。`stat -> functioncall` - 赋值。`stat -> var = expr` - 执行语句块。`stat -> do block end` **致 lua 程序员**：mini-lua 不支持多变量赋值（类似 `a, b = b, a`）。在这个问题中，无需进行递归优化。 ### 控制流（Control Flows） `while`，`repeat` 和 `if` 语句会进行条件判断。`nil` 和 `false` 被认定为假，其他值都被认定为真（值得注意的是，数字 0 和空字符串等都被认定为真）。这些语句的语法如下： - `while` 语句： `stat -> while expr do block end` - `repeat` 语句： `stat -> repeat block until expr` - `if` 语句： `stat -> if expr then block { elseif expr then block } [ else block ] end` `if` 语句可以包含零个或多个 `elseif` 分支，和至多一个 `else` 分支。 有两种类型的 `for` 循环，第一种： ``` stat -> for NAME = expr, expr [, expr] do block end ``` 这三个表达式分别为循环变量的初始值、上下界（取决于增量的正负）以及每次循环的增量（如果不填则为 1）。三个表达式只会在循环之前被计算一次，并转换为数字类型（相当于 `tonumber` 函数）。这三个表达式都需要保证能用 `tonumber` 函数转换成非 `nil` 的值。请注意，`NAME` 是一个局部变量，不可以在循环体外访问。你可以用 `break` 语句跳出循环，但是没有 `continue` 语句。 第二种是通过迭代来遍历一个表中的所有值。 ``` stat -> for NAME in iterator do block end ``` 这里的迭代器为 `ipairs(table)` 或 `pairs(table)`（`table` 为要遍历的变量）。区别在于，`ipairs` 从 1 循环到 `#table`（即 `table` 的长度）并取出所有存在的键值对，而 `pairs` 会无序地遍历所有键值对。 ### 函数定义（Function definition） 考虑上面讨论过的部件，函数定义其实非常简单。 `stat -> function NAME'(' [ NAME{, NAME} ] ')' block end` 注意所有的参数都是局部变量。正如先前所说，你可以用 `return` 语句结束函数，也可以一并返回一个值。你只能在语句块结尾使用 `return`，所以如果你想要在中途返回值，可以使用 `do return end` 将其封装在一个语句块中，它意味着从包含它的最内层函数返回。 ### 作用域和变量可见性（Scoping and Visibility） 你可以通过如下方式声明一个局部变量： `stat -> local NAME [= expr]` 和 Lua 一样，mini-Lua 是一个词法作用域语言（lexically scoped language）。一个变量的作用域从它声明后的第一个语句开始，到包含该声明语句的最内层语句块的末尾结束。如果外层块有另一个同名变量，那么内层块的声明将会覆盖外层的声明（外层的变量仍然存在，但是不再能从内层访问），直到内层语句块结束（此时内层变量不再存在）。回忆一下，代码块也是一种语句块，所以你也可以在最外层定义局部变量。 注意，局部变量只有在定义之后才能访问，所以你可以使用 `local x = x` 来定义一个名为 `x` 的局部变量，并用一个外层的同名变量初始化它。 另外一点，`repeat-until` 循环中，内层块并不在 `until` 处结束，而是在条件之后。所以，这个条件可以用到声明在循环内的局部变量。 由于词法作用域规则，函数可以自由地访问声明在其内部的局部变量。然而，为了简化问题，我们将所有的函数声明在全局（而不是嵌套在另一个函数或者语句块中），而局部变量的声明总是在函数之后。 ## 输入格式 包含多个 mini-lua 程序。每个程序的开头都包括 `--PROGRAM` 注释（这行注释不会出现在程序内部）。 ## 输出格式 对于每个程序，输出它的编号和程序的输出。输出完一个程序的结果后，再输出一个空行。 ## 提示 注意到，mua 满足 LL(1) 语法，一个递归下降解析器足以完成本题的要求。