Compiler Course

一、基础知识题

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 最小化
- Finite Automata
词法分析程序的生成方法
实验一与实验二

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 表示该路径不可达。

生成边缘字符数组的代码：

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;
}

生成 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;
}

生成字符位置获取函数的代码：

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;
}

生成主函数的代码：

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;
}

生成 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;
    }

整合所有函数：

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表中添加归约项
                    }
                }
            }
        }
    }
}

项目

TINY

program->stmt-sequence
stmt-sequence-> stmt-sequence ;statement |statement
statement->if-stmt|repeat-stmt|assign-stmt|read-stmt|write-stmt
if-stmt->if exp then stmt-sequence end|if exp then stmt-sequence else stmt-sequence end
repeat-stmt->repeat stmt-sequence until exp
assign-stmt->identifier := exp
read-stmt->read identifier
write-stmt->write exp
exp->simple-exp comparison-op simple-exp |simple-exp
comparison-op-> < | = |<= | <> |>= |>
simple-exp->simple-exp addop term |term 
addop-> + |-
term->term mulop factor | factor 
mulop-> * | / |%
factor->(exp) | number | identifier

(1). 关键词： if then else end repeat until read write 不区分大小写

(2). 专用符号： + – * / % < <> ⇐ >= > = { } ; :=

(3). identifier和number，则定义： identifier：字母开头，后面可跟若干个字母或数字符号，且不区分大小写 number：数字符号开头，后面可跟若干个数字也可以抽象地表示为： identifier = letter(letter|digit)* number = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9

(4). 空格由空白、换行符和制表符组成。

(5).用表示{ }注释,注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。

{ 这是一个多行注释的示例
它展示了注释可以如何跨越多行
但不能嵌套其他注释 }

read x
read y
{ 单行注释示例 }
z := x + y;  { 在语句末尾添加注释 }
write z

if x = 0 then
    y := 1
else
    y := y / (x * 2 + 1)   { 使用多个运算符和括号 }
end

repeat
    x := x - 1
    write x
until x = 0

{ 使用所有比较运算符 }
if x < y then write x
if x > y then write y
if x <= y then write x
if x >= y then write y
if x <> y then write y
if x = y then write x

{ 复杂表达式的使用 }
a := 100 * (b + c / 10) - 5 % 2

MiniC

program-> definition-list
definition-list-> definition-list definition | definition
definition-> variable-definition | function-definition
variable-definition-> type-indicator ID ；|type-indicator ID[NUM]；
type-indicator-> int | float | double|void
function-definition-> type-indicator ID（parameters）compound-stmt
parameters->parameter-list | void
parameter-list->parameter-list, parameter | parameter
parameter-> type-indicator ID | type-indicator ID[ ]
compound-stmt-> { local-definitions statement-list }
local-definitions-> local-definitions variable-definition |empty
statement-list-> statement-list statement | empty
statement->expression-stmt | compound-stmt | condition-stmt|dowhile-stmt | return-stmt
expression-stmt-> expression ； | ；
condition-stmt-> if(expression) statement |if（expression）statement else statement
dowhile-stmt->do statement while ( expression) ；
return-stmt->return ；| return expression ；
expression-> variable=expression | simple-expression
variable->ID |ID[expression]
simple-expression->additive-expression relop additive-expression
ditive-expression
relop-><=|<|>|>=|==|!=
additive-expression->additive-expression addop term | term
addop->+|-
term->term mulop factor | factor
mulop->*|/|%
factor->(expression )| variable | call | NUM
call->ID(arguments)
arguments->argument-list | empty
argument-list->argument-list,expression | expression

1).下面是语言的关键字: e1se if int float double return void do while 所有的关键字都是保留字,并且必须是小写。

2).下面是专用符号: _ + - * / % < ⇐ > >= == != = ；, ( ) [ ] { } //行注解

3).其他标记是ID和NUM ，通过下列正则表达式定义: ID= (|letter)(|letter|digit)* NUM=digit digit *(.digit digit *)? letter= a | .. | z | A | .. | Z digit=0 | .. | 9 小写和大写字母是有区别的。

4).空格由空白、换行符和制表符组成。空格通常被忽略,除了它必须分开ID、NUM关键字。

5).注释用通常的C语言符号//是行注解且不可以超过一行。注释不能嵌套。

Fish Touching🐟🎣

Explorer

Compiler Course

一、基础知识题

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

id 的正则表达式怎么写

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

三、自顶向下分析设计题

四、LR 分析题

五、语义分析题

六、综合分析设计

第一章

程序语言的分类

第二章

重点:

第三章

文法、语言的概念

重点

第四章

重点

第五章

第六章

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

十进制数的文法规则

后缀表达式的语义动作

文法规则和语义动作

程序

变量定义的语义动作

文法规则和语义动作

程序

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

文法规则和语义动作

代码

正则 →…→词法分析程序

正则转后缀表达式

最小化 DFA

DFA→语法分析程序

First&Follow

存储结构

First

Follow

递归下降生成四元式

if 语句

for 语句

while 语句

语法树

存储结构

算法

判断 SLR1 文法

SLR1 分析表

存储结构

辅助函数

算法

项目

TINY

MiniC

Graph View

Table of Contents

Backlinks