编译原理入门

# 编译过程示意

源代码 (Source Code)
|
v
[词法分析] (Lexical Analysis)
|
v
记号流 (Token Stream)
|
v
[语法分析] (Syntax Analysis)
|
v
抽象语法树 (AST)
|
v
[语义分析] (Semantic Analysis)
|
v
标注的 AST (Annotated AST)
|
v
[中间代码生成] (IR Generation)
|
v
中间表示 (IR)
|
v
[优化] (Optimization)
|
v
优化的 IR
|
v
[目标代码生成] (Code Generation)
|
v
目标代码 (Object Code)
|
v
[链接] (Linking)
|
v
可执行程序

# 示例：编译 C 程序
# gcc -O2 -o program main.c

# 分步执行
gcc -E main.c -o main.i      # 预处理
gcc -S main.i -o main.s      # 编译为汇编
gcc -c main.s -o main.o      # 汇编为目标文件
gcc main.o -o program        # 链接生成可执行文件

# 词法分析器示例（Python 实现）

import re

# 定义记号类型
TOKEN_TYPES = [
('NUMBER', r'\d+'),
('IDENT', r'[a-zA-Z_][a-zA-Z0-9_]*'),
('PLUS', r'\+'),
('MINUS', r'-'),
('MULTIPLY', r'\*'),
('DIVIDE', r'/'),
('ASSIGN', r'='),
('LPAREN', r'\('),
('RPAREN', r'\)'),
('LBRACE', r'\{'),
('RBRACE', r'\}'),
('SEMICOLON', r';'),
('WHITESPACE', r'\s+'),  # 忽略空白
]

# 关键字
KEYWORDS = {'if', 'else', 'while', 'int', 'return', 'void'}

def tokenize(code):
tokens = []
pos = 0

while pos < len(code):
    match = None
    for token_type, pattern in TOKEN_TYPES:
        regex = re.compile(pattern)
        match = regex.match(code, pos)
        if match:
            value = match.group()
            if token_type == 'WHITESPACE':
                pos = match.end()
                break
            elif token_type == 'IDENT' and value in KEYWORDS:
                token_type = 'KEYWORD'
            tokens.append((token_type, value))
            pos = match.end()
            break

    if not match:
        raise SyntaxError(f'Unexpected character at position {pos}')

return tokens

# 测试
code = 'int x = 10 + 20;'
tokens = tokenize(code)
for token_type, value in tokens:
  print(f'{token_type}: {value}')

# 简单的递归下降解析器

class Parser:
def __init__(self, tokens):
    self.tokens = tokens
    self.pos = 0

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

def eat(self, expected_type):
    token = self.current_token()
    if token and token[0] == expected_type:
        self.pos += 1
        return token
    raise SyntaxError(f'Expected {expected_type}, got {token}')

# 表达式解析
def expr(self):
    node = self.term()
    while self.current_token() and self.current_token()[0] in ('PLUS', 'MINUS'):
        op = self.eat(self.current_token()[0])
        right = self.term()
        node = ('binop', op[1], node, right)
    return node

def term(self):
    node = self.factor()
    while self.current_token() and self.current_token()[0] in ('MULTIPLY', 'DIVIDE'):
        op = self.eat(self.current_token()[0])
        right = self.factor()
        node = ('binop', op[1], node, right)
    return node

def factor(self):
    token = self.current_token()
    if token[0] == 'NUMBER':
        self.pos += 1
        return ('number', int(token[1]))
    elif token[0] == 'IDENT':
        self.pos += 1
        return ('identifier', token[1])
    elif token[0] == 'LPAREN':
        self.eat('LPAREN')
        node = self.expr()
        self.eat('RPAREN')
        return node
    raise SyntaxError(f'Unexpected token: {token}')

# AST 节点示例
# 表达式: 1 + 2 * 3
# AST: ('binop', '+', ('number', 1), ('binop', '*', ('number', 2), ('number', 3)))