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的初始状态, 并进行闭包操作, 只经过标号为$\epsilon$ 的边所能到达的状态, 在实现中, 我将其称为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集

编译原理算法实现