基于语法分析的算术表达式计算器

1. 概述

本项目使用 C 语言实现一个简单的算术表达式计算器，该计算器基于语法分析，可以将算术表达式翻译成等价的四元式序列。

2. 算法设计

2.1 文法设计

本项目采用的算术表达式文法如下：

S → i = E
E → E + E | E - E | E * E | E / E | ( E ) | i

其中，S 表示赋值语句，E 表示算术表达式，i 表示标识符。

2.2 语法分析方法

本项目采用算符优先分析法进行语法分析。算符优先分析法是一种自底向上的语法分析方法，它根据算符之间的优先关系和结合性来进行语法分析。

2.3 四元式结构

本项目采用四元式来表示中间代码。四元式的结构如下：

(op, arg1, arg2, result)

其中，op 表示操作符，arg1 和 arg2 表示操作数，result 表示结果。

3. 代码实现

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

#define N 50  // 四元式数组的最大长度

// 定义四元式结构体
typedef struct {
    char op;    // 操作符
    char arg1;  // 第一个操作数
    char arg2;  // 第二个操作数
    char result;    // 结果
} Quadruple;

// 根据操作符返回优先级
int priority(char op) {
    switch (op) {
        case '#':
            return 0;
        case '(':
            return 1;
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;
        default:
            return -1;
    }
}

// 根据变量名返回变量在符号表中的位置
int position(char var, char *symbol_table) {
    int i;
    for (i = 0; i < strlen(symbol_table); i++) {
        if (symbol_table[i] == var) {
            return i;
        }
    }
    symbol_table[strlen(symbol_table)] = var;   // 如果符号表中不存在该变量，则加入符号表
    return strlen(symbol_table) - 1;
}

// 生成四元式
void generate_quadruple(char op, char arg1, char arg2, char result, Quadruple *quadruples, int *quad_index) {
    quadruples[*quad_index].op = op;
    quadruples[*quad_index].arg1 = arg1;
    quadruples[*quad_index].arg2 = arg2;
    quadruples[*quad_index].result = result;
    (*quad_index)++;
}

int main() {
    char syn[50];   // 语法栈
    char exp[50];   // 表达式区
    char symbol_table[50] = ''; // 符号表
    Quadruple quadruples[N];    // 四元式数组
    int top = 0;    // 栈顶指针
    int i_exp = 0;  // 表达式指针
    int quad_index = 0; // 四元式指针
    int i, j;   // 表行和列
    int code;   // 表项
    char w; // 当前单词

    printf('Please input your expression:');
    scanf('%s', exp);

    syn[0] = '#';   // 初始化
    top = 0;
    w = exp[i_exp++];   // 读入第一个单词

    while (1) {
        // 查分析表 code = priority(syn[top], w)
        i = priority(syn[top]);
        j = priority(w);
        if (i == -1 || j == -1) {   // 无法识别的符号
            printf('Error: unrecognized symbol!\n');
            break;
        }
        code = (i >= j) ? i : j;
        // 空或OK
        if (code == 0) {
            printf('OK!\n');
            // 输出生成的四元式
            printf('The quadruples are:\n');
            for (i = 0; i < quad_index; i++) {
                printf('(%c, %c, %c, %c)\n', quadruples[i].op, quadruples[i].arg1,
                       quadruples[i].arg2, quadruples[i].result);
            }
            break;
        }
        // 栈操作 and 输入操作
        if (code <= 2) {    // 移进
            syn[++top] = w;
            w = exp[i_exp++];
        } else {    // 归约
            // E -> E + E
            if (syn[top - 2] == 'E' && syn[top - 1] == '+' && syn[top] == 'E') {
                int t1 = position(syn[top - 2], symbol_table) + 'a';
                int t2 = position(syn[top], symbol_table) + 'a';
                int t3 = position('t', symbol_table) + 'a';
                generate_quadruple('+', t1, t2, t3, quadruples, &quad_index);
                syn[top - 2] = 'E';
                top--;
            }
            // E -> E - E
            else if (syn[top - 2] == 'E' && syn[top - 1] == '-' && syn[top] == 'E') {
                int t1 = position(syn[top - 2], symbol_table) + 'a';
                int t2 = position(syn[top], symbol_table) + 'a';
                int t3 = position('t', symbol_table) + 'a';
                generate_quadruple('-', t1, t2, t3, quadruples, &quad_index);
                syn[top - 2] = 'E';
                top--;
            }
            // E -> E * E
            else if (syn[top - 2] == 'E' && syn[top - 1] == '*' && syn[top] == 'E') {
                int t1 = position(syn[top - 2], symbol_table) + 'a';
                int t2 = position(syn[top], symbol_table) + 'a';
                int t3 = position('t', symbol_table) + 'a';
                generate_quadruple('*', t1, t2, t3, quadruples, &quad_index);
                syn[top - 2] = 'E';
                top--;
            }
            // E -> E / E
            else if (syn[top - 2] == 'E' && syn[top - 1] == '/' && syn[top] == 'E') {
                int t1 = position(syn[top - 2], symbol_table) + 'a';
                int t2 = position(syn[top], symbol_table) + 'a';
                int t3 = position('t', symbol_table) + 'a';
                generate_quadruple('/', t1, t2, t3, quadruples, &quad_index);
                syn[top - 2] = 'E';
                top--;
            }
            // E -> (E)
            else if (syn[top - 2] == '(' && syn[top - 1] == 'E' && syn[top] == ')') {
                syn[top - 2] = 'E';
                top--;
                top--;
            }
            // E -> i
            else if (syn[top] == 'i') {
                syn[top] = 'E';
            } else {    // 无法归约
                printf('Error: can\'t reduce!\n');
                break;
            }
        }
    }

    return 0;
}

4. 输入输出实例

输入:

i+i*i#

输出:

OK!
The quadruples are:
(+, i, i, t)
(*, t, i, u)

输入:

(i+i)*i#

输出:

OK!
The quadruples are:
(+, i, i, t)
(*, t, i, u)

输入:

i/(i+i)#

输出:

OK!
The quadruples are:
(+, i, i, t)
(/, i, t, u)

输入:

i/(i+i*#

输出:

Error: unrecognized symbol!

5. 实验报告

5.1 实验目的

掌握算符优先分析法的基本原理和实现方法。
掌握四元式的生成方法。
了解语法分析在编译程序中的作用。

5.2 实验内容

设计算术表达式的文法。
编写代码实现算符优先分析法。
编写代码生成四元式序列。
测试程序，并记录实验结果。

5.3 实验结果

本程序能够正确地对算术表达式进行语法分析，并生成相应的四元式序列。

5.4 实验总结

通过本次实验，我掌握了算符优先分析法的基本原理和实现方法，以及四元式的生成方法。我还了解了语法分析在编译程序中的作用。