一、基础知识题
- 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 交集
- 直接和间接左递归
- 没有 epsilon
- 递归下降语法分析方法 (或称递归子程序)
- 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语言符号//是行注解且不可以超过一行。注释不能嵌套。