• 日期: 2028-09-17
  • 标签: 常规

以下是使用LR分析法和语法制导翻译法实现简单算术表达式求值的完整C语言代码：

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

#define MAX_STACK_SIZE 100
#define MAX_INPUT_SIZE 100

// 产生式为L→En E→E1+T E→T T→T1*F T→F F→(E) F→1 F→2 F→3 F→4 F→5
// 定义终结符和非终结符的枚举类型
typedef enum {
    ENDFILE, PLUS, TIMES, LPAREN, RPAREN, NUM1, NUM2, NUM3, NUM4, NUM5
} TokenType;

typedef struct {
    TokenType type;
    int value;
} Token;

typedef struct {
    int state;
    TokenType symbol;
} LRItem;

// 定义LR分析表
LRItem LRTable[18][10] = {
    {{5, ENDFILE}, {-1, PLUS}, {-1, TIMES}, {4, LPAREN}, {-1, RPAREN}, {1, NUM1}, {2, NUM2}, {3, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {6, PLUS}, {-1, TIMES}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {-1, PLUS}, {7, TIMES}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {-1, PLUS}, {8, TIMES}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{5, ENDFILE}, {-1, PLUS}, {-1, TIMES}, {4, LPAREN}, {-1, RPAREN}, {9, NUM1}, {10, NUM2}, {11, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 1}, {reduce, 1}, {-1, LPAREN}, {reduce, 1}, {reduce, 1}, {reduce, 1}, {reduce, 1}, {reduce, 1}, {reduce, 1}},
    {{5, ENDFILE}, {-1, PLUS}, {-1, TIMES}, {4, LPAREN}, {-1, RPAREN}, {1, NUM1}, {2, NUM2}, {3, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 3}, {11, TIMES}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 5}, {10, TIMES}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 7}, {9, TIMES}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{5, ENDFILE}, {-1, PLUS}, {-1, TIMES}, {4, LPAREN}, {-1, RPAREN}, {1, NUM1}, {2, NUM2}, {3, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 9}, {reduce, 9}, {-1, LPAREN}, {reduce, 9}, {reduce, 9}, {reduce, 9}, {reduce, 9}, {reduce, 9}, {reduce, 9}},
    {{5, ENDFILE}, {-1, PLUS}, {-1, TIMES}, {4, LPAREN}, {-1, RPAREN}, {1, NUM1}, {2, NUM2}, {3, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 11}, {reduce, 11}, {-1, LPAREN}, {reduce, 11}, {reduce, 11}, {reduce, 11}, {reduce, 11}, {reduce, 11}, {reduce, 11}},
    {{5, ENDFILE}, {-1, PLUS}, {-1, TIMES}, {4, LPAREN}, {-1, RPAREN}, {1, NUM1}, {2, NUM2}, {3, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 2}, {6, PLUS}, {-1, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 4}, {reduce, 4}, {7, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}},
    {{-1, ENDFILE}, {reduce, 6}, {reduce, 6}, {8, LPAREN}, {-1, RPAREN}, {-1, NUM1}, {-1, NUM2}, {-1, NUM3}, {-1, NUM4}, {-1, NUM5}}
};

// 定义符号栈和状态栈
TokenType symbolStack[MAX_STACK_SIZE];
int stateStack[MAX_STACK_SIZE];
int stackTop = -1;

// 定义输入缓冲区和指针
char input[MAX_INPUT_SIZE];
int inputIndex = 0;

// 从输入缓冲区读取下一个Token
Token getNextToken() {
    Token token;
    char c = input[inputIndex++];

    switch (c) {
        case '+':
            token.type = PLUS;
            break;
        case '*':
            token.type = TIMES;
            break;
        case '('
            token.type = LPAREN;
            break;
        case ')':
            token.type = RPAREN;
            break;
        case '1':
            token.type = NUM1;
            token.value = 1;
            break;
        case '2':
            token.type = NUM2;
            token.value = 2;
            break;
        case '3':
            token.type = NUM3;
            token.value = 3;
            break;
        case '4':
            token.type = NUM4;
            token.value = 4;
            break;
        case '5':
            token.type = NUM5;
            token.value = 5;
            break;
        case '\0':
            token.type = ENDFILE;
            break;
        default:
            printf("Error: invalid input\n");
            exit(1);
    }

    return token;
}

// 将Token压入符号栈
void pushSymbol(TokenType symbol) {
    if (stackTop >= MAX_STACK_SIZE - 1) {
        printf("Error: stack overflow\n");
        exit(1);
    }
    symbolStack[++stackTop] = symbol;
}

// 将状态压入状态栈
void pushState(int state) {
    if (stackTop >= MAX_STACK_SIZE - 1) {
        printf("Error: stack overflow\n");
        exit(1);
    }
    stateStack[++stackTop] = state;
}

// 从符号栈弹出一个符号
TokenType popSymbol() {
    if (stackTop < 0) {
        printf("Error: stack underflow\n");
        exit(1);
    }
    return symbolStack[stackTop--];
}

// 从状态栈弹出一个状态
int popState() {
    if (stackTop < 0) {
        printf("Error: stack underflow\n");
        exit(1);
    }
    return stateStack[stackTop--];
}

// 获取当前状态
int getCurrentState() {
    return stateStack[stackTop];
}

// 根据产生式进行归约
void reduce(int production) {
    switch (production) {
        case 1: // L → E
            popSymbol(); // 弹出E
            break;
        case 2: // E → E1 + T
            popSymbol(); // 弹出T
            popSymbol(); // 弹出+
            popSymbol(); // 弹出E1
            pushSymbol(ENDFILE); // 压入L
            break;
        case 3: // E → T
            popSymbol(); // 弹出T
            pushSymbol(ENDFILE); // 压入L
            break;
        case 4: // T → T1 * F
            popSymbol(); // 弹出F
            popSymbol(); // 弹出*
            popSymbol(); // 弹出T1
            pushSymbol(T); // 压入T
            break;
        case 5: // T → F
            popSymbol(); // 弹出F
            pushSymbol(T); // 压入T
            break;
        case 6: // F → (E)
            popSymbol(); // 弹出)
            popSymbol(); // 弹出E
            popSymbol(); // 弹出(
            pushSymbol(F); // 压入F
            break;
        case 7: // F → 1
            popSymbol(); // 弹出1
            pushSymbol(F); // 压入F
            break;
        case 8: // F → 2
            popSymbol(); // 弹出2
            pushSymbol(F); // 压入F
            break;
        case 9: // F → 3
            popSymbol(); // 弹出3
            pushSymbol(F); // 压入F
            break;
        case 10: // F → 4
            popSymbol(); // 弹出4
            pushSymbol(F); // 压入F
            break;
        case 11: // F → 5
            popSymbol(); // 弹出5
            pushSymbol(F); // 压入F
            break;
        default:
            printf("Error: invalid production\n");
            exit(1);
    }

    // 根据语法制导翻译法计算产生式的值
    switch (production) {
        case 2: // E → E1 + T
            symbolStack[stackTop].value = symbolStack[stackTop - 2].value + symbolStack[stackTop].value;
            break;
        case 4: // T → T1 * F
            symbolStack[stackTop].value = symbolStack[stackTop - 2].value * symbolStack[stackTop].value;
            break;
        case 6: // F → (E)
            symbolStack[stackTop].value = symbolStack[stackTop - 1].value;
            break;
        case 7: // F → 1
            symbolStack[stackTop].value = 1;
            break;
        case 8: // F → 2
            symbolStack[stackTop].value = 2;
            break;
        case 9: // F → 3
            symbolStack[stackTop].value = 3;
            break;
        case 10: // F → 4
            symbolStack[stackTop].value = 4;
            break;
        case 11: // F → 5
            symbolStack[stackTop].value = 5;
            break;
        default:
            break;
    }
}

// 进行LR分析
int parse() {
    pushState(0); // 初始状态为0
    Token token = getNextToken(); // 获取第一个Token

    while (1) {
        int state = getCurrentState();
        TokenType symbol = token.type;
        LRItem action = LRTable[state][symbol];

        if (action.state == -1) { // 发生错误
            printf("Error: invalid input\n");
            exit(1);
        } else if (action.state == reduce) { // 归约
            reduce(action.symbol);
        } else if (action.state == accept) { // 接受
            return symbolStack[stackTop].value;
        } else { // 移入
            pushState(action.state);
            pushSymbol(symbol);
            token = getNextToken();
        }
    }
}

int main() {
    printf("请输入算术表达式：");
    scanf("%s", input);

    int result = parse();

    printf("计算结果为：%d\n", result);

    return 0;
}
LR分析法和语法制导翻译法实现简单算术表达式求值

原文地址: https://www.cveoy.top/t/topic/fYrE 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录