lex/yacc

乔姆斯基体系将形式文法的表达能力划分为四个层次，分别是Type-0到Type-3，并呈包含关系。

* Grammar

先为了使表述简洁清晰，来定义如下名词：
non-terminal
terminal
ε
rule/production

* Regular grammar

其中的Type-3称为正则文法，可以用正则表达式来描述，并转化为有限自动状态机。
它是文法中最简单的一种情况，它可以用来匹配和捕获文件中的字符序列。

正则文法的形式是：
B -> a
B -> aC
B -> ε

正则表达式中用基本字符表示其本身，并用若干方式表达字符的组合方式。
其中“|”表示选择，“*”表示0个或多个，“()”表示结合顺序，连续排列表示相连接。
在日常使用的正则表达式中，会用到一些其他的常用的表示符号。
它们可以用上面的更基础的方式表示出来，这里不必举例。

借助于非确定有限自动机(NFA)，正则表达式可以转化为确定有限自动机(DFA)。
通过已接受的字符确定的当前状态可以通过将要介绍的字符转向下一个状态。
可能到一个中间状态，或者匹配失败或者转移到某个接受状态上。

通常我们借助Lex这个工具生成又DFA表构成的程序，例如用GNU的flex可以：
下面这个.lex程序可以用来输出文件中的全部带符号整数：
%{
#include
%}
%option noyywrap
DIGIT [0-9]
INTEGER ("+"|"-")?{DIGIT}+
%%
{INTEGER} {
printf("Got integer %s\n", yytext);
}
.|\n
%%
int main(void){
yylex();
return 0;
}
如果要在别的代码中使用它的话，例如结合yacc来使用，会在下面的内容里再说。
详细情况可以参考http://flex.sourceforge.net/manual/


* Context-free grammar

其中的Type-2称为上下文无关文法，可以用BNF（巴克斯-诺尔范式）来描述，并转化为下推自动机。
它是多数程序设计语言文法的基础，可以用它来将Token序列转化为文法对应的语法树。

上下文无关的意思是满足 V -> w 使得V总能被w替换而无需考虑上下文。
虽然程序语言中变量的含义是上下文有关的，不过我们可以到更高级层次的文法再处理。

和正则表达式不同的是，在BNF中允许递归文法的出现，其表达能力呈包含关系。
而在EBNF（扩展巴科斯范式）中，递归文法可以表达为产生式右端的可选部件。

当一个BNF使得一个词法满足多个结构的语法树时，则称这个文法是有歧义的。
可以通过改写规则增强约束来消除歧义，或者可以在解析时增加额外的限定。

不同的Parse方式对BNF文法的处理能力有差异，所以下面将结合Top-Down和Bottom-Up来说明。

常用的Top-Down方法是LL(1)，意思是从左到右根据一个预读单词解析当前最左端的单词。
实现时可以手写递归下降的解析器，或者基于Stack使用解析转移表。
例如对于EBNF：
exp -> term { addop trem }
addop -> + | -
term -> factor { mulop factor }
factor -> '(' exp | Number ')'
可以把exp写为tmp=term();while(peekToken==op){match(op);tmp=op(tmp,term())}return tmp;
这里可选部件和做递归是等价的。

条件语句和语句块可以写为：
补丁
需要避免else结合时的歧义

递归下降的解析器可以直接通过EBNF来改写，额外的要求是在预读字符后要能够转移到特定的规则上。
虽然用Left Recursion Removal和Left Factoring可以改写部分EBNF是指满足上述的改写方式。
但是因为这种解析方式的能力限制，依然对文法的First Set和Follow Set有所限定。

常用的Bottom-Up方法是LALR(1)，可以通过工具yacc来生成程序。
LALR(1)文本的状态不再直接对应所给的规则，而是基于Stack和Action table进行Shift和Reduce操作。
当Action table不确定时会产生歧义（shift-reduce或reduce-reduce），在该解析算法下有歧义时工具会给出提示。

下面会使用GNU的Bison来构建一个简单的正整数四则运算的运算器的，容错机制通过在解析规则中添加额外的规则来弥补。
%{
#include
#include
#define YYSTYPE int
%}
%token NUMBER
%%
stmt :
| stmt expr '\n' { printf("%d\n", $2); }
| '\n'
| error '\n' { yyerrok; }
;
expr : expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
| term
;
term : term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
| factor
;
factor : NUMBER { $$ = $1; }
| '(' expr ')' { $$ = $2; }
| '(' expr error { $$ = $2; yyerror("\")\" missing"); yyerrok; }
| '-' factor { $$ = -$2; }
%%
int main(void){
return yyparse();
}
int yylex(void){
int c;
while ((c = getchar()) == ' ');
if (isdigit(c)) {
ungetc(c, stdin);
scanf("%d", &yylval);
return NUMBER;
}
return c;
}
int yyerror(char *msg){
fprintf(stderr,"%s\n", msg);
return 0;
}

这里还需要做一些额外的说明：
使用%left '+' '-';%left '*' '/';可以标记运算符的优先级和结合顺序，这样可以不必把expr的规则分解为多个层次来避免歧义。
上面的yylex通常是由lex生成的，其中NUMBER或者其他类型的单词类型可以用yacc生成的.h文件在两者之间共享。
这里指定“YYSTYPE int”表示每条规则的获得的值和返回的值都是int，若要使不同规则使用不同类型的话用%union申明并在%token和%type指定。
详细参考http://www.gnu.org/software/bison/manual/bison.html


* Abstract Syntax tree

最近玩多了Scheme，其中的sexp是AST的一种很天然的表达形式。C语言的Struct，用Class构成的Composite模式，ML语言的ADT，还有json都是很相似的表达。
根据本编的上下文的话，就是在lex中获得匹配的文本，而在yacc中构建树结构。
例如在lex将匹配的类型放在由yytext存放在yylval中，而yacc中可以{$$=new Node();doSthWith($$)}。
不过貌似ML系的写法要好看一点。


* Sematic Analysis

上面也说过在词法和语法解析过后，目的是获得语法树。能在解析中直接处理当然更快捷，不过没有处理语法树来得简单。

这里要做一些事情，标记语法树节点的类型，将数值字符串转化为数值类型，生成符号表判断词法作用域。


* Compile

如果要让程序可以运行的话，可以构建Stack虚拟机或者三地址虚拟机，并设计内存在运行时的管理方式。
C语言是全局变量Static，函数调用是基于Stack，而分配的空间在Heap上。
然后，在生成代码的时候，计算好内存间的相对位置，再做一些不影响程序语义的优化。
简单的说，就这些内容了，写出来整理一下思路。

* End

详细见这份资料吧：
《Compiler Construction. Principles and Practice. by Kenneth C. Louden》