跳到主要内容

编译原理

把某高级语言书写的源程序翻译成与之等价的目标程序

编译过程​

flowchart TB;
ST[符号表管理]
S[源程序]
LA[词法分析]
SA[语法分析]
SEA[语义分析]
TAC[中间代码生成]
CO[代码优化]
GTC[目标代码生成]
TC[目标代码]
EH[出错处理]
subgraph flow
  S --> LA -->|符号流| SA -->|语法树| SEA -->|语法树| TAC -->|中间代码| CO -->|目标语言| GTC --> TC
end
ST --- flow --- EH
  • 词法分析
    • 顺序逐字扫描源程序，形成符号栈和值栈
  • 语法分析
    • 形成语法树，节点表示运算，子节点表示运算分量
  • 语义分析
    • 类型检查
    • 类型转换
    • 生成语法树
  • 中间代码生成
    • 通常使用四元式实现
  • 代码优化
  • 目标代码生成
  • 符号表管理
  • 出错处理
    • 运行时动态错误/语义错误
    • 编译时静态错误
      • 语法错误
      • 静态语义错误

语言​

语言LL是有限字母表Σ\Sigma上的有限长度字符串的集合

字符串​

  • 字符
    • 具有独立含义的最小单位一个字母、数字或符号
  • 字母表 Σ\Sigma
    • 字母表是字符的非空有穷集合
    • 字符是字母表中的元素
  • 字符串
    • Σ\Sigma 中字符组成的有穷序列
  • 空串 ϵ\epsilon
    • 长度为 0 的字符串

字符串运算​

  • 或运算/并运算
    • A∪B={α∣α∈A or α∈B}A \cup B=\{\alpha| \alpha \in A \space or \space \alpha \in B \}
  • 积运算/连接运算
    • α⋅β=αβ\alpha \cdot \beta=\alpha \beta
    • AB={αβ∣α∈A and β∈B}AB=\{\alpha \beta| \alpha \in A \space and \space \beta \in B\}
  • 幂运算
    • αn=α⋅αn−1=αn−1α\alpha^n=\alpha \cdot \alpha^n-1=\alpha^{n-1} \alpha
    • An=A⋅An−1 and A0={ϵ}A^n=A \cdot A^{n-1} \space and \space A^0=\{\epsilon\}
  • 正闭包
    • A+=A1∪A2∪...∪AnA^+=A^1 \cup A^2 \cup ... \cup A^n
    • Σ+=Σ1∪Σ2∪...∪Σn\Sigma^+=\Sigma^1 \cup \Sigma^2 \cup ... \cup \Sigma^n
  • 闭包
    • A∗=A0∪A+A^*=A^0 \cup A^+
    • Σ∗=Σ0∪Σ+\Sigma^*=\Sigma^0 \cup \Sigma^+

文法​

表示为一个四元组 G=(Σ,N,P,S)G=(\Sigma,N,P,S),用于描述语言语法结构的规则

构成​

  • Σ\Sigma
    • 字母表/终结符集
  • NN
    • 语法变量集/非终结符集
  • VV
    • 词汇表
    • V=Σ∪NV=\Sigma \cup N
    • Σ∩N=Φ\Sigma \cap N = \Phi
  • PP
    • 产生式集
    • α→β\alpha \to \beta
    • α∈V+ and ∀α∈,A⊂Σ\alpha \in V^+ \space and \space \forall \alpha \in,A \subset \Sigma
    • β∈V∗\beta \in V^*
    • if α→β1,α→β2,...,α→βn\alpha \to \beta_1,\alpha \to \beta_2,...,\alpha \to \beta_n
      • α→β1∣β2∣...∣βn∣\alpha \to \beta_1|\beta_2|...|\beta_n|
      • 称 βi(1≤i≤n)\beta_i(1 \le i \le n) 为 α\alpha 的候选式
  • SS
    • 开始符号
    • S∈ΣS \in \Sigma

分类​

  • 0 型
    • 短文语法
    • ∀α→β, α∈(Σ∪N)+ and β∈(Σ∪N)∗for a∈A and A⊂Σ, ∣A∣≥1\forall \alpha \to \beta ,\space \alpha \in (\Sigma \cup N)^+ \space and \space \beta \in (\Sigma \cup N)^* \\ \text{for} \space a \in A \space and \space A\sub \Sigma , \space |A| \ge 1
  • 1 型
    • 上下文有关语法
  • 2 型
    • 上下文无关文法
  • 3
    • 正规文法/线性文法
    • (stmt→if (expr) stmt else stmt)∈Pif,else,()∈Σstmt,expr∈N(\textit{stmt} \to \textbf{if} \space \textit{(expr)} \space \textit{stmt} \space \textbf{else} \space \textit{stmt}) \in P \\ \textbf{if} , \textbf{else} ,\textbf{()} \in \Sigma \\ \textit{stmt} , \textit{expr} \in N

处理​

  • 推导与直接推导
  • 归约和直接归约
  • 等价
  • 句型和句子
  • 语言

词法​