实验 2 —— 语法程序的设计与实现

Posted on 2021-11-21 Edited on 2021-11-23 In 专业 , 专业课程 , 编译原理 Views: Symbols count in article: 4.6k Reading time ≈ 4 mins.

1 实验 2 —— 语法程序的设计与实现

1.1 实验内容及要求

1.1.1 实验内容

编写语法分析程序，实现对算术表达式的语法分析。要求所分析算数表达式由如下的文法产生：

1
2
3

E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|num

1.1.2 实验要求

在对输入的算术表达式进行分析的过程中，依次输出所采用的产生式。

1.1.3 实验方法要求

方法 1：编写递归调用程序实现自顶向下的分析。
方法 2：编写 LL(1) 语法分析程序，要求如下。（必做）
- 编程实现算法 4.2，为给定文法自动构造预测分析表。
- 编程实现算法 4.1，构造 LL(1) 预测分析程序。
方法 3：编写语法分析程序实现自底向上的分析，要求如下。（必做）
- 构造识别该文法所有活前缀的 DFA。
- 构造该文法的 LR 分析表。
- 编程实现算法 4.3，构造 LR 分析程序。
方法 4：利用 YACC 自动生成语法分析程序，调用 LEX 自动生成的词法分析程序。

1.2 程序设计说明

1.2.1 总体设计说明

本次实验我编程实现了前三种语法分析方法：递归调用分析程序、LL(1) 语法分析程序、LR(1) 语法分析程序。我使用了 C++ 的面向对象特性，将三种方法以及各种数据的存储封装在了 Grammar 类（见 Grammar.h）中。

1.2.1.1 数据结构

类型定义

using Symbol = std::string;                                                            // 符号类型
using SymbolSet = std::set<Symbol>;                                                    // 符号集合类型
using VecSymbol = std::vector<Symbol>;                                                 // 符号的 vector 类型
using RHS = std::vector<Symbol>;                                                       // 右部产生式 (right hand side) 类型
using VectorRHS = std::vector<RHS>;                                                    // 右部产生式的集合
using UpdateMap = std::unordered_map<Symbol, SymbolSet>;                               // 存储更新式的类型
using SymbolToRHS = std::unordered_map<Symbol, RHS>;                                   // 符号到右部产生式的映射类型
using SymbolTable = std::unordered_map<Symbol, std::unordered_map<Symbol, RHS>>;       // 行列表头为 Symbol 的二维表（预测分析表类型）
using Productions = std::unordered_map<Symbol, VectorRHS>;                             // 产生式集合类型
using ProdSplit = std::pair<Symbol, RHS>;                                              // 单个产生式类型
using ProdCnt = std::unordered_map<int, ProdSplit>;                                    // 带编号的产生式集合类型
using Project = std::pair<ProdSplit, SymbolSet>;                                       // 项目类型
using ProjectMap = std::map<ProdSplit, SymbolSet>;                                     // 项目集合类型
using ProjectCluster = std::unordered_map<int, ProjectMap>;                            // 项目族类型
using ActGotoTable = std::unordered_map<int, std::unordered_map<Symbol, std::string>>; // LR1 分析表类型

Grammar 类的私有属性

class Grammar
{
private:
    SymbolSet N;                                  // 非终结符集合
    SymbolSet T;                                  // 终结符集合
    Productions P;                                // 所有产生式
    Symbol S;                                     // 文法起始符号 S
    VecSymbol s;                                  // 待分析的串
    int pointer = -1;                             // 当前指向的位置
    Symbol ch = "";                               // 当前指向的字符
    std::unordered_map<Symbol, SymbolSet> first;  // first 集合
    std::unordered_map<Symbol, SymbolSet> follow; // follow 集合
    SymbolTable LL1AnaTable;                      // LL1 分析表
    ProdCnt extensionP;                           // 带编号的拓广文法
    ActGotoTable LR1AnaTable;                     // LR1 分析表
    ProjectCluster C;                             // 规范项目族
};

Grammar 类的常量

class Grammar
{
public:
    static const int ERR_MISSING_R_BRACKET = 1; // 错误状态代码
    static const int ERR_MISSING_OBJECT = 2;    // 错误状态代码
    static const int ERR_MISSING_OPERATOR = 3;  // 错误状态代码
    const RHS ERR = { "ERR" };                  // 错误状态
    static const int SPLIT_LINE_WIDTH = 60;     // 用于格式化输出
};

1.2.1.2 通用函数说明（Grammar.cpp）

Grammar() 默认构造函数

默认构造函数将为 Grammar 类内 N、T、P、S 赋初值，默认的文法使用实验要求的示例文法

Grammar::Grammar()
{
    this->N = { "E", "T", "F" };
    this->T = { "+", "-", "*", "/", "(", ")", "num" };
    this->S = "E";
    this->P["E"] = { {"E", "+", "T"}, {"E", "-", "T"}, {"T"} };
    this->P["T"] = { {"T", "*", "F"}, {"T", "/", "F"}, {"F"} };
    this->P["F"] = { {"(", "E", ")"}, {"num"} };
}

error() 错误处理函数

错误处理函数的参数是错误状态码（Grammar 类内有相关静态变量），传入 0 代表未知错误。LL(1) 和 LR(1) 分析程序遇到错误时没有分析错误类型，全部调用了 error(0)。

void Grammar::error(int errState)
{
    switch (errState)
    {
    case Grammar::ERR_MISSING_R_BRACKET:
        std::cout << "错误：括号不匹配" << std::endl;
        break;
    case Grammar::ERR_MISSING_OBJECT:
        std::cout << "错误：缺少运算对象" << std::endl;
        break;
    case Grammar::ERR_MISSING_OPERATOR:
        std::cout << "错误：缺少运算符号" << std::endl;
        break;
    default:
        std::cout << "未知错误" << std::endl;
        break;
    }
    std::cout << std::endl << std::endl;
    system("pause");
    exit(0);
}

输入输出函数

1
2
3

void Grammar::output() const; // 输出文法
void Grammar::inputS();       // 读入待分析的串
void Grammar::input();        // 读取用户输入的文法

forwardPointer() 指针前移操作

指针前移，并更新 ch 中的值

void Grammar::forwardPointer()
{
    pointer++;
    if (pointer < s.size())
        ch = s[pointer];
    else
        ch = "\0";
}

1.2.1.3 main 函数说明

构造文法对象
提供分析方案的选择
提供各个分析方案的调用

1.2.2 方法 1：递归调用分析程序（1_recursive_analysis.cpp）

1.2.2.1 函数调用关系图

1.2.2.2 设计状态转移图

1.2.3 方法 2：LL(1) 语法分析程序（2_LL(1)_analysis.cpp）

1.2.3.1 函数调用关系图

1.2.3.2 函数功能及实现思路

请见源程序以及程序注释

1.2.4 方法 3：LR(1) 语法分析程序（3_LR(1)_analysis.cpp）

1.2.4.1 函数调用关系图

1.2.4.2 函数功能及实现思路

请见源程序以及程序注释

1.3 源程序

Compiler_Labs/Lab2_syntax_analysis at master · thatmee/Compiler_Labs (github.com)

1.4 程序测试及成果说明

1.4.1 递归调用分析程序

1.4.2 LL(1) 分析程序

1.4.3 LR(1) 分析程序

1.4.4 错误测试——递归调用分析程序

1.4.5 错误测试——LL(1) 分析程序

1.4.6 错误测试——LR(1) 分析程序

1.5 值得注意的问题总结

VS2019 常量中有换行符、报错缺少 ; 等奇怪的问题

多半是编码的问题，记录 VS2019 如何修改编码：
getline 有时被跳过导致无法输入数据的问题

C++中getline被跳过 - wswang - 博客园 (cnblogs.com)
unordered_map 的key值问题

自定义的类型作为 key，需要自己重写哈希函数，或者改为使用 map。但是 map 的效率远不如 unordered_map，最优思路还是重写哈希函数。

1.6 仍待改进的地方

没有使用程序实现 LL(1) 文法的改写（消除二义性、消除左递归、提取左公因子）
程序中使用大量较为复杂的数据类型，执行效率有待考量
LL(1) 和 LR(1) 分析程序的错误报告不能报告错误类型。