← Compiler Front End for a Small Language
Compiler front-end walkthrough
Port of the lab program · output checked against the C++
Write a program in the lab's small language and watch my front end compile it: the lexer cuts it into tokens, the recursive-descent parser builds the syntax tree, and three-address code comes out with jump labels filled in by back-patching. The original C++ file sits beside it with the running lines highlighted.
Everything runs in your browser. The compiler is a TypeScript port of my lab program, function by function. For each example below the page also stores what the compiled C++ program printed, and section 3 compares the two. Section 4, which runs the generated code, was added for this page and is not part of the lab.
Write a program
Grammar (left recursion removed)
Program→StmtListStmtList→Stmt StmtList'StmtList'→; Stmt StmtList'StmtList'→εStmt→id = ExprStmt→if Bool then Stmt ElsePartStmt→while Bool do StmtStmt→begin StmtList endStmt→εElsePart→else StmtElsePart→εExpr→Term Expr'Expr'→+ Term Expr'Expr'→- Term Expr'Expr'→εTerm→Factor Term'Term'→* Factor Term'Term'→/ Factor Term'Term'→εFactor→idFactor→numFactor→( Expr )Bool→Expr relop Expr
relop is one of < > = <= >= <>. Numbers can be decimal, octal (017) or hexadecimal (0x1f). Statements are separated, not terminated, by ;.
Watch it compile
Input
Call stack
Productions
23.cpp · original file#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <string>
/* ============================================================
* 第一部分: 词法分析 (保持不变)
* ============================================================ */
#define IDN 1
#define DEC 2
#define OCT 3
#define HEX 4
#define ADD 5
#define SUB 6
#define MUL 7
#define DIV 8
#define GT 9
#define LT 10
#define EQ 11
#define GE 12
#define LE 13
#define NEQ 14
#define SLP 15
#define SRP 16
#define SEMI 17
#define IF 18
#define THEN 19
#define ELSE 20
#define WHILE 21
#define DO 22
#define BEGIN 23
#define END 24
#define ILOCT 25
#define ILHEX 26
#define ERROR -1
const char* token_names[] = {
"", "IDN", "DEC", "OCT", "HEX",
"ADD", "SUB", "MUL", "DIV", "GT",
"LT", "EQ", "GE", "LE", "NEQ",
"SLP", "SRP", "SEMI", "IF", "THEN",
"ELSE", "WHILE", "DO", "BEGIN", "END",
"ILOCT", "ILHEX"
};
const char* keywords[] = { "if", "then", "else", "while", "do", "begin", "end" };
const int keyword_tokens[] = { IF, THEN, ELSE, WHILE, DO, BEGIN, END };
#define KEYWORD_COUNT 7
char input_buf[100000];
int pos = 0;
int input_len = 0;
int cur_line = 1;
int cur_col = 1;
typedef struct {
int kind;
char str_val[256];
int int_val;
int has_int_val;
int line;
int col;
} Token;
char lex_peek(void) {
if (pos < input_len) return input_buf[pos];
return '\0';
}
char lex_advance(void) {
if (pos < input_len) {
char c = input_buf[pos++];
if (c == '\n') { cur_line++; cur_col = 1; }
else { cur_col++; }
return c;
}
return '\0';
}
void skip_whitespace(void) {
while (pos < input_len && (input_buf[pos] == ' ' || input_buf[pos] == '\t' ||
input_buf[pos] == '\n' || input_buf[pos] == '\r')) {
if (input_buf[pos] == '\n') { cur_line++; cur_col = 1; }
else { cur_col++; }
pos++;
}
}
int is_keyword(const char* str) {
for (int i = 0; i < KEYWORD_COUNT; i++) {
if (strcmp(str, keywords[i]) == 0) return keyword_tokens[i];
}
return -1;
}
int hex_char_val(char c) {
if (c >= '0' && c <= '9') return c - '0';
if (c >= 'a' && c <= 'f') return c - 'a' + 10;
if (c >= 'A' && c <= 'F') return c - 'A' + 10;
return -1;
}
Token lexical_analyze(void) {
Token token;
memset(&token, 0, sizeof(Token));
token.has_int_val = 0;
skip_whitespace();
token.line = cur_line;
token.col = cur_col;
if (pos >= input_len) { token.kind = 0; return token; }
char ch = lex_peek();
if (isalpha(ch)) {
int len = 0;
while (pos < input_len && (isalpha(input_buf[pos]) || isdigit(input_buf[pos]))) {
token.str_val[len++] = input_buf[pos]; lex_advance();
}
token.str_val[len] = '\0';
int kw = is_keyword(token.str_val);
if (kw != -1) token.kind = kw;
else token.kind = IDN;
return token;
}
if (isdigit(ch)) {
if (ch == '0') {
lex_advance();
char next = lex_peek();
if (next == 'x' || next == 'X') {
lex_advance();
char buf[256]; int len = 0; int illegal = 0;
while (pos < input_len && isalnum(input_buf[pos])) {
char c = input_buf[pos];
if (!((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'))) illegal = 1;
buf[len++] = c; lex_advance();
}
buf[len] = '\0';
if (len == 0) { token.kind = ILHEX; return token; }
if (illegal) { token.kind = ILHEX; }
else {
token.kind = HEX; int val = 0;
for (int i = 0; i < len; i++) val = val * 16 + hex_char_val(buf[i]);
token.int_val = val; token.has_int_val = 1;
}
return token;
}
if (next >= '0' && next <= '9') {
char buf[256]; int len = 0; int illegal = 0;
while (pos < input_len && (input_buf[pos] >= '0' && input_buf[pos] <= '9')) {
if (input_buf[pos] == '8' || input_buf[pos] == '9') illegal = 1;
buf[len++] = input_buf[pos]; lex_advance();
}
buf[len] = '\0';
if (illegal) token.kind = ILOCT;
else {
token.kind = OCT; int val = 0;
for (int i = 0; i < len; i++) val = val * 8 + (buf[i] - '0');
token.int_val = val; token.has_int_val = 1;
}
return token;
}
token.kind = DEC; token.int_val = 0; token.has_int_val = 1;
return token;
}
{
int val = 0;
while (pos < input_len && isdigit(input_buf[pos])) {
val = val * 10 + (input_buf[pos] - '0'); lex_advance();
}
token.kind = DEC; token.int_val = val; token.has_int_val = 1;
return token;
}
}
switch (ch) {
case '+': lex_advance(); token.kind = ADD; return token;
case '-': lex_advance(); token.kind = SUB; return token;
case '*': lex_advance(); token.kind = MUL; return token;
case '/': lex_advance(); token.kind = DIV; return token;
case '=': lex_advance(); token.kind = EQ; return token;
case '(': lex_advance(); token.kind = SLP; return token;
case ')': lex_advance(); token.kind = SRP; return token;
case ';': lex_advance(); token.kind = SEMI; return token;
case '>':
lex_advance();
if (lex_peek() == '=') { lex_advance(); token.kind = GE; }
else token.kind = GT;
return token;
case '<':
lex_advance();
if (lex_peek() == '=') { lex_advance(); token.kind = LE; }
else if (lex_peek() == '>') { lex_advance(); token.kind = NEQ; }
else token.kind = LT;
return token;
default:
lex_advance(); token.kind = ERROR;
token.str_val[0] = ch; token.str_val[1] = '\0';
return token;
}
}
void print_token(Token t) {
if (t.kind == 0) return;
if (t.kind == ERROR) { printf(" ERROR: '%s'\n", t.str_val); return; }
const char* name = (t.kind >= 1 && t.kind <= 26) ? token_names[t.kind] : "UNKNOWN";
if (t.kind == IDN) printf(" (%s, %s)\n", name, t.str_val);
else if (t.has_int_val) printf(" (%s, %d)\n", name, t.int_val);
else printf(" (%s, -)\n", name);
}
/* ============================================================
* 第二部分: 预扫描
* ============================================================ */
std::vector<Token> token_list;
int tok_pos = 0;
void prescan(void) {
token_list.clear();
pos = 0; cur_line = 1; cur_col = 1;
while (1) {
Token t = lexical_analyze();
if (t.kind == 0) break;
token_list.push_back(t);
}
tok_pos = 0;
}
/* ============================================================
* 第三部分: 语法树节点 + 打印
* ============================================================ */
struct TreeNode {
std::string label;
std::vector<TreeNode*> children;
TreeNode(const std::string& l) : label(l) {}
void add(TreeNode* c) { if (c) children.push_back(c); }
};
struct ExprRet {
std::string val;
TreeNode* node;
};
void print_tree(TreeNode* n, const std::string& prefix, bool isLast) {
if (!n) return;
printf("%s%s%s\n", prefix.c_str(),
isLast ? "└── " : "├── ",
n->label.c_str());
std::string np = prefix + (isLast ? " " : "│ ");
for (size_t i = 0; i < n->children.size(); i++)
print_tree(n->children[i], np, i == n->children.size() - 1);
}
void print_tree_root(TreeNode* n) {
if (!n) return;
printf(" %s\n", n->label.c_str());
for (size_t i = 0; i < n->children.size(); i++)
print_tree(n->children[i], " ", i == n->children.size() - 1);
}
/* ============================================================
* 第四部分: 语法分析 + 三地址代码 + 语法树 + ★产生式序列★
*
* 消除左递归后的文法:
* (1) Program → StmtList
* (2) StmtList → Stmt StmtList'
* (3) StmtList' → ; Stmt StmtList'
* (4) StmtList' → ε
* (5) Stmt → id = Expr
* (6) Stmt → if Bool then Stmt ElsePart
* (7) Stmt → while Bool do Stmt
* (8) Stmt → begin StmtList end
* (9) Stmt → ε
* (10) ElsePart → else Stmt
* (11) ElsePart → ε
* (12) Expr → Term Expr'
* (13) Expr' → + Term Expr'
* (14) Expr' → - Term Expr'
* (15) Expr' → ε
* (16) Term → Factor Term'
* (17) Term' → * Factor Term'
* (18) Term' → / Factor Term'
* (19) Term' → ε
* (20) Factor → id
* (21) Factor → num
* (22) Factor → ( Expr )
* (23) Bool → Expr relop Expr
* ============================================================ */
/* ★ 产生式序列:按最左派生顺序记录 ★ */
std::vector<std::string> productions;
std::vector<std::string> tac_code;
std::vector<std::string> errors;
int temp_count = 0;
int label_count = 0;
std::string new_temp(void) {
char buf[32]; sprintf(buf, "t%d", ++temp_count);
return std::string(buf);
}
std::string new_label(void) {
char buf[32]; sprintf(buf, "L%d", label_count++);
return std::string(buf);
}
void emit(const std::string& code) { tac_code.push_back(code); }
/* ★ 记录一条产生式 ★ */
void record_production(const std::string& prod) {
productions.push_back(prod);
}
Token cur_token(void) {
if (tok_pos < (int)token_list.size()) return token_list[tok_pos];
Token eof; memset(&eof, 0, sizeof(Token)); eof.kind = 0;
eof.line = cur_line; eof.col = cur_col;
return eof;
}
void next_token(void) {
if (tok_pos < (int)token_list.size()) tok_pos++;
}
std::string token_repr(Token t) {
if (t.kind == 0) return "EOF";
if (t.kind == IDN) return std::string(t.str_val);
if (t.has_int_val) { char buf[64]; sprintf(buf, "%d", t.int_val); return std::string(buf); }
if (t.kind >= 1 && t.kind <= 26) return std::string(token_names[t.kind]);
return "?";
}
void report_error(const char* expected, Token t) {
char buf[512];
sprintf(buf, "Syntax Error at line %d, col %d: expected '%s', got '%s'",
t.line, t.col, expected, token_repr(t).c_str());
errors.push_back(std::string(buf));
}
void match(int expected_kind, const char* expected_name) {
Token t = cur_token();
if (t.kind == expected_kind) next_token();
else report_error(expected_name, t);
}
/* ---- 前置声明 ---- */
ExprRet parse_Expr(void);
ExprRet parse_ExprPrime(ExprRet left);
ExprRet parse_Term(void);
ExprRet parse_TermPrime(ExprRet left);
ExprRet parse_Factor(void);
TreeNode* parse_Bool(std::string& bl, std::string& bo, std::string& br);
TreeNode* parse_Stmt(void);
TreeNode* parse_Stmt_full(const std::string& next_label, const std::string& begin_label);
TreeNode* parse_ElsePart(TreeNode* bool_tree, TreeNode* then_tree,
const std::string& next_label);
TreeNode* parse_StmtList(void);
void parse_StmtListPrime(TreeNode* parent);
TreeNode* parse_Program(void);
std::string relop_str(int kind) {
switch (kind) {
case GT: return ">"; case LT: return "<"; case EQ: return "=";
case GE: return ">="; case LE: return "<="; case NEQ: return "<>";
default: return "?";
}
}
int is_relop(int kind) {
return kind == GT || kind == LT || kind == EQ || kind == GE || kind == LE || kind == NEQ;
}
/* ============================================================
* 各递归子程序函数
* ============================================================ */
/*
* Factor → id (20)
* Factor → num (21)
* Factor → ( Expr ) (22)
*/
ExprRet parse_Factor(void) {
Token t = cur_token();
ExprRet ret;
if (t.kind == IDN) {
record_production("Factor -> id"); // (20)
next_token();
ret.val = std::string(t.str_val);
ret.node = new TreeNode("Factor");
ret.node->add(new TreeNode(ret.val));
}
else if (t.kind == DEC || t.kind == OCT || t.kind == HEX) {
record_production("Factor -> num"); // (21)
next_token();
char buf[64]; sprintf(buf, "%d", t.int_val);
ret.val = std::string(buf);
ret.node = new TreeNode("Factor");
ret.node->add(new TreeNode(ret.val));
}
else if (t.kind == SLP) {
record_production("Factor -> ( Expr )"); // (22)
next_token();
ret = parse_Expr();
match(SRP, ")");
/* 把 Expr 子树包在 Factor 节点下 */
TreeNode* fn = new TreeNode("Factor");
fn->add(new TreeNode("("));
fn->add(ret.node);
fn->add(new TreeNode(")"));
ret.node = fn;
}
else {
report_error("id/num/(", t);
next_token();
ret.val = "?";
ret.node = new TreeNode("Factor(error)");
}
return ret;
}
/*
* Term' → * Factor Term' (17)
* Term' → / Factor Term' (18)
* Term' → ε (19)
*/
ExprRet parse_TermPrime(ExprRet left) {
Token t = cur_token();
if (t.kind == MUL) {
record_production("Term' -> * Factor Term'"); // (17)
next_token();
ExprRet right = parse_Factor();
std::string tmp = new_temp();
emit(tmp + " = " + left.val + " * " + right.val);
TreeNode* n = new TreeNode("Term'");
n->add(new TreeNode("*"));
n->add(right.node);
ExprRet combined;
combined.val = tmp;
/* 递归调用,继续收集 */
ExprRet rest = parse_TermPrime(combined);
n->add(rest.node); /* rest.node 是下一层 Term' 的树 */
/* 但我们需要正确构建树;这里把整个 Term' 链作为节点 */
rest.node = n;
return rest;
}
else if (t.kind == DIV) {
record_production("Term' -> / Factor Term'"); // (18)
next_token();
ExprRet right = parse_Factor();
std::string tmp = new_temp();
emit(tmp + " = " + left.val + " / " + right.val);
TreeNode* n = new TreeNode("Term'");
n->add(new TreeNode("/"));
n->add(right.node);
ExprRet combined;
combined.val = tmp;
ExprRet rest = parse_TermPrime(combined);
n->add(rest.node);
rest.node = n;
return rest;
}
else {
record_production("Term' -> epsilon"); // (19)
ExprRet ret;
ret.val = left.val;
ret.node = new TreeNode("Term'(ε)");
return ret;
}
}
/*
* Term → Factor Term' (16)
*/
ExprRet parse_Term(void) {
record_production("Term -> Factor Term'"); // (16)
ExprRet left = parse_Factor();
ExprRet result = parse_TermPrime(left);
TreeNode* n = new TreeNode("Term");
n->add(left.node);
n->add(result.node);
result.node = n;
return result;
}
/*
* Expr' → + Term Expr' (13)
* Expr' → - Term Expr' (14)
* Expr' → ε (15)
*/
ExprRet parse_ExprPrime(ExprRet left) {
Token t = cur_token();
if (t.kind == ADD) {
record_production("Expr' -> + Term Expr'"); // (13)
next_token();
ExprRet right = parse_Term();
std::string tmp = new_temp();
emit(tmp + " = " + left.val + " + " + right.val);
TreeNode* n = new TreeNode("Expr'");
n->add(new TreeNode("+"));
n->add(right.node);
ExprRet combined;
combined.val = tmp;
ExprRet rest = parse_ExprPrime(combined);
n->add(rest.node);
rest.node = n;
return rest;
}
else if (t.kind == SUB) {
record_production("Expr' -> - Term Expr'"); // (14)
next_token();
ExprRet right = parse_Term();
std::string tmp = new_temp();
emit(tmp + " = " + left.val + " - " + right.val);
TreeNode* n = new TreeNode("Expr'");
n->add(new TreeNode("-"));
n->add(right.node);
ExprRet combined;
combined.val = tmp;
ExprRet rest = parse_ExprPrime(combined);
n->add(rest.node);
rest.node = n;
return rest;
}
else {
record_production("Expr' -> epsilon"); // (15)
ExprRet ret;
ret.val = left.val;
ret.node = new TreeNode("Expr'(ε)");
return ret;
}
}
/*
* Expr → Term Expr' (12)
*/
ExprRet parse_Expr(void) {
record_production("Expr -> Term Expr'"); // (12)
ExprRet left = parse_Term();
ExprRet result = parse_ExprPrime(left);
TreeNode* n = new TreeNode("Expr");
n->add(left.node);
n->add(result.node);
result.node = n;
return result;
}
/*
* Bool → Expr relop Expr (23)
*/
TreeNode* parse_Bool(std::string& bl, std::string& bo, std::string& br) {
record_production("Bool -> Expr relop Expr"); // (23)
ExprRet left = parse_Expr();
bl = left.val;
Token t = cur_token();
if (is_relop(t.kind)) {
bo = relop_str(t.kind);
next_token();
}
else {
report_error("relational operator", t);
bo = "?";
}
ExprRet right = parse_Expr();
br = right.val;
TreeNode* n = new TreeNode("Bool");
n->add(left.node);
n->add(new TreeNode(bo));
n->add(right.node);
return n;
}
/*
* Stmt → id = Expr (5)
* Stmt → if Bool then Stmt ElsePart (6)
* Stmt → while Bool do Stmt (7)
* Stmt → begin StmtList end (8)
* Stmt → ε (9)
*/
TreeNode* parse_Stmt_full(const std::string& next_label, const std::string& begin_label) {
Token t = cur_token();
/* ---- 赋值 id = Expr ---- */
if (t.kind == IDN) {
record_production("Stmt -> id = Expr"); // (5)
std::string id_name(t.str_val);
next_token();
match(EQ, "=");
ExprRet expr = parse_Expr();
emit(id_name + " = " + expr.val);
TreeNode* n = new TreeNode("Stmt");
n->add(new TreeNode(id_name));
n->add(new TreeNode("="));
n->add(expr.node);
return n;
}
/* ---- WHILE ---- */
if (t.kind == WHILE) {
record_production("Stmt -> while Bool do Stmt"); // (7)
next_token();
std::string L_begin;
if (!begin_label.empty()) { L_begin = begin_label; }
else { L_begin = new_label(); emit(L_begin + ":"); }
std::string L_body = new_label();
std::string bl, bo, br;
TreeNode* bool_tree = parse_Bool(bl, bo, br);
match(DO, "do");
emit("if " + bl + " " + bo + " " + br + " goto " + L_body);
int end_idx = (int)tac_code.size();
emit("goto __PLACEHOLDER__");
emit(L_body + ":");
TreeNode* body_tree = parse_Stmt_full(L_begin, "");
emit("goto " + L_begin);
if (!next_label.empty()) {
tac_code[end_idx] = "goto " + next_label;
}
else {
std::string L_end = new_label();
tac_code[end_idx] = "goto " + L_end;
emit(L_end + ":");
}
TreeNode* n = new TreeNode("Stmt");
n->add(new TreeNode("while"));
n->add(bool_tree);
n->add(new TreeNode("do"));
n->add(body_tree);
return n;
}
/* ---- IF ---- */
if (t.kind == IF) {
record_production("Stmt -> if Bool then Stmt ElsePart"); // (6)
next_token();
std::string bl, bo, br;
TreeNode* bool_tree = parse_Bool(bl, bo, br);
match(THEN, "then");
std::string L_true = new_label();
emit("if " + bl + " " + bo + " " + br + " goto " + L_true);
int false_idx = (int)tac_code.size();
emit("goto __PLACEHOLDER__");
emit(L_true + ":");
TreeNode* then_tree = parse_Stmt_full(next_label, L_true);
/* 处理 ElsePart */
Token nx = cur_token();
if (nx.kind == ELSE) {
record_production("ElsePart -> else Stmt"); // (10)
next_token();
std::string L_false = new_label();
tac_code[false_idx] = "goto " + L_false;
int end_goto_idx = -1;
if (!next_label.empty()) { emit("goto " + next_label); }
else { end_goto_idx = (int)tac_code.size(); emit("goto __PLACEHOLDER__"); }
emit(L_false + ":");
TreeNode* else_tree = parse_Stmt_full(next_label, "");
if (end_goto_idx >= 0) {
std::string L_end = new_label();
tac_code[end_goto_idx] = "goto " + L_end;
emit(L_end + ":");
}
TreeNode* n = new TreeNode("Stmt");
n->add(new TreeNode("if"));
n->add(bool_tree);
n->add(new TreeNode("then"));
n->add(then_tree);
TreeNode* ep = new TreeNode("ElsePart");
ep->add(new TreeNode("else"));
ep->add(else_tree);
n->add(ep);
return n;
}
else {
record_production("ElsePart -> epsilon"); // (11)
if (!next_label.empty()) {
tac_code[false_idx] = "goto " + next_label;
}
else {
std::string L_false = new_label();
tac_code[false_idx] = "goto " + L_false;
emit(L_false + ":");
}
TreeNode* n = new TreeNode("Stmt");
n->add(new TreeNode("if"));
n->add(bool_tree);
n->add(new TreeNode("then"));
n->add(then_tree);
n->add(new TreeNode("ElsePart(ε)"));
return n;
}
}
/* ---- BEGIN-END ---- */
if (t.kind == BEGIN) {
record_production("Stmt -> begin StmtList end"); // (8)
next_token();
TreeNode* sl = parse_StmtList();
match(END, "end");
TreeNode* n = new TreeNode("Stmt");
n->add(new TreeNode("begin"));
n->add(sl);
n->add(new TreeNode("end"));
return n;
}
/* ---- 空语句 ---- */
if (t.kind == 0 || t.kind == END || t.kind == ELSE || t.kind == SEMI) {
record_production("Stmt -> epsilon"); // (9)
return new TreeNode("Stmt(ε)");
}
report_error("statement (id, if, while, begin)", t);
next_token();
return new TreeNode("Stmt(error)");
}
TreeNode* parse_Stmt(void) {
return parse_Stmt_full("", "");
}
/*
* StmtList' → ; Stmt StmtList' (3)
* StmtList' → ε (4)
*/
void parse_StmtListPrime(TreeNode* parent) {
if (cur_token().kind == SEMI) {
record_production("StmtList' -> ; Stmt StmtList'"); // (3)
next_token();
TreeNode* s = parse_Stmt();
parent->add(s);
parse_StmtListPrime(parent);
}
else {
record_production("StmtList' -> epsilon"); // (4)
/* ε,不做任何事 */
}
}
/*
* StmtList → Stmt StmtList' (2)
*/
TreeNode* parse_StmtList(void) {
record_production("StmtList -> Stmt StmtList'"); // (2)
TreeNode* n = new TreeNode("StmtList");
TreeNode* s = parse_Stmt();
n->add(s);
parse_StmtListPrime(n);
return n;
}
/*
* Program → StmtList (1)
*/
TreeNode* parse_Program(void) {
record_production("Program -> StmtList"); // (1)
TreeNode* n = new TreeNode("Program");
n->add(parse_StmtList());
return n;
}
/* ============================================================
* 主程序
* ============================================================ */
int main(void) {
int c;
input_len = 0;
while ((c = getchar()) != EOF && input_len < (int)sizeof(input_buf) - 1) {
input_buf[input_len++] = (char)c;
}
input_buf[input_len] = '\0';
prescan();
printf("===== Token 序列 =====\n");
for (int i = 0; i < (int)token_list.size(); i++) print_token(token_list[i]);
printf("\n");
temp_count = 0;
label_count = 0;
tok_pos = 0;
tac_code.clear();
errors.clear();
productions.clear();
TreeNode* tree = parse_Program();
/* ★ 输出最左派生的产生式序列 ★ */
printf("===== 最左派生 产生式序列 =====\n");
for (int i = 0; i < (int)productions.size(); i++) {
printf(" (%d) %s\n", i + 1, productions[i].c_str());
}
printf("\n");
/* 输出语法树 */
printf("===== 语法树 =====\n");
print_tree_root(tree);
printf("\n");
printf("===== 三地址代码 =====\n");
for (int i = 0; i < (int)tac_code.size(); i++) {
printf(" %s\n", tac_code[i].c_str());
}
printf("\n");
if (!errors.empty()) {
printf("===== 错误 =====\n");
for (int i = 0; i < (int)errors.size(); i++)
printf(" %s\n", errors[i].c_str());
}
return 0;
}Syntax tree
non-terminal token ε error
Three-address code
Program output
This is exactly what the program writes to the console, Chinese section headings included.
Run the three-address code
Added for this page: a small interpreter executes the generated code with 32-bit integers, as C would. Give the variables starting values, then step through the jumps.
Code
Variables
| Name | Value |
|---|
What is original and how it was checked
- The lexer, parser, tree, production record and three-address code follow
23.cpp(Project2 of my compiler lab) function by function. The highlighted lines are the original file, re-encoded from GBK to UTF-8. - I compiled the C++ with g++ and fed the same 4,020 programs to both versions: valid programs, programs with random edits, and random characters. The outputs were identical byte for byte. The stored outputs for the examples above came from that binary.
- The replay order, call stack and node timing come from extra bookkeeping in the port; they do not change the result.
- The interpreter in section 4 is new. On 1,903 random valid programs, running the generated code gave the same variable values as evaluating the source directly.
- Input is limited to 4,000 characters here. Non-ASCII characters become one error token per UTF-8 byte, as in the C++ program; this page shows those bytes as
\xHH.