状态机练习
编译原理 状态机识别标识符-CSDN博客
大体思路是先区分数字，标识符，然后标识符再区分保留字这样。
随后根据PL0 字符改状态机
改了3次才出来
状态矩阵，一行一行写
input.txt
const a=10; var b,c;beginread(b);c:=a+b;write(c)end.
#include <stdio.h>
#include <string.h>
//#include <ctype.h>#define END 6 // 状态机回退检测
#define CHECK 7
#define ERROR 8
// 状态机设计
// 0 行不用
// 0 列不用
//列查找按代号查询
// 代号是经过合并如123456789是数字合并为1 就是第一列
//延续状态机，改终止状态，当没有字符输入时，当前状态就是要进行判断的状态//提示，可使用如下二维数组存储DFA。
//一个状态对应一行；一个输入符号（digit/other）对应一列。
//每看到输入字符串中一个符号，就以当且状态为行号，
//看到的符号为列号查询下个状态作为当前状态。// 以下状态机画了一周画了三次图，写了三种状态数组
int integerDFA[][7] = {// 符号，下个状态// space letter digit calculate border other{0, 0, 0, 0, 0, 0, 0},{0, 1, 2, 3, 4, 5, ERROR}, // 状态1 就绪{0, END, 2, 2, CHECK, END, ERROR}, // 状态2 标识符{0, END, 3, 3, END, END, ERROR}, // 状态3 数字，0b带，0x之流，后续检测字符，因只一个字母接数字后。{0, END, END, END, 4, END, ERROR}, // 状态4 运算符，由于有+,<= 这种一个两个，所以后续还得检测<<<这样是否合法的代码{0, ERROR, ERROR, ERROR, ERROR, ERROR, ERROR}, // 状态5 边界,;.直接结束{0, 0, 0, 0, 0, 0, 0}, // 状态6 最先于字母结束还要再次判断最后是什么字符导致的变动，用于合规检测当前字符{0, 0, 0, 0, 0, 0, 0}, // 状态7 同状态6，但是发现void+ 这样会有BUG，用于标识符识别为保留字再次检测符号合法否。{0, 0, 0, 0, 0, 0, 0}, // 状态8 想新BUG，发现有￥这样字符，直接报错};// 12 个保留字char ident[100][100] = {"begin","call","const","do","end","if","procedure","read","then","var","while","write",
};// 11个运算符
char calculate[100][100] = {"+","-","*","/","=","<>","<","<=",">",">=",":=",
};
// 对应运算符序号，用于查表
char calcu[100][100] = {"plus", "minus", "times", "slash", "eql", "neq", "lss", "leq", "gtr", "gep", "becomes",
};
// 五个界符
char board[100][100] = {"(",")",",",";",".",
};
// 界符对应名字
char boardname[100][100] = {"lparen","rparen","comma","semicolon","period",
};int have = 12;
//intint statu; // 当前状态
int old_sta; // 上一个状态
FILE* fp;
FILE* fa2;int lenth = 10000;
char* str = new char[1200]; // 循环读取文件，分200字节读取
char** cmd = new char*[lenth]; // 词元存储
int* sign = new int[lenth]; // 对应词元的标识
int cnt = 0; // 分割词元个数
int num = 0; // 当前字符填充位置// 是空白符
int isspace(char* p) {if (*p == ' ' || *p == '\n' || *p == '\0') {return 1;}return 0;
}
//是字母
int isletter(char* p) {if ((*p >= 'a' && *p <= 'z') || (*p >= 'A' && *p <= 'Z')) {return 1;}return 0;
// return isalpha(*p);}
// 是数字
int isnum(char* p) {if (*p >= '0' && *p <= '9') {return 1;}return 0;
}// 是calculate 是运算符
int iscalculate(char* p) {if (*p == ':' || *p == '+' || *p == '-' || *p == '*' || *p == '/' || *p == '<' || *p == '=' || *p == '>') {return 1;}return 0;
}
// 是界符号
int isborder(char* p) {if (*p == ';' || *p == ',' || *p == '.' || *p == '(' || *p == ')') {return 1;}return 0;
}// 查空白符号，字符，数字，运算符号，界符号，乱码字符
int transchar(char* p) {int a = 0;int b = 0;int c = 0;int d = 0;int e = 0;a = isspace(p);b = isletter(p);c = isnum(p);d = iscalculate(p);e = isborder(p);if (a != 0) {
// printf("isspace\n");return 1;} else if (b != 0) {return 2; // 不是return b,c,d,e,因为都是1} else if (c != 0) {return 3;} else if (d != 0) {return 4;} else if (e != 0) {return 5;} else {return 6;}}//int check(char* str) {
void check(char* str) {int checknum;checknum = 10;char*p = str;// 进入字符探测，允许跳转状态
// statu = 1; // 初始化设置，全局变量
// old_sta = statu;// 字符 '\0'也是比较对象，对应于状态机的非字符直接到结束状态。只有一个非字符就是结束符才能输出正确do {// 选状态checknum = transchar(p);// printf("%c\n", *p);
// printf("%d\n", checknum);old_sta = statu;statu = integerDFA[statu][checknum];
// printf("%d\n", statu);
// printf("%d\n",cnt);// 字符写入cmd[cnt][num] = *p;num++; // 用于最后循环结束判断是否分词if (statu == 5) { // 边界
// num--;
// num++;cmd[cnt][num] = '\0'; // 填充
// printf("--%s--\n",cmd[cnt]);sign[cnt] = 5; // 字符存储记录为边界符号cnt++; // 下一个字符num = 0;statu = 1;old_sta = 1;} else if (statu == 6) { // 要复位num--;cmd[cnt][num] = '\0';
// printf("--%s--\n", cmd[cnt]);num = 0;if (old_sta == 2) { // 字母sign[cnt] = 2;} else if (old_sta == 3) { // 数字sign[cnt] = 3;} else if (old_sta == 4) { // 运算符号sign[cnt] = 4;}cnt++;statu = 1;old_sta = 1;statu = integerDFA[statu][checknum];cmd[cnt][num] = *p;num++;if (statu == 5) { // 边界num++;cmd[cnt][num] = '\0'; // 填充
// printf("--%s--\n",cmd[cnt]);sign[cnt] = 5; // 字符存储记录为边界符号cnt++; // 下一个字符num = 0;statu = 1;old_sta = 1;}} else if (statu == 7) {num--;cmd[cnt][num] = '\0';
// printf("--%s--\n", cmd[cnt]);num = 0;if (old_sta == 2) { // 字母sign[cnt] = 2;} else if (old_sta == 3) { // 数字sign[cnt] = 3;} else if (old_sta == 4) { // 运算符号sign[cnt] = 4;}cnt++;
// statu = 0;statu = 1;old_sta = statu;statu = integerDFA[statu][checknum];cmd[cnt][num] = *p;num++;// 因为7是calculate 在标识符而来，所以*p一定是标识符，就一定不是边界// printf("检测保留字与运算符\n");// 发现利用状态机分词后可以根据保留字判断后续词语。} else if (statu == 8) {printf("ERROR 有非法字符\n");}p++;} while (*p != '\0');// 选状态checknum = transchar(p);printf("%c\n", *p);
// printf("%d\n", checknum);old_sta = statu;statu = integerDFA[statu][checknum];
// printf("%d\n", statu);// 字符写入cmd[cnt][num] = *p;num++; // 用于最后循环结束判断是否分词if (statu == 5) { // 边界cmd[cnt][num] = '\0'; // 填充printf("--%s--\n", cmd[cnt]);sign[cnt] = 5; // 字符存储记录为边界符号cnt++; // 下一个字符num = 0;statu = 1;old_sta = 1;} else if (statu == 6) { // 要复位num--;cmd[cnt][num] = '\0';printf("%d\n", old_sta);printf("--%s--\n", cmd[cnt]);num = 0;if (old_sta == 2) { // 字母sign[cnt] = 2;} else if (old_sta == 3) { // 数字sign[cnt] = 3;} else if (old_sta == 4) { // 运算符号sign[cnt] = 4;} else if (old_sta == 1) {sign[cnt] = 99;} else if (old_sta == 5) {sign[cnt] = 100;}cnt++;statu = 1;old_sta = 1;} else if (statu == 7) {num--;cmd[cnt][num] = '\0';printf("--%s--\n", cmd[cnt]);num = 0;if (old_sta == 2) { // 字母sign[cnt] = 2;} else if (old_sta == 3) { // 数字sign[cnt] = 3;} else if (old_sta == 4) { // 运算符号sign[cnt] = 4;}cnt++;statu = 1;old_sta = 1;} else if (statu == 8) {printf("ERROR 有非法字符\n");num = 0;} else if (statu == 1) {printf("回复原样\n");num = 0;}// num=0;}void init_cmd() {for (int i = 0; i < lenth; i++) {cmd[i] = new char[200];}// 分词存储先清空杂乱数据for (int i = 0; i < lenth; i++) {for (int j = 0; j < 200; j++) {cmd[i][j] = '\0';}}cnt = 0;num = 0;
}void init_statu() {statu = 1;old_sta = 1;
}int find_reserve(char* str) {for (int i = 0; i < have; i++) {if (strcmp(str, ident[i]) == 0) {return 1;}}return -1;
}int find_calculate(char* str) {for (int i = 0; i < 11; i++) {if (strcmp(str, calculate[i]) == 0) {return i;}}return -1;
}int find_borad(char* str) {for (int i = 0; i < 5; i++) {if (strcmp(str, board[i]) == 0) {return i;}}return -1;
}int main() {fp = fopen("input.txt", "r");fa2 = fopen("output.txt", "w");init_cmd();init_statu();// 分割词语
// while (fgets(str, 200, fp) != NULL) {// 利用scanf 读取吸收回车，而希冀里不能执行 '\n'的比较while (fscanf(fp, "%s", str) != EOF) {// 处理回车，有些回车读取会影响代码结果if (str[0] == '\n' && strlen(str) == 1) {continue;} else if (str[strlen(str) - 1 ] == '\n') { // 发现文末回车str[strlen(str) - 1 ] = '\0';}// 剥离成函数使用check(str);}// 对每个单词进行检查// 这样解决不知道什么时候根据状态进行结束的问题。字符连续，没有字符了就根据状态给结论。for (int i = 0; i < cnt; i++) {// printf("%d\n", i);
// printf("--%s--\n", cmd[i]);
// printf("%d\n", sign[i]);if (sign[i] == 2) { // 如果是字母打头的if (find_reserve(cmd[i]) != -1) {printf("( %ssym, %s )\n", cmd[i], cmd[i]);} else {printf("( IDENT, %s )\n", cmd[i]);}} else if (sign[i] == 3) { // 如果是数字打头的printf("( NUMBER, %s )\n", cmd[i]);} else if (sign[i] == 4) {int a = 0;a = find_calculate(cmd[i]);if (a != -1) {
// printf("%d", a);printf("( %s, %s )\n", calcu[a], cmd[i]);} else {printf("非法的运算符 --%s--\n", cmd[i]);}} else if (sign[i] == 5) {int a = 0;a = find_borad(cmd[i]);if (a != -1) {printf("( %s, %s )\n", boardname[a], cmd[i]);} else {printf("非法的边界符号 --%s--\n", cmd[i]);}}if (sign[i] == 2) { // 如果是字母打头的if (find_reserve(cmd[i]) != -1) {fprintf(fa2,"( %ssym, %s )\n", cmd[i], cmd[i]);} else {fprintf(fa2,"( IDENT, %s )\n", cmd[i]);sign[i]=22; // 标记为自定义的标识符号}} else if (sign[i] == 3) { // 如果是数字打头的fprintf(fa2,"( NUMBER, %s )\n", cmd[i]);} else if (sign[i] == 4) {int a = 0;a = find_calculate(cmd[i]);if (a != -1) {
// printf("%d", a);fprintf(fa2,"( %s, %s )\n", calcu[a], cmd[i]);} else {fprintf(fa2,"非法的运算符 --%s--\n", cmd[i]);}} else if (sign[i] == 5) {int a = 0;a = find_borad(cmd[i]);if (a != -1) {fprintf(fa2,"( %s, %s )\n", boardname[a], cmd[i]);} else {fprintf(fa2,"非法的边界符号 --%s--\n", cmd[i]);}}// fprintf(fa2, "(%d,%s)\n", cmd[i], sign[i]);}fclose(fa2);fclose(fp);return 0;
}
效果
