Lex和Yacc应用方法(八).使用堆栈编译语法
草木瓜 20070604
一、序
前面一些系列文章着重介绍了递归语法树在编译理论方面的应用。本文则会介绍另一种
实现方式----堆栈。
堆栈在底层系统有十分广泛的应用，同样也十分擅长处理语法结构，这里通过实际示例
探讨如何构造堆栈完成语法分析。
重要补充：下面是本系列文章全示例代码统一的调试测试环境，另对于lex,yacc文件需
要存储为Unix格式，这一点和Linux，Unix下shell很类似，DOS格式的Shell是不能够被执行
的，同样bison,lex编译DOS格式文件会出错误提示：
Red Hat Linux release 9 (Shrike)
Linux 2.4.20-8
gcc version 3.2.2 20030222
bison (GNU Bison) 1.35
lex version 2.5.4
flex version 2.5.4
注：本站文章难免有错误疏漏之处。Lex,Yacc系列文章 http://blog.csdn.net/liwei_cmg/category/207528.aspx
二、具体示例
本示例主要完成功能：
1 支持整型，浮点型和字符串型
2 支持变量存储，变量名可为多个字符
3 支持整型，浮点型的+-*/()=运算法则
4 支持字符串型赋值
5 支持print打印整型，浮点型和字符串型
6 支持打印变量值
7 支持while if else switch四种控制结构，并支持控制结构的嵌套
8 支持> >= < <= != == 六种比较运算，同时也支持字符串的比较
9 支持 && || 复合比较运算
10 支持对空格和TAB的忽略处理
11 支持#的单行注释
12 支持{}多重组合
13 支持编译错误的具体显示
14 支持外部变量值传入(整型，浮点型和字符型)
15 支持外部变量获取(整型，浮点型和字符型)
16 完整的企业应用模式
三、示例全代码(略)
A.stack.l
----------------------------------------------
B.stack.y
----------------------------------------------
C.stack.h
----------------------------------------------
D.stackparser.c
----------------------------------------------
E.public.h
----------------------------------------------
F.main.c
----------------------------------------------
G.mk 编译shell文件
----------------------------------------------
bison -d stack.y
lex stack.l
gcc -g -c lex.yy.c stack.tab.c stackparser.c
ar -rl stack.a *.o
gcc -g -o lw main.c stack.a
H.mkclean shell文件
----------------------------------------------
rm stack.tab.c
rm stack.tab.h
rm lex.yy.c
rm *.o
rm *.a
rm lw
四、思路说明
上面列出的代码是目前最长的。
可见写一个堆栈编译器并不是一簇而就的事情，即使对于目前的实例，也需要有很多完
善的地方。设计一个堆栈编译器，我们往往需要从最简单最容易的语句开始。
A.简单的堆栈分析思想
我们先举一个简单的例子，a=1+2。要完成这个公式的计算，我们首先需要将1和2，压
入堆栈，然后分析到+运算，此时又需要将1和2出栈，执行+法后将3压入。继续分析，需要
压入a，在最后的=运算时，将3和a出栈进行赋值运算后，将a入栈。运作序列如下：
id: 0 act: pushvalue
id: 1 act: pushvalue
id: 2 act: add
id: 3 act: pushvar
id: 4 act: assign
使用堆栈进行编译的难点在于，将无比复杂的语法结构抽象到简单的入栈出栈操作。单
从这个角度讲，是很难一步倒位的。一般地，我们需要先将指令字符串根据设定的语法归并
规则编译成有序的指令序列。然后对指令序列制定堆栈动作执行函数，依次执行指令并调用
相应函数。
值得欣慰的是，早在N年前，外国人就形成了一套十分强大的编译理论体系(lex,yacc)
去完成归并语法的工作。我们只需实现外部的规则动作。
B.lex和yacc的归并语法设计
与前面例子相似的是，使用G_Var存储编译时的变量信息，G_sBuff存储编译语句，这里
又增加了G_String统一存储编译语句中的所有字符串。至于lex和yacc设计方法也是相近的，
只是冗余了一些语句标志，如ifx,elsex,switchx等。这些标志是为了生成顺序正确的指令
序列。
lex和yacc会把编译后的所有结果指令存于G_Command中。见AddCommand。
/* 内存指令集结构 */
typedef struct {
int iTypeAction;
int iTypeVal;
float fVal;
int iVar;
int iString;
int iControl;
} TCommand;
这个指令集的设计是关键所在，iTypeAction说明这个指令的类型，iTypeVal表示指令
的值类型。fVal存储整型浮点型数值，iVar存储变量索引，iString如果不是-1，则表示字
符串的索引，iControl表示指令返回的控制信息。
C.堆栈编译
lex和yacc编译后会把指令生成到G_Command中，随后对G_Command进行遍历处理，并调
用相关动作函数进行出入栈操作。(见Act系列函数) 这里出入栈操作的是G_Command索引，处
理的结果皆存于G_Command中，这是外人比较难以理解的一点。
TCommand结构体元素是相对独立的，fVal,iString互斥,iVar标志变量索引，iControl
只用于控制堆栈的值。
在刚开始时需要对各种语法结构做统筹分析。比如拿分支和循环这类语句来说，if分支
就需要维护一个控制状态，由于嵌套语句的存在，这个控制状态需要具有堆栈的特点。每次压
入新if语句要进行现有堆栈的判断，如果前一if为false，这个if即使为true也还是false，另
外else也要做相似处理。之后对于endif做出栈操作，标志这对if/else已处理。switch比if要
稍微复杂一些，还要记录原始值，每次case要做比较。while不仅需要条件还要进行跳转，这是
Act动作函数有返回值的重要原因。
以上这个分析要进行比较体系化的考虑，这些也便于以后的功能扩展，如goto等。
这里我引入了StackValue和StackControl两个堆栈。Value用于普通的顺序计算，Control
用于if else switch while等控制结构。关于控制堆栈，可以参见Act_If,Act_Else等控制
动作函数，在编译指令序列时，会读取控制信息来判断是否执行该指令。值的注意的是，Act
动作函数还返回了下一指令的索引，这主要用于对循环，跳转等方面的处理，默认是顺序执行。
总得来说，TCommand的元素含义要独立，并严格保证处理指令时G_Command的指令数据的
合法性。
D.变量传值和获取
还是回调函数的思想，只是由于字符串的存在制造了一些小麻烦，所以使用了二级指针，
并通过返回值类型，来进行外部判断处理。不过Linux Unix下的gcc不支持引用传值，这里使
用的都是指针传递。
五、一些注意事项
A.stack.l,stack.y 文件要求为Unix格式，这一点和Linux，Unix下shell很类似，DOS
格式的Shell是不能够被执行的，同样bison,lex编译DOS格式文件会出错误提示。
B.SegmentFault多半产生于内存越界(前面已经着重说明过)，除此以为还经常出现这类
情况，产生这类错误的位置的代码并无错误，但是内存值已出现乱码，这一般是指针使用不当。
C.避免一切的warning项，比如在stack.y中，将函数的预说明去除，会提示warning，但
是在执行中，函数传值就会发生根本性的错误。
D.还在在编译C/C++出现的堆栈溢出错误，当然可以用ulimit查看参数，但多半也由内存
越界有关，遇到莫名其妙的错误第一点就要想到内存问题。
E.stack.l,stack.y 注意 规则应用顺序，shift-reduce的顺序
F.耐心才是最重要的，尽量多打印一些调试信息，对于复杂的语法结构调试起来并不是很
轻松的事。
六、总结
lex和yacc应用目前是在Unix/Linux平台下，生成的是C代码，固然C++使用这些接口没有
问题，但不能满足Windows平台的使用需求。从下文起会开始介绍Windows下这类工具的使用，
以及C/C++/Java代码的生成。
联系客服
