1957 - Backus 的 FORTRAN（第一個成功的編譯器）#

; X = (A + B) * C 的組合語言
LOAD  A        ; 載入 A 到暫存器
ADD   B        ; 加 B
STORE  T1      ; 存到暫存器 T1
LOAD  T1
MUL   C        ; 乘 C
STORE  X       ; 存到 X

import re

# 1) 詞法分析：把字元流切成記號
def tokenize(expr):
    """詞法分析：數字、識別字、運算子"""
    token_spec = r'\d+\.?\d*|[A-Za-z_]\w*|[+\-*/()]'
    return re.findall(token_spec, expr)

# 2) 遞迴下降語法分析：expr → term → factor
class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def consume(self):
        tok = self.peek()
        self.pos += 1
        return tok

    def expr(self):
        """expr := term (('+'|'-') term)*"""
        node = self.term()
        while self.peek() in ('+', '-'):
            op = self.consume()
            node = (op, node, self.term())
        return node

    def term(self):
        """term := factor (('*'|'/') factor)*"""
        node = self.factor()
        while self.peek() in ('*', '/'):
            op = self.consume()
            node = (op, node, self.factor())
        return node

    def factor(self):
        """factor := number | ident | '(' expr ')'"""
        tok = self.consume()
        if tok == '(':
            node = self.expr()
            self.consume()   # 吃掉 ')'
            return node
        return tok

# 3) 程式碼生成：從語法樹產生（虛擬）機器碼
def gen_code(node, temps=[], counter=[0]):
    """後序走訪：產生虛擬機器碼（LOAD/ADD/MUL/STORE）"""
    if isinstance(node, str):
        return f"LOAD {node}"
    op, left, right = node
    opname = {'+':'ADD', '-':'SUB', '*':'MUL', '/':'DIV'}[op]
    code_l = gen_code(left, temps, counter)
    code_r = gen_code(right, temps, counter)
    counter[0] += 1
    temp = f"T{counter[0]}"
    return f"{code_l}\nPUSH\ncode_r = {code_r}\n{opname}\nSTORE {temp}".replace("code_r = ", "")

# 簡化的程式碼生成（避免嵌套字串問題）
def gen_simple(node):
    """產生三地址碼（three-address code）"""
    lines = []
    def walk(n):
        if isinstance(n, str):
            return n
        op, l, r = n
        tl = walk(l)
        tr = walk(r)
        t = f"t{len(lines)}"
        opname = {'+':'ADD', '-':'SUB', '*':'MUL', '/':'DIV'}[op]
        lines.append(f"{opname} {tl}, {tr} -> {t}")
        return t
    walk(node)
    return lines

# 測試：X = (A + B) * C
expr = "(A + B) * C"
tokens = tokenize(expr)
print(f"原始運算式：{expr}")
print(f"詞法分析：{tokens}")
parser = Parser(tokens)
tree = parser.expr()
print(f"語法樹：{tree}")
code = gen_simple(tree)
print("\n產生的三地址碼：")
for line in code:
    print(f"  {line}")
print("\n→ 編譯器管線：詞法 → 語法 → 最佳化 → 生成（FORTRAN 1957 的架構）")

# 4) BNF 范式示範
print("\nBNF 范式（Backus Normal Form, 1959）：")
print("  <expr>  ::= <term> | <expr> + <term> | <expr> - <term>")
print("  <term>  ::= <factor> | <term> * <factor> | <term> / <factor>")
print("  <factor>::= number | ident | ( <expr> )")
print("  → 所有程式語言的規格書都用 BNF 寫（1959 的發明）")

原始運算式：(A + B) * C
詞法分析：['(', 'A', '+', 'B', ')', '*', 'C']
語法樹：('*', ('+', 'A', 'B'), 'C')

產生的三地址碼：
  ADD A, B -> t0
  MUL t0, C -> t1

→ 編譯器管線：詞法 → 語法 → 最佳化 → 生成（FORTRAN 1957 的架構）

BNF 范式（Backus Normal Form, 1959）：
  <expr>  ::= <term> | <expr> + <term> | <expr> - <term>
  <term>  ::= <factor> | <term> * <factor> | <term> / <factor>
  <factor>::= number | ident | ( <expr> )
  → 所有程式語言的規格書都用 BNF 寫（1959 的發明）