编译器的语法分析，要大量地使用递归。

因为源代码里各种类型的语句是互相嵌套的，编译器没法事先知道源代码的结构，所以只能递归分析：遇到什么类型的语句就按什么语法规则来分析。

对于初学者来说，按照自己熟悉的那门语言，用递归去分析它的语法，是最简单的入门方法。

编译器的编写并不受语言的限制，可以用C/C++，也可以用其他语言，选一门自己最熟悉的语言就行。

我对C语言最熟悉，所以scf框架的语法分析是以C语言为基础的（做了一些简化）。

在gitee上看过我的代码的应该知道，语法分析的那个文件叫scf_parse2.c，是我做的第2个版本。

第1版的语法分析，我就是把它写成了各种函数的递归调用。

语法分析的代码流程图

如上图，箭头表示在这种类型的语句里可以嵌套另一种类型的语句。

编程语言的各类语句之间，大多数都是可以互相嵌套的，所以语法分析的代码是这样的：

int parse_if()

{

word* w = get_word();

switch (w->type) {

case IF:

return parse_if(); // 连续的if嵌套

break;

case WHILE:

return parse_while(); // if里嵌套while循环

break;

case FOR:

return parse_for(); // if里嵌套for循环

break;

default:

return parse_expr(); // if里的表达式

break;

};

return -1; // 未知语句类型，语法错误

}

parse_while()和parse_for()函数的写法也类似parse_if()，也是对嵌套的各种语句的递归。

这种初级版的代码耦合度是非常大的，任何微小的语法调整都可能要对代码进行大修改。

比较死板，但容易入门。

通过顺序块去解耦合

为了减少各种语句之间的耦合，可以通过顺序块去解耦，如上图。

在没有顺序块解耦的情况下，语法分析模块的复杂度是语句类型数的平方。

如果有3种语句类型，那么复杂度就是9，因为它们互相之间都可以嵌套。

在有顺序块解耦的情况下，语法分析模块的复杂度就变成了语句类型数的2倍。

语言的语句类型数越多，对复杂度的降低越明显，因为从O(N^2)变成了O(2N)。

在上面2个图上，每一个回路都对应着实际（语法分析）代码里的递归。

if (p)

printf("p: %p ", p);

这类代码，不管有没有{}都把if的主体部分看作一个顺序块。

顺序块，是由表达式或其他语句构成的顺序运行的代码块。

函数调用printf("p: %p ", p); 也看作一种特殊的表达式，毕竟表达式里可以包含函数调用。

if关键字 -> 条件表达式 -> 顺序块 -> 表达式 -> 函数调用 ->结尾的分号，这是上述代码的语法分析流程。

后来为了灵活的编辑语法，我还是给scf做了一个简单的自动机框架，即以scf_dfa开头的那些文件。

scf dfa的数据结构

因为懒得去熟悉flex bison的文档，我就自己随手写了一个DFA框架，反正每个节点也就两个函数：

1，is()函数用于判断接不接收当前的词，

2，action()函数用于执行接收动作，构造抽象语法树。

还是以这段if (p) printf("p: %p ", p); 为例，说明一下设计思路：

因为是递归分析，终止条件就是最后的分号：

1，当发现分号之后，说明函数调用printf()结束了，

2，进一步说明if语句的主体部分结束了，

3，进一步说明if语句结束了。

如果直接在代码里写死递归的话，这3个返回过程是代码的函数调用链自动执行的。

但是当通过dfa节点把它解耦之后，它们就不是函数的直接递归了，只能去“模拟”这种递归，所以我就给它加了hook[呲牙]

把hook的单链表当作一个栈，来记录代码的“递归链”。

scf_dfa_hook_t* next指针组成一个单链表，node是它的语法分析节点。

scf_dfa_node_s的内容很简单，除了2个函数is()和action()之外，就是它的子节点列表。

发现某个词之后，它的下一个词该怎么处理？

去它的子节点列表(childs)里找，只要找到能接收这个词的子节点，就可以处理了。

编辑语法时，只要把一个节点加到另一个节点的子节点列表里，就可以构成语法规则了。

while语句的语法规则

while (*p) p++;

所有的while循环，都是while关键字后面跟左小括号(，然后是条件表达式，然后是右小括号)，最后跟顺序块组成的循环体（可以只有一行分号结尾的表达式）。

所以从父节点到子节点的顺序是这样的：while -> lp -> expr -> rp -> block。

lp是左小括号的英文缩写，rp是右小括号的英文缩写。

写代码的时候是什么符号挨着什么符号，编辑语法的时候就什么节点是什么节点的子节点。

至于while的循环体部分，不管它多么复杂或多么简单，一律让顺序块模块block去处理。

每一种类型的语句，做一个dfa模块，所以我给它定义了一个scf_dfa_module_s结构：

1，name是这个模块的名字字符串，

2，有2个init函数，在编译器启动的时候初始化。1个fini函数，在编译器退出的时候析构。

3，一个表示模块个数索引的数字。

这个设计模式是我从俄罗斯的nginx那里学来的[大笑]

语法分析，while模块的结构体

scf框架支持的所有语法模块：

所有语法模块

dfa语法分析模块的初始化：

dfa模块初始化

每个模块的初始化

scf语法分析部分的总初始化函数，scf_parse_open()：

整个框架都是围绕着scf_parse_t这个结构体来运作的。

scf语法分析部分的总初始化函数，scf_parse_open()

最主要的是这个结构体：

1，lex是词法分析用的，

2，ast是抽象语法树，语法分析完成之后的操作都以它为基础，

3，dfa和dfa_data是语法分析用的，

scf_parse_t结构体

4，symtab当然是符号表，它是一个动态数组，

5，全局常量或全局结构体，这些都是往.data数据段里填写的，global_consts。

6，debug，用于gdb的调试信息。

gdb有个dwarf标准，用于给程序生成调试信息的，代码在scf/elf目录，以scf_dwarf开头的文件，我对dwarf标准的支持并不全。