基于算符优先分析算法的语法制导翻译——程序设计与编译原理

一、在算符优先语法分析的基础上进行翻译工作（即语义分析），每当将一个最左素短语归约为一个非终结符号时，就调用对应产生式的语义子程序，去完成相应的语义翻译工作，这步归约使用的产生式对非终结符号不加区分（即将所有的非终结符号用一个通用的非终结符号表示）。

判断是句子的情况下，输出：四元式序列（*，val，count，T1）

算符优先分析前期准备：https://blog.csdn.net/lfy905805357/article/details/89333111

二、code

#include <iostream> #include "stdio.h" #include "stdlib.h" #include <string> #include <map> #include <sstream> using namespace std; char Data[20][20]; //算符优先关系 char s[100]; //模拟符号栈s string str[100]; //用来类似模拟符号栈s，不过该栈为字符串（用于同时给非终结符加上下标，例如P1） char lable[20]; //文法终极符集 char input[100]; //文法输入符号串 char In_str[20][10]; //用于输入串的分析 char text[20][10]; int k; char a; int j; char q; int r; //文法规则个数 int r1; //转化后文法规则个数 char st[10][30]; //用来存储文法规则 char first[10][10]; //文法非终结符FIRSTVT集 char last[10][10]; //文法非终结符LASTVT集 int fflag[10] = { 0 }; //标志第i个非终结符的FIRSTVT集是否已求出 int lflag[10] = { 0 }; //标志第i个非终结符的LASTVT集是否已求出 map<char,int> charmap; //用来判断该字符的下标是几 map<string,string> stringmap; //用来下标，值健对查找 stringstream ss; //利用该stringstream来进行其他类型转换为字符串 string qua[100][4]; //存储四元组 int quaCounts=0; //四元组个数 int deal(); //对输入串的分析 int deal1(); //对输入串的分析（包括求四元组） int Terminator(char c); //判断字符c是否是终极符 int getIndex(char c); //求字符c在算符优先关系表中的下标 void out(int j, int k, char *s); //打印s栈 void out1(int j, int k, string *str); //打印str栈 void firstvt(char c); //求非终结符c的FIRSTVT集 void lastvt(char c); //求非终结符c的LASTVT集 void table(); //创建文法优先关系表 bool check(char *in); //判断输入是不是都是终结符构成的句子 int main() { int i, j, k = 0; printf("请输入文法规则数："); cin >> r; printf("请输入文法规则：\n"); for (i = 0; i<r; i++) { cin >> st[i]; //存储文法规则，初始化FIRSTVT集和LASTVT集*/ first[i][0] = 0; /*first[i][0]和last[i][0]分别表示st[i][0]非终极 符的FIRSTVT集和LASTVT集中元素的个数*/ last[i][0] = 0; } for (i = 0; i<r; i++) //判断文法是否合法 { for (j = 0; st[i][j] != '\0'; j++) { if (st[i][0]<'A' || st[i][0]>'Z') { printf("不是算符文法!\n"); exit(-1); } if (st[i][j] >= 'A'&&st[i][j] <= 'Z') { if (st[i][j + 1] >= 'A'&&st[i][j + 1] <= 'Z')//两非终结符不能相邻 { printf("不是算符文法!\n"); exit(-1); } } } } for (i = 0; i<r; i++) { for (j = 0; st[i][j] != '\0'; j++) { if ((st[i][j]<'A' || st[i][j]>'Z') && st[i][j] != '-'&&st[i][j] != '>'&&st[i][j] != '|') lable[k++] = st[i][j]; } } lable[k] = '#';//把井号终结符加入到终结符集合里面 lable[k + 1] = '\0'; table(); printf("每个非终结符的FIRSTVT集为：\n"); //输出每个非终结符的FIRSTVT集 for (i = 0; i<r; i++) { printf("%c: ", st[i][0]); for (j = 0; j<first[i][0]; j++) { printf("%c ", first[i][j + 1]); } printf("\n"); } printf("每个非终结符的LASTVT集为：\n"); //输出每个非终结符的LASTVT集 for (i = 0; i<r; i++) { printf("%c: ", st[i][0]); for (j = 0; j<last[i][0]; j++) { printf("%c ", last[i][j + 1]); } printf("\n"); } printf("算符优先分析表如下:\n"); for (i = 0; lable[i] != '\0'; i++) printf("\t%c", lable[i]); printf("\n"); for (i = 0; i<k + 1; i++) { printf("%c\t", lable[i]); for (j = 0; j<k + 1; j++) { printf("%c\t", Data[i][j]); } printf("\n"); } printf("请输入文法输入符号串以#结束:"); while (cin >> input && input != "exit") { int flag=deal1();//标记是否符合文法定义 if(flag==1&&check(input)){//检测输入串是否是终结符组成的句子 cout<<"该符号串是句子！"<<endl; cout<<"\n四元式如下："<<endl; for(int i=0;i<quaCounts;i++){ cout<<"产生【"<<(i+1)<<"】："; cout<<"("+qua[i][0]+","+qua[i][1]+","+qua[i][2]+","+qua[i][3]+")"<<endl; } } quaCounts=0;//重新归零 printf("请输入文法输入符号串以#结束:"); } system("pause"); } //判断输入是不是都是终结符，判断是不是句子 bool check(char *in){ for(int i=0;in[i]!='\0';i++){ if(!Terminator(in[i]))//逐个判断是不是终结符 return false; } return true; } void table() { //char text[20][10]; int i, j, k, t, l, x = 0, y = 0; int m, n; x = 0; //求firstvt集和lastvt集 for (i = 0; i<r; i++) { firstvt(st[i][0]); lastvt(st[i][0]); } //转化文法，化为单候选式文法 for (i = 0; i<r; i++) { text[x][y] = st[i][0]; y++; for (j = 1; st[i][j] != '\0'; j++) { if (st[i][j] == '|') { text[x][y] = '\0'; x++; y = 0; text[x][y] = st[i][0]; y++; text[x][y++] = '-'; text[x][y++] = '>'; } else { text[x][y] = st[i][j]; y++; } } text[x][y] = '\0'; x++; y = 0; } r1 = x;//更改转换后文法的数目 printf("转化后的文法为:\n"); for (i = 0; i<x; i++) //输出转化后的文法规则串 { printf("%s\n", text[i]); } /*求每个终结符的推导结果(去掉"->" 后的转化文法，用于最后的规约)*/ for (i = 0; i<x; i++) { In_str[i][0] = text[i][0]; for (j = 3, l = 1; text[i][j] != '\0'; j++, l++) In_str[i][l] = text[i][j]; In_str[i][l] = '\0'; } //利用书上算法构造算符优先分析表 //firstvt[0][0]第一位为firstvt集元素数目 //lastvt集也一样 for (i = 0; i<x; i++) { for (j = 1; text[i][j + 1] != '\0'; j++) { if (Terminator(text[i][j]) && Terminator(text[i][j + 1])) { m = getIndex(text[i][j]); n = getIndex(text[i][j + 1]); Data[m][n] = '='; } if (text[i][j + 2] != '\0'&&Terminator(text[i][j]) && Terminator(text[i][j + 2]) && !Terminator(text[i][j + 1])) { m = getIndex(text[i][j]); n = getIndex(text[i][j + 2]); Data[m][n] = '='; } if (Terminator(text[i][j]) && !Terminator(text[i][j + 1])) { for (k = 0; k<r; k++) { if (st[k][0] == text[i][j + 1]) break; } m = getIndex(text[i][j]); for (t = 0; t<first[k][0]; t++) { n = getIndex(first[k][t + 1]); Data[m][n] = '<'; } } if (!Terminator(text[i][j]) && Terminator(text[i][j + 1])) { for (k = 0; k<r; k++) { if (st[k][0] == text[i][j]) break; } n = getIndex(text[i][j + 1]); for (t = 0; t<last[k][0]; t++) { m = getIndex(last[k][t + 1]); Data[m][n] = '>'; } } } } //将#E#开始文法也加上去求出其对应的firstvt和lastvt集。 m = getIndex('#'); for (t = 0; t<first[0][0]; t++) { n = getIndex(first[0][t + 1]); Data[m][n] = '<'; } n = getIndex('#'); for (t = 0; t<last[0][0]; t++) { m = getIndex(last[0][t + 1]); Data[m][n] = '>'; } Data[n][n] = '='; } void firstvt(char c) //求FIRSTVT集 { int i, j, k, m, n; for (i = 0; i<r; i++) { if (st[i][0] == c) break; } if (fflag[i] == 0) { n = first[i][0] + 1; m = 0; do { if (m == 2 || st[i][m] == '|') { if (Terminator(st[i][m + 1])) { first[i][n] = st[i][m + 1]; n++; } else { if (Terminator(st[i][m + 2])) { first[i][n] = st[i][m + 2]; n++; } if (st[i][m + 1] != c) { firstvt(st[i][m + 1]); for (j = 0; j<r; j++) { if (st[j][0] == st[i][m + 1]) break; } for (k = 0; k<first[j][0]; k++) { int t; for (t = 0; t<n; t++) { if (first[i][t] == first[j][k + 1]) break; } if (t == n) { first[i][n] = first[j][k + 1]; n++; } } } } } m++; } while (st[i][m] != '\0'); first[i][n] = '\0'; first[i][0] = --n;//第一位值存firstvt集中元素的个数（字符形式） fflag[i] = 1;//表明该非终极符的firstvt集求出来了 } } void lastvt(char c) //求LASTVT集 { int i, j, k, m, n; for (i = 0; i<r; i++) { if (st[i][0] == c) break; } if (lflag[i] == 0) { n = last[i][0] + 1; m = 0; do { if (st[i][m + 1] == '\0' || st[i][m + 1] == '|') { if (Terminator(st[i][m])) { last[i][n] = st[i][m]; n++; } else { if (Terminator(st[i][m - 1])) { last[i][n] = st[i][m - 1]; n++; } if (st[i][m] != c) { lastvt(st[i][m]); for (j = 0; j<r; j++) { if (st[j][0] == st[i][m]) break; } for (k = 0; k<last[j][0]; k++) { int t; for (t = 0; t<n; t++) { if (last[i][t] == last[j][k + 1]) break; } if (t == n) { last[i][n] = last[j][k + 1]; n++; } } } } } m++; } while (st[i][m] != '\0'); last[i][n] = '\0'; last[i][0] = --n; lflag[i] = 1; } } int deal() { int i, j; int x, y; int z; //输入串的长度 k = 1; s[k] = '#'; //栈置初值 for (i = 0; input[i] != '\0'; i++); //计算输入串的长度 z = i--; i = 0; while ((a = input[i]) != '\0') { //j指向最接近栈顶的终极符 if (Terminator(s[k])) j = k; else j = k - 1; x = getIndex(s[j]);//获取最接近栈顶的终极符在终极符表中位置 y = getIndex(a);//获取第一个输入符号在终极符表中位置 if (Data[x][y] == '>')//归约 { out(1, k, s); printf("%c", a); out(i + 1, z, input); printf("规约\n"); do { q = s[j]; if (Terminator(s[j - 1])) j = j - 1; else j = j - 2; x = getIndex(s[j]); y = getIndex(q); } while (Data[x][y] != '<'); int m, n, N; for (m = j + 1; m <= k; m++) { for (N = 0; N<r1; N++) for (n = 1; In_str[N][n] != '\0'; n++) { if (!Terminator(s[m]) && !Terminator(In_str[N][n])) { if (Terminator(s[m + 1]) && Terminator(In_str[N][n + 1]) && s[m + 1] == In_str[N][n + 1]) { s[j + 1] = In_str[N][0]; break; } } else if (Terminator(s[m])) if (s[m] == In_str[N][n]) { s[j + 1] = In_str[N][0]; break; } } } k = j + 1; if (k == 2 && a == '#') { out(1, k, s); printf("%c", a); out(i + 1, z, input); printf("结束\n"); printf("\n输入串符合文法的定义！\n"); return 1; //输入串符合文法的定义 } } else if (Data[x][y] == '<' || Data[x][y] == '=') { //移进 out(1, k, s); printf("%c", a); out(i + 1, z, input); printf("移进\n"); k++; s[k] = a; i++; } else { printf("\n输入串不符合文法的定义！\n"); return 0; } } printf("\n输入串不符合文法的定义！\n"); return 0; } int deal1() { int i, j; int x, y; int z; //输入串的长度 k = 1; s[k] = '#'; //s栈置初值 str[k]="#"; //类似str栈置初值 for (i = 0; input[i] != '\0'; i++); //计算输入串的长度 z = i--; i = 0; while ((a = input[i]) != '\0') { //j指向最接近栈顶的终极符 if (Terminator(s[k])) j = k; else j = k - 1; x = getIndex(s[j]);//获取最接近栈顶的终极符在终极符表中位置 y = getIndex(a);//获取第一个输入符号在终极符表中位置 if (Data[x][y] == '>')//归约 { out1(1, k, str); printf("%c", a); out(i + 1, z, input); printf("规约"); do { q = s[j]; if (Terminator(s[j - 1])) j = j - 1; else j = j - 2; x = getIndex(s[j]); y = getIndex(q); } while (Data[x][y] != '<'); int m, n, N; for (m = j + 1; m <= k; m++) { for (N = 0; N<r1; N++) for (n = 1; In_str[N][n] != '\0'; n++) { if (!Terminator(s[m]) && !Terminator(In_str[N][n])) { if (Terminator(s[m + 1]) && Terminator(In_str[N][n + 1]) && s[m + 1] == In_str[N][n + 1]) { //printf("%s",text[N]); //printf("%c%d->%c%d%c%c%d",In_str[N][0],m,s[m],m,s[m+1],s[m+2],m+2); //printf("s[%d]==%c&In_str[%d][%d]==%c&s[%d]==%c&In_str[%d][%d]==%c",m,s[m],N,n,In_str[N][n],m+1,s[m+1],N,n+1,In_str[N][n+1]); string avl=str[m];//提前保留还未规约更新的值用于输出 s[j + 1] = In_str[N][0];//规约代替例如T->E+P charmap[In_str[N][0]]+=1;//利用map存储记忆该X的下标，例如X1->i ss<<In_str[N][0];//利用ss将char转换为string ss<<charmap[In_str[N][0]];//对应数字下标也转入string方便入栈str str[j+1]=ss.str()+"\0";//str栈内对应s栈一样压入对应值，不同点非终结符X加入下标X1 ss.str("");//ss清空 cout<<str[j+1]<<"->"<<avl<<str[m+1]<<str[m+2];//输出规约对应表达式（推导式） stringmap[str[j+1]]=str[j+1];//将转换对应值用map存储，例如X1=i或X1=X1那么stringmap[X1]="i"，用于四元组输出求值 qua[quaCounts][0]=str[m+1];//存入四元组计算符，例如+ qua[quaCounts][1]=stringmap[avl];//存入四元组第一个计算数，例如E1 qua[quaCounts][2]=stringmap[str[m+2]];//存入四元组第二个计算数，例如P1 qua[quaCounts][3]=stringmap[str[j+1]];//存入四元组计算结果，例如T1 cout<<"\t\t"; cout<<"产生【"<<(quaCounts+1)<<"】："; cout<<"("+qua[quaCounts][0]+","+qua[quaCounts][1]+","+qua[quaCounts][2]+","+qua[quaCounts][3]+")";//输出对应直接生成的四元组 quaCounts++;//四元组数目加一 goto outer;//直接跳出全部循环 } } else{ if(Terminator(s[m])&&s[m]=='('&&Terminator(s[m+2])&&s[m+2]==')'){//专门为T->(E)这种情况而设定 if (s[m] == In_str[N][n]) { //printf("%c%d->%c",In_str[N][0],m,In_str[N][n]); string avl=str[m];//提前保留还未规约更新的值用于输出 s[j + 1] = In_str[N][0];//规约代替T->(E) charmap[s[j + 1]]+=1;//利用map存储记忆该X的下标，例如X1->i ss<<s[j+1];//利用ss将char转换为string ss<<charmap[s[j + 1]];//对应数字下标也转入string方便入栈str str[j+1]=ss.str()+"\0";//str栈内对应s栈一样压入对应值，不同点非终结符X加入下标X1 ss.str("");//ss清空 cout<<str[j+1]<<"->"<<avl<<str[m+1]<<str[m+2];//输出规约对应表达式（推导式） stringmap[str[j+1]]=str[j+1];//将转换对应值用map存储，例如X1=i或X1=X1那么stringmap[X1]="i"，用于四元组输出求值 goto outer;//直接跳出全部循环 } } else if (Terminator(s[m]))//若为终结符例如X->i if (s[m] == In_str[N][n]) { //printf("%c%d->%c",In_str[N][0],m,In_str[N][n]); s[j + 1] = In_str[N][0];//将终结符i利用X规约代替 charmap[s[j + 1]]+=1;//利用map存储记忆该X的下标，例如X1->i ss<<s[j+1];//利用ss将char转换为string ss<<charmap[s[j + 1]];//对应数字下标也转入string方便入栈str str[j+1]=ss.str()+"\0";//str栈内对应s栈一样压入对应值，不同点非终结符X加入下标X1 ss.str("");//ss清空 cout<<str[j+1]<<"->"<<In_str[N][n];//输出规约对应表达式（推导式） ss<<In_str[N][n];//利用ss将char转换为string stringmap[str[j+1]]=ss.str();//将转换对应值用map存储，例如X1->i那么stringmap[X1]="i"，用于四元组输出求值 ss.str("");//ss清空 goto outer;//直接跳出全部循环 } } } } outer://循环跳出位置 k = j + 1;//栈顶位置k更新 printf("\n");//下一行 if (k == 2 && a == '#')//规约完毕，只剩#X符号 { out1(1, k, str); printf("%c", a); out(i + 1, z, input); printf("结束\n"); printf("\n输入串符合文法的定义！\n"); return 1; //输入串符合文法的定义 } } else if (Data[x][y] == '<' || Data[x][y] == '=') { //移进 out1(1, k, str);//输出当前范围内的栈str printf("%c", a); out(i + 1, z, input); printf("移进\n"); k++; s[k] = a;//移进赋值 //类似的栈str也对应移进赋值，此处借用ss将char转换为string类型 ss<<a; str[k]=ss.str()+"\0"; ss.str("");//清空ss i++; } else { printf("\n输入串不符合文法的定义！\n"); return 0; } } printf("\n输入串不符合文法的定义！\n"); return 0; } void out(int j, int k, char *s) { int n = 0; int i; for (i = j; i <= k; i++) { printf("%c", s[i]); n++; } for (; n<15; n++) { printf(" "); } } void out1(int j, int k, string *str) { int n = 0; int i; for (i = j; i <= k; i++)//输出到k位置范围内的栈str { cout<<str[i]; n=n+str[i].size(); } for (; n<15; n++)//差额空格，水平制表 { cout<<" "; } } int getIndex(char c) //求字符c在文法终极符表中的下标 { int i; for (i = 0; lable[i] != '\0'; i++) { if (c == lable[i]) return i; } return -1; } int Terminator(char c) //判断字符c是否是终极符 { int i; for (i = 0; lable[i] != '\0'; i++) { if (c == lable[i]) return 1; } return 0; }

三、结果