基于SLR(1)分析的语义分析及中间代码生成程序
发布时间：2023年12月20日
制作一个简单的C语言词法分析程序_c语言编写词法分析程序-CSDN博客
https://blog.csdn.net/lijj0304/article/details/134078944?spm=1001.2014.3001.5501前置程序词法分析器参考这个帖子??
1.程序目标?
?算符优先语法分析程序，程序可以识别实验1的输出文件中的二元序列，然后通过已经构造好的SLR1分析表，进行语法分析，程序能够实时输出分析栈的状态，遇到错误位置会停止，对于正确的语句可以输出对应的四元式序列。算式的语法如下：
G[S]:S→V=E
E→E+T∣E-T∣T
T→T*F∣T/F∣F
??? F→(E)∣i
??? V→i
2.程序设计
SLR1语法分析部分是通过提前根据语法构造分析表，分析表以数组的形式存储，数组中存储了每个状态遇到的终结符和非终结符对应的动作和转移到的状态。大于0表示移进操作，小于0表示先规约后移进操作，0表示为不存在的状态，遇到则需要报错。
根据文法构造SLR1分析表：
S‘→S
S→V=E
E→E+T
E→E-T
E→T
T→T*F
T→T/F
T→F
F→(E)
F→i
V→i
| GOTO | ACTION | |||||||||||||
| i | = | + | - | * | / | ( | ) | # | S | E | T | F | V | |
| 0 | S3 | 1 | 2 | |||||||||||
| 1 | ACC | |||||||||||||
| 2 | S4 | |||||||||||||
| 3 | R10 | R10 | R10 | R10 | R10 | R10 | R10 | R10 | R10 | |||||
| 4 | S9 | S8 | 5 | 6 | 7 | |||||||||
| 5 | R1 | R1 | S10 | S11 | R1 | R1 | R1 | R1 | R1 | |||||
| 6 | R4 | R4 | S12 | S13 | R4 | R4 | R4 | R4 | R4 | |||||
| 7 | R7 | R7 | R7 | R7 | R7 | R7 | R7 | R7 | R7 | |||||
| 8 | S9 | S8 | 14 | 6 | 7 | |||||||||
| 9 | R9 | R9 | R9 | R9 | R9 | R9 | R9 | R9 | R9 | |||||
| 10 | S9 | S8 | 15 | 7 | ||||||||||
| 11 | S9 | S8 | 16 | 7 | ||||||||||
| 12 | S9 | S8 | 17 | |||||||||||
| 13 | S9 | S8 | 18 | |||||||||||
| 14 | S10 | S11 | S19 | |||||||||||
| 15 | R2 | R2 | R2 | R2 | S12 | S13 | R2 | R2 | R2 | |||||
| 16 | R3 | R3 | R3 | R3 | S12 | S13 | R3 | R3 | R3 | |||||
| 17 | R5 | R5 | R5 | R5 | R5 | R5 | R5 | R5 | R5 | |||||
| 18 | R6 | R6 | R6 | R6 | R6 | R6 | R6 | R6 | R6 | |||||
| 19 | R8 | R8 | R8 | R8 | R8 | R8 | R8 | R8 | R8 | |||||
程序额外构造了一种栈的数据结构来辅助运算。栈中有一个整形数组和一个符号数组，用来保存分析栈的信息，实现实时输出分析状态?
?四元式构造思路：
- 扫描默认start=0，end=串长
- 从左向右扫描一对最短距离括号，把start和end置为括号范围
- 若括号内没有算符，消除括号后重复1
- 在start和end范围内优先扫描乘号和除号，遇到则进行乘法或除法计算，没有则取第一个加减法符号计算，若只剩下等于号，取做变量，产生四元式，结束算法
- 取左右两个变量，计算中间变量序号，产生四元式
3.完整程序?
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_LEN 1000
struct stack {
char s[MAX_LEN];
int i[MAX_LEN];
int top;
};
// GOTO | ACTION
//i, =, +, -, *, /, (, ), #, S, E, T, F, V
int table[20][14] ={{ 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2},// 0
{ 0, 0, 0, 0, 0, 0, 0, 0,-11,0,0, 0, 0, 0},// 1
{ 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},// 2
{-10,-10,-10,-10,-10,-10,-10,-10,-10, 0, 0, 0, 0, 0},//3
{ 9, 0, 0, 0, 0, 0, 8, 0, 0, 0, 5, 6, 7, 0},// 4
{-1,-1,10,11,-1,-1,-1,-1,-1, 0, 0, 0, 0, 0},// 5
{-4,-4,-4,-4,12,13,-4,-4,-4, 0, 0, 0, 0, 0},// 6
{-7,-7,-7,-7,-7,-7,-7,-7,-7, 0, 0, 0, 0, 0},// 7
{ 9, 0, 0, 0, 0, 0, 8, 0, 0, 0,14, 6, 7, 0},// 8
{-9,-9,-9,-9,-9,-9,-9,-9,-9, 0, 0, 0, 0, 0},// 9
{ 9, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0,15, 7, 0},//10
{ 9, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0,16, 7, 0},//11
{ 9, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0,17, 0},//12
{ 9, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0,18, 0},//13
{ 0, 0,10,11, 0, 0, 0,19, 0, 0, 0, 0, 0, 0},//14
{-2,-2,-2,-2,12,13,-2,-2,-2, 0, 0, 0, 0, 0},//15
{-3,-3,-3,-3,12,13,-3,-3,-3, 0, 0, 0, 0, 0},//16
{-5,-5,-5,-5,-5,-5,-5,-5,-5, 0, 0, 0, 0, 0},//17
{-6,-6,-6,-6,-6,-6,-6,-6,-6, 0, 0, 0, 0, 0},//18
{-8,-8,-8,-8,-8,-8,-8,-8,-8, 0, 0, 0, 0, 0}};//19
int getindex(char ch) {
switch(ch) {
case 'i': return 0;
case '=': return 1;
case '+': return 2;
case '-': return 3;
case '*': return 4;
case '/': return 5;
case '(': return 6;
case ')': return 7;
case '#': return 8;
case 'S': return 9;
case 'E': return 10;
case 'T': return 11;
case 'F': return 12;
case 'V': return 13;
default: return -1;
}
}
void print(char *str, struct stack *stk, int now) { // 打印分析状态
for(int i = 0; i <= stk->top; i++) {
printf("%c:%2d ", stk->s[i], stk->i[i]);
}
for(int i = 0; i <= 60 - stk->top*7; i++) {
printf(" ");
}
for(int i = now; i < strlen(str); i++) {
printf("%c", str[i]);
}
// printf("\n");
// for(int i = 0; i <= stk->top; i++) {
// printf("%3d", stk->i[i]);
// }
printf("\n");
}
void getfour(char *str) {
int tmp = 1;
while(1) {
int flag = 0, close = 0, ptr = 0, start = 0, end = strlen(str);
for(int i = 0; i < strlen(str); i++) { // 括号优先级高，先找括号
if(str[i] == '(') start = i + 1;
else if(str[i] == ')') {
end = i;
break;
}
}
for(int i = start; i < end; i++) {
if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
close = 1;
break;
}
}
if(close == 0) { // 如果括号内没有运算符，消除括号，再重新找括号
int t = start - 1;
for(int i = start; i < end; i++) {
str[t++] = str[i];
}
for(int i = end + 1; i < strlen(str); i++) {
str[t++] = str[i];
}
str[t] = '\0';
start = 0, end = strlen(str);
for(int i = 0; i < strlen(str); i++) {
if(str[i] == '(') start = i + 1;
else if(str[i] == ')') {
end = i;
break;
}
}
}
for(int i = start; i < end; i++) {
if(str[i] == '*' || str[i] == '/') { // 优先乘除
flag = 1;
ptr = i;
break;
}
else if(str[i] == '+' || str[i] == '-') { // 然后加减
if(flag == 0) {
flag = 1;
ptr = i;
}
}
else if(str[i] == '=') {
ptr = i;
}
}
char left[MAX_LEN] = "";
printf("(%c, ", str[ptr]);
int j = ptr - 1, p = 0, k = ptr + 1;
if(flag == 0) { // 当前为赋值运算
while(k < end && str[k] != '+' && str[k] != '-' && str[k] != '*' && str[k] != '/' && str[k] != '=') {
printf("%c", str[k++]);
}
printf(", , ");
while(j >= start && str[j] != '+' && str[j] != '-' && str[j] != '*' && str[j] != '/' && str[j] != '=') {
left[p++] = str[j];
j--;
}
for(int q = p - 1; q >= 0; q--) {
printf("%c", left[q]);
}
printf(")\n");
break;
}
while(j >= start && str[j] != '+' && str[j] != '-' && str[j] != '*' && str[j] != '/' && str[j] != '=') {
left[p++] = str[j];
j--;
}
for(int q = p - 1; q >= 0; q--) {
printf("%c", left[q]); // 输出第一个操作数
}
printf(", ");
while(k < end && str[k] != '+' && str[k] != '-' && str[k] != '*' && str[k] != '/' && str[k] != '=') {
printf("%c", str[k++]); // 输出第二个操作数
}
printf(", ");
char num[3] = "";
sprintf(num, "T%d", tmp);
printf("%s) ", num); // 输出目的操作数
tmp++;
for(int q = 0; q < strlen(num); q++) {
str[++j] = num[q];
}
for(int q = k; q < strlen(str); q++) {
str[++j] = str[q];
}
str[j+1] = '\0'; // 更新串
}
}
int SLR(char *str, struct stack *stk) { // SLR1分析函数
int i = 0;
int next;
printf("stack: str:\n");
while(i < strlen(str)) {
if(stk->top < 0) return 0; // 分析栈不可能为空
int y = getindex(str[i]);
if(y == -1 || table[stk->i[stk->top]][y] == 0) { // 表中不存在的状态，分析报错
return 0;
}
if(table[stk->i[stk->top]][y] > 0) { // 移进操作
next = table[stk->i[stk->top]][y];
stk->top++;
stk->s[stk->top] = str[i];
stk->i[stk->top] = next;
i++;
print(str, stk, i);
}
else if(table[stk->i[stk->top]][y] < 0) { // 归约操作
int tmp = -table[stk->i[stk->top]][y];
if(tmp == 4 || tmp == 7 || tmp == 9 || tmp == 10) {
stk->top--;
}
else {
stk->top -= 3;
}
if(tmp == 1) {
y = getindex('S');
next = table[stk->i[stk->top]][y];
stk->top++;
stk->s[stk->top] = 'S';
stk->i[stk->top] = next; // 归约修改栈顶
}
else if(tmp == 2 || tmp ==3 || tmp == 4) {
y = getindex('E');
next = table[stk->i[stk->top]][y];
stk->top++;
stk->s[stk->top] = 'E';
stk->i[stk->top] = next;
}
else if(tmp == 5 || tmp == 6 || tmp == 7) {
y = getindex('T');
next = table[stk->i[stk->top]][y];
stk->top++;
stk->s[stk->top] = 'T';
stk->i[stk->top] = next;
}
else if(tmp == 8 || tmp == 9) {
y = getindex('F');
next = table[stk->i[stk->top]][y];
stk->top++;
stk->s[stk->top] = 'F';
stk->i[stk->top] = next;
}
else if(tmp == 10) {
y = getindex('V');
next = table[stk->i[stk->top]][y];
stk->top++;
stk->s[stk->top] = 'V';
stk->i[stk->top] = next;
}
else if(tmp == 11) {
return 1;
}
print(str, stk, i);
}
}
return 0;
}
int main() {
for(int m = 1; m <= 2; m++) {
printf("\ntest%d: ", m);
char txt[] = "./lexical/analyze";
char num[8];
sprintf(num, "%d.txt", m);
strcat(txt, num);
FILE *fp = fopen(txt, "r");
char buf[MAX_LEN] = "";
char input[MAX_LEN] = "";
char str[MAX_LEN] = "";
fgets(buf, MAX_LEN, fp);
int i = 0, j = 0;
for(int k = 0; k < strlen(buf); k++) {
if(buf[k] == '1' && buf[k+1] == ',') {
str[i++] = 'i';
k += 3;
while(1) {
if(buf[k] == ')' && buf[k+1] == ' ')
break;
input[j++] = buf[k++];
}
continue;
}
if(buf[k] == ',' && buf[k+1] == ' ') {
k += 2;
while(1) {
if(buf[k] == ')' && buf[k+1] == ' ')
break;
str[i++] = buf[k];
input[j++] = buf[k++];
}
}
}
printf("Input scentence: %s\n", input);
str[i] = '#';
fclose(fp);
struct stack *stk;
stk = (struct stack *)malloc(sizeof(struct stack));
stk->s[0] = '#';
stk->i[0] = 0;
stk->top = 0;
if(SLR(str, stk)) {
printf("Gramma legal: %s\n", str);
printf("Quaternion: ");
getfour(input);
}
else {
printf("Gramma illegal\n");
}
}
return 0;
}4.程序测试
tets1：a=(b+c*d)/f+e*g
test2：a=b+(c+d)*/e
analyze1：
(1, a) (36, =) (16, () (1, b) (44, +) (1, c) (50, *) (1, d) (17, )) (38, /) (1, f) (44, +) (1, e) (50, *) (1, g)
analyze2：
(1, a) (36, =) (1, b) (44, +) (16, () (1, c) (44, +) (1, d) (17, )) (50, *) (38, /) (1, e)
运行结果
文章来源:https://blog.csdn.net/lijj0304/article/details/135097554
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！