コンパイラ & インタプリタ設計完全ガイド2025：Lexer、Parser、AST、コード生成

ソースコード -> コンパイレーションパイプライン：

┌──────────┐    ┌──────────┐    ┌──────────┐
│  Source   │───>│  Lexer   │───>│  Parser  │
│  Code     │    │(Tokenizer)│    │          │
└──────────┘    └──────────┘    └──────────┘
                                      │
                                      v
┌──────────┐    ┌──────────┐    ┌──────────┐
│  Code    │<───│Optimizer │<───│ Semantic │
│Generator │    │          │    │ Analysis │
└──────────┘    └──────────┘    └──────────┘
      │
      v
┌──────────┐
│ Target   │
│ Code     │
└──────────┘

各段階の役割：
1. Lexer：ソースコード -> トークンストリーム
2. Parser：トークンストリーム -> AST（抽象構文木）
3. Semantic Analysis：型検査、スコープ解決
4. Optimizer：IRレベルでの最適化
5. Code Generator：ターゲットコード生成（機械語、バイトコード、WASM等）

// トークン型列挙
enum TokenType {
  // リテラル
  Number = 'Number',
  String = 'String',
  Boolean = 'Boolean',

  // 識別子 & キーワード
  Identifier = 'Identifier',
  Let = 'Let',
  Const = 'Const',
  Function = 'Function',
  If = 'If',
  Else = 'Else',
  Return = 'Return',
  While = 'While',
  For = 'For',

  // 演算子
  Plus = 'Plus',           // +
  Minus = 'Minus',         // -
  Star = 'Star',           // *
  Slash = 'Slash',         // /
  Percent = 'Percent',     // %
  Assign = 'Assign',       // =
  Equal = 'Equal',         // ==
  NotEqual = 'NotEqual',   // !=
  LessThan = 'LessThan',  // <
  GreaterThan = 'GreaterThan', // >
  And = 'And',             // &&
  Or = 'Or',               // ||
  Not = 'Not',             // !

  // 区切り文字
  LeftParen = 'LeftParen',     // (
  RightParen = 'RightParen',   // )
  LeftBrace = 'LeftBrace',     // { （コードブロック内のみ）
  RightBrace = 'RightBrace',   // } （コードブロック内のみ）
  LeftBracket = 'LeftBracket', // [
  RightBracket = 'RightBracket', // ]
  Comma = 'Comma',
  Semicolon = 'Semicolon',
  Colon = 'Colon',
  Dot = 'Dot',
  Arrow = 'Arrow',         // =>

  // 特殊
  EOF = 'EOF',
}

// トークンインターフェース
interface Token {
  type: TokenType;
  value: string;
  line: number;
  column: number;
}

class Lexer {
  private source: string;
  private pos: number = 0;
  private line: number = 1;
  private column: number = 1;
  private tokens: Token[] = [];

  // キーワードマップ
  private static keywords: Map<string, TokenType> = new Map([
    ['let', TokenType.Let],
    ['const', TokenType.Const],
    ['function', TokenType.Function],
    ['if', TokenType.If],
    ['else', TokenType.Else],
    ['return', TokenType.Return],
    ['while', TokenType.While],
    ['for', TokenType.For],
    ['true', TokenType.Boolean],
    ['false', TokenType.Boolean],
  ]);

  constructor(source: string) {
    this.source = source;
  }

  tokenize(): Token[] {
    while (this.pos < this.source.length) {
      this.skipWhitespace();
      this.skipComments();

      if (this.pos >= this.source.length) break;

      const char = this.source[this.pos];

      if (this.isDigit(char)) {
        this.readNumber();
      } else if (this.isAlpha(char) || char === '_') {
        this.readIdentifier();
      } else if (char === '"' || char === "'") {
        this.readString(char);
      } else {
        this.readOperator();
      }
    }

    this.tokens.push(this.makeToken(TokenType.EOF, ''));
    return this.tokens;
  }

  private readNumber(): void {
    const start = this.pos;

    while (this.pos < this.source.length && this.isDigit(this.current())) {
      this.advance();
    }

    // 小数点処理
    if (this.current() === '.' && this.isDigit(this.peek())) {
      this.advance();
      while (this.pos < this.source.length && this.isDigit(this.current())) {
        this.advance();
      }
    }

    const value = this.source.slice(start, this.pos);
    this.tokens.push(this.makeToken(TokenType.Number, value));
  }

  private readIdentifier(): void {
    const start = this.pos;

    while (
      this.pos < this.source.length &&
      (this.isAlphaNumeric(this.current()) || this.current() === '_')
    ) {
      this.advance();
    }

    const value = this.source.slice(start, this.pos);
    const type = Lexer.keywords.get(value) || TokenType.Identifier;
    this.tokens.push(this.makeToken(type, value));
  }

  private readString(quote: string): void {
    this.advance(); // 開始引用符をスキップ
    let value = '';

    while (this.pos < this.source.length && this.current() !== quote) {
      if (this.current() === '\\') {
        this.advance();
        switch (this.current()) {
          case 'n': value += '\n'; break;
          case 't': value += '\t'; break;
          case '\\': value += '\\'; break;
          default: value += this.current();
        }
      } else {
        value += this.current();
      }
      this.advance();
    }

    if (this.current() !== quote) {
      throw new Error('Unterminated string at line ' + this.line);
    }
    this.advance(); // 閉じ引用符をスキップ

    this.tokens.push(this.makeToken(TokenType.String, value));
  }

  // ユーティリティメソッド
  private current(): string { return this.source[this.pos]; }
  private peek(): string { return this.source[this.pos + 1]; }
  private advance(): void {
    if (this.current() === '\n') {
      this.line++;
      this.column = 1;
    } else {
      this.column++;
    }
    this.pos++;
  }
  private isDigit(c: string): boolean { return /[0-9]/.test(c); }
  private isAlpha(c: string): boolean { return /[a-zA-Z_]/.test(c); }
  private isAlphaNumeric(c: string): boolean { return /[a-zA-Z0-9_]/.test(c); }
  private skipWhitespace(): void {
    while (this.pos < this.source.length && /\s/.test(this.current())) {
      this.advance();
    }
  }
  private skipComments(): void {
    if (this.current() === '/' && this.peek() === '/') {
      while (this.pos < this.source.length && this.current() !== '\n') {
        this.advance();
      }
    }
  }
  private makeToken(type: TokenType, value: string): Token {
    return { type, value, line: this.line, column: this.column };
  }
}

// エラー回復が可能なLexer
class RobustLexer extends Lexer {
  private errors: LexerError[] = [];

  tokenize(): Token[] {
    while (this.pos < this.source.length) {
      try {
        this.skipWhitespace();
        if (this.pos >= this.source.length) break;
        // ... 通常のトークン化ロジック
      } catch (error) {
        // エラーを記録して次の有効な位置に移動
        this.errors.push({
          message: error.message,
          line: this.line,
          column: this.column,
        });
        this.synchronize();
      }
    }
    return this.tokens;
  }

  private synchronize(): void {
    // 次の空白または区切り文字までスキップ
    while (
      this.pos < this.source.length &&
      !/[\s;,(){}[\]]/.test(this.current())
    ) {
      this.advance();
    }
  }
}

パーサー型比較：
┌────────────────────┬──────────┬──────────┬──────────────┐
│ 型                 │ 実装難度 │ 表現力   │ 代表ツール   │
├────────────────────┼──────────┼──────────┼──────────────┤
│ 再帰下降           │ 易しい   │ LL(k)    │ GCC, Go      │
│ Pratt Parser       │ 普通     │ 優先順位 │ V8, Rust     │
│ PEG                │ 普通     │ 無制限   │ pest, PEG.js │
│ Parser Combinator  │ 普通     │ 柔軟     │ nom, parsec  │
│ LR/LALR            │ 難しい   │ LR(1)    │ yacc, bison  │
│ Earley             │ 普通     │ 全CFG    │ nearley      │
└────────────────────┴──────────┴──────────┴──────────────┘

// AST ノード型定義
type ASTNode =
  | NumberLiteral
  | StringLiteral
  | BooleanLiteral
  | Identifier
  | BinaryExpression
  | UnaryExpression
  | CallExpression
  | VariableDeclaration
  | FunctionDeclaration
  | IfStatement
  | ReturnStatement
  | BlockStatement
  | Program;

interface NumberLiteral {
  type: 'NumberLiteral';
  value: number;
}

interface BinaryExpression {
  type: 'BinaryExpression';
  operator: string;
  left: ASTNode;
  right: ASTNode;
}

interface FunctionDeclaration {
  type: 'FunctionDeclaration';
  name: string;
  params: string[];
  body: BlockStatement;
}

interface Program {
  type: 'Program';
  body: ASTNode[];
}

// 再帰下降パーサー
class RecursiveDescentParser {
  private tokens: Token[];
  private pos: number = 0;

  constructor(tokens: Token[]) {
    this.tokens = tokens;
  }

  parse(): Program {
    const body: ASTNode[] = [];

    while (!this.isAtEnd()) {
      body.push(this.parseStatement());
    }

    return { type: 'Program', body };
  }

  private parseStatement(): ASTNode {
    const token = this.current();

    switch (token.type) {
      case TokenType.Let:
      case TokenType.Const:
        return this.parseVariableDeclaration();
      case TokenType.Function:
        return this.parseFunctionDeclaration();
      case TokenType.If:
        return this.parseIfStatement();
      case TokenType.Return:
        return this.parseReturnStatement();
      case TokenType.LeftBrace:
        return this.parseBlockStatement();
      default:
        return this.parseExpressionStatement();
    }
  }

  private parseFunctionDeclaration(): FunctionDeclaration {
    this.expect(TokenType.Function);
    const name = this.expect(TokenType.Identifier).value;

    this.expect(TokenType.LeftParen);
    const params: string[] = [];

    if (!this.check(TokenType.RightParen)) {
      do {
        params.push(this.expect(TokenType.Identifier).value);
      } while (this.match(TokenType.Comma));
    }

    this.expect(TokenType.RightParen);
    const body = this.parseBlockStatement();

    return { type: 'FunctionDeclaration', name, params, body };
  }

  // ユーティリティメソッド
  private current(): Token { return this.tokens[this.pos]; }
  private consume(): Token { return this.tokens[this.pos++]; }
  private isAtEnd(): boolean { return this.current().type === TokenType.EOF; }
  private check(type: TokenType): boolean { return this.current().type === type; }
  private match(type: TokenType): boolean {
    if (this.check(type)) { this.consume(); return true; }
    return false;
  }
  private expect(type: TokenType): Token {
    if (this.check(type)) return this.consume();
    throw new Error(
      'Expected ' + type + ' but got ' + this.current().type
    );
  }
}

// 演算子優先順位定義
enum Precedence {
  None = 0,
  Assignment = 1,  // =
  Or = 2,          // ||
  And = 3,         // &&
  Equality = 4,    // == !=
  Comparison = 5,  // < > （以下/以上含む）
  Term = 6,        // + -
  Factor = 7,      // * / %
  Unary = 8,       // ! -
  Call = 9,        // ()
  Member = 10,     // .
}

type PrefixParseFn = () => ASTNode;
type InfixParseFn = (left: ASTNode) => ASTNode;

class PrattParser {
  private tokens: Token[];
  private pos: number = 0;

  private prefixParsers: Map<TokenType, PrefixParseFn> = new Map();
  private infixParsers: Map<TokenType, InfixParseFn> = new Map();
  private precedences: Map<TokenType, Precedence> = new Map();

  constructor(tokens: Token[]) {
    this.tokens = tokens;

    // Prefixパーサー登録
    this.registerPrefix(TokenType.Number, this.parseNumber.bind(this));
    this.registerPrefix(TokenType.String, this.parseString.bind(this));
    this.registerPrefix(TokenType.Identifier, this.parseIdentifier.bind(this));
    this.registerPrefix(TokenType.LeftParen, this.parseGrouping.bind(this));
    this.registerPrefix(TokenType.Minus, this.parseUnary.bind(this));
    this.registerPrefix(TokenType.Not, this.parseUnary.bind(this));

    // Infixパーサー登録
    this.registerInfix(TokenType.Plus, Precedence.Term, this.parseBinary.bind(this));
    this.registerInfix(TokenType.Minus, Precedence.Term, this.parseBinary.bind(this));
    this.registerInfix(TokenType.Star, Precedence.Factor, this.parseBinary.bind(this));
    this.registerInfix(TokenType.Slash, Precedence.Factor, this.parseBinary.bind(this));
    this.registerInfix(TokenType.Equal, Precedence.Equality, this.parseBinary.bind(this));
    this.registerInfix(TokenType.LessThan, Precedence.Comparison, this.parseBinary.bind(this));
    this.registerInfix(TokenType.GreaterThan, Precedence.Comparison, this.parseBinary.bind(this));
    this.registerInfix(TokenType.And, Precedence.And, this.parseBinary.bind(this));
    this.registerInfix(TokenType.Or, Precedence.Or, this.parseBinary.bind(this));
    this.registerInfix(TokenType.LeftParen, Precedence.Call, this.parseCall.bind(this));
  }

  // コア：Prattパーシングアルゴリズム
  parseExpression(precedence: Precedence = Precedence.None): ASTNode {
    const token = this.current();
    const prefixFn = this.prefixParsers.get(token.type);

    if (!prefixFn) {
      throw new Error('No prefix parser for ' + token.type);
    }

    let left = prefixFn();

    // 現在の優先順位より高いinfix演算子があれば続けてパース
    while (
      !this.isAtEnd() &&
      precedence < this.getPrecedence(this.current().type)
    ) {
      const infixFn = this.infixParsers.get(this.current().type);
      if (!infixFn) break;
      left = infixFn(left);
    }

    return left;
  }

  private parseBinary(left: ASTNode): ASTNode {
    const operator = this.consume();
    const precedence = this.precedences.get(operator.type) || Precedence.None;
    const right = this.parseExpression(precedence);

    return {
      type: 'BinaryExpression',
      operator: operator.value,
      left,
      right,
    };
  }

  private parseCall(left: ASTNode): ASTNode {
    this.consume(); // '('を消費
    const args: ASTNode[] = [];

    if (!this.check(TokenType.RightParen)) {
      do {
        args.push(this.parseExpression());
      } while (this.match(TokenType.Comma));
    }

    this.expect(TokenType.RightParen);

    return {
      type: 'CallExpression',
      callee: left,
      arguments: args,
    } as CallExpression;
  }

  private registerPrefix(type: TokenType, fn: PrefixParseFn): void {
    this.prefixParsers.set(type, fn);
  }

  private registerInfix(type: TokenType, prec: Precedence, fn: InfixParseFn): void {
    this.infixParsers.set(type, fn);
    this.precedences.set(type, prec);
  }

  private getPrecedence(type: TokenType): Precedence {
    return this.precedences.get(type) || Precedence.None;
  }

  private parseNumber(): ASTNode {
    const token = this.consume();
    return { type: 'NumberLiteral', value: parseFloat(token.value) };
  }

  private parseString(): ASTNode {
    const token = this.consume();
    return { type: 'StringLiteral', value: token.value } as StringLiteral;
  }

  private parseIdentifier(): ASTNode {
    const token = this.consume();
    return { type: 'Identifier', name: token.value } as Identifier;
  }

  private parseGrouping(): ASTNode {
    this.consume();
    const expr = this.parseExpression();
    this.expect(TokenType.RightParen);
    return expr;
  }

  private parseUnary(): ASTNode {
    const operator = this.consume();
    const operand = this.parseExpression(Precedence.Unary);
    return {
      type: 'UnaryExpression',
      operator: operator.value,
      operand,
    } as UnaryExpression;
  }

  private current(): Token { return this.tokens[this.pos]; }
  private consume(): Token { return this.tokens[this.pos++]; }
  private isAtEnd(): boolean { return this.current().type === TokenType.EOF; }
  private check(type: TokenType): boolean { return this.current().type === type; }
  private match(type: TokenType): boolean {
    if (this.check(type)) { this.consume(); return true; }
    return false;
  }
  private expect(type: TokenType): Token {
    if (this.check(type)) return this.consume();
    throw new Error('Expected ' + type + ' but got ' + this.current().type);
  }
}

// Visitorインターフェース
interface ASTVisitor<T> {
  visitProgram(node: Program): T;
  visitNumberLiteral(node: NumberLiteral): T;
  visitBinaryExpression(node: BinaryExpression): T;
  visitIdentifier(node: Identifier): T;
  visitVariableDeclaration(node: VariableDeclaration): T;
  visitFunctionDeclaration(node: FunctionDeclaration): T;
  visitCallExpression(node: CallExpression): T;
  visitIfStatement(node: IfStatement): T;
  visitReturnStatement(node: ReturnStatement): T;
  visitBlockStatement(node: BlockStatement): T;
}

// ASTプリンター（デバッグ用）
class ASTPrinter implements ASTVisitor<string> {
  visitBinaryExpression(node: BinaryExpression): string {
    return (
      '(' +
      this.visit(node.left) +
      ' ' + node.operator + ' ' +
      this.visit(node.right) +
      ')'
    );
  }

  visitNumberLiteral(node: NumberLiteral): string {
    return node.value.toString();
  }

  visitIdentifier(node: Identifier): string {
    return node.name;
  }

  visit(node: ASTNode): string {
    switch (node.type) {
      case 'NumberLiteral': return this.visitNumberLiteral(node as NumberLiteral);
      case 'BinaryExpression': return this.visitBinaryExpression(node as BinaryExpression);
      case 'Identifier': return this.visitIdentifier(node as Identifier);
      default: return 'Unknown: ' + node.type;
    }
  }
}

// シンボル情報
interface Symbol {
  name: string;
  type: DataType;
  kind: 'variable' | 'function' | 'parameter';
  mutable: boolean;
  scope: Scope;
}

// スコープ（レキシカルスコープチェーン）
class Scope {
  private symbols: Map<string, Symbol> = new Map();
  private parent: Scope | null;

  constructor(parent: Scope | null = null) {
    this.parent = parent;
  }

  define(symbol: Symbol): void {
    if (this.symbols.has(symbol.name)) {
      throw new Error('Symbol already defined: ' + symbol.name);
    }
    this.symbols.set(symbol.name, symbol);
  }

  resolve(name: string): Symbol | null {
    if (this.symbols.has(name)) {
      return this.symbols.get(name)!;
    }
    // 親スコープで検索
    if (this.parent) {
      return this.parent.resolve(name);
    }
    return null;
  }

  createChild(): Scope {
    return new Scope(this);
  }
}

// 型システム
type DataType =
  | { kind: 'number' }
  | { kind: 'string' }
  | { kind: 'boolean' }
  | { kind: 'void' }
  | { kind: 'function'; params: DataType[]; returnType: DataType }
  | { kind: 'array'; elementType: DataType };

class TypeChecker implements ASTVisitor<DataType> {
  private currentScope: Scope = new Scope();

  visitBinaryExpression(node: BinaryExpression): DataType {
    const leftType = this.visit(node.left);
    const rightType = this.visit(node.right);

    // 算術演算子
    if (['+', '-', '*', '/', '%'].includes(node.operator)) {
      if (node.operator === '+') {
        if (leftType.kind === 'string' || rightType.kind === 'string') {
          return { kind: 'string' };
        }
      }

      if (leftType.kind !== 'number' || rightType.kind !== 'number') {
        throw new TypeError(
          'Operator ' + node.operator +
          ' requires number operands, got ' +
          leftType.kind + ' and ' + rightType.kind
        );
      }
      return { kind: 'number' };
    }

    // 比較演算子
    if (['==', '!=', '<', '>'].includes(node.operator)) {
      return { kind: 'boolean' };
    }

    // 論理演算子
    if (['&&', '||'].includes(node.operator)) {
      return { kind: 'boolean' };
    }

    throw new TypeError('Unknown operator: ' + node.operator);
  }

  visit(node: ASTNode): DataType {
    switch (node.type) {
      case 'NumberLiteral': return { kind: 'number' };
      case 'StringLiteral': return { kind: 'string' };
      case 'BooleanLiteral': return { kind: 'boolean' };
      case 'BinaryExpression': return this.visitBinaryExpression(node as BinaryExpression);
      default: return { kind: 'void' };
    }
  }
}

// 三番地コード（Three-Address Code）
type IRInstruction =
  | { op: 'CONST'; dest: string; value: number }
  | { op: 'ADD' | 'SUB' | 'MUL' | 'DIV'; dest: string; left: string; right: string }
  | { op: 'LABEL'; name: string }
  | { op: 'JUMP'; target: string }
  | { op: 'JUMP_IF_FALSE'; condition: string; target: string }
  | { op: 'CALL'; dest: string; fn: string; args: string[] }
  | { op: 'RETURN'; value: string | null };

// AST -> IR変換
class IRGenerator {
  private instructions: IRInstruction[] = [];
  private tempCounter: number = 0;
  private labelCounter: number = 0;

  private newTemp(): string {
    return '_t' + (this.tempCounter++);
  }

  private newLabel(): string {
    return '_L' + (this.labelCounter++);
  }

  private emit(instruction: IRInstruction): void {
    this.instructions.push(instruction);
  }

  generateBinary(node: BinaryExpression): string {
    const left = this.generate(node.left);
    const right = this.generate(node.right);
    const dest = this.newTemp();

    const opMap: Record<string, string> = {
      '+': 'ADD', '-': 'SUB', '*': 'MUL', '/': 'DIV',
    };

    this.emit({
      op: opMap[node.operator] as 'ADD',
      dest,
      left,
      right,
    });

    return dest;
  }

  generate(node: ASTNode): string {
    switch (node.type) {
      case 'NumberLiteral': {
        const dest = this.newTemp();
        this.emit({ op: 'CONST', dest, value: (node as NumberLiteral).value });
        return dest;
      }
      case 'BinaryExpression':
        return this.generateBinary(node as BinaryExpression);
      default:
        return '';
    }
  }
}

LLVM IRの基本構造：

; 関数定義
define i32 @add(i32 %a, i32 %b) {
entry:
  %sum = add i32 %a, %b
  ret i32 %sum
}

; if-else構造
define i32 @max(i32 %a, i32 %b) {
entry:
  %cmp = icmp sgt i32 %a, %b
  br i1 %cmp, label %then, label %else

then:
  ret i32 %a

else:
  ret i32 %b
}

; ループ構造
define i32 @sum_to_n(i32 %n) {
entry:
  br label %loop

loop:
  %i = phi i32 [ 0, %entry ], [ %next_i, %loop ]
  %sum = phi i32 [ 0, %entry ], [ %next_sum, %loop ]
  %next_sum = add i32 %sum, %i
  %next_i = add i32 %i, 1
  %cond = icmp slt i32 %next_i, %n
  br i1 %cond, label %loop, label %exit

exit:
  ret i32 %next_sum
}

SSA（Static Single Assignment）の特徴：
- 各変数は正確に一度だけ割り当てられる
- phiノードで制御フロー合流地点を処理
- 最適化パスの適用が容易

// 定数畳み込み：コンパイル時に定数式を計算
class ConstantFolding {
  optimize(node: ASTNode): ASTNode {
    if (node.type === 'BinaryExpression') {
      const binary = node as BinaryExpression;
      const left = this.optimize(binary.left);
      const right = this.optimize(binary.right);

      // 両方が定数なら事前計算
      if (left.type === 'NumberLiteral' && right.type === 'NumberLiteral') {
        const leftVal = (left as NumberLiteral).value;
        const rightVal = (right as NumberLiteral).value;

        let result: number;
        switch (binary.operator) {
          case '+': result = leftVal + rightVal; break;
          case '-': result = leftVal - rightVal; break;
          case '*': result = leftVal * rightVal; break;
          case '/': result = leftVal / rightVal; break;
          default: return { ...binary, left, right };
        }

        return { type: 'NumberLiteral', value: result };
      }

      return { ...binary, left, right };
    }

    return node;
  }
}

// 例：2 + 3 * 4 -> 14

// デッドコード除去
class DeadCodeElimination {
  optimize(program: Program): Program {
    const usedVariables = this.collectUsedVariables(program);

    const optimizedBody = program.body.filter((stmt) => {
      if (stmt.type === 'VariableDeclaration') {
        const decl = stmt as VariableDeclaration;
        if (!usedVariables.has(decl.name) && !this.hasSideEffects(decl.initializer)) {
          return false;
        }
      }
      return true;
    });

    return { ...program, body: optimizedBody };
  }

  private collectUsedVariables(program: Program): Set<string> {
    const used = new Set<string>();
    function walk(node: ASTNode): void {
      if (node.type === 'Identifier') {
        used.add((node as Identifier).name);
      }
    }
    program.body.forEach(walk);
    return used;
  }

  private hasSideEffects(node: ASTNode | null): boolean {
    if (!node) return false;
    return node.type === 'CallExpression';
  }
}

ループ最適化技法：

1. ループ不変コード移動（LICM）
   // Before                    // After
   for (i = 0; i < n; i++)    x = a + b;  // ループ外に移動
     arr[i] = a + b + i;      for (i = 0; i < n; i++)
                                  arr[i] = x + i;

2. ループ展開（Loop Unrolling）
   // Before                    // After
   for (i = 0; i < 4; i++)    arr[0] = 0;
     arr[i] = 0;               arr[1] = 0;
                                arr[2] = 0;
                                arr[3] = 0;

3. 強度削減（Strength Reduction）
   // Before                    // After
   for (i = 0; i < n; i++)    t = 0;
     arr[i] = i * 4;           for (i = 0; i < n; i++)
                                  arr[i] = t;
                                  t = t + 4;  // 乗算 -> 加算

// AST -> WebAssembly Text Format (WAT) コード生成
class WasmCodeGenerator {
  private output: string[] = [];

  generate(program: Program): string {
    this.output.push('(module');

    for (const stmt of program.body) {
      if (stmt.type === 'FunctionDeclaration') {
        this.generateFunction(stmt as FunctionDeclaration);
      }
    }

    this.output.push(')');
    return this.output.join('\n');
  }

  private generateFunction(node: FunctionDeclaration): void {
    const params = node.params.map((p) => '(param $' + p + ' i32)').join(' ');

    this.output.push('  (func $' + node.name + ' ' + params + ' (result i32)');

    for (const stmt of node.body.body) {
      this.generateStatement(stmt);
    }

    this.output.push('  )');
    this.output.push('  (export "' + node.name + '" (func $' + node.name + '))');
  }

  private generateExpression(node: ASTNode): void {
    switch (node.type) {
      case 'NumberLiteral':
        this.output.push('    i32.const ' + (node as NumberLiteral).value);
        break;
      case 'Identifier':
        this.output.push('    local.get $' + (node as Identifier).name);
        break;
      case 'BinaryExpression': {
        const binary = node as BinaryExpression;
        this.generateExpression(binary.left);
        this.generateExpression(binary.right);

        const opMap: Record<string, string> = {
          '+': 'i32.add', '-': 'i32.sub',
          '*': 'i32.mul', '/': 'i32.div_s',
          '<': 'i32.lt_s', '>': 'i32.gt_s',
          '==': 'i32.eq', '!=': 'i32.ne',
        };

        this.output.push('    ' + opMap[binary.operator]);
        break;
      }
    }
  }

  private generateStatement(node: ASTNode): void {
    if (node.type === 'ReturnStatement') {
      const ret = node as ReturnStatement;
      if (ret.value) {
        this.generateExpression(ret.value);
      }
      this.output.push('    return');
    }
  }
}

// スタックベースのバイトコード
enum OpCode {
  CONST = 0x01,        // 定数プッシュ
  ADD = 0x02,          // 加算
  SUB = 0x03,          // 減算
  MUL = 0x04,          // 乗算
  DIV = 0x05,          // 除算
  LOAD = 0x10,         // 変数ロード
  STORE = 0x11,        // 変数ストア
  JUMP = 0x20,         // 無条件ジャンプ
  JUMP_IF_FALSE = 0x21,// 条件付きジャンプ
  CALL = 0x30,         // 関数呼び出し
  RETURN = 0x31,       // リターン
  PRINT = 0x40,        // 出力
  HALT = 0xFF,         // 停止
}

class BytecodeCompiler {
  private bytecode: number[] = [];
  private constants: any[] = [];
  private locals: Map<string, number> = new Map();

  compile(program: Program): Uint8Array {
    for (const stmt of program.body) {
      this.compileNode(stmt);
    }
    this.emit(OpCode.HALT);
    return new Uint8Array(this.bytecode);
  }

  private compileNode(node: ASTNode): void {
    switch (node.type) {
      case 'NumberLiteral': {
        const index = this.addConstant((node as NumberLiteral).value);
        this.emit(OpCode.CONST);
        this.emit(index);
        break;
      }
      case 'BinaryExpression': {
        const binary = node as BinaryExpression;
        this.compileNode(binary.left);
        this.compileNode(binary.right);
        switch (binary.operator) {
          case '+': this.emit(OpCode.ADD); break;
          case '-': this.emit(OpCode.SUB); break;
          case '*': this.emit(OpCode.MUL); break;
          case '/': this.emit(OpCode.DIV); break;
        }
        break;
      }
      case 'VariableDeclaration': {
        const decl = node as VariableDeclaration;
        const slot = this.locals.size;
        this.locals.set(decl.name, slot);
        if (decl.initializer) {
          this.compileNode(decl.initializer);
          this.emit(OpCode.STORE);
          this.emit(slot);
        }
        break;
      }
    }
  }

  private emit(byte: number): void { this.bytecode.push(byte); }
  private addConstant(value: any): number {
    this.constants.push(value);
    return this.constants.length - 1;
  }
}

// Tree-Walkingインタプリタ
class TreeWalkInterpreter {
  private environment: Environment;

  constructor() {
    this.environment = new Environment();
    this.environment.define('print', (args: any[]) => {
      console.log(...args);
      return null;
    });
  }

  interpret(program: Program): any {
    let result: any = null;
    for (const stmt of program.body) {
      result = this.execute(stmt);
    }
    return result;
  }

  private execute(node: ASTNode): any {
    switch (node.type) {
      case 'NumberLiteral':
        return (node as NumberLiteral).value;
      case 'StringLiteral':
        return (node as StringLiteral).value;
      case 'Identifier':
        return this.environment.get((node as Identifier).name);
      case 'BinaryExpression': {
        const binary = node as BinaryExpression;
        const left = this.execute(binary.left);
        const right = this.execute(binary.right);
        switch (binary.operator) {
          case '+': return left + right;
          case '-': return left - right;
          case '*': return left * right;
          case '/': return left / right;
          case '==': return left === right;
          case '<': return left < right;
          case '>': return left > right;
          default: throw new Error('Unknown operator: ' + binary.operator);
        }
      }
      case 'FunctionDeclaration': {
        const fn = node as FunctionDeclaration;
        const closure = this.environment;
        const callable = (args: any[]) => {
          const fnEnv = new Environment(closure);
          fn.params.forEach((param, i) => fnEnv.define(param, args[i]));
          const prevEnv = this.environment;
          this.environment = fnEnv;
          try {
            for (const stmt of fn.body.body) {
              const result = this.execute(stmt);
              if (result && result.__return__) return result.value;
            }
          } finally {
            this.environment = prevEnv;
          }
          return null;
        };
        this.environment.define(fn.name, callable);
        return null;
      }
      case 'CallExpression': {
        const call = node as CallExpression;
        const fn = this.execute(call.callee);
        const args = call.arguments.map((arg: ASTNode) => this.execute(arg));
        return fn(args);
      }
      case 'ReturnStatement': {
        const ret = node as ReturnStatement;
        return { __return__: true, value: ret.value ? this.execute(ret.value) : null };
      }
      default:
        throw new Error('Unknown node type: ' + node.type);
    }
  }
}

// 環境（Environment）- 変数バインディング管理
class Environment {
  private bindings: Map<string, any> = new Map();
  private parent: Environment | null;

  constructor(parent: Environment | null = null) {
    this.parent = parent;
  }

  define(name: string, value: any): void { this.bindings.set(name, value); }

  get(name: string): any {
    if (this.bindings.has(name)) return this.bindings.get(name);
    if (this.parent) return this.parent.get(name);
    throw new Error('Undefined variable: ' + name);
  }
}

// スタックベースのバイトコードVM
class VirtualMachine {
  private stack: any[] = [];
  private locals: any[] = new Array(256).fill(null);
  private ip: number = 0;

  execute(bytecode: Uint8Array, constants: any[]): any {
    while (this.ip < bytecode.length) {
      const opcode = bytecode[this.ip++];

      switch (opcode) {
        case OpCode.CONST: {
          const index = bytecode[this.ip++];
          this.stack.push(constants[index]);
          break;
        }
        case OpCode.ADD: {
          const b = this.stack.pop();
          const a = this.stack.pop();
          this.stack.push(a + b);
          break;
        }
        case OpCode.SUB: {
          const b = this.stack.pop();
          const a = this.stack.pop();
          this.stack.push(a - b);
          break;
        }
        case OpCode.MUL: {
          const b = this.stack.pop();
          const a = this.stack.pop();
          this.stack.push(a * b);
          break;
        }
        case OpCode.LOAD: {
          const slot = bytecode[this.ip++];
          this.stack.push(this.locals[slot]);
          break;
        }
        case OpCode.STORE: {
          const slot = bytecode[this.ip++];
          this.locals[slot] = this.stack.pop();
          break;
        }
        case OpCode.JUMP: {
          this.ip = bytecode[this.ip++];
          break;
        }
        case OpCode.JUMP_IF_FALSE: {
          const target = bytecode[this.ip++];
          if (!this.stack.pop()) this.ip = target;
          break;
        }
        case OpCode.PRINT:
          console.log(this.stack.pop());
          break;
        case OpCode.HALT:
          return this.stack.length > 0 ? this.stack.pop() : null;
      }
    }
    return null;
  }
}

GCアルゴリズム比較：
┌──────────────────┬────────────┬────────────┬──────────────┐
│ アルゴリズム     │ スループット│ 一時停止   │ メモリオーバヘッド│
├──────────────────┼────────────┼────────────┼──────────────┤
│ 参照カウント     │ 高い      │ 短い      │ オブジェクト毎│
│ Mark-Sweep       │ 高い      │ 長くなりうる│ マークビット │
│ Mark-Compact     │ 普通      │ 長くなりうる│ マークビット │
│ 世代別           │ 非常に高い│ 概ね短い  │ カードテーブル│
│ 並行(Concurrent) │ 高い      │ 非常に短い│ Write Barrier│
└──────────────────┴────────────┴────────────┴──────────────┘

// シンプルなMark-Sweep GC
class GarbageCollector {
  private heap: GCObject[] = [];
  private roots: Set<GCObject> = new Set();

  allocate(value: any): GCObject {
    const obj: GCObject = { value, marked: false, references: [] };
    this.heap.push(obj);

    if (this.heap.length > 1000) {
      this.collect();
    }

    return obj;
  }

  collect(): void {
    // Mark段階
    for (const root of this.roots) {
      this.mark(root);
    }
    // Sweep段階
    this.heap = this.heap.filter((obj) => {
      if (obj.marked) {
        obj.marked = false;
        return true;
      }
      return false;
    });
  }

  private mark(obj: GCObject): void {
    if (obj.marked) return;
    obj.marked = true;
    for (const ref of obj.references) {
      this.mark(ref);
    }
  }
}

interface GCObject {
  value: any;
  marked: boolean;
  references: GCObject[];
}

// ミニ言語「MiniLang」全パイプライン
class MiniLang {
  static run(source: string): any {
    // 1. トークン化
    const lexer = new Lexer(source);
    const tokens = lexer.tokenize();

    // 2. パース
    const parser = new RecursiveDescentParser(tokens);
    const ast = parser.parse();

    // 3. 最適化
    const optimizer = new ConstantFolding();
    // const optimizedAst = optimizer.optimize(ast);

    // 4. 実行
    const interpreter = new TreeWalkInterpreter();
    return interpreter.interpret(ast);
  }
}

// 使用例
const source = `
let x = 10;
let y = 20;

function add(a, b) {
  return a + b;
}

function factorial(n) {
  if (n == 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

let result = add(x, y);
print(result);
print(factorial(5));
`;

MiniLang.run(source);
// 出力：30
// 出力：120

現代コンパイラ/トランスパイラ比較：

Rust Compiler (rustc):
  Source -> HIR -> MIR -> LLVM IR -> 機械語
  特徴：所有権システム、借用チェッカー、モノモーフィゼーション

V8 TurboFan (JavaScript):
  Source -> AST -> Bytecode(Ignition) -> 最適コード(TurboFan)
  特徴：インラインキャッシュ、投機的最適化、脱最適化

TypeScript Compiler (tsc):
  Source -> Scanner -> Parser -> AST -> Binder -> Checker -> Emitter
  特徴：構造的型システム、型推論、.d.ts生成

SWC (Speedy Web Compiler):
  Source -> Lexer -> Parser -> AST -> Transform -> Codegen
  特徴：Rustで記述、Babel比20-70倍高速

esbuild:
  Source -> Lexer -> Parser -> AST -> Linker -> Codegen
  特徴：Goで記述、極めて高速なバンドリング

コンパイラ学習ロードマップ：

初級：
├── Crafting Interpreters（Robert Nystrom）
│   - Tree-Walkingインタプリタ（Java）
│   - バイトコードVM（C）
├── Writing An Interpreter In Go（Thorsten Ball）
└── ミニLispインタプリタ実装

中級：
├── Engineering a Compiler（Cooper & Torczon）
├── LLVM Tutorial: Kaleidoscope
└── WebAssemblyコンパイラ実装

上級：
├── コンパイラ ─ 原理・技法・ツール（Dragon Book）
├── SSA-based Compiler Design（Springer）
└── 実際のオープンソースコンパイラに貢献
    - Rust, V8, LLVM, GCC等