编写一个C语言代码,对于表达式按照自上而下的方法构造一颗语法分析树,对其进行语义分析,将可执行语句或表达式翻译为四元式,并将错误信息输出
时间: 2024-03-08 16:47:49 浏览: 74
编译原理 语法分析C语言源代码
好的,以下是一个可能的实现,仅供参考:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
/* 词法分析器 */
typedef enum {
TOKEN_PLUS, // +
TOKEN_MINUS, // -
TOKEN_MUL, // *
TOKEN_DIV, // /
TOKEN_LPAREN, // (
TOKEN_RPAREN, // )
TOKEN_NUMBER, // 数字
TOKEN_EOF, // 结束符
TOKEN_INVALID, // 非法输入
} TokenKind;
typedef struct {
TokenKind kind; // 词法单元类型
int value; // 数字的值
} Token;
Token current_token; // 当前词法单元
void error(const char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
int next_char() {
return getchar();
}
Token get_token() {
int c = next_char();
// 跳过空格和换行符
while (isspace(c)) {
c = next_char();
}
if (isdigit(c)) {
// 处理数字
int value = 0;
while (isdigit(c)) {
value = value * 10 + (c - '0');
c = next_char();
}
ungetc(c, stdin); // 将多读的一个字符退回
return (Token){TOKEN_NUMBER, value};
} else if (c == '+') {
return (Token){TOKEN_PLUS};
} else if (c == '-') {
return (Token){TOKEN_MINUS};
} else if (c == '*') {
return (Token){TOKEN_MUL};
} else if (c == '/') {
return (Token){TOKEN_DIV};
} else if (c == '(') {
return (Token){TOKEN_LPAREN};
} else if (c == ')') {
return (Token){TOKEN_RPAREN};
} else if (c == EOF) {
return (Token){TOKEN_EOF};
} else {
return (Token){TOKEN_INVALID};
}
}
/* 语法分析器 */
typedef enum {
NODE_NUMBER, // 数字节点
NODE_BINARY, // 二元运算符节点
} NodeKind;
typedef struct _Node Node;
typedef struct _BinaryNode BinaryNode;
struct _Node {
NodeKind kind; // 节点类型
};
struct _BinaryNode {
NodeKind kind; // 节点类型
Node* left; // 左子树
Node* right; // 右子树
Token op; // 运算符
};
Node* new_number_node(int value) {
Node* node = (Node*)malloc(sizeof(Node));
node->kind = NODE_NUMBER;
return node;
}
Node* new_binary_node(Node* left, Node* right, Token op) {
BinaryNode* node = (BinaryNode*)malloc(sizeof(BinaryNode));
node->kind = NODE_BINARY;
node->left = left;
node->right = right;
node->op = op;
return (Node*)node;
}
Node* expression();
Node* factor() {
Token token = current_token;
if (token.kind == TOKEN_NUMBER) {
// 处理数字
current_token = get_token();
return new_number_node(token.value);
} else if (token.kind == TOKEN_LPAREN) {
// 处理括号表达式
current_token = get_token();
Node* node = expression();
if (current_token.kind != TOKEN_RPAREN) {
error("expecting a right parenthesis");
}
current_token = get_token();
return node;
} else {
error("unexpected token");
return NULL;
}
}
Node* term() {
Node* node = factor();
while (current_token.kind == TOKEN_MUL || current_token.kind == TOKEN_DIV) {
Token op = current_token;
current_token = get_token();
node = new_binary_node(node, factor(), op);
}
return node;
}
Node* expression() {
Node* node = term();
while (current_token.kind == TOKEN_PLUS || current_token.kind == TOKEN_MINUS) {
Token op = current_token;
current_token = get_token();
node = new_binary_node(node, term(), op);
}
return node;
}
/* 语义分析器 */
typedef enum {
OP_PLUS,
OP_MINUS,
OP_MUL,
OP_DIV,
} Operator;
typedef struct {
Operator op;
int arg1;
int arg2;
int result;
} Quadruple;
void generate(Operator op, int arg1, int arg2, int result) {
static int quad_count = 0;
printf("%d: ", quad_count++);
switch (op) {
case OP_PLUS:
printf("ADD ");
break;
case OP_MINUS:
printf("SUB ");
break;
case OP_MUL:
printf("MUL ");
break;
case OP_DIV:
printf("DIV ");
break;
default:
error("unknown operator");
break;
}
printf("%d, %d, %d\n", arg1, arg2, result);
}
int current_temp = 0; // 当前可用的临时变量编号
int new_temp() {
return current_temp++;
}
int evaluate(Node* node) {
if (node->kind == NODE_NUMBER) {
return ((BinaryNode*)node)->op.value;
} else if (node->kind == NODE_BINARY) {
BinaryNode* binary = (BinaryNode*)node;
int left_value = evaluate(binary->left);
int right_value = evaluate(binary->right);
int result_temp = new_temp();
switch (binary->op.kind) {
case TOKEN_PLUS:
generate(OP_PLUS, left_value, right_value, result_temp);
break;
case TOKEN_MINUS:
generate(OP_MINUS, left_value, right_value, result_temp);
break;
case TOKEN_MUL:
generate(OP_MUL, left_value, right_value, result_temp);
break;
case TOKEN_DIV:
generate(OP_DIV, left_value, right_value, result_temp);
break;
default:
error("unknown operator");
break;
}
return result_temp;
} else {
error("unknown node kind");
return 0;
}
}
/* 主程序 */
int main() {
printf("Please input an expression:\n");
// 读入表达式并构造语法树
current_token = get_token();
Node* root = expression();
if (current_token.kind != TOKEN_EOF) {
error("unexpected token");
}
// 进行语义分析并生成四元式
evaluate(root);
return 0;
}
```
这个代码实现了一个简单的表达式解释器,可以读入一个表达式并将其翻译为四元式。具体的实现方式如下:
1. 首先实现了一个词法分析器,用于将输入的字符流转换为词法单元(如运算符、数字)。
2. 然后实现了一个语法分析器,用于根据词法单元构造语法树。
3. 最后实现了一个语义分析器,用于对语法树进行类型检查和语义分析,并将其转换为四元式。
在主程序中,我们读入一个表达式并构造语法树,然后进行语义分析并生成四元式。如果表达式不合法,会输出错误信息。注意,这个代码只是一个简单的示例,还有很多可以改进的地方,例如处理运算符的优先级、支持变量和函数、优化生成的四元式等。
阅读全文