UVA12423 (Last) Mua(III) - Full Interpreter

在这个系列的题目中，你需要实现 Lua 语言（$5.1$ 版本）的一个子集，叫做 mini-Lua（mua）。这是刘汝佳的实验性语言之一，主要用于实现算法，而非真实世界的程序。 这是这个系列题目的第三道（也是最后一道！）题目，你需要实现一个完整的解释器。请确保你在尝试解决这个问题之前已经解决了前两道问题。如果你没有，可能会在理解这道题目时出现问题。 译注：以下定义中的圆括号 $\texttt{(}$ 和 $\texttt{)}$ 表示圆括号字符本身，等于号 $\texttt =$ 同理。而方括号 $\texttt{[\dots]}$ 表示中间的 $\dots$ 出现零次或一次，而大括号 $\{\dots\}$ 代表中间内容出现任意次（可能是零次）。 ### 代码块（Chunk） 一个代码块（一个程序或者一个作为完整的一段来执行的程序段）是一个单独的语句段（$\mathrm{block}$）： $$ \mathrm{block}\to \{\mathrm{stat}\space \texttt{EOL}\}\space \texttt [\mathrm{laststat}\space \texttt{EOL}\texttt] \\ \mathrm{laststat}\to\texttt{return}\space\texttt[\mathrm{expr}\texttt]\space\texttt|\space\texttt{break}$$ 注意 $\texttt{break}$ 只能出现在一个语句段的最后一个语句中（为了让事情更加简单，Lua 甚至不支持 $\texttt{continue}$！）。 **对于 Lua 程序员**：在 Lua 中，你可以把两条语句写在一行中，甚至可以不写分号。但是在 mini-lua 中，你不可以把多条语句写在一行中。实际上分号不能够用作分隔符。另外，一个语句段只能返回一个值。 ### 简单语句（Simple Statements） 下列类型的语句很容易理解： - 空语句：$\mathrm{stat}\to$。 - 函数调用，并丢弃返回值：$\mathrm{stat}\to\mathrm{functioncall}$。 - 赋值：$\mathrm{stat}\to\mathrm{var}\space\texttt{=}\space\mathrm{expr}$。 - 执行语句段：$\mathrm{stat}\to\texttt{do}\space\mathrm{block}\space\texttt{end}$。 **对于 Lua 程序员**：多个变量同时赋值（如 $\mathrm{a}\texttt,\mathrm b\texttt =\mathrm b\texttt,\mathrm a$）在 mua 中不支持。另外，尾递归优化在这个题目中并不是必须的。 ### 控制流（Control Flows） $\mathrm{while}$，$\mathrm{repeat}$ 和 $\mathrm{if}$ 语句都需要条件参数。$\texttt{nil}$ 和 $\texttt{false}$ 都使条件为假，其它任何值都使条件为真。这些语句的定义如下： - $\mathrm{while}$ 语句：$\mathrm{stat}\to\texttt{while}\space\mathrm{expr}\space\texttt{do}\space\mathrm{block}\space\texttt{end}$。 - $\mathrm{repeat}$ 语句：$\mathrm{stat}\to\texttt{repeat}\space\mathrm{block}\space\texttt{until}\space\mathrm{expr}$。 - $\mathrm{if}$ 语句：$\mathrm{stat}\to\texttt{if}\space\mathrm{expr}\space\texttt{then}\space\mathrm{block}\space\{\space\texttt{elseif}\space\mathrm{expr}\space\texttt{then}\space\mathrm{block}\space\}\space\texttt{[else}\space\mathrm{block}\texttt]\space\texttt{end}$。 还有两种类型的 $\mathrm{for}$ 循环。第一种是： $$ \mathrm{stat}\to\texttt{for}\space\mathrm{NAME}\space\texttt{=}\space\mathrm{expr}\space\texttt,\space\mathrm{expr}\space\texttt{[,}\space\mathrm{expr}\texttt]\space\texttt{do}\space\mathrm{block}\space\texttt{end}$$ 三个 $\mathrm{expr}$ 表达式是分别是循环变量的初始值，上界（当第三个参数 $\mathrm{step}>0$）或下界（当 $\mathrm{step}\le 0$），和循环步长 $\mathrm{step}$（默认为 $1$）。三个表达式都会且仅会在循环开始之前被计算一次，然后转化为数字（使用 $\texttt{tonumber(}e\texttt)$ 函数）。三个表达式的返回值转化为数字后都不应该为 $\mathrm{nil}$。注意 $\mathrm{NAME}$ 是一个局部变量（你不可以在循环结束之后访问），你可以使用 $\texttt{break}$ 来退出循环，但是没有 $\texttt{continue}$ 语句。 第二种是一个更加通用的循环，循环一个映射表（$\mathrm{table}$）中的所有键： $$\mathrm{stat}\to\texttt{for}\space\mathrm{NAME}\space\texttt{in}\space\mathrm{iterator}\space\texttt{do}\space\mathrm{block}\space\texttt{end}$$ 这里，$\mathrm{iterator}$ 是 $\texttt{ipairs(}\mathrm{table}\texttt)$ 或 $\texttt{pairs(}\mathrm{table}\texttt)$（当然列表的名称可以和 $\mathrm{table}$ 不同）。差别在于，$\texttt{ipairs}$ 从 $1$ 到 $\#\mathrm{table}$ 遍历，而 $\texttt{pairs}$ 以任意顺序遍历所有的键。 ### 函数定义（Function definition） 通过上述我们讨论的基本结构，函数的定义十分简单： $$\mathrm{stat}\to\texttt{function}\space\mathrm{NAME}\space\texttt(\space\texttt[\mathrm{NAME}\space\{\texttt,\space\mathrm{NAME}\}\space\texttt]\space\texttt)\space\mathrm{block}\space\texttt{end}$$ 注意所有的参数都是局部变量。我们上面已经说过，你可以使用 $\texttt{return}$ 语句来退出一个函数，还可以（也可以不）带上一个返回值。你只能在一个语句段的末尾使用 $\texttt{return}$ 语句，所以如果你想要在函数中间退出，你可以把它包装在一个语句段中，比如 $\texttt{do}$，$\texttt{return}$ 和 $\texttt{end}$。它代表退出包含该语句段的最近的函数。 ### 作用域与可见性（Scoping and Visibility） 你可以这样定义一个局部变量： $$\mathrm{stat}\to\texttt{local}\space\mathrm{NAME}\space\texttt[\space\texttt =\space\mathrm{expr}\space\texttt]$$ 类似于 Lua，mini-Lua 也是一个词法作用域语言。一个变量的作用域从定义它的语句的**下一个**语句开始，直到它所在的最内层语句段的末尾。如果在它所在的语句段之外有另一个同名的变量，那么位于外面的变量被遮盖（它依然存在，但你没法访问它）。只有在内层语句段结束后，我们才可以访问它，因为内层变量不存在了。注意到代码块（$\mathrm{chunk}$）也是一个语句段（$\mathrm{block}$），所以你也可以在代码块中定义局部变量。 注意局部变量的作用范围在定义它的语句之后。也就是你可以使用 $\texttt{local}\space x\space\texttt=\space x$ 来定义一个叫做 $x$ 的局部变量，初始化为在外层定义域的叫做 $x$ 的值。 注意在 $\texttt{repeat-until}$ 循环中，内层语句段并不在 $\texttt{until}$ 关键字处结束，而是在条件之后。所以，条件仍然可以使用在循环语句段中定义的局部变量。 由于词法作用域规则，局部变量可以被定义于语句段内部的函数自由访问。然而，为了让事情更加简单，所有函数都会定义为全局函数（不会在语句段或另一个函数内），而代码块中的所有局部变量（如果存在）都会在函数之后定义。

输入多个 mini-Lua 程序。每个程序都会以 $\texttt{--}\space\texttt{PROGRAM}$ 开头（它不会在程序内部出现）。

对于每个程序，先输出程序的编号，然后换一行再输出程序的执行结果。每个程序结束后都要输出一个空行。

你发现 Mua 是 $\mathrm{LL}(1)$ 的了吗？一个递归下降解析器对于这道题已经足够了。