实现一个简单的编程语言的语法制导翻译和中间代码生成

补充后的文法：

𝑉𝑡 = {+, −,∗,/, , , (, ),[,], 𝑓, 𝑋} 𝑉𝑛 = {S, A, E, T, F, P, Q}

G[S]: S → f[A] = E A → X | A, X X → 𝑥 E → E + T | E − T | T T → T ∗ F | T / F | F F → (E) | 𝑋 P → (E) Q → P | 𝑋 | 𝑥

SLR(1)分析表：

状态 𝑋 𝑥 + - * / ( ) [ ] 𝑓 $ A E F P Q S T 0 s8 s9 s10 s11 s12 s13 s14 s15 s16 s7 1 2 3 4 1 r1 2 s17 s18 s19 s20 s21 s22 s23 s24 s25 5 6 7 3 r3 4 r5 5 r2 6 r6 7 s26 8 r7 9 r8 10 s27 s28 s29 s30 s31 16 17 18 11 s32 s33 s34 s35 s36 12 13 14 12 r9 13 r10 14 r11 15 r12 16 s37 s38 s39 21 22 23 17 r13 18 r14 19 r15 20 r16 21 r17 22 s40 23 r18 24 r19 25 r20 26 r4 27 s41 28 s42 29 s43 30 s44 31 s45 32 r23 33 r24 34 r25 35 r26 36 r27 37 s46 38 s47 39 s48 40 s49 41 s50 42 r12 43 r13 44 r14 45 r15 46 r21 47 r22 48 r28 49 r29 50 r30

C++代码实现：（省略了一些辅助函数的实现）

#include #include #include #include #include

using namespace std;

enum TokenType { ADD, SUB, MUL, DIV, LPAR, RPAR, LBRACKET, RBRACKET, COMMA, ID, EQUAL, END, ERROR };

struct Token { TokenType type; string value; };

struct Quad { string op; string arg1; string arg2; string result; };

vector lexer(string input); int getPrecedence(TokenType op); vector generator(vector tokens); void printQuads(vector quads);

vector lexer(string input) { vector tokens; string buffer = ''; for (char ch : input) { if (ch == ' ') { continue; } if (ch == '+') { tokens.push_back({ADD, '+'}); } else if (ch == '-') { tokens.push_back({SUB, '-'}); } else if (ch == '') { tokens.push_back({MUL, ''}); } else if (ch == '/') { tokens.push_back({DIV, '/'}); } else if (ch == '(') { tokens.push_back({LPAR, '('}); } else if (ch == ')') { tokens.push_back({RPAR, ')'}); } else if (ch == '[') { tokens.push_back({LBRACKET, '['}); } else if (ch == ']') { tokens.push_back({RBRACKET, ']'}); } else if (ch == ',') { tokens.push_back({COMMA, ','}); } else if (ch == '=') { tokens.push_back({EQUAL, '='}); } else if (islower(ch)) { buffer += ch; } else { tokens.push_back({ERROR, 'Invalid character'}); return tokens; } } if (!buffer.empty()) { tokens.push_back({ID, buffer}); } tokens.push_back({END, '$'}); return tokens; }

int getPrecedence(TokenType op) { if (op == MUL || op == DIV) { return 2; } else if (op == ADD || op == SUB) { return 1; } else { return 0; } }

vector generator(vector tokens) { vector quads; stack opStack; stack valStack; map<string, int> argMap; int argCount = 0; for (Token token : tokens) { if (token.type == ID) { valStack.push(token); } else if (token.type == ADD || token.type == SUB || token.type == MUL || token.type == DIV) { while (!opStack.empty() && getPrecedence(opStack.top().type) >= getPrecedence(token.type)) { Token opToken = opStack.top(); opStack.pop(); Token arg2Token = valStack.top(); valStack.pop(); Token arg1Token = valStack.top(); valStack.pop(); string arg1 = arg1Token.value; string arg2 = arg2Token.value; string result = 'T' + to_string(quads.size() + 1); if (argMap.count(arg1) == 0) { quads.push_back({'DEF_ARG', arg1, '', ''}); argMap[arg1] = argCount++; } if (argMap.count(arg2) == 0) { quads.push_back({'DEF_ARG', arg2, '', ''}); argMap[arg2] = argCount++; } quads.push_back({opToken.value, arg1, arg2, result}); valStack.push({ID, result}); } opStack.push(token); } else if (token.type == LPAR) { opStack.push(token); } else if (token.type == RPAR) { while (!opStack.empty() && opStack.top().type != LPAR) { Token opToken = opStack.top(); opStack.pop(); Token arg2Token = valStack.top(); valStack.pop(); Token arg1Token = valStack.top(); valStack.pop(); string arg1 = arg1Token.value; string arg2 = arg2Token.value; string result = 'T' + to_string(quads.size() + 1); if (argMap.count(arg1) == 0) { quads.push_back({'DEF_ARG', arg1, '', ''}); argMap[arg1] = argCount++; } if (argMap.count(arg2) == 0) { quads.push_back({'DEF_ARG', arg2, '', ''}); argMap[arg2] = argCount++; } quads.push_back({opToken.value, arg1, arg2, result}); valStack.push({ID, result}); } opStack.pop(); } else if (token.type == LBRACKET) { while (!opStack.empty() && opStack.top().type != LBRACKET) { Token opToken = opStack.top(); opStack.pop(); Token argToken = valStack.top(); valStack.pop(); string arg = argToken.value; string result = 'T' + to_string(quads.size() + 1); if (argMap.count(arg) == 0) { quads.push_back({'DEF_ARG', arg, '', ''}); argMap[arg] = argCount++; } quads.push_back({opToken.value, arg, '', result}); valStack.push({ID, result}); } opStack.pop(); } else if (token.type == COMMA) { while (!opStack.empty() && opStack.top().type != LBRACKET) { Token opToken = opStack.top(); opStack.pop(); Token arg2Token = valStack.top(); valStack.pop(); Token arg1Token = valStack.top(); valStack.pop(); string arg1 = arg1Token.value; string arg2 = arg2Token.value; string result = 'T' + to_string(quads.size() + 1); if (argMap.count(arg1) == 0) { quads.push_back({'DEF_ARG', arg1, '', ''}); argMap[arg1] = argCount++; } if (argMap.count(arg2) == 0) { quads.push_back({'DEF_ARG', arg2, '', ''}); argMap[arg2] = argCount++; } quads.push_back({opToken.value, arg1, arg2, result}); valStack.push({ID, result}); } } else if (token.type == EQUAL) { while (!opStack.empty()) { Token opToken = opStack.top(); opStack.pop(); Token arg2Token = valStack.top(); valStack.pop(); Token arg1Token = valStack.top(); valStack.pop(); string arg1 = arg1Token.value; string arg2 = arg2Token.value; string result = 'T' + to_string(quads.size() + 1); if (argMap.count(arg1) == 0) { quads.push_back({'DEF_ARG', arg1, '', ''}); argMap[arg1] = argCount++; } if (argMap.count(arg2) == 0) { quads.push_back({'DEF_ARG', arg2, '', ''}); argMap[arg2] = argCount++; } quads.push_back({opToken.value, arg1, arg2, result}); valStack.push({ID, result}); } string result = valStack.top().value; quads.push_back({'DEF_FUNC', 'f', '', ''}); while (!valStack.empty()) { string arg = valStack.top().value; valStack.pop(); if (argMap.count(arg) == 0) { quads.push_back({'DEF_ARG', arg, '', ''}); argMap[arg] = argCount++; } quads.push_back({'ASSIGN', arg, '', argMap[arg] == 0 ? 'R' : 'T' + to_string(argMap[arg])}); } quads.push_back({'END_FUNC', '', '', ''}); quads.push_back({'ASSIGN', result, '', 'R'}); } else if (token.type == END) { while (!opStack.empty()) { Token opToken = opStack.top(); opStack.pop(); Token arg2Token = valStack.top(); valStack.pop(); Token arg1Token = valStack.top(); valStack.pop(); string arg1 = arg1Token.value; string arg2 = arg2Token.value; string result = 'T' + to_string(quads.size() + 1); if (argMap.count(arg1) == 0) { quads.push_back({'DEF_ARG', arg1, '', ''}); argMap[arg1] = argCount++; } if (argMap.count(arg2) == 0) { quads.push_back({'DEF_ARG', arg2, '', ''}); argMap[arg2] = argCount++; } quads.push_back({opToken.value, arg1, arg2, result}); valStack.push({ID, result}); } } else { quads.push_back({'ERROR', 'Invalid token', '', ''}); return quads; } } return quads; }

void printQuads(vector quads) { for (Quad quad : quads) { cout << '(' << quad.op << ', ' << quad.arg1 << ', ' << quad.arg2 << ', ' << quad.result << ')' << endl; } }

int main() { string input; getline(cin, input); vector tokens = lexer(input); vector quads = generator(tokens); printQuads(quads); return 0;