语法和语义分析

顾名思义，一个命令式语言是由一个个“命令”为单元组成，不过一般很少用命令这个词，而是细分一下，比较低级的语言用指令（instruction），高低的语言一般认为是一个语句（statement，以后简称stmt），词法分析只将一段高级语言代码分解成一个个词，接下来还要做语句层面的分析，最终目标是生成抽象语法树（ast）

代码：

a = 1;   
s = 0;   
while (a <= 100)   
{   
    if (a % 2 == 0)   
    {   
        continue;   
    }   
    s = s + a;   
}   
print s;

这段代码含有四条语句，两个赋值，一个while和一个print，其中while里面的内容并不会被展开，可以认为编译过后，这段代码会生成一个长度为4的stmt_list，包含四个stmt对象

stmt对象有各种类型，比如赋值、for循环、while循环等，每种类型包含的内容也不同，但一般来说是包含stmt和表达式(expression，以后简称expr）。又因为所有stmt要放在一个list，所以它们应该有同一个基类或实现同一个接口（java代码表示）：

class Stmt   
{   
    RetType execute();   
}

整个语法分析就是分析出一个stmt的list：

StmtList build_stmt_list(TokenList token_list);

语法分析过程，编译原理一般都会说用上下文无关语言，BNF范式等，实际上这个分析和词法分析有类似的地方，都可以用自动机来做，只不过一个是正则语言的自动机，一个需要用下推自动机，因为可能有任意深度的语句包含，这里我们可以用递归来实现

另外，如果认真设计语法，也能很大简化这个过程，实际上语法分析和我们阅读代码在“可读性”上有很大的一致性，比如分支语句：

if (x) {...} else   
{...} if (x) else

下面这行是我举的例子，并不是某个我知道的语言的语法。这两个例子都可以是一条分支语句，在日常说话中，我们可能会说出后面这种类似语法，但对于代码而言，选择前者可读性较好，因为如果{}里面很长，我们得到很后面才知道这句语句是什么意思，对编译器也是一样，if写在前面能及早确定stmt类型，因此不妨考察下各种语言，绝大多数语句都是关键字开头的，所以stmt_list的分析过程大致可以写成这样（伪代码）：

while (token_list.size() > 0)   
{   
    if (token_list[0] == "if") .....;//parse if   
    else if (token_list[0] == "while") .....; //parse while   
    ......   
    else ......; //parse expr   
}

不以关键字开头的一般都是表达式，比如函数调用或赋值（如果赋值被设计为表达式的话）

一个print语句对象和解析代码可能是这样：

class StmtPrint extends Stmt   
{   
    Expr e;   
    RetType execute();   
}

assert token_list.pop_front() == "print"   
Stmt stmt = new StmtPrint()   
stmt.e = build_expr(token_list)   
return stmt

而一个while语句可能是这样：

class StmtWhile extends Stmt   
{   
    Expr condition;   
    StmtList stmt_list;   
    RetType execute();   
}   
assert token_list.pop_front() == "while"   
assert token_list.pop_front() == "("   
Stmt stmt = new StmtWhile()   
stmt.condition = build_expr(token_list)   
assert token_list.pop_front() == ")"   
assert token_list.pop_front() == "{"   
stmt.stmt_list = build_stmt_list(token_list) //递归解析while的执行体   
assert token_list.pop_front() == "}"   
return stmt

比较复杂的可能是连续if...else这种，有两种风格，C和java的else if是把后面的if放在else部分，即：

if (a) x; else if (b) y; else z;

相当于：

if (a) x; else {if (b) y; else z;}

这样

class StmtIf extends Stmt   
{   
    Expr condition;   
    StmtList when_true;   
    StmtList else_part;   
    RetType execute();   
}

这样的一个问题是多个else if可能会导致树非常深

另一种像python的elif就是所有条件和执行体是并列的，差不多是这样：

class StmtIf extends Stmt   
{   
    class IfElem   
    {   
        Expr condition;   
        StmtList stmt_list;   
    }   
    IfElemList if_list;   
    StmtList else_part;   
    RetType execute();   
}

执行时顺序遍历if_list，如果有condition成立则执行对应的stmt_list，如果所有都不成立，则执行else_part，若一个语句没有最后的else，则else_part为null

当然像continue，break这种，就没有内容了，其余像return、for甚至try这种语句的解析都是一样的，略过

不以关键字开头的都是表达式，这里分两种情况，赋值表达式和非赋值表达式，C和java里面都是讲赋值实现为表达式，然后有时候在判断全等时候将==写为=就出现了比较隐晦的错误，所以我倾向于将赋值看做语句而非表达式，赋值语句由左右两个表达式组成，其中左表达式必须是左值

expr的实现编译原理有讲，用两个栈实现表达式树，很经典的算法。实际实现的时候可以用一些小技巧，比如碰到正括号的时候不入符号栈，而是直接递归调用build_expr，这样能简单些。另外需要注意某些符号可能在不同的状态下有不同的含义，例如+-可以是加减，也可以是正负，python中的“[”可能是取前面表达式的下标运算，也可能是一个列表的开始，python的tuple两头可以不加()，用逗号分隔，C语言也有逗号运算符，而同时逗号在这两个语言也是函数的参数分隔等等。还有一些更模糊的地方，比如python的for语法，是for ... in ....，而同时in在表达式也作为一个运算符，如果太难解析，不妨对某些语法规定必须加括号

所有expr都是右值表达式，但不是所有都是左值表达式，左值是指能放在赋值语句左边的。判断一个表达式是否左值可以先将其作为右值表达式来解析，看它的表达式树的根的操作符，如果是访问变量、访问属性、访问数组元素或通过地址取内存内容（C中的*运算）等，总之就是直接从存储区某个地方拿数据的操作，即是左值

不过有时候左值判断也要结合一些特殊语法，比如python中的unpack语法：

a, b, c = f()

赋值语句左边是个tuple形式（list形式也行），这里从语法上可以判断出，一个build_tuple表达式是左值当且仅当它所有元素是左值，递归判断即可

语法分析可以完成expr树，在静态类型语言中，每个变量或表达式的结果都是有类型的，还需要对树进行类型检查，比如：

long a;   
void f(double, long);   
f(a+1, 123);

最后这条语句的语法分析expr树画出来应该是： () / | \ f + 123 / \ a 1 然后对每个节点做类型分析，a是个long，1是个int，需要提升为long，于是加一个类型转换的节点，节点“+”的类型为long，而f接受的参数为double，也需要类型转换，第二个参数123也是，于是就成为： () / | \ / | \ f D L | |

   +   123 
  / \ 
 a   L 
     | 
     1 

其中D和L表示double和long类型转换运算 P.S.这个树中是将f作为()操作的一个参数，这是把f当成一个对象来看待，当然也可以将f()本身当成一个操作

在语义分析中，这个树还可以进一步简化，对于L-123这个子树而言，在任何情况下运行时都会得出结果123L，因此可以在编译期就计算好，同理L-1这个子树也可以计算，但是+不行，因为a的值只有运行时才知道，如果一个表达式树（整棵或子树）都由常量和确定的运算组成，且返回一个不可变的值，则可以在编译期算好，比如：

seconds_per_day = 24 * 60 * 60

代码中可以写个常量算式，更直观，对运行效率没有影响 python代码赋值一个tuple：

a = 1,2,(3,"a")

右边的build_tuple树的值是在编译期确定的，会整合成一个常量，但是这样不行：

a = [1,2,3]

虽然子树是由常量和一个build_list操作组成，但是由于list是可变对象，可能在后面改变a的内容，所以不能作为一个常量出现（即便能，运行时也是拷贝一个副本给a）