小C语言–词法分析程序
#include <bits/stdc++.h>
using namespace std;
string s[2010];
string temp;
int check(char c) {
//运算符输出1，数组输出2，字母输出3，界符输出4
//其他字符输出3（因为可能下划线之类的字符出现在自定义标识符中）
if (c == '=' || c == '-' || c == '+' || c == '*' || c == '/' || c == '>' ||c == '<' || c == '!')
return 1;
if (c >= '0' && c <= '9') return 2;
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) return 3;
if (c == '{' || c == '}' || c == ',' || c == ';' || c == '(' || c == ')')
return 4;
return 3;
}
void check_s(string s) {
//判断字符串为整数、关键字还是自定义标识符
if (temp.size() == 0) return;
int f = 0;
for (int i = 0; i < s.size(); i++)
if (check(s[i]) == 3) {//如果有一个字符为字母，则肯定不是整数
f = 1;
break;
}
//检查是否为关键字
if (s == "main" || s == "if" || s == "else" || s == "for" || s == "while" ||
s == "int") {
cout << "(keyword," << s << ')' <<endl;
return;
}
//不是关键字且f=1则为自定义标识符
if (f == 1) {
cout << "(identifier," << s << ')' << endl;
} else {//否则为数字
cout << "(integer," << s << ')' << endl;
}
}
int main(int argc, char const *argv[]) {
int n = 0;
while(cin >> s[n++]);//输入所有的字符串，存储在string数组中
for(int i = 0; i < n; i++){//遍历每个字符串
for(int j = 0; j < s[i].size(); j++) {//遍历字符串中的每个字符
switch (check(s[i][j])) {
case 1 : {//当前字符为运算符
check_s(temp);//处理运算符之前的字符串，下同
temp.clear();//清空，下同
if (j + 1 < s[i].size() && check(s[i][j + 1]) == 1)//判断是否为双字符的运算符
printf("(operator,%c%c)\n",s[i][j],s[i][j+1]),j++;//下标下移
else
printf("(operator,%c)\n", s[i][j]);
break;
}
case 2://数字加入temp
temp += s[i][j];
break;
case 3://字母加入temp
temp += s[i][j];
break;
case 4: {//处理界符
check_s(temp);
temp.clear();
printf("(boundary,%c)\n",s[i][j]);
break;
}
}
}
check_s(temp);//注意最后可能还剩下没有输出的字符串，需要进行处理
temp.clear();
}
return 0;
}
识别浮点常量问题
#include <bits/stdc++.h>
using namespace std;
int check(char c) {
if(c <= '9'&&c >= '0') return 1;
if(c == '+' || c == '-') return 2;
return 0;
}
int main(int argc, char const *argv[]) {
string s;
cin >> s;
int cnt = 0;//记录有几个 '.'和'e','E'
int i = 0;
int front = 0;//记录某个符号前数字的长度
while(i < s.size()) {//遍历字符串
if(s[i] == 'e' || s[i] =='E'){
//e和E的前面不能没有数字，同时不能有两个以上的'e'或'.'，同时不能在末尾，同时后面只能接数字或者正负号
if(front == 0 || cnt >= 2 || i == s.size() - 1 || check(s[i+1]) == 0) {
puts("NO");
return 0;
}
cnt++;//记录小数符的个数
front = 0;//记录下一个符号之前数字的长度，所以要清空
}
else if(s[i] == '.') {
// '.'的前面不能没有数字，同时前面不能有'.'或'E'，同时不能在末尾，同时后面只能接数字或者正负号
if(front == 0 || cnt != 0|| i == s.size() - 1 || check(s[i+1]) == 0) {
puts("NO");
return 0;
}
cnt++;//同上
front = 0;
}
else if(s[i] == '+' || s[i] == '-') {
//正负号前不能有数字，且后面必须接数字
if(front!=0 || i == s.size() - 1 || check(s[i+1]) != 1) {
puts("NO");
return 0;
}
front = 0;
}
else if(check(s[i]) != 1) {
//如果不为数字以及其他合法字符，则输出NO
puts("NO");
return 0;
}else//如果为数字，则记录数字长度的front+1
front++;;
i++;
}
//如果小数符有一个或两个(一个'.' + 一个 'E')则合法，否则不是浮点数
if(cnt == 1 || cnt == 2) puts("YES");
else puts("NO");
return 0;
}
Python版本
正则表达式yyds！
import re
s = r'[+-]?\d+((\.\d+)([Ee][+-]?\d+)?|([eE][+-]?\d+))$'
if re.match(s,input().strip()) :
print("YES")
else :
print("NO")
表达式语法分析——递归子程序法
这题需要注意的是，对于句子：$E \rightarrow TG$ 和 $T \rightarrow FS$ 需要先判断一下 $SELECT$ 集再进行递归，如果输入字符不属于 $SELECT$ 集则直接输出 ERROR。
当然对于这道题是需要计算SELECT集的，但是对于书上的递归下降子程序法是不需要判断的，直接往下递归就行，不过如果遇到的文法中包含句子 $E \rightarrow F|S$ ，那么就不能用递归下降子程序法了，因为不知道选取哪个候选式进行递归，此时就需要计算SELECT集了。
下面给出的代码是在PTA上可以过的（但自认为与递归子程序法的描述有些出入）：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
void T();
void G();
void S();
void F();
string s;
int pos, cnt;
void E() {
if (s[pos] != 'i' && s[pos] != '(') {
cout << "error" << endl;
exit(0);
}
printf("%d E-->TG\n", cnt++);
T();
G();
}
void G() {
if (s[pos] == '+') {
printf("%d G-->+TG\n", cnt++);
pos++;
T();
G();
} else
printf("%d G-->&\n", cnt++);
}
void T() {
if (s[pos] != 'i' && s[pos] != '(') {
cout << "error" << endl;
exit(0);
}
printf("%d T-->FS\n", cnt++);
F();
S();
}
void S() {
if (s[pos] == '*') {
printf("%d S-->*FS\n", cnt++);
pos++;
F();
S();
} else
printf("%d S-->&\n", cnt++);
}
void F() {
if (s[pos] == '(') {
pos++;
printf("%d F-->(E)\n", cnt++);
E();
if (s[pos] == ')')
pos++;
else {
puts("error");
exit(0);
}
} else if (s[pos] == 'i') {
pos++;
printf("%d F-->i\n", cnt++);
} else {
puts("error");
exit(0);
}
}
int main(int argc, char const *argv[]) {
cin >> s;
E();
if (s[pos] == '#')
puts("accept");
else
puts("error");
return 0;
}
表达式语法分析——预测分析法
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
string s;
int pos,cnt;
stack<char> sta;
bool check(char x) {
char y = s[pos];
if(x == y) {
pos++;
return 1;
}
if (x == 'E' && (y == 'i' || y == '(')) {
printf("%d E->TG\n",++cnt);
sta.push('G');
sta.push('T');
return 1;
} else if (x == 'G') {
if(y == '+') {
printf("%d G->+TG\n", ++cnt);
sta.push('G');
sta.push('T');
sta.push('+');
return 1;
}else if(y == ')' || y == '#') {
printf("%d G->^\n", ++cnt);
return 1;
}
}else if(x == 'T' && (y == 'i' || y == '(')) {
printf("%d T->FS\n", ++cnt);
sta.push('S');
sta.push('F');
return 1;
}else if(x == 'S') {
if(y == '+' || y == ')' || y == '#') {
printf("%d S->^\n", ++cnt);
return 1;
}
else if(y == '*') {
printf("%d S->*FS\n", ++cnt);
sta.push('S');
sta.push('F');
sta.push('*');
return 1;
}
}else if(x == 'F') {
if(y == 'i') {
printf("%d F->i\n", ++cnt);
sta.push('i');
return 1;
}
else if(y == '(') {
printf("%d F->(E)\n", ++cnt);
sta.push(')');
sta.push('E');
sta.push('(');
return 1;
}
}
return 0;
}
int main(int argc, char const *argv[]) {
cin >> s;
sta.push('#');
sta.push('E');
while(sta.size()) {
char now = sta.top();
sta.pop();
if(!check(now)){
puts("error!");
break;
}
if(sta.top() == '#') break;
}
if(sta.top() == '#' && s[pos] == '#') puts("acc!");
return 0;
}
翻译布尔表达式
关于拉链-回填技术可以看这篇博客：传送门
但是对于这道题，我们不用真正实现拉链回填技术（虽然题目说练习拉链回填技术），因为拉链回填技术是在中间代码生成的过程中完成的，而中间代码生成又是在语法分析中完成的，这就意味着，如果是要实现拉链回填技术，需要先进行某种文法的分析（LR(1)或LALR(1)等），然后实现布尔表达式的翻译模式，这就太复杂了。不过我们还是参照了拉链回填技术的思想。
具体思想是这样的：
由于只有 and 和 or ，所以我们只需要分析这两种逻辑就行。
对于 and ，两边只要有一个为假则就都为假，全真才为真。多个 and 连接也是一样：只要有一个表达式为假则全假，全真整体才为真。所以，我们可以把一段连续的 and 看做一个整体，这个整体中每个 and 的假链都连向最后一句的下一句。但是由于需要拉链，所以这个整体的最后一句的假链连向最后第二句的假地址，最后第二句连向最后第三句的假……直到第一句的假链连向整体的最后一句的下一句。 那么对于每个表达式的真链，都指向下一个表达式的开始，因为需要逐个判断都为真才整体真，最后一个表达式的真链指向整体的真链。
对于 or 类似分析即可。
（文字分析比较麻烦，看一下代码就能懂）
#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
char s[111][111], temp[111][111];
int cnt;
int main(int argc, char const *argv[]) {
while(cin >> s[cnt++]); // 先按照空格读入每个单词
int True = 1, False = 100, id = 100;// 初始真链为1，假链为100，四元式编号为100
vector<char *> temp;//存放一段连续的and
for(int i = 0; i < cnt; i++) {
if(strcmp(s[i], "or") == 0 || i == cnt - 1) { //当前单词为or或者最后一个单词
if(strcmp(s[i], "or") == 0) False += 2; //如果为 or 则假链再+2
else False = 0; //否则假链为整个式子的假链出口 0
//先将前面的几个逻辑语句处理完，剩最优一个
for(int j = 0; j < temp.size() - 3; j += 3) {
printf("%d(j%s,%s,%s,%d)\n", id++, temp[j+1], temp[j], temp[j+2], id+2);
printf("%d(j,_,_,%d)\n", id, False);
False = id++;
}
//处理最后一句
int j = temp.size() - 3;
printf("%d(j%s,%s,%s,%d)\n", id, temp[j+1], temp[j], temp[j+2], True);
True = id++;
printf("%d(j,_,_,%d)\n", id++, False);
temp.clear();
}
else if(strcmp(s[i], "and") == 0) False += 2; //如果为and则将假链后移2
else temp.push_back(s[i]); //将当前单词压入temp
}
return 0;
}
DAG优化
#include <bits/stdc++.h>
using namespace std;
struct node
{
int l, r; // 左右儿子编号
char op; //存节点的标记
vector<char> fu; //存附加标记
}tr[111];
int cnt, flag[111];
char ans[111][1111];
bool has(int id, char c) { // 检查编号为id的节点中是否存在附加节点 k
for(int i = 0; i < tr[id].fu.size(); i++)
if(tr[id].fu[i] == c) return 1;
return 0;
}
int creat(char c) { //返回含有k的节点编号
for (int i = cnt; i >= 1; i--) //倒序查找是否存在含有k的节点
if(has(i, c) || tr[i].op == c) return i;
tr[++cnt].op = c; //不存在则新建节点，标记为k
return cnt;
}
void add(int l, int r, char op, char c) { //建边
for(int i = cnt; i >= 1; i--) { //寻找是否已经存在这样的点
if(tr[i].l == l && tr[i].r == r && tr[i].op == op) {
tr[i].fu.push_back(c);
return;
}
}
cnt++; //不存在则新建
tr[cnt] = {l,r,op};
tr[cnt].fu.push_back(c);
}
void dfs(int x) {
if(tr[x].l && tr[x].r) {
flag[x] = 1; //由于要按照顺序输出，所以先标记，最后一起输出
dfs(tr[x].l);
dfs(tr[x].r);
}
}
void solve(int so, int ta, int pos) {
//在编号为so的节点中查找，结果存在第ta个优化后表达式的pos位置
if(tr[so].fu.size() == 0) { //如果so中没附加标记，则op的值赋到pos
ans[ta][pos] = tr[so].op;
return;
}
//遍历附加标记，优先使用A和B赋值，题目保证不会同时存在A和B
for(int i = 0; i < tr[so].fu.size(); i++) {
if(tr[so].fu[i] == 'A' || tr[so].fu[i] == 'B') {
ans[ta][pos] = tr[so].fu[i];
return;
}
}
ans[ta][pos] = tr[so].fu[0];//不存在A和B则用第一个附加标记赋值
}
int main(int argc, char const *argv[]) {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
int l = creat(s[2]), r = creat(s[4]);//寻找表达式的左右节点
add(l,r,s[3],s[0]);//表达式建边
}
for(int i = 1; i <= cnt; i++) {//优化每个表达式
if(tr[i].l && tr[i].r) {//如果不是叶子节点，说明该节点表示一个表达式
ans[i][1] = '=', ans[i][3] = tr[i].op, ans[i][5] = '\0';
//分别进行表达式的优化
solve(i, i, 0);
solve(tr[i].l, i, 2);
solve(tr[i].r, i, 4);
}
}
//要求只保留A和B相关的表达式，从后往前找最后一个A和B出现的位置，递归输出整个子树
for(int i = cnt; i >= 1; i--) {
if(ans[i][0] == 'A') {dfs(i);break;}
}
for(int i = cnt; i >= 1; i--) {
if(ans[i][0] == 'B') {dfs(i); break;}
}
for(int i = 1; i <= cnt; i++) {
if(flag[i]) printf("%s\n",ans[i]);
}
return 0;
}
简单的代码生成程序
#include <bits/stdc++.h>
using namespace std;
string s[111];
char r[111];
int n, m, cnt; // n表示三地址代码数量，m代表寄存器最多个数，cnt表示已经使用的寄存器数量
int use(int i, char c) {
/*
查找从第i个三地址代码开始，最早出现变量c的三地址代码的编号
*/
for( ; i < n; i++) { // 从i开始遍历所有的代码
if(s[i][3] == c || s[i][5] == c) return i;
}
return n;
}
int find(int pos) {
/*
返回一个可用的寄存器下标，有两种情况：
1. 有空寄存器，则直接返回空寄存器下标
2. 没有空寄存器，遍历所有寄存器，寻找寄存器中所存储的变量最晚被用到的那个寄存器，将其中的变量存到内存中。
*/
if(cnt < m) return cnt++; //空寄存器
int Max = -1, id;
for(int i = 0; i < cnt; i++) {
int temp = use(pos, r[i]); //use查找从pos开始最早出现r[i]的三地址代码
if(temp > Max) {
Max = temp;//维护最晚出现的，即三地址代码下标最大的寄存器
id = i;
}
}
return id;
}
int main(int argc, char const *argv[]) {
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> s[i];
for(int i = 0; i < n; i++) {
int id = find(r, r + cnt, s[i][3]) - r; //寻找当前寄存器中是否存在左操作数
if(id == cnt) {//不存在，需要LD左操作数
id = find(i); //寻找用于LD左操作数的寄存器
if(r[id] != '\0' && use(i, r[id]) < n) {
// 如果用于LD的寄存器非空，且该寄存器中存的变量之后还要被用到，则需要ST一下寄存器中的变量
printf("ST R%d, %c\n", id, r[id]);
r[id] = '\0'; // ST完后这个寄存器就空了，一定要清空！！
}
printf("LD R%d, %c\n", id, s[i][3]); // LD左操作数
}
char op = s[i][4]; // 输出op
if(op == '+') printf("ADD ");
else if(op == '-') printf("SUB ");
else if(op == '*') printf("MUL ");
else printf("DIV ");
printf("R%d, ", id); //输出左操作数所在寄存器
int id2 = find(r, r + cnt, s[i][5]) - r;//寻找当前寄存器中是否有右操作数
if(id2 == cnt) printf("%c\n", s[i][5]); //不存在则直接输出右操作数，表示读取内存
else printf("R%d\n", id2); // 否则直接从寄存器中取右操作数，输出所在的寄存器
r[id] = s[i][0]; //最后将结果存在左操作数所在的寄存器中
}
return 0;
}
