0.2 Example: Straight-line Program Language

在正式学习编译理论前，我们简单地热个身。

先讨论一类最简单的语言：直线式程序语言。这类语言只有一般语句和表达式，没有循环和分支判断语句。

我们用形式化的文法规则来描述它的语法（理解成广义的上下文无关文法）：

语句文法（statement）：

• Stm -> Stm; Stm，即：一个语句可以是另外两个语句以 semicon（结束符）分隔组成（执行顺序从左到右），称 CompoundStm；
• Stm -> id := Exp，即：一个语句可以是一个赋值语句（作用域内唯一合法标识符 id、一个表达式，执行顺序先 Exp 后赋值），称 AssignStm；
• Stm -> print( ExpList )，即：一个语句可以是输出语句（print 关键字 token、一个表达式列表，输出顺序从左到右），称 PrintStm；

表达式文法（expression）：

• Exp -> id，即：一个表达式可以是仅仅一个标识符的陈列，称 IdExp；
• Exp -> num，即：一个表达式可以是仅仅一个合法数字 token，称 NumExp；
• Exp -> Exp Bionp Exp，即：一个表达式可以是两个表达式间用二元运算符连接（执行顺序先左后右），称 OpExp；
• Exp -> (Stm, Exp)，即：一个表达式可以是一个语句和一个表达式的组合的序列（以逗号分隔，先执行左边的语句，再执行右边表达式），称 EseqExp；

表达式列表文法（Expression List）：

• ExpList -> Exp, ExpList，即一个表达式列表可以由一个表达式和另一个表达式列表组成（逗号分隔），称 PairExpList（递归定义）；
• ExpList -> Exp，即一个表达式可以仅由一个表达式构成，称 LastExpList（递归定义终止）；

二元运算符文法（Binary Operator）：

• Binop -> + or - or * or /，即一个二元运算符只可以是 +，-，*，/ 其中一个；