📄 算符优先.cpp
字号:
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
//----------------------------------------------------------------------------
typedef struct{
char elem[10][15];
int top;
}SeqStack;;
//----------------------------------------------------------------------------
char LessLetter[10]; //存放产生式里面出现的终结符
int LetterNumber; //存放终结符的数目
char FIRSTVT[10][15]; //存放非终结符的FIRSTVT集合
char LASTVT[10][15]; //存放非终结符的LASTVT集合
bool judge[10][10]; //用于判断查找FIRSTVT和LASTVT集合
SeqStack STACK;
//----------------------------------------------------------------------------
void init(char temp[][15]){ //对数组进行初始化
int i,j;
for(i=0;i<10;i++)
for(j=0;j<15;j++)
temp[i][j]='\0';
}
void InitBool(bool judge[][10]){ //对布尔数组进行初始化
int i,j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
judge[i][j]=false;
}
void input(char temp[][15],int number){
int i;
for(i=0;i<number;i++){
printf("\n输入产生式%d:",i+1);
scanf("%s",temp[i]);
}
}
bool IsLetter(char a){ //判断字母a是否为非终结符
if((a<='Z')&&(a>='A'))
return true;
else
return false;
}
bool judgement(char a){ //判断字母a是否出现在终结字母表中
int i;
for(i=0;i<10;i++)
if(a==LessLetter[i])
return false;
return true;
}
void MakeLessLetter(char temp[][15],int number){ //生成终结符字母表
int i,j;
for(i=0;i<number;i++)
for(j=3;j<15;j++){
if(!IsLetter(temp[i][j])&&temp[i][j]!='|'){
if(judgement(temp[i][j]))
LessLetter[LetterNumber++]=temp[i][j];
}
}
LessLetter[LetterNumber++]='#';
LessLetter[LetterNumber]='\0';
}
void outFIRSTStack(char temp[][15],int number){
int i,j,t;
for(i=0;i<number;i++)
for(j=3;j<15;j++){
if(temp[i][3]==STACK.elem[STACK.top][0]){ //判断若有产生式右部是以STACK.elem[STACK.top][0]开头的
STACK.elem[STACK.top][0]=temp[i][0];
for(t=0;t<LetterNumber;t++){
if(LessLetter[t]==STACK.elem[STACK.top][1]){
judge[i][t]=true;
break;
}
}
}
if(temp[i][j]=='|'&&temp[i][j+1]==STACK.elem[STACK.top][0]){
STACK.elem[STACK.top][0]=temp[i][0];
for(t=0;t<LetterNumber;t++){
if(LessLetter[t]==STACK.elem[STACK.top][1]){
judge[i][t]=true;
break;
}
}
}
}
if(STACK.elem[STACK.top][0]==temp[0][0])
STACK.top--;
}
void manageFIRST(char temp[][15],int i,int j){
int t;
if(!IsLetter(temp[i][j])&&temp[i][j]!='|'){ //终结符在产生式右部最左边
for(t=0;t<LetterNumber;t++)
if(temp[i][j]==LessLetter[t]){
judge[i][t]=true;
STACK.top++;
STACK.elem[STACK.top][0]=temp[i][0];
STACK.elem[STACK.top][1]=LessLetter[t];
break;
}
}
else if(!IsLetter(temp[i][j+1])&&temp[i][j+1]!='|'&&IsLetter(temp[i][j])){ //终结符在产生式右部第二个位置
for(t=0;t<LetterNumber;t++)
if(temp[i][j+1]==LessLetter[t]){
judge[i][t]=true;
STACK.top++;
STACK.elem[STACK.top][0]=temp[i][0];
STACK.elem[STACK.top][1]=LessLetter[t];
break;
}
}
}
void Firstvt(char temp[][15],int number){ //求FIRSTVT集合
int i,j,t;
for(i=0;i<number;i++){
manageFIRST(temp,i,3);
for(j=0;j<15;j++){
if(temp[i][j]=='|')
manageFIRST(temp,i,j+1);
}
}
while(STACK.top!=-1)
outFIRSTStack(temp,number);
for(i=0;i<number;i++){
t=0;
for(j=0;j<LetterNumber;j++)
if(judge[i][j])
FIRSTVT[i][t++]=LessLetter[j];
}
printf("\n\n所有非终结符的FIRSTVT集合如下:\n");
for(i=0;i<number;i++){
printf("FIRSTVT(%c)={",temp[i][0]);
for(j=0;j<15;j++)
if(FIRSTVT[i][j+1]=='\0'){
printf("%c}\n",FIRSTVT[i][j]);
break;
}
else
printf("%c,",FIRSTVT[i][j]);
}
}
void manageLAST(char temp[][15],int i,int j){
int t;
if(!IsLetter(temp[i][j])&&temp[i][j]!='|'){ //终结符在产生式右部最右边
for(t=0;t<LetterNumber;t++)
if(temp[i][j]==LessLetter[t]){
judge[i][t]=true;
STACK.top++;
STACK.elem[STACK.top][0]=temp[i][0];
STACK.elem[STACK.top][1]=LessLetter[t];
break;
}
}
else if(!IsLetter(temp[i][j-1])&&temp[i][j-1]!='|'&&IsLetter(temp[i][j])){ //终结符在产生式右部倒数第二个位置
for(t=0;t<LetterNumber;t++)
if(temp[i][j-1]==LessLetter[t]){
judge[i][t]=true;
STACK.top++;
STACK.elem[STACK.top][0]=temp[i][0];
STACK.elem[STACK.top][1]=LessLetter[t];
break;
}
}
}
void outLASTStack(char temp[][15],int number){
int i,j,t,k;
for(i=0;i<number;i++)
for(j=3;j<15;j++){
if(temp[i][j]=='\0'){
k=j;
if(temp[i][k-1]==STACK.elem[STACK.top][0]){ //判断若有产生式右部是以STACK.elem[STACK.top][0]结尾的
STACK.elem[STACK.top][0]=temp[i][0];
for(t=0;t<LetterNumber;t++){
if(LessLetter[t]==STACK.elem[STACK.top][1]){
judge[i][t]=true;
break;
}
}
}
break;
}
}
for(j=3;j<15;j++){
if(temp[i][j]=='|'&&temp[i][j-1]==STACK.elem[STACK.top][0]){
STACK.elem[STACK.top][0]=temp[i][0];
for(t=0;t<LetterNumber;t++){
if(LessLetter[t]==STACK.elem[STACK.top][1]){
judge[i][t]=true;
break;
}
}
}
}
if(STACK.elem[STACK.top][0]==temp[0][0])
STACK.top--;
}
void Lastvt(char temp[][15],int number){
STACK.top=-1; //将栈重新初始化
init(STACK.elem);
InitBool(judge); //将布尔数组重新初始化
int i,j,t;
for(i=0;i<number;i++){
for(j=0;j<15;j++){ //找到产生式在数组中的最后位置,记录在t里
if(temp[i][j]=='\0'){
t=j;
break;
}
}
manageLAST(temp,i,t-1);
for(j=t;j>0;j--){ //从后往前处理
if(temp[i][j]=='|')
manageLAST(temp,i,j-1);
}
}
while(STACK.top!=-1)
outLASTStack(temp,number);
for(i=0;i<number;i++){
t=0;
for(j=0;j<LetterNumber;j++)
if(judge[i][j])
LASTVT[i][t++]=LessLetter[j];
}
printf("\n\n所有非终结符的LASTVT集合如下:\n");
for(i=0;i<number;i++){
printf("LASTVT(%c)={",temp[i][0]);
for(j=0;j<15;j++)
if(LASTVT[i][j+1]=='\0'){
printf("%c}\n",LASTVT[i][j]);
break;
}
else
printf("%c,",LASTVT[i][j]);
}
}
int Search(char a){
int i;
for(i=0;i<LetterNumber;i++)
if(a==LessLetter[i])
return i;
return -1;
}
int Find(char a,char temp[][15],int number){ //找出非终结符在产生式里的位置
int i;
for(i=0;i<number;i++)
if(a==temp[i][0])
return i;
return -1;
}
void CreatTable(int number,char table[][15],char temp[][15]){ //构造优先关系表
int i,j,t,k,r,location;
for(i=0;i<number;i++){
for(j=3;j<15;j++){
if(!IsLetter(temp[i][j])&&temp[i][j]!='|'&&temp[i][j]!='\0'){ //找出终结符
r=Search(temp[i][j]);
if(IsLetter(temp[i][j-1])){ //若终结符前一个位置为非终结符则这个非终结符的LASTVT集合里的元素均>终结符
location=Find(temp[i][j-1],temp,number);
for(t=0;t<15;t++){
if(LASTVT[location][t]!='\0'&&Search(LASTVT[location][t]!=-1)){
k=Search(LASTVT[location][t]);
table[k][r]='>';
}
}
}
if(IsLetter(temp[i][j+1])){ //若终结符后一个位置为非终结符则这个非终结符的FIRSTVT集合里的元素均<终结符
location=Find(temp[i][j+1],temp,number);
for(t=0;t<15;t++){
if(FIRSTVT[location][t]!='\0'&&Search(FIRSTVT[location][t]!=-1)){
k=Search(FIRSTVT[location][t]);
table[r][k]='<';
}
}
}
if(!IsLetter(temp[i][j+1])&&temp[i][j+1]!='|'){ //若两个终结符相连则优先关系相等
k=Search(temp[i][j+1]);
table[r][k]='=';
}
if(!IsLetter(temp[i][j+2])&&temp[i][j+2]!='|'&&IsLetter(temp[i][j+1])){ //若两个终结符终结只有一个非终结符则两个终结符优先关系也相等
k=Search(temp[i][j+2]);
table[r][k]='=';
}
}
}
}
for(i=0;i<LetterNumber;i++)
if(LessLetter[i]=='#'){
for(j=0;j<LetterNumber;j++){ //优先表最下面的#号小于开始符号的FIRSTVT集合
k=Search(FIRSTVT[0][j]);
if(k!=-1)
table[i][k]='<';
r=Search(LASTVT[0][j]); //优先表的最右边的的#号大于开始符号的LASTVT集合
if(r!=-1)
table[r][i]='>';
}
break;
}
table[i][i]='='; //两个#号优先关系相等
}
void outTable(char table[][15]){ //将优先算符关系表输出
int i,j;
printf("\n\n算符优先关系表如下:\n");
for(i=0;i<LetterNumber;i++)
printf("\t%c",LessLetter[i]);
printf("\n");
for(i=0;i<LetterNumber;i++){
printf("%c\t",LessLetter[i]);
for(j=0;j<LetterNumber;j++)
printf("%c\t",table[i][j]);
printf("\n");
}
}
int main(){
char temp[10][15]; //存放文法的产生式
int number; //存放产生式的个数
char table[10][15]; //存放优先算符关系表
STACK.top=-1;
init(STACK.elem);
init(temp);
init(FIRSTVT);
init(LASTVT);
init(table);
InitBool(judge);
printf("\n请输入文法里的产生式个数:");
scanf("%d",&number);
input(temp,number);
MakeLessLetter(temp,number);
Firstvt(temp,number);
Lastvt(temp,number);
CreatTable(number,table,temp);
outTable(table);
return 1;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -