C语言算术表达式语法分析：实现词法分析、优先级判断与四元式生成

1. 概述

本文将介绍如何使用C语言实现一个简单的算术表达式语法分析器。该分析器能够处理包含加减乘除运算和赋值语句的表达式，并将其转换为等价的四元式序列。

2. 语法规则

我们定义的算术表达式和赋值语句的文法如下：

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

其中，S表示赋值语句，E表示算术表达式，i表示变量。

3. 词法分析

词法分析的任务是将输入的表达式分解成一个个词法单元（Token）。在本例中，词法单元包括：

标识符（i）：表示变量名。- 运算符（+、-、*、/、=）：表示算术运算和赋值操作。- 分界符（(、)）：用于改变运算顺序。

4. 语法分析和优先级判断

语法分析的任务是检查输入的表达式是否符合语法规则，并将其转换成一棵语法树。在本例中，我们使用算符优先分析法进行语法分析。

算符优先分析法是一种自底向上的语法分析方法，它根据算符之间的优先级关系来进行语法分析。

5. 四元式生成

四元式是一种中间代码表示形式，它由四个部分组成：

操作符（op）：表示要执行的操作。- 第一个操作数（arg1）。- 第二个操作数（arg2）。- 结果（result）。

6. 代码实现c#include <stdio.h>#include <string.h>

#define N 4#define MAX_EXP_LEN 15#define MAX_STACK_SIZE 15#define MAX_HANDLE_SIZE 10

typedef struct { int op; // 操作符，0表示数字，1表示加法，2表示减法，3表示乘法，4表示除法，5表示结束符 int val; // 数字的值} Token;

typedef struct { int op; // 操作符，1表示赋值，2表示加法，3表示减法，4表示乘法，5表示除法 int arg1; // 第一个操作数的位置 int arg2; // 第二个操作数的位置 int res; // 结果的位置} Quadruple;

int map(char ch) { char loca[7] = {'+', '*', 'i', '(', ')', '#'}; char *p = strchr(loca, ch); if (p == NULL) { return -1; } else { return p - loca; }}

void print_token(Token token) { if (token.op == 0) { printf('%d', token.val); } else { printf('%c', token.op == 1 ? '+' : token.op == 2 ? '-' : token.op == 3 ? '*' : '/'); }}

void print_quadruple(Quadruple quadruple) { printf('(%d, ', quadruple.op); if (quadruple.arg1 != -1) { printf('%d, ', quadruple.arg1); } else { printf('-, '); } if (quadruple.arg2 != -1) { printf('%d, ', quadruple.arg2); } else { printf('-, '); } if (quadruple.res != -1) { printf('%d)', quadruple.res); } else { printf('-)'); }}

int prio[6][6] = { {3, 1, 1, 1, 3, 3}, {3, 3, 1, 1, 3, 3}, {3, 3, 0, 0, 3, 3}, {1, 1, 1, 1, 2, 0}, {3, 3, 0, 0, 3, 3}, {1, 1, 1, 1, 0, 4}};

int main() { char exp[MAX_EXP_LEN + 1]; printf('Please input your expression: '); scanf('%s', exp);

Token tokens[MAX_EXP_LEN];    int num_tokens = 0;    int i = 0;    while (exp[i] != '�') {        if (exp[i] >= '0' && exp[i] <= '9') {            int val = exp[i] - '0';            i++;            while (exp[i] >= '0' && exp[i] <= '9') {                val = val * 10 + exp[i] - '0';                i++;            }            Token token = {0, val};            tokens[num_tokens++] = token;        } else {            Token token = {map(exp[i]), -1};            tokens[num_tokens++] = token;            i++;        }    }    Token end_token = {5, -1};    tokens[num_tokens++] = end_token;

Quadruple quadruples[MAX_EXP_LEN];    int num_quadruples = 0;    Token stack[MAX_STACK_SIZE];    int top = 0;    int handle[MAX_HANDLE_SIZE];    int top_h = -1;    stack[top++] = end_token;

int i_token = 0;    while (top > 0) {        Token token = tokens[i_token];        Token top_token = stack[top - 1];        int code = -1;        if (top_token.op == 0) {            code = 2;        } else if (token.op == 5) {            code = 4;        } else {            int i = top_token.op;            int j = token.op;            code = prio[i][j];        }        if (code == 0) {            printf('Error!

'); return 0; } else if (code == 1 || code == 2) { stack[top++] = token; if (code == 1) { handle[++top_h] = top - 1; } i_token++; } else { Quadruple quadruple = {1, -1, -1, handle[top_h - 1]}; if (top_token.op == 1) { quadruple.op = 2; quadruple.arg1 = handle[top_h - 1] - 1; quadruple.arg2 = handle[top_h] - 1; } else if (top_token.op == 2) { quadruple.op = 3; quadruple.arg1 = handle[top_h - 1] - 1; quadruple.arg2 = handle[top_h] - 1; } else if (top_token.op == 3) { quadruple.op = 4; quadruple.arg1 = handle[top_h - 1] - 1; quadruple.arg2 = handle[top_h] - 1; } else if (top_token.op == 4) { quadruple.op = 5; quadruple.arg1 = handle[top_h - 1] - 1; quadruple.arg2 = handle[top_h] - 1; } quadruple.res = handle[top_h - 1] - 2; quadruples[num_quadruples++] = quadruple; top_h--; top -= 2; stack[top] = end_token; stack[top - 1].op = 0; } }

printf('Quadruples:

'); for (int i = 0; i < num_quadruples; i++) { print_quadruple(quadruples[i]); printf(' '); }

return 0