KamiertopのBlogSite
KamiertopのBlogSite

Principles of Compiler

编译原理

kamiertop kamiertop 收录于 system
 约 4500 字 预计阅读 9 分钟 
编译原理 www.icourse163.org/course/NUDT-1003101005 card image

引论

  • 什么是编译程序（编译器）：将一种高级语言程序等价地转换成另一种低级语言程序（汇编语言、机器语言）的程序
  • 为什么学习编译原理：感兴趣
  • 编译程序5个阶段：词法分析，语法分析，中间代码生成，优化，目标代码生成
  • 编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码生成，与机器无关的优化
  • 编译后端：与目标机器有关，与目标机器有关的优化，目标代码生成
---
title: 编译前端与编译后端
---
graph LR;
    源语言 -- 前端 --> 中间语言
    中间语言 -- 后端 --> 目标语言
---
title: 编译前端与编译后端
---
graph LR;
    源语言 -- 前端 --> 中间语言
    中间语言 -- 后端 --> 目标语言
---
title: 编译前端与编译后端
---
graph LR;
    源语言 -- 前端 --> 中间语言
    中间语言 -- 后端 --> 目标语言

高级程序设计语言概述

摘要
本章较为简单, 简单记录下
详情

  • 标识符是语法概念, 名字是语义概念

  • 程序语言定义包含语法和语义

    • 语法: 一组规则, 用它可以形成和产生一个合式的程序
      • 词法规则: 单词符号的形成规则, 一般包括常数,标识符,基本字,算符等
      • 使用有限自动机描述
    • 语义: 语法单位的形成规则, 可以定义一个程序的意义
      • 语法单位通常包括: 标傲世,语句, 过程, 函数, 程序等
      • 使用上下文无关文法描述

  • 最近嵌套原则

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    func main(){
    var x int = 1
    {
        println(x) // 可以访问外部作用域的x
        var y int = 1
        x = 10    // 还可以修改x
    }
  // println(y) 无法访问
  println(x) // 10
}

  • 数据类型三要素

    • 用于区别这种类型数据对象的属性
    • 这种类型的数据对象可以具有的值
    • 可以作用域这种类型的数据对象的操作

  • 抽象数据类型包括

    • 数据对象集合
    • 作用于这些数据对象的抽象运算的几何
    • 这种类型对象的封装

  • 表达式由运算符(也称操作数, 即数据引用或函数调用)和算符(运算符,操作符)组成. (Rust就是一门基于表达式的语言)

    • 中缀: X-Y
    • 前缀: -A
    • 后缀: p->

  • 表达式形成规则(表达式是一个值)

    • 变量和常数是表达式
    • 若E1和E2是表达式, α是一个运算符, 则E1αE2是表达式
    • 若E是表达式,α是一元算符, 则αE或Eα是表达式
    • 若E是表达式,则(E)是表达式

  • 表达式计算规定即算符的优先次序

  • 赋值语句

    • A := B (将B的右值赋值给A的左值)
    • 名字的左值: 该名字代表的存储单元的地址
    • 名字的右值: 该名字代表的存储单元的内容

  • 控制语句

    • 无条件转移语句: goto
    • 条件语句: if else
    • 循环语句: while, for, loop
    • 过程调用语句
    • 返回语句: return

高级程序设计语言的语法描述

详情

  • 文法: 描述语言的语法结构的形式规则

  • 定义文法的目的是描述语言. 一个符号怎么替换, 都和它周围的符号没有关系. 是一套规则集合, 用来描述一类语言的结构

  • 字母表: 一个有穷字符集, 字母表中每个元素成为字符

  • 上下文无关文法: G是一个四元组G=(VT,VN,S,P)G=(V_T,V_N,S,P)

    • VTV_T: 终结符集合(非空), 不能再拆分的’最小单位’
    • VNV_N: 非终结符集合(非空), 且VT∩VN=∅V_T ∩ V_N = \emptyset, 可以被替换的’占位符'
    • S: 文法的开始符号, 是一个特殊的非终结符, 至少必须在某个产生式左部出现一次
    • P: 产生式集合(有限)

  • 通俗易懂解释(感谢豆包大人)

    • 产生式的左边只能有一个非终结符, 而且这个非终结符的替换规则, 和它左右是什么符号没有关系. 比如主语->猫, 那么不管主语出现在句子的什么位置, 都可以换成猫
    • 直观展示
      1. 起点: 句子
      2. 应用规则(句子由主语+谓语组成): 句子->主语+谓语
      3. 应用规则(这里的主语是猫): 主语->猫 -> 猫+谓语
      4. 应用规则: 谓语->吃+鱼 -> 猫+吃+鱼
      5. 现在所有符号都是终结符(猫,吃,鱼), 最终得到合法句子: 猫吃鱼
    • 以Python为例
      1. 非终结符: 赋值语句, 变量, 表达式
      2. 终结符: =,x,5,+
      3. 产生式: 赋值语句->变量=表达式; 变量->x, 表达式->5
      4. 推导: 赋值语句->变量=表达式 -> x=5 -> 合法的Python语句 x=5

  • 上下文无关文法约定: P->a1,P->a2,…P->an; 可缩写为 P->a1|a2|a3|…|an, 其中ai为P的一个候选式

  • 推导: α1=>α2=>α3=>…=>αn,那么称这个序列是从α1到αn的一个推导

    • α1 ⇒∗\stackrel{*}{\Rightarrow} αn: 从α1出发, 经过0步或若干步推出
    • α1 ⇒+\stackrel{+}{\Rightarrow} αn: 从α1出发, 经过1步或若干步推出

  • 假定G是一个文法, S是G的开始符号. 如果S ⇒∗\stackrel{*}{\Rightarrow} α, 则称α是一个句型

  • 只含有终结符号的句型是一个句子

  • 文法G所产生的句子的全体是一个语言, 记为L(G)

  • 最左推导和最后推导: 先替换最左或者最右

  • 语法树: 用一张图表示一个句型的推导, 称为语法树

    • E(E) -> i | E+E | E*E | (E)
    • (i*i+i)
    graph TD
  L1[E] --> L21["("]
  L1[E] --> L22[E]
  L1[E] --> L23[")"]
  L22   --> L31[E]
  L22   --> L32[+]
  L22   --> L33[E]
  L31   --> L41[E]
  L31   --> L42[*]
  L31   --> L43[E]
  L33   --> L44[i]
  L41   --> L51[i]
  L43   --> L52[i]
    graph TD
  L1[E] --> L21["("]
  L1[E] --> L22[E]
  L1[E] --> L23[")"]
  L22   --> L31[E]
  L22   --> L32[+]
  L22   --> L33[E]
  L31   --> L41[E]
  L31   --> L42[*]
  L31   --> L43[E]
  L33   --> L44[i]
  L41   --> L51[i]
  L43   --> L52[i]
    graph TD
  L1[E] --> L21["("]
  L1[E] --> L22[E]
  L1[E] --> L23[")"]
  L22   --> L31[E]
  L22   --> L32[+]
  L22   --> L33[E]
  L31   --> L41[E]
  L31   --> L42[*]
  L31   --> L43[E]
  L33   --> L44[i]
  L41   --> L51[i]
  L43   --> L52[i]

  • 文法的二义性: 如果一个文法存在某个句子对应两颗不同的语法树, 则说这个文法是二义的

  • 语言的二义性来自语言本身, 和文法无关, 二义性问题是不可判定问题

  • 形式语言分为0,1,2,3型, 0型 包含 1型 包含 2型 包含 3型

词法分析

词法分析的核心任务是将源代码中的字符流分解为有意义的符号(称为词法单元或token)

  • 词法分析器的结构：输入缓冲区 -> 预处理子程序(剔除无用的空白跳格、回车，区分标号区、连接续行和给出句末符等) -> 扫描缓冲区 -> 扫描器 -> 单词符号
  • 扫描缓冲区：使用起点指示器和搜索指示器
    • 将缓冲区分为两个半区， 两个半区互补使用
  • 单词符号的识别：超前搜索
    • 关键字识别
      • 以Fortran语言的DO关键字为例：DO99K=1,10 -> DO 99 k = 1, 1=；DO99k=1.0，只有超前扫描到,和.才能知道是干嘛的
    • 标识符识别：字母开头的字母数字串，后跟界符或算符
    • 常数识别：识别出算数常数并将其转变为二进制内码表示
    • 算符和界符的识别
  • 几点限制——不必使用超前搜索（可读性强，词法分析方便）
    • 所有关键字都是保留字
    • 关键字作为特殊的标识符来处理，使用保留字表
    • 如果关键字（基本字）、标识符和常数之间没有确定的运算符或界符作间隔，则必须使用一个空白符做间隔
  • 状态转换图：一张有限方向图
    • 只包含有限个状态，其中一个为初态，至少要有一个终态
  • 一个简单的词法分析程序，由Golang实现，Copilot给出了一个极简的代码用于学习
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

package main

import (
	"fmt"
	"unicode"
)

type Token struct {
	Kind string
	Lit  string
}

const (
	Reset = "\033[0m"
	Red   = "\033[31m"
	Blue  = "\033[34m"
)

func RedString(str string) string {
	return Red + str + Reset
}

func BlueString(str string) string {
	return Blue + str + Reset
}

var keywords = map[string]string{
	"package": "KW_PACKAGE",
	"func":    "KW_FUNC",
	"var":     "KW_VAR",
	"return":  "KW_RETURN",
	"int":     "KW_TYPE_INT",
	"println": "KW_BUILTIN_FUNC",
	"main":    "KW_MAIN",
}

func main() {
	srcCode := `
package main

func main() {
	var a int = 10
	println(a)
}
`
	println(srcCode)
	tokens := Lex(srcCode)
	for _, tok := range tokens {
		fmt.Printf("Kind: %-15s Lit: %s\n", tok.Kind, tok.Lit)
	}
}

func Lex(src string) []Token {
	var tokens []Token
	r := []rune(src)
	for i, n := 0, len(r); i < n; {
		ch := r[i]
		// whitespace
		if unicode.IsSpace(ch) {
			if ch == '\n' {
				tokens = append(tokens, Token{Kind: "NEWLINE", Lit: "\n"})
			}
			i++
			continue
		}
		// identifier / keyword
		if unicode.IsLetter(ch) {
			j := i + 1
			for j < n {
				if unicode.IsLetter(r[j]) || unicode.IsDigit(r[j]) {
					j++
				} else {
					break
				}
			}
			lit := string(r[i:j])
			if tokenType, ok := keywords[lit]; ok {
				tokens = append(tokens, Token{Kind: RedString(tokenType), Lit: BlueString(lit)})
			} else {
				tokens = append(tokens, Token{Kind: "IDENTIFIER", Lit: lit})
			}
			// update i
			i = j
			continue
		}
		// number literal
		if unicode.IsDigit(ch) {
			j := i + 1
			for j < n && unicode.IsDigit(r[j]) {
				j++
			}
			tokens = append(tokens, Token{Kind: "NUMBER", Lit: string(r[i:j])})
			i = j
			continue
		}
		if ch == ':' && i+1 < n && r[i+1] == '=' {
			tokens = append(tokens, Token{Kind: "OP_ASSIGN", Lit: ":="})
			i += 2
			continue
		}
		// string literal
		if ch == '"' {
			j := i + 1
			for j < n && r[j] != '"' {
				if r[j] == '\\' && j+1 < n {
					j += 2
				} else {
					j++
				}
			}
			if j < n && r[j] == '"' {
				j++
			}
			tokens = append(tokens, Token{"STRING", string(r[i:j])})
			i = j
			continue
		}
		// single char symbol
		tokens = append(tokens, Token{"SingleCharacterSymbol", string(ch)})
		i++
	}

	return append(tokens, Token{Kind: "EOF", Lit: ""})
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


package main

func main() {
        var a int = 10
        println(a)
}

Kind: NEWLINE         Lit:

Kind: KW_PACKAGE Lit: package
Kind: KW_MAIN Lit: main
Kind: NEWLINE         Lit:

Kind: NEWLINE         Lit:

Kind: KW_FUNC Lit: func
Kind: KW_MAIN Lit: main
Kind: SingleCharacterSymbol Lit: (
Kind: SingleCharacterSymbol Lit: )
Kind: SingleCharacterSymbol Lit: {
Kind: NEWLINE         Lit:

Kind: KW_VAR Lit: var
Kind: IDENTIFIER      Lit: a
Kind: KW_TYPE_INT Lit: int
Kind: SingleCharacterSymbol Lit: =
Kind: NUMBER          Lit: 10
Kind: NEWLINE         Lit:

Kind: KW_BUILTIN_FUNC Lit: println
Kind: SingleCharacterSymbol Lit: (
Kind: IDENTIFIER      Lit: a
Kind: SingleCharacterSymbol Lit: )
Kind: NEWLINE         Lit:

Kind: SingleCharacterSymbol Lit: }
Kind: NEWLINE         Lit:

Kind: EOF             Lit:

正规集和正规式

  • 正规式是一种表示（描述）正规集的代数工具，它用一套规范的符号来精确地描述一个正规集
  • 正规集是由正规式描述的字符串集合, 包含所有符合正规式描述的字符串, 一个正规集就是有限状态自动机能够接受的所有字符串的集合
  • 正规式(R)是一种描述形式, 正规集L(R)是被描述的字符串集合
  • 闭包表示由集合A的元素重复出现任意次所构成的所有字符串的集合：A∗=A0∪A1∪A2∪A3∪⋯∪An∪…A^* = A^0 \cup A^1 \cup A^2 \cup A^3 \cup \dots \cup A^n \cup \dots
  • 正闭包：A+=A1∪A2∪A3∪…A^+ = A^1 \cup A^2 \cup A^3 \cup \dots

确定有限自动机DFA(Deterministic Finite Automata)

状态机的本质是分段处理输入，将输入字符串的处理过程分解成多个状态和状态转移，目的是处理特定模式的字符串

  • DFA是一个五元组(S,Σ,f,S0,F)(S, \Sigma, f, S_0, F)

    • S: 有限状态集合
    • Σ: 有限输入符号集合(字母表)
    • f: 状态转移函数, 是S × Σ → S的单值部分映射，f(s,a)=s’ 表示当现在状态为s, 输入符号为a时, 转移到下一状态s’，s’是s的一个后继状态
    • S0∈S S_0 ∈ S 是唯一的一个初态
    • F⊆SF ⊆ S：终态集（可空）

  • 举例说明：假设要判断一个字符串是否是以 ab结尾的字符串，肯定要找a和b，并且读到b之后，后面没有其他的了

    • 状态集合S={S0, S1, S2}，S0是初始状态，表示没有看到a呢，S1表示已经看到a了，正在找b，S2表示已经看到ab了，这是目标格式
    • 输入符号集合Σ={a, b}
    • 初态S0
    • 终态F={S2}：表示已经成功匹配到目标模式 ab 结尾
    • 状态转移函数f定义如下:
      • f(S0, a) = S1：读到a，从初态S0转移到状态S1，表示已经读到了a，要去找b
      • f(S0, b) = S0：读到b，还是在初态S0，表示还没有读到a
      • f(S1, a) = S1：读到a，还是在状态S1，表示已经读到了a，要继续找b
      • f(S1, b) = S2：读到b，从状态S1转移到状态S2，表示已经读到了ab
      • f(S2, a) = S1：读到a，从状态S2转移到状态S1，表示已经读到了a，要去找b
      • f(S2, b) = S0：读到b，从状态S2转移到初态S0，表示还没有读到a
    • 一段简单的代码如下
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    enum State {
    Start,
    SawA,
    SawAB,
}

fn transition(state: State, input: char) -> State {
    match state {
        State::Start => {
            match input { 'a' => State::SawA, _ => State::Start }
        }
        State::SawA => {  // 已经看到了a
            match input { 'a' => State::SawA, 'b' => State::SawAB, _ => State::Start }
        }
        State::SawAB => {
            match input { 'a' => State::SawA, 'b' => State::Start, _ => State::Start }
        }
    }
}

fn main(){
    let test_list:[&str;9] = ["ab","","a","b","aba","ab","abab","aab","bba"];
    for str in test_list {
        let mut current_state = State::Start;
        for ch in str.chars() {
            current_state = transition(current_state, ch);
        }
        match current_state {
            State::SawAB => println!("'{}' is accepted by the DFA", str),
            _ => println!("'{}' is rejected by the DFA", str),
        }
    }
}

非确定优先自动机NFA(Nondeterministic Finite Automata)

  • 每个状态对每个输入符号可以有多个可能的下一个状态(甚至没有状态)
  • 可以允许空字符串转移
  • 输入字符串的每个字符可能有多条状态转移路径（并行考虑所有可能性）
  • 状态转换可能有多个分支

语法分析

属性文法和语法制导翻译

语义分析和中间代码生成

符号表

优化

目标代码生成

更新于 2025-11-27 
返回 | 主页

目录