懒得写这么大的模拟了,想学的可以去看看我的项目QAQ
很显然,这是一道编译原理题目(我的专项awa)
编译原理 - 编译器结构
首先,编译器由Lexer,Parser,(Codegen,Optimizer)组成
然而严格来讲这道题需要的是解析器,那么结构变成:
Lexer, Parser, Interpreter
Lexer
Lexer负责生成tokens(符号表),就比如说:
#include<iostream>
#include<cstdio>
using namespace std;int main() {return 0;
}
依据题意,你可以舍弃前三行,然后利用正则表达式进行搜索。
很显然你看到了题目给你的上下文无关法里面有:
NAME ::= 仅包含大小写字母、数字、下划线的非空字符串,且不以数字开头。
转换为正则表达式就是:
[a-zA-Z_][a-zA-Z0-9_]*
还有整数
INT_CONSTANT ::= 仅包含数字的非空字符串,且不以0开头,或这个字符串就是0。
转换为正则表达式就是:
[1-9][0-9]*|0
然后你就可以利用std::regex
正则表达式进行搜索了。
当然,你还要使用regex搜索一些关键字:
int, if, for, while, return, cin, cout, endl
以及一些符号(自己看上下文无关法)
Parser
Parser负责生成AST(抽象语法树),那么你需要根据上下文无关法生成对应的语法树节点。
首先你需要定义一个节点类,然后根据上下文无关法生成对应的节点,比如:
// shared_ptr是C++11引入的智能指针,用于自动管理内存
#include<memory>
using namespace std;
class Node{public:AstType type; // 节点类型Token token; // 节点对应的tokenvector<shared_ptr<Node>> children; // 子节点Node(AstType type, Token token) : type(type), token(token) {} // 构造函数
};
然后你需要根据上下文无关法生成对应的节点,比如:
// 生成一个变量声明节点
shared_ptr<Node> varDecl(Token name, Token type) {shared_ptr<Node> node(new Node(AstType::VarDecl, name));node->children.push_back(make_shared<Node>(AstType::Type, type));return node;
}
然后自上而下依次解析递归生成语法树。(还是那句话,自己看上下文无关法)
比如:
#include<iostream>
#include<cstdio>
using namespace std;int main() {return 3*1-2;
}
对应的语法树就是:
intmain[] // 没有参数,所以是空数组(STATEMENTS)return(EXPRESSION)*31-2
Interpreter
Interpreter负责解释AST,那么你需要根据上下文无关法解释对应的语法树节点。
首先你需要写一个虚拟机进行输入输出流控制:
class VM {public:// cin从输入流中读取一个整数// cout输出一个整数到输出流中// putchar输出一个字符到输出流中// endl输出一个换行符到输出流中
}
当然,虚拟机的属性是static
。
假设你现在有N个整数要输入,那么你可以:
deque<int> istream; // 输入流
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {int x;scanf("%d", &x);istream.push_back(x);
}
然后你就可以在VM
中写一个cin
函数了:
int cin() {int x = istream.front();istream.pop_front();return x;
}
在解析树中,你可以用类似DFS的方法来解释语法树节点。比如:
void Interpreter::visit(Node* node) {switch (node->type) {case AstType::Program:visitProgram(node);break;case AstType::VarDecl:visitVarDecl(node);break;case AstType::Type:visitType(node);break;/*...*/}
}
在visitProgram
中,你需要遍历语法树中的所有VarDecl
节点,然后调用visitVarDecl
来解释这些节点。在visitVarDecl
中,你需要解释Type
节点,然后解释Identifier
节点,最后解释Expression
节点。
当你使用cin
或者cout
时,你需要调用VM
中的对应函数。
最后,你需要写一个main
函数来运行你的解释器:
int main() {// 读取输入// 构造语法树// 解释语法树return 0;
}
结语
由于代码过长(且过于麻烦),这里就不贴了(实则没写)。如果有对编译原理感兴趣的童鞋可以去看看我自己写的编程语言:
Cabbagelang