← 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

Examples marked ⚑ show input the C++ program mishandles without an error.
Grammar (left recursion removed)
  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

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

          NameValue

          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.