学校课程 NFA DFA Lex & Yacc 编译器

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 Creator对CMake优秀的支持减轻了我们生成项目的烦恼

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类中, 定义有re2post与post2nfa函数, 分别完成中缀正则表达式转为后缀, 以及后缀表达式转换为NFA, 具体实现敬请查看项目代码中./lex/nfa.h

3.进行NFA表达式合并

合并过程

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

4.NFA到DFA 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, 以及left和right, 在这里均有意义 其中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语法分析器的模型

当我们有了ACTION与GOTO表之后, 需要对其进行应用, 这里, 我们直接以最终的输出为例, 这里, 并不是说我们的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是代码外进行构建, 需要同时将Lex与 Yacc的文件进行输入, 下面可以实现将文件拷贝到编译的目录中.

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集

编译原理算法实现