数据库大作业要到ddl了。为了实现数据库的两个顶层模块——系统管理模块和命令解析模块，首先需要一个SQL语句的命令解析器。在这里，将使用Lex+Yacc来实现命令解析器模块。
其实这两个工具在编译原理课的PA中已经用过了，但是PA里给了框架，只需要照着框架的样子改一改抄一抄，而数据库的命令解析器需要从头开始写起。所幸SQL的语法比编译原理PA中的语法简单多了。

本文节选并翻译自Writing an Interpreter with Lex, Yacc, and Memphis

在这篇文章中，提供了一个用Lex，Yacc和Memphis实现的目标语言的解析器。目标语言举例如下：

x := 8;
y := 12;
WHILE x != y DO
   IF x > y THEN x := x-y
   ELSE y := y-x
   FI
OD;
PRINT x

我们将用以下两步完成语法解析器。

• Task1(the analizer) 读取源代码并分析代码结构
• Task2(the tree walker) 处理代码

The Analizer

在这部分，我们将分两步完成分析代码结构的任务，分别是词法分析和语法分析。

词法分析 Lex

词法分析将目标文本分解成一个由token、空格、空行、注释组成的序列。比如，如果目标文本是

x:=   // multiply x
x*100 // by hundred

那么，它将被分解成由tokenx,:=,x,*,100组成的序列。
每个token都属于一个类，比如:=属于类ASSIGN，100属于类Number。对于Number这样的类，我们可以使用正则表达式[0-9]+来表示。
词法分析通过yylex()函数实现。yylex()首先从目标串中读入下一个token，然后返回这个token属于哪个类，并把这个token的语义值传给全局变量yylval。
为了完成这个步骤，我们需要向lex输入以下语句，然后lex将会根据这个语句自动生成上述的yylex()过程。

 regular-expression {action}

比如

  [0-9]+ { yylval=atoi(yytext); return NUMBER; }

执行的操作就是，如果下一个token匹配了正则表达式[0-9]+，那么yylval就是这个token所表示的数字，并且这个token的类型为NUMBER。
完整的lex输入代码如下：

 %{
   #include "y.tab.h"
   extern int yylval;
   %}
   %%
   "="      { return EQ; }
   "!="     { return NE; }
   "<"      { return LT; }
   "<="     { return LE; }
   ">"      { return GT; }
   ">="     { return GE; }
   "+"      { return PLUS; }
   "-"      { return MINUS; }
   "*"      { return MULT; }
   "/"      { return DIVIDE; }
   ")"      { return RPAREN; }
   "("      { return LPAREN; }
   ":="     { return ASSIGN; }
   ";"      { return SEMICOLON; }
   "IF"     { return IF; }
   "THEN"   { return THEN; }
   "ELSE"   { return ELSE; }
   "FI"     { return FI; }
   "WHILE"  { return WHILE; }
   "DO"     { return DO; }
   "OD"     { return OD; }
   "PRINT"  { return PRINT; }
   [0-9]+   { yylval = atoi(yytext); return NUMBER; }
   [a-z]    { yylval = yytext[0] - 'a'; return NAME; }   
   \        { ; }
   \n       { nextline(); }
   \t       { ; }
   "//".*\n { nextline(); }
   .        { yyerror("illegal token"); }
   %%
   #ifndef yywrap
   yywrap() { return 1; }
   #endif

语法分析 yacc

语法分析中，将采用上下文无关语法来实现语法结构的匹配。在上一步中，我们已经识别了所有的token，因此在这部分里，我们可以将所有的token用它们的类名来代替，比如100即为NUMBER，:=即为ASSIGN，x即为designator，因此分析x:=x*100就变成了分析designator ASSIGN designator MULT NUMBER。
然后，我们就可以定义上下文无关语法来定义目标语言的语法规则了。在yacc中代码片段如下：

statement:
   designator ASSIGN expression {$$ = assignment($1, $3);} 
 | PRINT expression {$$ = print($2);} 
 | IF expression THEN stmtseq ELSE stmtseq FI
     {$$ = ifstmt($2, $4, $6);}
 | IF expression THEN stmtseq FI
     {$$ = ifstmt($2, $4, empty());}
 | WHILE expression DO stmtseq OD {$$ = whilestmt($2, $4);}
 ;

The Glue

写完语法分析和词法分析，我们就知道了由上下文无关语法定义的匹配规则。当目标代码输入后，通过上面定义的规则分析，需要得到一棵语法分析树。
为了获得语法分析树，我们还需要为yacc中的建树规则定义一些抽象类，比如yacc中文法的第一条规则Statement : designator ASSIGN expression {$$ = assignment($1, $3)}，我们需要通过assignment方法传入designator和expression的参数来构造出Statement节点。这样我们就获得了一个Statement类型的节点，之后就可以在其他部分代码中使用这棵语法分析树的节点了。
完整的定义如下：

domain Statement {

      assignment (Expression lhs, Expression rhs)
      print (Expression x)
      ifstmt (Expression cond, Statement thenpart, Statement elsepart)   
      whilestmt (Expression cond, Statement body)
      seq (Statement s1, Statement s2)
      empty ()

 }

domain Expression {

      eq (Expression x, Expression y)
      ne (Expression x, Expression y)
      lt (Expression x, Expression y)
      le (Expression x, Expression y)
      gt (Expression x, Expression y)
      ge (Expression x, Expression y)
      plus (Expression x, Expression y)
      minus (Expression x, Expression y)
      mult (Expression x, Expression y)
      divide (Expression x, Expression y)
      neg (Expression x)
      number (int x)
      name (int location)

}

The Tree Walker

现在我们可以使用语法分析树了，原文中定义了两个函数evaluate(Expression e)和execute(Statement)，如果语法分析树中一个节点是Expression类型的，就调用evaluate方法，则去计算表达式e的值，如果分析树中一个节点的类型是Statement，那么调用execute方法来执行这个语句。
由于这部分的代码和需求密切相关，我们要解析SQL语法并获取执行对数据库的操作而不是解析执行文中的目标语言，因此这部分不在这里详述了。

接下来，就可以构造SQL的命令解析器了。