赋值语句四元式生成算法与代码实现

一、实验目的：赋值语句的四元式生成

二、实验内容：

1. 设计语法制导生成赋值语句的四元式的算法；
2. 编写代码并上机调试运行通过。

要求：

• 输入——原文件；
• 输出——相应的表达式的四元式。

三、原理：

1. 原文法：

EVA_SENTENCE  id := E
E  E ω0 T 
E  T
                  T  T ω1 F 
                  T  F
                  F  id 
                  F  cons
                  F  (E)

• 其中：id —— 标识符； cons —— 常数。

2. 属性文法 G'(E):

| 产生式 | 语义规则 | 规则编码 | |---|---|---| | EVA_SENTENCE id := E | QUAT(:=); | | | E E ω0 T | QUAT(ω0); | (1) | | E.place:= ti.entry； | | | | E T | E.place:=T.place | | | T T ω1 F | QUAT(ω1); | (1) | | T.place:= ti.entry； | | | | T F | T.place:=F.place | | | F id | F.place:=id.entry | (2) | | F cons | F.place:=cons.entry | (2) | | F (E) | F.place:=E.place | (3) |

• 其中：
  • QUAT(:=) —— 生成一个赋值四元式； i. (:=, E.place, _, id.entry); ii. j++;
  • QUAT(ω0) ——生成一个运算四元式； i. ti:=newt(i); //申请一个临时变量 ii. (ω0, E.place, T.place, ti.entry); iii. j++;
  • QUAT(ω1) ——类似 QUAT(ω0)。 i. ti:=newt(i); //申请一个临时变量 ii. (ω1, T.place, F.place, ti.entry); iii. j++;

四、代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAXSIZE 1000 //定义最大长度
#define MAXNUM 100 //定义最大数字

typdef struct{
    char op[5]; //操作符
    char arg1[5]; //第一个操作数
    char arg2[5]; //第二个操作数
    char result[5]; //结果
}Quaternary;

typdef struct{
    char name[5]; //变量名
    char value[5]; //变量值
}Symbol;

int j = 0; //四元式编号
int t = 0; //临时变量编号
int s = 0; //符号表编号
Quaternary quat[MAXSIZE]; //四元式数组
Symbol sym[MAXNUM]; //符号表数组

int getSym(char *str); //获取符号表中变量的位置
void insertSym(char *str); //插入符号表
void error(); //错误处理函数
void E(); //E语法分析函数
void T(); //T语法分析函数
void F(); //F语法分析函数

int main(){
    char str[MAXSIZE]; //输入的字符串
    printf("请输入要分析的赋值语句：\n");
    scanf("%s", str);
    E(str); //开始语法分析
    printf("四元式：\n");
    for(int i = 0; i < j; i++){ //输出四元式
        printf("(%s, %s, %s, %s)\n", quat[i].op, quat[i].arg1, quat[i].arg2, quat[i].result);
    }
    return 0;
}

int getSym(char *str){
    for(int i = 0; i < s; i++){ //遍历符号表
        if(strcmp(sym[i].name, str) == 0){ //找到变量
            return i; //返回变量位置
        }
    }
    return -1; //未找到变量
}

void insertSym(char *str){
    strcpy(sym[s].name, str); //插入变量名
    sprintf(sym[s].value, "t%d", t); //插入变量值
    t++; //临时变量编号加一
    s++; //符号表编号加一
}

void error(){
    printf("语法错误！\n");
    exit(0);
}

void E(char *str){
    char op[5]; //操作符
    char arg1[5]; //第一个操作数
    char arg2[5]; //第二个操作数
    char result[5]; //结果
    int i = 0; //字符串下标
    T(str); //分析T
    while(str[i] == '+' || str[i] == '-'){ //循环分析E'
        op[0] = str[i]; //获取操作符
        op[1] = '\0';
        i++;
        T(str+i); //分析T
        sprintf(result, "t%d", t); //生成临时变量
        t++; //临时变量编号加一
        sprintf(arg1, "t%d", t-2); //获取第一个操作数
        sprintf(arg2, "t%d", t-1); //获取第二个操作数
        strcpy(quat[j].op, op); //插入操作符
        strcpy(quat[j].arg1, arg1); //插入第一个操作数
        strcpy(quat[j].arg2, arg2); //插入第二个操作数
        strcpy(quat[j].result, result); //插入结果
        j++; //四元式编号加一
    }
}

void T(char *str){
    char op[5]; //操作符
    char arg1[5]; //第一个操作数
    char arg2[5]; //第二个操作数
    char result[5]; //结果
    int i = 0; //字符串下标
    F(str); //分析F
    while(str[i] == '*' || str[i] == '/'){ //循环分析T'
        op[0] = str[i]; //获取操作符
        op[1] = '\0';
        i++;
        F(str+i); //分析F
        sprintf(result, "t%d", t); //生成临时变量
        t++; //临时变量编号加一
        sprintf(arg1, "t%d", t-2); //获取第一个操作数
        sprintf(arg2, "t%d", t-1); //获取第二个操作数
        strcpy(quat[j].op, op); //插入操作符
        strcpy(quat[j].arg1, arg1); //插入第一个操作数
        strcpy(quat[j].arg2, arg2); //插入第二个操作数
        strcpy(quat[j].result, result); //插入结果
        j++; //四元式编号加一
    }
}

void F(char *str){
    char arg[5]; //操作数
    int i = 0; //字符串下标
    if(str[i] >= '0' && str[i] <= '9'){ //数字
        while(str[i] >= '0' && str[i] <= '9'){ //循环获取数字
            i++;
        }
        if(str[i] == '\0'){ //到达字符串末尾
            sprintf(arg, "c%s", str); //生成常数
            strcpy(quat[j].op, "cons"); //插入操作符
            strcpy(quat[j].arg1, arg); //插入操作数
            quat[j].arg2[0] = '\0'; //第二个操作数为空
            sprintf(quat[j].result, "t%d", t); //生成临时变量
            t++; //临时变量编号加一
            j++; //四元式编号加一
            return;
        }
        else{ //语法错误
            error();
        }
    }
    else if(str[i] >= 'a' && str[i] <= 'z'){ //变量
        while((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= '0' && str[i] <= '9')){ //循环获取变量名
            i++;
        }
        if(str[i] == '\0'){ //到达字符串末尾
            int pos = getSym(str); //获取变量位置
            if(pos == -1){ //未找到变量
                insertSym(str); //插入符号表
                pos = s-1; //获取变量位置
            }
            strcpy(quat[j].op, ":="); //插入操作符
            strcpy(quat[j].arg1, sym[pos].value); //插入操作数
            quat[j].arg2[0] = '\0'; //第二个操作数为空
            strcpy(quat[j].result, str); //插入结果
            j++; //四元式编号加一
            return;
        }
        else{ //语法错误
            error();
        }
    }
    else if(str[i] == '('){ //括号
        i++;
        E(str+i); //分析E
        if(str[i] == ')'){ //匹配括号
            i++;
            return;
        }
        else{ //语法错误
            error();
        }
    }
    else{ //语法错误
        error();
    }
}