首页 > 代码库 > 编写Lex和Yacc

编写Lex和Yacc

大学课程设计中,有一次是编写Lex(词法分析器的生成器)和Yacc(语法分析器的生成器),编写这类工具软件不是一件容易的事情。这篇文章记录了当时编程时候的主要思想,主要还是编译原理的思想。

准备

Lex

根据输入文件生成RE—>NFA—>DFA—>简化的DFA—>根据DFA生成文件。

RE处理:

对正规表达式进行处理使其只有|、*、(、)等特殊符号,代换{}[]-等
将RE转化为后缀表达式   

生成NFA:

把下列类型的string转换:

M+----->M.M*

M?------>M|e

最后一共有四种连接:

普通字符(除了.,|,*):

编译lex1

a*:增加三条epsilon边,并且修改终点和起点。

编译lex3

a|b:

新建两个节点,并把其中一个指向原来的两个nfa的起点,另一个被原来的两个终点指向。这四个边均是epsilon。修改终点和起点。

编译lex2

a.b:连接,合并2号和3号节点。(红色代表nfa的起点,黑色代表nfa的终点)

编译lex4

NFA合并:

直接添加一个起点,指向所有nfa的起点。修改起点值,并把原来的终点(每个nfa只有一个)都加入到最后的终点集合。

NFA--->DFA

求闭包

通过epsilon到达的边。迭代直到T’=T,每次

repeat:
T1 = T;
T=T1∪T1所有点能通过epsilon到达的边
until T1==T
求通过某个字母到达的子集
for each(Node* node in d)//对d的每一个节点
{
vector<Node*> eout = node->findNext(c);//求出每个节点的出边集合
d1.insert(eout.begin(), eout.end());//将后继的每一个节点不重复的插入d1
}
最后返回这个d1的闭包
 
生成DFA

用j标记当前遍历的节点,用p标记已经存在的节点数量

对当前遍历的节点求每个字符的出边集合,如果有的话,就求该集合的闭包,并判断是否已经存在,做相应的处理:

    如果已经存在,则加边

    如果不存在,新建节点,再加边,p++

DFA最小化

参考维基百科中关于Hopcroft的算法。

但是对于DFA来说,刚开始并不能简单地分为两个非终结符和终结符的集合,因为每个终结符最后应该在单独的一个集合中。

Yacc

读取文件设置符号和产生式的值—>计算FIRST和FOLLOW—>构造LR(1)预测分析器和PPT(预测分析表)—>LR(1)—>LALR—>打印到输出文件。

计算FIRST和FOLLOW

还是参考的“现代编译原理”这本书。

对于LR(1)可以不计算FOLLOW,所以只计算FIRST。

初始化:每个终结符的FIRST是自己

设置一个是否修改的bool变量,检测本次循环是否修改过

遍历每个产生式

    每个产生式的右部符号,如果当前符号前面都是可为空,则将这个产生式左部的FIRST增加当前符号。

    如果每个符号都是可为空的,则把这个产生式置为可为空。

 

构造预测分析器(FA)和预测分析表(PPT)

计算闭包和计算GOTO

类似Lex的计算闭包和子集

构造LR状态图和分析表

类似构造DFA

 

反思

感觉这次做的比较辛苦,可能这是因为是工具软件的原因吧。工具软件要能针对不同的输入,生成不同的代码,然后生成出来的代码可以去分析一个文件。

Technorati 标记: 编译原理,Lex,Yacc,课程设计