Github地址: https://github.com/corvofeng/compiler

课程主要目的

  • 加深对编译原理及编译程序构造过程的理解
  • 增强程序设计能力
  • 学会编写工具软件

课程要求

SeuLex

  • Lex输入文件的解析
  • 正规表达式的解析
  • 一个正规表达式到NFA的转换算法实现
  • 多个NFA的合并
  • NFA的确定化和最小化算法实现
  • 返回状态与返回内容的对应
  • SeuLex应用

SeuYacc

  • Yacc输入文件的解析
  • 上下文无关文法到对应LR(1)文法的下推自动机的构造
  • LR(1)文法的下推自动机到相应分析表的构造
  • LR(1)总控程序的构造(查表程序)
  • LR(1)到LALR(1)的映射
  • 符号表的构建与相应管理程序
  • 语义动作程序的加入
  • SeuYacc的应用

工具使用

本次实验, 使用了众多的开源工具进行辅助, 下面我将列出最主要的几种. 这一节可以完全跳过阅读.

Linux

  • 操作系统

在此次开发中, 为了大家环境的统一, 也为了使用已有的成熟的开发工具 我们全组使用了Linux作为系统开发环境.

GCC

  • 编译器

作为编译器被使用: 项目中也大量使用了C++11的新特性, 使用成熟编译器极大的提高了 开发效率

GDB

  • 调试工具

    内存泄露以及Segmentation fault调试的利器, 有些时候针对某个断点的透彻调试更有

效率, GDB的命令行模式有时更加清晰明了

Git

  • 版本控制

    使用Git轻松进行了协作, 即使组很小, 我们也采用了协作方式, Git的使用大大减轻了

交流的困难

CMake(Makefile)

  • 编译安装工具

整个项目构建均使用CMake, 跨平台支持性良好, 可以支持众多的IDE构建项目. 动态链接库, 静态链接库的使用支持大大简化了项目构建难度, 使得开发者能够尽快的专注于代码

Qt Creator

  • IDE

    与CMake相仿的跨平台开发利器, 组员均在Linux上进行开发. 相比于Eclipse,

Qt CreatorCMake优秀的支持减轻了我们生成项目的烦恼

valgrind

  • 软件分析工具

    由于项目使用C++进行编写, 内存控制十分头疼, 使用valgrind. 可以方便分析泄露, 在

项目进行过程中, 有不止一处的内存泄露, 凭借valgrind可以很快找到泄露位置, 由于 我们水平所限, 仅用来进行泄露分析

lex&yacc

  • 编程工具

项目中使用了lex与yacc进行了语法与语义分析示例, 在项目尚未开始时, 我们需要首先对 Lex与Yacc进行理解, 而已有的工具可以帮助我们快速入门

Lex设计

Lex为整个项目的第一个核心组件, 下面本文档将会分为 进行介绍

Lex架构分析

此图形象的介绍了Lex的使用场景以及我们将要实现的目标: Lex编译器, 一个可以读 取Lex源程序(lex.l), 并生成lex.yy.c的工具, 抛开NFA, DFA这些专业术语不说, 我们已经对当前所做的项目的输入输出了解, 剩下的实现细节将由文档后文慢慢道来.

输入文件(lex源程序)

  • 由于实现难度, 本项目中使用的源程序与标准lex源程序有所不同, lex源程序存放在 ./input/require.l中, (源程序片段)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
%{
#include "stdio.h"
#include "y.tab.h"
#define LT 1 extern int lineno;

int isDigit(char ch)
{
if(ch <= '9' && ch >= '0')
return 1;
return 0;
}

int isLetter(char ch)
{
if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
return 1;
return 0;
}
%}

%!
letter=isLetter
digit=isDig
%!

%%
({letter}|_)({letter}|_|{digit})* {
int id = getKeyId(SYLEX_TEXT);
if(id != 0)
printf("<%s,->\n", SYLEX_TEXT);
else {
printf("<$ID,%s>\n", SYLEX_TEXT);
}
}
%$
{digit}+(%.{digit}*)?((E|e)(%+|-)?{digit}+)? {
printf("<$NUM,%s>\n", SYLEX_TEXT);
}
%%

标准的lex源文件是没有中间的%! %!段的, 自行编写程序时, [0-9], [a-zA-Z] 很难进行表述, 所以这里采用一种事先定义函数的形式, 可以由自定义程序进行单个 字符的解析

输出文件(lex词法解析程序)

  • 该输出文件中, 主要由scaner函数构成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//扫描函数
void SYLEX_scanner(char *str)
{
char ch = ' ';
while(ch != '\0')
{
//printf("%c %d\n", ch, SYLEX_STATE);
switch(SYLEX_STATE) {
case 0: {
//篇幅原因不进行展开
//...
break;
}
case 1: {
ch = *str++;
SYLEX_TEXT[SYLEX_TEXT_LEN++] = ch;
if(isLetter(ch)){
SYLEX_STATE = 30;
}
else if(isDigit(ch)){
SYLEX_STATE = 31;
}
else if(ch == '_'){
SYLEX_STATE = 32;
}
else {
SYLEX_TEXT[SYLEX_TEXT_LEN-1] = '\0';
SYLEX_TEXT_LEN = 0;
SYLEX_STATE = 0;
str --;
//---------------------
{ int id = getKeyId(SYLEX_TEXT); if(id != 0) printf("<%s,->\n", SYLEX_TEXT); else { printf("<$ID,%s>\n", SYLEX_TEXT); }}
//---------------------
}
}
break;
}
}
}
int main(int argc, char **args)
{
if(argc == 1)
{
printf("没有输入源文件名");
return 0;
}
else if(argc == 2)
{
strcpy(SYLEX_FILE_NAME, args[1]);
sprintf(SYLEX_OUT_FILE_NAME, "%s.out", SYLEX_FILE_NAME);
}
else
{
strcpy(SYLEX_FILE_NAME, args[1]);
strcpy(SYLEX_OUT_FILE_NAME, args[2]);
}
FILE* file = fopen(SYLEX_FILE_NAME, "r");
while(NULL != fgets(SYLEX_BUFF, SYLEX_MAXSIZE_BUFF, file))
{
++SYLEX_LINE;
SYLEX_scanner(SYLEX_BUFF);
}
return 0;
}

此文件为Lex程序的输出文件, 可以看到case 1中添加了有关解析式的使用, 在Lex运行 过程中, 将上方的lex源文件进行了正则解析, 并对匹配到的正则表达式进行操作, 在case1中, 我们可以得到下面的正则表达式所对应的操作输出

1
2
3
4
5
6
7
8
({letter}|_)({letter}|_|{digit})* {
int id = getKeyId(SYLEX_TEXT);
if(id != 0)
printf("<%s,->\n", SYLEX_TEXT);
else {
printf("<$ID,%s>\n", SYLEX_TEXT);
}
}

处理流程

  • 当我们已知了Lex程序的输入输出后, 接下来要介绍流程的介绍, 接下来, 文档将 会通过简单的示例介绍从正则表达式开始的整个流程,

1.假设我们有如下正则表达式a*(b|(cd?))+与表达式ef

2.进行正则表达式到NFA转换

转换过程

在Re2NFA类中, 定义有re2postpost2nfa函数, 分别完成中缀正则表达式转为后缀, 以及后缀表达式转换为NFA, 具体实现敬请查看项目代码中./lex/nfa.h

3.进行NFA表达式合并

合并过程

由于合并过程也是产生NFA的过程, 这里, 我们使用NFA2LIST类进行合并, 用户可以 不断调用merge函数进行合并, 合并时, 新建一个新的起始节点, 再将两个NFA的字符 集进行合并

4.NFADFA NFA到DFA

转换过程

采用子集构造法

使用NFA中的初始状态作为DFA的初始状态, 并进行闭包操作, 只经过标号为ϵ 的边所能到达的状态, 在实现中, 我将其称为findSimple, 从核心点衍生到所有点, 此函数用于核心点到其周围点的映射

以上图NFA为例, 节点0将会作为DFA的初始状态, findSimple函数将会进行扩展 将节点1, 3, 4, 7, 9也添加到DFA的初始状态.

这里我想说明一下, 核心点的设置是十分有必要的, 由于我们每产生一个新的DFA状态就要与先前存在过的DFA状态进行比较, 如果将该DFA 状态所对应的核心点均进行比较, 相对而言, 代价巨大, 设置了核心点后, 可以大大减少 比较次数.

下面我将使用伪代码进行描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while(存在未遍历的DFA状态) {
取出该状态;
for(每个输入符号a) {

if (状态经过a可以到达节点) {
将该节点作为新的状态的核心节点
}

if(新状态的核心节点数为0) {
没有新状态产生
continue
}

if(该状态已经存在) {
仅将该状态添加到`DFA`路径
} else {
创建新状态
将其定义为未遍历的情况
将新状态添加至`DFA`路径中
}
}
}

以上图的DFA状态0为例, 我们遍历a, b, c, d, e, f这些状态 同时, 我们将会发现可以构建这样一些核心节点的DFA状态, 括号中为核心节点 - 0 -> e -> 1 (16) - 0 -> a -> 2 (7) - 0 -> c -> 4 (15) - 0 -> b -> 3 (12)

拥有了核心节点之后可以使用findSimple进行扩展

重要数据结构定义

基础数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
* NFA节点
*
* Represents an NFA state plus zero or one or two arrows exiting.
* if c == Match, no arrows out; matching state.
* If c == Split, unlabeled arrows to out and out1 (if != NULL).
* If c < 256, labeled arrow with character c to out.
*
* 这里做一下解释: 枚举体中表示了一个节点的状态, 他可能没有出度(例如尾节点)或是一个节点,
* 或是两个节点. 当然, 我们可以确保所有的节点均的出度不会超过两个,并且能够保证如果为两个出度
* 其中一个出度一定为sigma边, 也就是可以直达的.
*
* if c == Match, 没有出度边, 意味着该状态为匹配状态
* if c == Split, 此状态表示有一条或两条sigma边时
* if c < 256 , 此状态有一条实边, 实边为out,非实边为out1
*/
class State {
int c;
State *out;
State *out1;
std::string endFunc; // 结束状态所对应的函数, 只有该点为Match时, 值可以视为有效
};

/*
* NFA片段, 取fragment之说
*/
class Frag
{
State *start; // 起始节点
State *end; // 尾节点
};

/**
* DFA 节点状态
*/
class DState {
std::map<DState*, int> out; // 记录DFA节点能够到达的状态以及路径
std::set<State*> coreState; // 当前状态所代表的NFA状态中的核心状态, 用于之后进行状态比较
std::set<State*> allState; // 记录所有可能状态, 在getAllState调用后被填充
bool hasTravel = false; // 构建DFA时, 表示该状态是否已经被遍历
bool isEnd = false; // 是否为接受节点
std::string endFunc; // 结束状态中所对应的执行函数, 只有该节点为结束状态才可以操纵该对象
};

NFA与DFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
* 每条正则语句对应于一条NFA
*
*/
class Re2NFA {
string func; // 该NFA所对应的终止状态的处理函数, 该NFA所对应的结局
State * nfa_s = NULL; // 保存解析后的数据
State * nfa_e = NULL; // 最终符合条件的状态
std::set<int> char_set; // 输入符号集合
};

/*
* 该类主要用来合并NFA, 合并完成后的NFA仍然为NFA, 只是不同的NFA链所对应的最终处理函数不同,
* 可以注意到, 该类也进行了new的操作. 我们遵循"谁创建, 谁释放"的原则, 由该类创建的对象, 最后
* 由自己进行统一的回收
*
*/
class NFA2LIST {
State *nfa_s = NULL;
std::set<int> char_set;
std::set<State*> st_create; // 统计新建的资源, 为了最终释放
};

// NFA 转换为DFA
class N2DFA {
DState *dstart;
NFA *nfa;
};

Lex

1
2
3
4
5
6
7
8
9
class Lex {
std::ostream *out = NULL; // 分析程序输出
std::istream *in = NULL; // Lex源文件输入

std::vector<Re2NFA*> re2NFAList;// 保存众多的NFA
NFA2LIST nfa2List; // 保存结合后的NFA

N2DFA* pN2DFA = NULL; // 保存解析完成后的DFA
};

词法分析程序的使用

我们获取了生成的词法分析程序(例如out.c), 接下来将要解析文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
☁  input  gcc out.c -o out # out就是我们的词法分析程序

☁ input cat main.c # 查看我们将要进行解析的文件
#include <stdio.h>
#include <string.h>
#include"aaa.h"

int main()
{
int a = 5;
int b = a + 3.5E3 - 5;
char s[] = "I love the world\n";
for(int i=0; i<5; i++)
printf("%s\n",s);
}

☁ input ./out main.c # 解析该文件
#include <stdio.h> //应该预处理的,暂时先忽略
#include <string.h> //应该预处理的,暂时先忽略
#include"aaa.h" //应该预处理的,暂时先忽略
<int,->
<$ID,main>
<(,->
<),->
<{,->
<int,->
<$ID,a>
<=,->
<$NUM,5>
<;,->
<int,->
<$ID,b>
<=,->
<$ID,a>
<+,->
...

Yacc设计

Yacc架构设计

Yacc

Lex类似, Yacc是作为生成y.tab.c的工具, 而y.tab.c也就是语法分析工具 可以了解到, 输入为Yacc源程序, 输出为y.tab.c. 本程序处理过程中, 将Yacc 处理程序集成到Yacc中, 并未将语法分析程序独立开来, 只是使用预测分析表进行了 简单测试

Yacc输入文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

%{

#include <stdio>


%}

%!
%token NUM
%head expr

%left + -
%left * +
%right UNINUS

%!
%%

expr : expr '+' expr {$$ = $1 + $3; }
| expr '-' expr {$$ = $1 - $3; }
| expr '*' expr {$$ = $1 * $3; }
| expr '/' expr {$$ = $1 / $3; }
| '('expr')' {$$ = $2;}
| NUM
|
;
%%

为了解析方便, 该语法与Yacc的标准语法略有不同, 不过这不影响文法解析.

%{, %}中包围的仍是语法输出的预定义, 由于我们不产生y.tab.c, 这里只作为占 位使用, %!, $!中包含了tocken, head, 以及leftright, 在这里均有意义 其中token记录终结符, head记录起始的非终结符(在上方为expr), left, right 记录优先级和结合律

Yacc输出

  • 在此项目中, Yacc是没有输出的, 我们将Yacc类中添加了parse函数, 此函数读取 词法分析器的生成文件, 进行解析输出

词法分析器输出文件

1
2
3
4
5
<$NUM,23>
<+,->
<$NUM,16>
<*,->
<$NUM,3>

parse函数输出

1
2
3
4
5
6
7
8
9
10
11
12
                  0                                                     s3
a 0 3 23 A->a
A 0 2 23 s8
A + 0 2 8 23 0 s3
A + a 0 2 8 3 23 0 16 A->a
A + A 0 2 8 18 23 0 16 s7
A + A * 0 2 8 18 7 23 0 16 0 s3
A + A * a 0 2 8 18 7 3 23 0 16 0 3 A->a
A + A * A 0 2 8 18 7 17 23 0 16 0 3 A->A*A
A + A 0 2 8 18 23 0 48 A->A+A
A 0 2 71 Accept
Accept

处理流程

  • 当我们已知了Yacc程序的输入输出后, 流程中将会精简无关的输入输出, 并且挑选主要 的逻辑流程进行介绍, 特别具体的细节, 请查看代码. 此处, 我们将以如下文法为例, 进行 流程分析
1
2
3
4
5
6
"S->S;A",
"S->A",
"A -> E",
"A->i=E",
"E->E+i",
"E->i"

1.文法的存储以及First集合的求解

文法被保存时, 首先进行转换, 具有相同的非终结符的产生式会被合并, 上文中的文法将会 这样保存

1
2
3
A -> E|i=E
E -> E+i|i
S -> A|S;A

First集合的求解调用makeFirst函数即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* 获取该文法的First集合, 通过dfs函就数进行计算
* @brief makeFirst
*/
void makeFirst() {
// 此处虽为循环调用, 但实际上执行时, 很多情况会直接返回, 复杂度并不很高
for (auto it : pExprVec) {
Expression *pExpr = it;
dfs(pExpr);
}
}

/**
* 此代码并非本人书写, 其中主要参考了如下代码:
* http://www.kancloud.cn/digest/compile-principle/143016
*
* 只能简单做下解析
* 对于FIRST集合的求解, 主要有4条规则
* 1. if X是终结符, 那么 FIRST(X) = {X}, 终结符的FIRST集就是它本身
* 2. if X不是非终结符, 且有产生式X→a…,a∈VT, 则 a∈FIRST(X),
* X→~,则~∈FIRST(X)
* 3. if X -> Y1 Y2 Y3 .. YK, 如果存在Y1 Y2 .. YK-1能够推导出 ~,
* 那么FIRST(YK)∈FIRST(X)
*
* 而在程序中采用了一种不太相同的思路:
*
* if 该项(X)已经完成解析 return
* else 标记为解析状态
*
* 遍历该项的所有产生式(例如 F->(E)|i 将会依次遍历F->(E), 与F->i):
*
* 遍历每个产生式中的单元 为x:
* if x为终结符, 直接加入 结束内层循环
*
* if x为非终结符:
* 取出该终结符对应的产生式
* dfs(产生式) 递归调用
* 将该项的的FIRST集合归并到FIRST(X)集合中
* if 产生式的存在~
* 说明规则三得到了满足, 需要继续看下一个非终结符的状态
* else
* 结束内层循环
*
* @brief dfs
* @param pExpr
*/
void dfs(Expression* pExpr);

上述代码的粘贴可能并不容易了解到函数的使用, 我将会在接下来进行一步步解析

我们依次来看, A -> E|i=E, 进行A -> E解析First(E)∈First(A), 深度优先遍历会 求解First(E), First(E) = i, 而后First(A) = First(E) ∩ {i}

而后S->A|S;A, 可知First(S)=First(A)

所以First(A) = First(S) = First(E) = {i}

2.进行LR1项集族构造

1
2
3
4
5
6
7
8
/**
* 此函数构建LR1状态转换图, 首先插入(push_back)初始状态. 因此, lrStateVec[0]为初
* 始状态, 并且开始调用getAllNextState(start), 如果此时状态增加了, 那么将会继续循环
* 直至所有状态都获取了它的下一个状态族
*
* @brief iterms
*/
void iterms();

接下来, 我将会从起始状态的构建开始说明整个项集族的构建过程

2.构建LR1起始状态

items函数中, 首先插入#->.S, $表达式作为闭包运算的起始

3.核心产生式的闭包运算

以起始状态的核心产生式闭包扩展为例, # -> .S term char: $, 该式进行扩展需要 用到LRState::findAllExpr函数, 该函数主要做了这样一件事: 不断遍历标准状态, 函数 中主要用到了LRState::findAllExpr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 函数主要在findAllExpr中被调用, 来增加当前状态中表达式的个数, 例如
*
* S-> .A, $ (输入为A$)
* 直接将A -> .<产生式>, $ 添加到向量组中
*
* S-> .ABC, $ (输入为ABC$)
* 将A -> .<产生式>, FIRST{B} 添加到向量组中
*
* S-> .Abc, $ (输入为Abc$)
* 将 A -> .<产生式>, b添加到向量组中
*
* @brief increaseState
* @param s
* @param term
*/
void increaseState(string &s);

4.LR1项集族状态转移

当我们达到某个状态, 并且已经由核心的产生式进行闭包运算, 接下来就需要到达下一个 状态, 此时, items函数调用LR1::getAllNextState进行扩展

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 获取该状态所有的后继状态, 如果该状态已经存在于之前的状态中, 那么将会将原状态添加到该状
* 态的后继状态族中, 此时不向状态向量组中添加状态
*
* 如果此时获得的状态为新的状态, 该状态添加到状态向量组中, 同时为状态进行编号, 编号信息
* 保存在state2id映射中
*
* @brief getAllNextState
* @param start
* @return
*/
bool getAllNextState(LRState *start);

5.ACTION与GOTO表的构建

在完成LR1项集族的构建后, 可以调用LR1::makeACTIONGOTO函数进行预测分析表的构建, 预测分析表的构建过程中, 面对二义性文法, 是有可能发生冲突的, 这里, 冲突主要体现在 Action表的构建过程中, 具体的优先级和结合性对表构造的影响将不在这里展开, 相信有 兴趣的读者会对代码进行探索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 构造Action表, 事实表明, 这是一个糟糕的函数, 即使使用了递归也无法解救这个函数
*
* 我们平时所建的LR1表需要考虑到二义性文法的问题, 一旦出现二义性文法, 我们需要做出说明.
* 如果某个文法是有二义性的, 而且文法中还未定义优先级和结合性, 那么在LR1阶段是被认为错误
* 的选择
* 同样, 如果某个文法定义了优先级和结合性, 那么, 我们需要在有冲突的位置做出反应, 对于
* 有二义性的位置, 需要做出抉择, 确保我们的预测分析表具有唯一性
*
* @brief actionHelp
* @param start
* @param res_action
* @param term
*/
void actionHelp(LRState *start, vector<vector<string>> &res_action,
map<string, int>& term);

/**
* @brief gotoHelp
* @param start
* @param res_goto
* @param nonTerm
*/
void gotoHelp(LRState *start, vector<vector<int>> &res_goto,
map<string, int>& nonTerm);

6.进行语法分析

一个LR语法分析器的模型

当我们有了ACTIONGOTO表之后, 需要对其进行应用, 这里, 我们直接以最终的输出为例, 这里, 并不是说我们的LR1只适用于当前的输入, 只是为了讲解方便, 并且该示例中的计算 过程经过了许久的验证. 整个语法如下

1
2
3
4
5
6
7
8

0: A -> .(A) term char: ? ---- {$$=$2;}
1: A -> .A*A term char: ? ---- {$$=$1*$3;}
2: A -> .A+A term char: ? ---- {$$=$1+$3;}
3: A -> .A-A term char: ? ---- {$$=$1-$3;}
4: A -> .A/A term char: ? ---- {$$=$1/$3;}
5: A -> .a term char: ? ----

ACTION表

表头为 ( ) * + - / NUM $

GOTO表

表头为A

待解析文本

1
2
3
4
5
<$NUM,23>
<+,->
<$NUM,16>
<*,->
<$NUM,3>

当我们读入NUM时 我们处于0状态, 此时对应的操作为s3, 进行移入操作, 并且处于 状态3, 而后我们读到+, 此时为r5, 使用第5个产生式进行规约, 如此继续, 下面为堆栈图

1
2
3
4
5
6
7
8
9
10
11
12
符号栈          状态栈                  实际计算栈                   当前动作
0 s3
a 0 3 23 A->a
A 0 2 23 s8
A + 0 2 8 23 0 s3
A + a 0 2 8 3 23 0 16 A->a
A + A 0 2 8 18 23 0 16 s7
A + A * 0 2 8 18 7 23 0 16 0 s3
A + A * a 0 2 8 18 7 3 23 0 16 0 3 A->a
A + A * A 0 2 8 18 7 17 23 0 16 0 3 A->A*A
A + A 0 2 8 18 23 0 48 A->A+A
A 0 2 71 Accept

重要数据结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
* 保存单个表达式, 例如
* S -> a | b
*
* 该表达式的形式主要用于语法定义, 且适合于求解FIRST集合
* @brief The Expression class
*/
class Expression {
string left;
set<string> right;
};

/**
* 单个表达式的表示, 在LR1状态转换图中, 单个的表达式需要有各种信息记录, 其中包括:
* 当前表达式解析到的位置, 当前表达式的终止符, 此表达式主要用于转换图中状态的记录
*
* 例如:
* S -> aB.c, $
* 其中.表示此次解析到达c字母之前, 而且此表达式的终止符为$
*
* @brief The SingleExpress class
*/
class SingleExpress {
string left;
string right;
string func;
int pos = 0;
char term;
};

/**
* 该类保存语法, 例如
* S -> aSb
* S -> ~
* @brief The Grammar class
*/
class Grammar {
map<string, Expression*> left2Expr;
map<string, set<char>> first;
string nonTermHead; // 获得非终结符的首结点
set<string> term; // 保存终结符的集合a, b, +, i ...
set<string> nonTerm; // 保存非终结符的集合(一定为大写字母) S, A, B ..

};


/**
* 该类记录了LR1状态转换图中的每一个状态, 对于各种状态信息来说, 我们需要有标准状态来与其进行
* 对比,
* 此类拥有静态变量lrStateStandard, 在调用此类时, 首先进行getStandardState, 将标准
* 状态进行记录, 在结束使用后, 请主动调用deleteStandardState
*
* @brief The LRState class
*/
class LRState {
std::map<char, LRState*> out;
/**
*
* acc = -2; 表示该状态属于中间状态, 只能进行移入
* acc = -1; 表明该状态为可以接受, 即为完成
* acc >= 0; 表示使用第acc个数字的产生式可以将进行规约
*
*/
int acc = -2;

/**
* 对于普通的状态, 该变量表示核心的expr
*
* 对于静态变量lrStateStandard, 此时的coreExpr就表示所有的标准的产生式, 并且每个
* 产生式位置也为固定值
* @brief coreExpr
*/
vector<SingleExpress*> coreExpr;

};

/**
* 整个LR1语法分析类:
* 承载了包括语法解析, 状态构建, 状态去重, 状态转移, Action表与Goto表的构建
* @brief The LR1 class
*/
class LR1 {
Grammar *grammar = NULL; // 该LR1解析中对应的文法

/*
* 存放ACTION表与GOTO表
*/
vector<vector<string>> res_action;
vector<vector<int>> res_goto;
map<string, int> actionTerm;
map<string, int> gotoNonTerm;

// 保存优先级, 例如 * > +, 则保存为 <*, +>
map<string, string> prior;

// 保存结合性, 如果为*左结合, 则保存为 <*, 1>; 右结合保存为<*, 2>, 以此进行区分
map<string, int> assoc;
};

语法分析程序的使用

  • 具体的解析过程上面已经列出, 接着主要说明语法分析程序的使用
1
2
3
4
# 使用词法分析工具生成待解析文件
./out input/yacc_test.c > lex.out

./bin/yacc_rel ./input/require.y lex.out

项目中遇到的问题

  • 对于一个比较大的项目来说, 遇到的问题是很多的, 这里我挑选一些整个过程中遇到的 一些令人困扰的问题, 也在此告诫自己要不断提高编程水平来解决之后的学习生活中遇到 的问题.

Lex中遇到的问题

1.正则表达式中缀转后缀

逆波兰表达式的构建是我们要做的第一步, 中缀转后缀其实很早就已经做过, 但是做为整个 程序的输入, 需要首先保持起正确性. 而且, 正则表达式的后缀与普通的计算式的后缀略有 不同, 因为普通的计算式是通过+-*/进行连接, 而正则表达式是通过不可见的连接符进行 连接.

因此, 写代码之前首先进行类似问题的查找, 确定已经有别人写好的代码, 对其进行参考 才最终完成, 我认为这是一个在项目构建中无法回避的问题, 有些时候, 我们由于一些 项目上的需求需要事先查看别人的程序进行参考.

2.NFA的定义

NFA是转换DFA的基础, NFA的表示一直到最终构建词法分析器的时候仍然存在. 正则表达式 的后缀形式转NFA在一定程度上是具有确定形式的. 这里, 我们首先论证了, 每个NFA节点 最多有两个出度即可表示所有的情况, 包括a+, a*, a|b .. , 其实这一步是影响整个Lex构建 的问题所在, 由于自己的小失误, 导致在整个NFA构建中a|b形式的NFA构建出现了问题, 一直影响到最后词法分析器的构成, 不得不说, 这样恼人的小错误造成了整个系统的失误

3.正则表达式对应动作的实现

程序当前状态: 之前的程序中其实已经完成了由NFA向DFA的转换, 但是, 多个NFA有多种结束与初始状态, 如果分 别将NFA转换为DFA, 依旧无法解决分析的问题, 因此, 此处需要现将NFA进行合并操作, 合并之后 再转换为DFA.

问题: 想法总是很好, 但随之而来的问题也并不简单, 多个NFA有多种结束状态, 每种结束状态对应的操 作函数不尽相同, 因此, 我们虽然将NFA进行了合并, 但是, 每个NFA所携带的结束状态的信息却 无法合并. 此时, 才是真正的尴尬, 如果无法解决这个问题, 程序是无法继续进行的.

解决方案: 此时, 我向State与DState类中, 添加了endFunc变量, 总体来看, 变量的添加造成了多余空 间的使用, 也使得程序并不优雅. 但此时, 主体框架已经定义, 不可能过多的修改NFA与DFA的创 建类, 当状态过多时, 将会导致程序的内存占用率上升.

由于我追求了DFA与NFA尽可能的分离, 并且分别定义了State类以及DState类, 由此带来的问 题只能通过使用多余空间进行解决. 此种方法有利有弊, 但不是权宜之计, 是解决之道.

4.正则表达式状态的表示

函数输入:

1
2
3
4
5
6
7
8
({letter}|_)({letter}|_|{digit})* {
int id = getKeyId(SYLEX_TEXT);
if(id != 0)
printf("<%s,->\n", SYLEX_TEXT);
else {
printf("<$ID,%s>\n", SYLEX_TEXT);
}
}

这里给出了一个匹配变量名的正则表达式(字母,数字,下划线组成, 只能由字母与下划线开头的字符串) 以及表达式对应的操作

首先调用getReAndFunc将正则表达式与处理逻辑相分离, 我们可以得到re以及func分别对应于两 部分, re = ({letter}|)({letter}||{digit})* func = {…} 而后的正则表达式进行处理, 因为表达式中有{letter},{digit}这样的长名称, 因此, 我们 通过state2ch来进行 {letter} -> char 的替换. 生成的正则表达式将会变为: re_s = (a|)(a||b)* 这里的a, b仅为填充字符, 真实的替换后正则表达式中, a b均为 不可见的字符

另外: 对于(%=?)这样的正则表达式, 因为表达式中有’‘存在, 直接匹配将会出现错误, 因此, 我们使用%进行转义, 而正则表达式中的转义为*, 我们也在此处进行修改, 它将会变为: (*=?)

基础的处理过正则表达式后, 我们将正则表达式与其对应的处理函数存储进入NFA类中 Re2NFA *pre2Nfa = new Re2NFA(re_s, func);

Yacc中遇到的问题

1.产生式的表示

万事总是开头难, 从一开始构建Yacc时, 就无法回避表达式的保存问题, 因为构建LR1 状态族时需要考虑First集合的构建, 一开始的数据结构选择很重要. 选择Expression 可以保存S -> a | b这样的表达式, 很方便的寻找同一个非终结符对应的产生式, 但也就是这样的产生式, 造成了后来LR1构建的麻烦. 由于Expression类中保存的表达式混杂在了一起, 如果每次状态转换进行检验, 工作量 巨大, 由于不堪此类的困扰, 所以在构造项集族时使用了新的自定义的类SingleExpression 状态转移使用的S -> aB.c, $

2.求解闭包操作(由核心的产生式进行扩展)

整个扩展过程中, 最初只是想要从核心产生式到全部产生式的形式, 到最后却发现了, 在扩展过程中, 我们将会遇到产生式的结尾(好吧, 是我没有考虑到), 而后的调参过程还是很辛苦的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if (pos >= right.size()) { // 如果当前位置已经处于末尾, 则不进行处理
i++;

if (right.size() == 1 && right.at(0) == nonTermHead.at(0)) { // 当前状态为可接受
//cout << right.at(pos - 1) << endl;
this->acc = -1;
} else { // 不可接受状态, 但已经到达末尾
// this->termAll += term;
// cout << "************" << endl;
// cout << this->termAll<< endl;
// cout << "************" << endl;

this->acc = this->findExprByLeftRight(sExpr->left, right); // 找寻该表达式在标准表达式中的位置
}
continue;
}

CMake使用中的问题

1.CMake进行库的构建

项目中涉及到了大量的.cpp, .h文件, 如果没有合适的管理工具是无法做到所有人进度 同步的, 以Lex为例

1
2
3
4
5
set(SOURCE_LIB ./lex.cpp ./lex.h
./nfa.cpp ./nfa.h
./dfa.cpp ./dfa.h
./state.h ./state.cpp)
add_library(lex ${SOURCE_LIB})
  1. 添加输入文件

构建过程中需要用到一些输入文件, 由于CMake是代码外进行构建, 需要同时将LexYacc的文件进行输入, 下面可以实现将文件拷贝到编译的目录中.

1
2
3
4
5
file(COPY
./main.c ./require.l
./run.sh ./MyMake
./yacc_test.c ./require.y
DESTINATION ${PROJECT_BINARY_DIR}/input)

小组分工

  • 本次的课程设计项目由三个人组成, 分别是09014310冯盼贺, 09014312冯裕浩,
  • 09014315张春秋

Lex

正则表达式中缀至后缀, 后缀到NFA, NFA到DFA, Lex语法分析程序的构建(读取lex源文件, 生成语法分析程序) lex源文件的书写, lex源文件的规范定义

Yacc

存取表达式并生成First集合, LR1项集族的构建, 预测分析表的构建, 读取Yacc源文件进行解析 解析结果的应用(使用预测分析表进行语法分析)

参考文献

自制Lex-词法分析器生成器C++

lex与yacc入门示例

正规表达式转NFA(C++)

CMakeFile命令之file

代码实现Thompson构造:由简单到复杂的构建NFA状态机

词法分析(4)—NFA与DFA的转化 编译原理

Lex词法分析生成器

编程实现计算FIRST集和FOLLOW集C++之(三)处理候选式:把空加入非终结符的First集

编译原理算法实现