1. 定义 SLang 1¶
1.1. SLang 1 的语法¶
到目前为止，我们已经考察了如何从函数式编程的角度进行编程，以及 λ-演算如何为这一视角奠定理论基础。现在我们将转换焦点，考虑如何 真正为一种基于 λ-演算的语言开发一个小型解释器。我们把这种语言 称为 SLang 1 ，即“Simple Language version 1”（简单语言第 1 版）的缩写。
这个解释器的开发过程要求我们编写一个 Jison 文法来定义该语言的 语法，并把该语言中的程序转换成 抽象语法树 （abstract syntax tree，AST）。
具体语法 （concrete syntax）与 抽象语法 （abstract syntax）有何不同？换句话说，分析树与抽象语法树有何不同？
分析树 （parse tree）为每个词法单元（token）设置一个叶结点， 为每个非终结符设置一个内部结点。分析树适合用来表示源程序的结构 或语法。
然而，我们现在感兴趣的是程序的含义，而不仅仅是它的表面结构。 抽象语法树 （abstract syntax tree，AST）是把分析树中所有对 后续处理（对我们来说，就是执行或解释过程）并非必需的结点都去掉 之后得到的树。
在 AST 中：
运算符出现在内部结点上，而不是叶结点上，其操作数成为它的子 结点。
单位产生式链（即形如
<X> ::= <Y>的产生式）会被折叠。列表会被展平。
语法细节（分号、括号等）会被省略。
下面的例子说明了这一点。
Parse Tree Abstract Syntax Tree
========== ====================
exp *
| / \
term 3 +
/|\ / \
term * factor 4 2
/ /|\
/ / | \
factor ( exp )
| /|\
3 exp + term
| |
term factor
| |
factor 2
|
4
AST 通常只包含少量对应非终结符的结点。尽管如此，它包含了解释器 推导输入程序正确含义（即对程序求值并返回正确结果）所需的全部 信息。
Input Parse Tree
===== ==========
{ ____ methodBody _________
x = 0; / / \ \
while (x<10) { { declList stmtList }
x = x+1; | / \
} epsilon stmtList stmt___
y = x*2; / \ / | \ \
} stmtList stmt ID = exp ;
/ \ \ (y) / | \
AST stmtList stmt ... exp * term
=== | / | | \ | |
epsilon ID = exp ; term factor
methodBody (x) | | |
/ \ INTLITERAL factor INT
declList stmtList (0) | (2)
/ | \ ID
assign while assign (x)
/ \ ... / \
ID INT ID *
(x) (0) (y) / \
ID INT
(x) (2)
SLang 1 的具体语法由以下 EBNF 文法定义：
<program> ::= <exp>
<exp> ::= <var_exp> | <fn_exp> | <app_exp> | <papp_exp> | <int>
<fn_exp> ::= fn '(' (<var_exp> (',' <var_exp>)*)? ')' => <exp>
<app_exp> ::= '(' <exp> <exp>* ')'
<papp_exp> ::= <prim_op> '(' <args>? ')'
<args> ::= <exp> (',' <exp>)*
<prim_op> ::= + | * | add1
SLang 1 “程序” (fn (a,b) => b y 3) 会得到如下的分析树和 AST。
parse tree AST
========== ===
program program
| |
exp app_exp
| / \
_ app_exp ______ fn_exp args
/ | | \ \ / \ / \
( exp exp exp ) [a,b] var_exp var_exp int
_________/ \ \ | | |
/ var_exp int b y 3
______fn_exp___________ \ \
/ / / | | \ \ \ y 3 [ "Program",
/ / / | | \ \ \ [ "AppExp",
fn ( var_exp , var_exp ) => exp [ "FnExp",
| | | ["a","b"],
a b var_exp ["VarExp","b"]],
| [ "args",
b ["VarExp","y"],
["IntExp",3]]]]
上例右下角的表达式把抽象语法树表示为一个列表的列表。
1.2. SLang 1 的具体语法¶
下面的问题将帮助你掌握 SLang 1 的具体语法。要获得这道题的学分， 你必须连续三次正确完成这个随机化问题。
1.3. SLang 1 具体语法的更多练习¶
下面的问题通过提供更密集的练习来巩固你对 SLang 1 具体语法的掌握。 要获得这道题的学分，你必须连续三次正确完成这个随机化问题。
1.4. SLang 1 的抽象语法¶
下面的问题将帮助你掌握 SLang 1 的抽象语法。
1.5. SLang 1 中的 curry¶
下面的问题将展示 SLang 1 的语义，同时帮助你复习 curry 函数的 定义。
1.6. SLang 1 的语义¶
下面的问题着重考察 SLang 1 的语义。
