一、基础知识题

  • 1 题,15 分

二、正则表达式 → DFA 分析题

  • 1 题,15 分
  • 正则表达式做实验一;实验二,讲稿例题
    • id 的正则表达式怎么写

    • 各种进制数正则表达式怎么写,小数,科学记数

    • 然后直接把 DFA 画出来,NFA 过渡(手工方法)

三、自顶向下分析设计题

  • 1 题,18 分
  • 写文法
  • 检查左递归,左公因子,消除
  • First,如果有 epsilon 还要求 follow
  • 遇到终结做匹配,非终结做函数调用

四、LR 分析题

  • 1 题,18 分

五、语义分析题

  • 1 题,18 分

六、综合分析设计

  • 1 题,16 分

第一章

程序语言的分类

  • 程序翻译的方式有哪几种? 有何不同?
    • 低级语言
      • 机器语言和汇编语言
    • 高级语言
  • 编译程序包含有多少个阶段, 各阶段的功能任务分别是什么?
    • 扫描程序:源代码-记号(lexeme/token)
    • 语法分析器:记号-语法树
    • 语义分析器:语法树-注释树
    • 源代码优化器:注释树-中间代码
    • 代码生成器:中间代码-目标代码
    • 目标代码优化程序:目标代码-目标代码

第二章

重点:

  • 正则表达式运算以及构建方法
  • 正则表达式 → NFA → DFA → DFA 最小化
  • 词法分析程序的生成方法
  • 实验一与实验二

TODO: 讲稿例题,实验一内容写正则表达式做之后转 DFA,最小化 + 源程序

第三章

文法、语言的概念

  • 文法的分类是怎样的? 它们之间有何关系?
    • 0-3 型文法,包含关系
    • 平时都是二型文法
      • 规则左边单一非终结符
  • 推导、规约、语法树、文法的二义性?
    • 找一个句子,有两种或以上语法书
    • 怎么消除二义性,讲了三个方法
      • 限制规则(补充说明)?
        • 例:自然语言 else 和 没匹配的 if
      • 修改语法书写格式(改造文法规则),修改优先级别。
  • 如何画语法树?
    • 分析树,两种方法
    • 保留信息
    • tiny 各个语句的语法树结构是什么样的,实验 3 设计说明
  • 文法二义性的消除方法有多少种?

重点

  • 文法的构建问题
  • 自顶向下分析法的问题: 左公共因子、左递归
    • first 元素跟 follow 的元素的交集是空的问题
    • 消除,提取,花括号,右递归
  • 文法的简化
  • First 与 Follow 集合 (实验四)

第四章

重点

  • 左公因子和左递归
    • 没有 epsilon
      • first 交集
    • 有 epsilon
      • first 和 follow 交集
    • 直接和间接左递归
  • 递归下降语法分析方法 (或称递归子程序)
  • LL(1) 分析方法
  • LL(1) 判断方法
  • LL(1) 分析表
  • LL(1) 分析过程
  • 实验三

第五章

  • LR(0) DFA、LR(1) DFA、LALR(1) DFA?

  • LR(0) 分析表、LR(1) 分析表、SLR(1) 分析表、LALR(1) 分析表?

  • LR(0) 文法、LR(1) 文法、SLR(1) 文法、LALR(1) 文法?如何判断 LR(0) 文法、SLR(1) 文法?

  • 文法如何利用 LR(0)、LR(1)、SLR(1)、LALR(1) 进行语法分析?

  • 实验四

  • follow 和移进后面的符号求交集,看空不空

    • 空 SLR1
    • 不空,不是,但可以最长串匹配,只做 shift 不 reduce,可以 SLR1 做
    • reduce reduce conflict,求 follow,两两相交 follow,不能只求一次?

第六章

  • 语法制导翻译的方法有多少种?
    • 四种/三种 LR,规约时候用语义动作
  • 中间代码?表示形式如何?
  • 如何将一个算术表达式转换为逆波兰表示、四元组表示、三元组表示?
    • 算术表达式转汇编的百度云盘,后缀有代码
    • 例题
  • 如何将一段代码翻译为中间代码(后缀、三元组、四元组)?几种常用语句的翻译——能写出语义函数或语义动作
    • (1)算术表达式
    • (2)说明语句
    • (3)赋值语句
    • (4)逻辑表达式
    • (5)条件判断语句—— if 语句
    • (6)循环语句——while 语句
    • (7)扩展到其他程序设计语句

如何用文法规则描述算术表达式

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

十进制数的文法规则

d -> [0-9]
Nat -> d+
SNat -> (+|-)?Nat
Number -> SNat(.Nat)?((E|e)SNat)?

后缀表达式的语义动作

文法规则和语义动作

E' -> E			{E'.val = E.val;}
E  -> EE+		{E1.val = E2.val + E3.val;}
E  -> EE-		{E1.val = E2.val - E3.val;}
E  -> EE*		{E1.val = E2.val * E3.val;}
E  -> EE/		{E1.val = E2.val / E3.val;}
E  -> n			{E.val = n.val;}

程序

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
// 解析后缀表达式并计算其值
double parsePostfixExpression(const string& expression) {
    stack<double> stack;  // 创建一个用于存储数字的栈
    istringstream tokens(expression);  // 使用字符串流读取表达式
    string token;  // 存储单个元素(数字或操作符)
 
    while (getline(tokens, token, ' ')) {  // 按空格分割表达式
        if (isdigit(token[0]) || (token.length() > 1 && isdigit(token[1]))) {
            // 如果元素是数字,将其转换为double类型并压入栈
            stack.push(stod(token));
        } else {
            // 如果元素是操作符,则从栈中弹出所需的操作数
            double rightOperand = stack.top();  // 弹出右操作数
            stack.pop();
            double leftOperand = stack.top();  // 弹出左操作数
            stack.pop();
 
            // 根据操作符进行计算
            if (token == "+") {
                stack.push(leftOperand + rightOperand);
            } else if (token == "-") {
                stack.push(leftOperand - rightOperand);
            } else if (token == "*") {
                stack.push(leftOperand * rightOperand);
            } else if (token == "/") {
                stack.push(leftOperand / rightOperand);
            }
        }
    }
 
    // 返回栈顶元素,即最终的计算结果
    return stack.top();
}
int main() {
    string expression;
    cout << "Enter a postfix expression (e.g., 2 3 + 5 4 - *): ";
    getline(cin, expression);  // 读取后缀表达式
 
    double result = parsePostfixExpression(expression);  // 解析并计算后缀表达式
    cout << "Result: " << result << endl;  // 输出结果
 
    return 0;
}
 

变量定义的语义动作

文法规则和语义动作

var i : integer

var i,j,k : float

D -> 'var' L ':' T  		{foreach(id in L) addSymbolTable(id,T.type);}
L -> id,L | id   			{L.list = L1.list + {id.name};}
T -> 'integer' 				{T.tyoe = 'integer';}
T -> 'float'				{T.type = 'float';}

程序

存储结构

// 定义一个符号表的类
class SymbolTable {
public:
    // 添加符号到符号表
    void addSymbol(const string& name, const string& type) {
        table[name] = type;
    }
 
    // 打印符号表
    void printTable() {
        for (const auto& pair : table) {
            cout << pair.first << " : " << pair.second << endl;
        }
    }
 
private:
    unordered_map<string, string> table; // 符号表存储变量名和类型
};

函数

// 前向声明
string parseT(const string& s, size_t& pos);
vector<string> parseL(const string& s, size_t& pos);
void parseD(const string& s, SymbolTable& table);
 
// 解析类型 T -> 'integer' | 'float'
string parseT(const string& s, size_t& pos) {
    if (s.substr(pos, 7) == "integer") {
        pos += 7; // 移动位置
        return "integer";
    } else if (s.substr(pos, 5) == "float") {
        pos += 5; // 移动位置
        return "float";
    } else {
        cerr << "Error: Expected 'integer' or 'float', found '" << s.substr(pos) << "'\n";
        exit(EXIT_FAILURE);
    }
}
 
// 解析变量列表 L -> id, L | id
vector<string> parseL(const string& s, size_t& pos) {
    vector<string> list;
    size_t nextPos = s.find(',', pos);
 
    while (nextPos != string::npos) {
        list.push_back(s.substr(pos, nextPos - pos)); // 添加变量名到列表
        pos = nextPos + 1; // 更新位置
        nextPos = s.find(',', pos);
    }
 
    size_t endPos = s.find(':', pos);
    list.push_back(s.substr(pos, endPos - pos)); // 添加最后一个变量名
    pos = endPos + 1; // 更新位置
 
    return list;
}
 
// 解析声明 D -> 'var' L ':' T
void parseD(const string& s, SymbolTable& table) {
    size_t pos = 0;
    if (s.substr(pos, 3) == "var") {
        pos += 4; // 跳过 "var" 和空格
        vector<string> variables = parseL(s, pos); // 解析变量列表
        string type = parseT(s, pos); // 解析类型
 
        // 将变量和类型添加到符号表
        for (const auto& id : variables) {
            table.addSymbol(id, type);
        }
    } else {
        cerr << "Error: Expected 'var', found '" << s.substr(pos) << "'\n";
        exit(EXIT_FAILURE);
    }
}

使用

int main() {
    SymbolTable symbolTable;
    string declaration;

    cout << "Enter a variable declaration (e.g., var i,j,k : float): ";
    getline(cin, declaration);

    parseD(declaration, symbolTable); // 解析声明并更新符号表
    symbolTable.printTable(); // 打印符号表

    return 0;
}

带小数的二进制数转换为十进制数

文法规则和语义动作

B' -> B.B	{B'.val = B1.val + B2.val/pow(2,B2.len);}
B  -> BD	{B1.val = B2.val*2 + D.val; B1.len = B2.len + D.len;}
B  -> D		{B.val = D.val; B.len = D.len;}
D  -> 0		{D.val = 0; D.len = 1;}
D  -> 1		{D.val = 1; D.len =1;}

代码

存储结构

#include <iostream>  // 引入输入输出流库
#include <cmath>     // 引入数学库,用于计算幂
#include <string>    // 引入字符串库
 
// 定义一个类来存储二进制数字的值和长度
class Binary {
public:
    double val;  // 二进制数的十进制值
    int len;     // 二进制数的长度
 
    Binary() : val(0), len(0) {}  // 构造函数,初始化 val 和 len
};

函数

// 函数声明
Binary parseD(const string &s, size_t &pos);
Binary parseB(const string &s, size_t &pos);
 
// 解析单个二进制数字(D -> 0 | 1)
Binary parseD(const string &s, size_t &pos) {
    Binary d;
    if (s[pos] == '0' || s[pos] == '1') {  // 检查当前字符是否为 '0' 或 '1'
        d.val = s[pos] - '0'; // 将字符转换为整数
        d.len = 1;            // 设置长度为 1
        pos++;                // 移动到下一个字符
    } else {
        // 如果不是 '0' 或 '1',输出错误信息并退出程序
        cerr << "Error: Expected '0' or '1', found '" << s[pos] << "'\n";
        exit(EXIT_FAILURE);
    }
    return d;  // 返回解析出的二进制数字
}
 
// 解析二进制数的整数部分或小数部分(B -> BD | D)
Binary parseB(const string &s, size_t &pos) {
    Binary b;
    b = parseD(s, pos); // 首先解析第一个二进制数字
 
    // 继续解析后续的二进制数字,直到字符串结束或遇到非二进制数字
    while (pos < s.length() && (s[pos] == '0' || s[pos] == '1')) {
        Binary d = parseD(s, pos);
        b.val = b.val * 2 + d.val;  // 计算当前二进制数的十进制值
        b.len += d.len;             // 更新长度
    }
 
    return b;  // 返回解析出的二进制数
}
 
// 解析整个带小数点的二进制数,并计算其十进制值(B' -> B.B)
double parseBPrime(const string &s) {
    size_t pos = 0;
    Binary b1 = parseB(s, pos);  // 解析小数点前的部分
 
    if (pos < s.length() && s[pos] == '.') {
        pos++; // 跳过小数点
        Binary b2 = parseB(s, pos);  // 解析小数点后的部分
        return b1.val + b2.val / pow(2, b2.len);  // 计算并返回十进制值
    } else {
        // 如果没有遇到小数点,输出错误信息并退出程序
        cerr << "Error: Expected '.', found '" << s[pos] << "'\n";
        exit(EXIT_FAILURE);
    }
}
 

使用

int main() {
    string binaryString;
    cout << "Enter a binary number (如 101.01): ";  // 提示用户输入
    cin >> binaryString;  // 读取用户输入的二进制字符串
 
    double decimalValue = parseBPrime(binaryString);  // 解析二进制字符串并转换为十进制
    cout << "Decimal value: " << decimalValue << endl;  // 输出十进制值
 
    return 0;  // 程序结束
}

正则->…->词法分析程序

正则转后缀表达式

int getPriority(int c);//得到运算符的优先级
bool isOperator(char c);//判断是不是运算符
//转为后缀表达式
string toSuffix(const string &expr)
{
    stack<char> op;
    string suffix;
    for (const auto &c: expr)
    {
        if (isOperator(c))
        {//是运算符
            if (op.empty())//栈空,直接入栈
                op.emplace(c);
            else
            {//优先级更大的运算符全部出栈
                while (!op.empty())
                {
                    int t = op.top();
                    if (getPriority(c) <= getPriority(t))
                    {
                        op.pop();
                        suffix.push_back(t);
                    }
                    else
                        break;
                }
                op.emplace(c);
            }
        }
        else
        {
            if (c == '(')//左括号直接入栈
                op.emplace(c);
            else if (c == ')')
            {//遇到右括号,一直出栈,直到遇到左括号
                while (op.top() != '(')
                {
                    suffix.push_back(op.top());
                    op.pop();
                }
                op.pop();
            }
            else
            	suffix.push_back(c);//操作数直接放入表达式中
        }
    }
    while (!op.empty())
    {//取出剩余的运算符
        suffix.push_back(op.top());
        op.pop();
    }
    return suffix;
}
 
bool isOperator(char c)
{//判断是不是运算符
    switch (c)
    {
        case '*':
        case '|':
        case '^':
            return true;
        default:
            return false;
    }
}
 
int getPriority(int c)
{//运算符的优先级
    int level = 0; // 优先级
    switch (c)
    {
        case '(':
            level = 1;
            break;
        case '|':
            level = 2;
            break;
        case '^':
            level = 3;
            break;
        case '*':
            level = 4;
            break;
        default:
            break;
    }
    return level;
}

最小化DFA

void minimizeDFA(DFA &dfa) {
  // 1. 初始化:将DFA的状态分为两组,一组是接受状态,另一组是非接受状态
  set<int> acceptStates(dfa.end.begin(), dfa.end.end());
  set<int> otherStates;
  for (auto &p : dfa.G) {
    // 如果状态不是接受状态,则添加到另一组
    if (acceptStates.count(p.first) == 0) {
      otherStates.insert(p.first);
    }
  }
  // 初始状态分区
  vector<set<int>> partitions = {acceptStates, otherStates};
  bool updated = true;
 
  // 2. 不断细分状态集合
  while (updated) {
    updated = false;
    for (int i = 0; i < partitions.size(); i++) {
	  auto p = partitions[i];
      map<int, set<int>> newPartitions;
      for (int state : p) {
        // 生成一个状态的key,用于比较状态是否等价
        int key = 0;
		for (auto &trans : dfa.G[state]) {
		  // 检查转移的目标状态属于哪个集合
		  for (int j = 0; j < partitions.size(); j++) {
		    if (partitions[j].count(trans.second)) {
		      key |= (1 << j);
		      break;
		    }
		  }
		}
        // 将状态按key分类
        newPartitions[key].insert(state);
      }
      // 如果有新的细分,则更新状态分区
      if (newPartitions.size() > 1) {
        updated = true;
        partitions.erase(partitions.begin() + i);
        for (auto &p : newPartitions)
          partitions.emplace_back(p.second);
        break;
      }
    }
  }
  // 3. 构建新的DFA
  DFA newDFA;
  // 旧状态到新状态的映射
  map<int, int> newStateMapping;
  int newStatedId = 0;
 
  // 为每个分区分配新的状态ID
  for (auto &partition : partitions) {
    for (int state : partition) {
      newStateMapping[state] = newStatedId;
    }
    newStatedId++;
  }
 
  // 构建新DFA的转移和终结状态
  for (auto &partition : partitions) {
    // 选择每个集合的代表状态
    int representative = *partition.begin();
    for (auto &trans : dfa.G[representative]) {
      newDFA.G[newStateMapping[representative]][trans.first] =
          newStateMapping[trans.second];
    }
    // 如果代表状态是终结状态,则相应的新状态也是终结状态
    if (dfa.end.count(representative)) {
      newDFA.end.insert(newStateMapping[representative]);
    }
  }
  // 更新原DFA为最小化的DFA
  dfa = newDFA;
}

DFA->语法分析程序

​ 假设DFA 存储结构为一个二维矩阵,矩阵的行表示状态,列表示输入字符,DFA [m][n]表示状态 m 经过输入 n 后到达的状态,-1 表示该路径不可达。

  1. 生成边缘字符数组的代码

    CString GenerateEdgeArray() {
        CString text = L"char edge[] = { '";
        CString s(edge[0]);
        text += s + L"'";
        for (int j = 1; j < edgeNumber; j++) {
            CString s(edge[j]);
            text += L" , '" + s + L"'";
        }
        text += L" };\n";
        return text;
    }
  2. 生成DFA矩阵的代码

    CString GenerateDFAMatrix() {
        CString num1, num2;
        num1.Format(_T("%d"), DtranNumber);
        num2.Format(_T("%d"), edgeNumber);
        CString text = L"int DFA[" + num1 + L"][" + num2 + L"] = {\n";
     
        for (int i = 0; i < DtranNumber; i++) {
            text += L"    {";
            for (int j = 0; j < edgeNumber; j++) {
                if (DFATable->GetValue(i, j) < 0) {
                    num1.Format(_T("%d"), -1);
                } else {
                    num1.Format(_T("%d"), DFATable->GetValue(i, j));
                }
                text += num1 + (j != edgeNumber - 1 ? L"," : L"");
            }
            text += (i != DtranNumber - 1 ? L"},\n" : L"}\n");
        }
        text += L"};\n";
        return text;
    }
  3. 生成字符位置获取函数的代码

    CString GenerateGetPosFunction() {
        CString num2;
        num2.Format(_T("%d"), edgeNumber);
        CString text = L"int getPos(char c) {\n";
        text += L"    int i = 0, pos = -1;\n";
        text += L"    for (i = 0; i < " + num2 + L"; i++) {\n";
        text += L"        if (edge[i] == c) pos = i;\n";
        text += L"    }\n";
        text += L"    return pos;\n";
        text += L"}\n";
        return text;
    }
  4. 生成主函数的代码

    CString GenerateMainFunction() {
        CString text = L"int main() {\n";
        text += L"    int j = 0, start = 0, column;\n";
        text += L"    char *str = new char[256];\n";
        text += L"    cin >> str;\n";
        text += L"    while (str[j] != '\\0') {\n";
        text += GenerateSwitchStatement();
        text += L"    }\n";
        text += L"    cout << (start == 接受状态 ? \"YES\" : \"NO\") << endl;\n";
        text += L"    return 0;\n";
        text += L"}";
        return text;
    }
  5. 生成switch语句的代码

    CString GenerateSwitchStatement() {
        CString switchstam = L"    switch (str[j]) {\n";
        for (int j = 0; j < edgeNumber; j++) {
            CString case1;
            CString s(edge[j]);
            case1 = L"        case '" + s + L"':\n";
            case1 += L"            column = getPos(str[j]);\n";
            case1 += L"            if (column != -1 && start != -1) {\n";
            case1 += L"                start = DFA[start][column];\n";
            case1 += L"            } else {\n";
            case1 += L"                cout << \"NO\" << endl;\n";
            case1 += L"                return -1;\n";
            case1 += L"            }\n";
            case1 += L"            break;\n";
            switchstam += case1;
        }
        switchstam += L"        default:\n";
        switchstam += L"            cout << \"NO\" << endl;\n";
        switchstam += L"            return -1;\n";
        switchstam += L"            break;\n";
        switchstam += L"    }\n";
        switchstam += L"    j++;\n";
        return switchstam;
        }
  6. 整合所有函数

    CString DFAToPro() {
        CString text = L"#include<iostream>\nusing namespace std;\n";
        text += GenerateEdgeArray();
        text += GenerateDFAMatrix();
        text += GenerateGetPosFunction();
        text += GenerateMainFunction();
        return text;
    }

对应的语法分析程序

#include<iostream>
using namespace std;
 
// 边缘字符数组
char edge[] = { '字符1', '字符2', ..., '字符N' };
 
// DFA 矩阵
int DFA[状态数][输入字符数] = {
    {状态1的转移, ..., 状态1的转移},
    {状态2的转移, ..., 状态2的转移},
    ...,
    {状态M的转移, ..., 状态M的转移}
};
 
// 获取字符在边缘字符数组中的位置
int getPos(char c) {
    int i = 0, pos = -1;
    for (i = 0; i < 输入字符数; i++) {
        if (edge[i] == c) pos = i;
    }
    return pos;
}
 
int main() {
    int j = 0, start = 0, column;
    char *st+w char[256];
    cin >> str;
    while (str[j] != '\0') {
        switch (str[j]) {
            case '字符1':
                column = getPos(str[j]);
                if (column != -1 && start != -1) {
                    start = DFA[start][column];
                } else {
                    cout << "NO" << endl;
                    return -1;
                }
                break;
            // 更多的 case 语句
            ...
            default:
                cout << "NO" << endl;
                return -1;
                break;
        }
        j++;
    }
    cout << "YES" << endl;
    return 0;
}

First&Follow

存储结构

// 假设产生式以某种方式存储
map<char, vector<string>> productions;
map<char, set<char>> followSets;

First

void Grammar::buildFirstSet() {
    // first set of terminal is itself
    for (const auto &ch: terminals_) {
        firstSet_[ch] = {ch};
    }

    // initialize first set of non-terminal
    for (const auto &ch: nonTerminals_) {
        firstSet_[ch] = {};
    }
    // first set of non-terminal
    bool changing = true;
    while (changing) {
        changing = false;
        for (const auto &p: productions_) {
            char lhs = p.first;
            for (const auto &rhs: p.second) {
                bool foundEpsilon = true;
                size_t before = firstSet_[lhs].size();
                size_t after;

                for (const auto &c: rhs) {
                    // if the symbol is a non-terminal
                    if (isupper(c)) {
                        // copy all elements except epsilon
                        for (const auto &ch: firstSet_[c]) {
                            if (ch != epsilon) {
                                firstSet_[lhs].insert(ch);
                            }
                        }
                        after = firstSet_[lhs].size();

                        // If nothing is added or epsilon is not in FIRST(symbol), then stop
                        if (before == after || firstSet_[c].find(epsilon) == firstSet_[c].end()) {
                            foundEpsilon = false;
                            break;
                        }
                    } else {
                        // if the symbol is a terminal
                        firstSet_[lhs].insert(c);
                        foundEpsilon = false;
                        break;
                    }
                }

                // If epsilon was found in all symbols of production, add epsilon to the non-terminal
                if (foundEpsilon) {
                    firstSet_[lhs].insert(epsilon);
                }

                // check if the first set of non-terminal is changed
                if (before != firstSet_[lhs].size()) {
                    changing = true;
                }
            }
        }
    }
}

Follow

// 辅助函数:检查是否为终结符
bool isTerminal(char symbol) {
    // 根据文法定义实现
    // 通常,非终结符是大写字母,终结符是小写字母或特殊符号
    return !isupper(symbol) || symbol == '$' || symbol == 'ε';
}
 
void Grammar::buildFollowSet() {
    // Initialize follow sets for all non-terminals
    for (const auto &item: productions_) {
        followSet_[item.first] = {};
    }
 
    // The follow set of the start symbol contains $
    followSet_[startSymbol_].insert('$');
 
    bool changing = true;
    while (changing) {
        changing = false;
 
        for (const auto &item: productions_) {
            char left = item.first;
 
            for (const auto &right: item.second) {
                set<char> trailer = followSet_[left];
 
                for (int i = right.size() - 1; i >= 0; i--) {
                    char symbol = right[i];
 
                    // 非终结符
                    if (isupper(symbol)) {
                        // add trailer to the follow set of the symbol
                        size_t before = followSet_[symbol].size();
                        followSet_[symbol].insert(trailer.begin(), trailer.end());
                        size_t after = followSet_[symbol].size();
                        if (before != after) {
                            changing = true;
                        }
 
                        // if the symbol can derive epsilon
                        if (firstSet_[symbol].find(epsilon) != firstSet_[symbol].end()) {
                            // add the first set of the symbol to the trailer
                            for (const auto &ch: firstSet_[symbol]) {
                                if (ch != epsilon) {
                                    trailer.insert(ch);
                                }
                            }
                        } else {
                            // if the symbol cannot derive epsilon
                            trailer = firstSet_[symbol];
                        }
                    } else {
                        // 终结符
                        trailer = {symbol};
                    }
                }
            }
        }
    }
}

递归下降生成四元式

if语句

#include<iostream>
#include<string>
string nextToken();
void match(const string);
string parseCondition();
void parseIfStatement();
string parseOperand();
string parseOperator();
string generateTemp();
string getNextToken();
void parseForInitStatement();
void parseForIterationStatement();
void parseExpression();
void emit(string op, string arg1, string arg2, string result);
 
void parseStatement(){
    if(nextToken()=="if"){
        parseIfStatement();
    }
}
 
void parseIfStatement(){
    match("if");
    match("(");
    parseCondition();
    match(")");
    parseStatement();
    if(nextToken()=="else"){
        match("else");
        parseStatement();
    }
}
 
string parseCondition(){
    string operand1 = parseOperand();
    string op = parseOperator();
    string operand2 = parseOperand();
 
    //生成四元组
    string temp = generateTemp();
    emit(op,operand1,operand2,temp);
    return temp;
}
 
string parseOperand() {
    // 解析并返回操作数(变量或常量)
    // 这可以是一个词法单元,例如:变量名或数字
    return getNextToken();
}
 
string parseOperator() {
    // 解析并返回操作符
    // 例如,如果下一个词法单元是 '<',则返回它
    return getNextToken();
}
 
string generateTemp() {
    // 生成新的临时变量名,例如:temp1, temp2, ...
    static int tempCount = 0;
    return "temp" + to_string(++tempCount);
}
 
void emit(string op, string arg1, string arg2, string result) {
    // 将四元组添加到中间代码的列表中
    // 例如,将 (op, arg1, arg2, result) 存储或打印出来
    cout << "(" << op << ", " << arg1 << ", " << arg2 << ", " << result << ")" << endl;
}

for语句

void parseForStatement() {
    match("for");
    match("(");
    parseForInitStatement();   // 解析for循环的初始化部分
    match(";");
    parseExpression();         // 解析for循环的条件表达式
    match(";");
    parseForIterationStatement(); // 解析for循环的迭代表达式
    match(")");
    parseStatement();          // 解析for循环体
}
 
void parseForInitStatement() {
    // 解析for循环的初始化部分,例如:int i = 0;
    // 这可能是一个赋值语句或者空语句
}
 
void parseForIterationStatement() {
    // 解析for循环的迭代部分,例如:i++
    // 这通常是一个表达式
}

while语句

void parseWhileStatement() {
    match("while");
    match("(");
    parseExpression();         // 解析while循环的条件表达式
    match(")");
    parseStatement();          // 解析while循环体
}

语法树

例如逻辑表达式

expr -> expr OR term | term
term -> term AND factor | factor
factor -> NOT factor | ( expr ) | variable
variable -> a | b | c | ...  // 布尔变量

存储结构

enum NodeType { AND, OR, NOT, VARIABLE };
 
struct Node {
    NodeType type;
    string value; // 仅在节点类型为VARIABLE时使用
    Node* left;  // 左子节点
    Node* right; // 右子节点,对于NOT和VARIABLE类型的节点,这个可能为空
 
    Node(NodeType type, Node* left = nullptr, Node* right = nullptr, string value = "")
        : type(type), left(left), right(right), value(value) {}
};

算法

Node* parseExpr() {
    Node* node = parseTerm();
    while (currentToken == "OR") {
        consume("OR");
        node = new Node(OR, node, parseTerm());
    }
    return node;
}
 
Node* parseTerm() {
    Node* node = parseFactor();
    while (currentToken == "AND") {
        consume("AND");
        node = new Node(AND, node, parseFactor());
    }
    return node;
}
 
Node* parseFactor() {
    if (currentToken == "NOT") {
        consume("NOT");
        return new Node(NOT, parseFactor());
    } else if (currentToken == "(") {
        consume("(");
        Node* node = parseExpr();
        consume(")");
        return node;
    } else if (isVariable(currentToken)) {
        string var = currentToken;
        consumeVariable();
        return new Node(VARIABLE, nullptr, nullptr, var);
    }
    // 错误处理
}

判断SLR1文法

#include <string>
#include <vector>
using namespace std;
 
const int MAX_STATES = M;  // 最大状态数,M表示总共有M个状态
const int MAX_RULES = N;   // 最大规则数,N表示每个状态最多有N个规则
 
// 定义一个结构体用于表示单个文法规则
struct GrammarRule {
    string leftSide; // 文法的左侧
    string rightSide; // 文法的右侧
    int dotPosition;  // 点的位置
};
 
// LL结构用于表示语法状态
struct GrammarState {
    GrammarRule rules[MAX_RULES]; // 存储所有文法规则
    int ruleCount;                // 该状态中语法的数量
} states[MAX_STATES];             // states 数组存储所有的状态
 
// 假设以下函数已定义
bool hasIntersection(const vector<string>& set1, const vector<string>& set2);
vector<string> Follow(const string& symbol);
vector<string> First(const string& symbol);
 
bool isSLR1() {
    vector<int> reductionItems; // 存储归约项的编号
 
    // 遍历所有状态
    for (int stateIndex = 0; stateIndex < MAX_STATES; stateIndex++) {
        reductionItems.clear();
 
        // 查找归约项
        for (int ruleIndex = 0; ruleIndex < states[stateIndex].ruleCount; ruleIndex++) {
            GrammarRule& currentRule = states[stateIndex].rules[ruleIndex]; // 引用当前规则以减少冗余
 
            if (currentRule.dotPosition == currentRule.rightSide.size()) {
                // 如果点在文法右侧的末尾,表示是归约项
                reductionItems.push_back(ruleIndex);
            }
        }
 
        // 检测归约-归约冲突
        for (size_t i = 0; i < reductionItems.size(); i++) {
            for (size_t j = i + 1; j < reductionItems.size(); j++) {
                GrammarRule& ruleI = states[stateIndex].rules[reductionItems[i]];
                GrammarRule& ruleJ = states[stateIndex].rules[reductionItems[j]];
 
                if (hasIntersection(Follow(ruleI.leftSide), Follow(ruleJ.leftSide))) {
                    return false;
                }
            }
        }
 
        // 检测移进-归约冲突
        for (size_t i = 0; i < reductionItems.size(); i++) {
            GrammarRule& reductionRule = states[stateIndex].rules[reductionItems[i]]; // 引用归约规则以减少冗余
 
            for (int ruleIndex = 0; ruleIndex < states[stateIndex].ruleCount; ruleIndex++) {
                GrammarRule& currentRule = states[stateIndex].rules[ruleIndex];
 
                if (currentRule.dotPosition != currentRule.rightSide.size()) {
                    if (!currentRule.rightSide.empty()) {
                        char nextSymbol = currentRule.rightSide[currentRule.dotPosition];
                        vector<string> firstSet = First(nextSymbol);
                        vector<string> followSet = Follow(reductionRule.leftSide);
 
                        if (hasIntersection(firstSet, followSet)) {
                            return false;
                        }
                    }
                }
            }
        }
    }
 
    return true; // 所有检查通过,是SLR(1)文法
}

SLR1分析表

存储结构

// 定义文法符号和文法规则的数据类型
typedef char Symbol;
struct GrammarRule {
    Symbol leftSide;
    string rightSide;
};
 
// 定义状态和项集的数据类型
struct Item {
    GrammarRule rule;
    int dotPosition;
};
 
struct State {
    vector<Item> items;
};
 
// 定义项集族和文法的数据类型
vector<State> states;
vector<GrammarRule> grammarRules;

辅助函数

// 辅助函数声明
State closure(const State& state); // 计算状态的闭包
State goTo(const State& state, Symbol symbol); // 计算在给定符号下的转移
bool isTerminal(Symbol symbol); // 判断符号是否是终结符
bool isNonTerminal(Symbol symbol); // 判断符号是否是非终结符
vector<Symbol> getGrammarSymbols(); // 获取所有文法符号
int findStateIndex(const State& state); // 根据状态找到其索引
int findRuleIndex(const GrammarRule& rule); // 根据规则找到其索引
set<Symbol> followSet(Symbol symbol); // 计算符号的FOLLOW集

算法

map<pair<int, Symbol>, string> actionTable; // ACTION表
map<pair<int, Symbol>, int> gotoTable; // GOTO表
void buildSLRTables() {
    // 构建ACTION表和GOTO表的主要逻辑
    for (int i = 0; i < states.size(); ++i) { // 遍历所有状态
        for (auto symbol : getGrammarSymbols()) { // 遍历所有文法符号
            State newState = goTo(states[i], symbol); // 计算状态转移
            if (!newState.items.empty()) {
                int newStateIndex = findStateIndex(newState); // 找到新状态的索引
                if (isTerminal(symbol)) {
                    // 如果symbol是终结符,则在ACTION表中添加移进项
                    actionTable[{i, symbol}] = "S" + to_string(newStateIndex);
                } else if (isNonTerminal(symbol)) {
                    // 如果symbol是非终结符,则在GOTO表中添加项
                    gotoTable[{i, symbol}] = newStateIndex;
                }
            }
        }
        // 检查归约和接受情况
        for (auto& item : states[i].items) {
            if (item.dotPosition == item.rule.rightSide.length()) { // 检查是否可以进行归约
                if (item.rule.leftSide == 'S') { // 假设'S'是起始符号
                    actionTable[{i, '$'}] = "ACC"; // 在ACTION表中标记为接受
                } else {
                    // 对于其他规则执行归约操作
                    int ruleIndex = findRuleIndex(item.rule); // 找到规则的索引
                    for (auto symbol : followSet(item.rule.leftSide)) { // 遍历FOLLOW集
                        actionTable[{i, symbol}] = "R" + to_string(ruleIndex); // 在ACTION表中添加归约项
                    }
                }
            }
        }
    }
}