多读书多看报

编译原理

Tagslinux
AI custom autofillThis document discusses compiler principles and grammar types in depth.
AI keywords

什么是编译原理?

编译原理一般指的是把(编译型)高级语言(c/c++, rust, go) 转换(编译)为机器代码的过程.

java属于半编译型语言, 代码执行前被编译为字节码, 然后由java虚拟机运行

python, js属于解释型语言, 边执行边把代码编译为对应虚拟机的代码表示, 然后由虚拟机解释执行

类型

namedesc
编译程序把高级程序语言变为机器语言(汇编或机器码)
汇编程序把汇编语言变为机器码

还有交叉汇编, 交叉编译, 反汇编, 反编译, 可变目标编译程序….的分类. 我觉得这不重要

编译系统的组成

一般可以分为前端 和 后端

前端把高级语言变为中间代码。这个中间代码是一种与机器无关的表示形式，通常是三地址码或四元式。后端则负责将中间代码转换为目标机器代码，并进行代码优化。这种分层设计使得编译器的前端可以适用于多种高级语言，而后端则可以针对不同的目标机器进行优化。

前端又包括: 源代码 → 词法分析(记号流) → 语法分析(语法树) → 语义分析(类型检查) (→中间代码生成)

文法

文法G是一个四元组 G=(VN,VT,P,S)G = (VN, VT, P, S)

  • VN → variable 变量, 也成为非终结符
  • VT → terminal 终结符, 常见有 ;
  • P → production 产生式 表示语法规定的状态转移形式
  • S → S∈V 为文法的开始符号

Chromsky 四种文法

0型到3型父级关系, 也就是如果是1型则也需要满足0型的规则

0型

都是, 除了瞎写的, 或写错的

α→βα,β∈(VN∪VT)∗alpha ightarrow eta \ alpha,eta in (VNcup VT)*

1型 上下文相关文法

α→β∣α∣≤∣β∣alpha ightarrow eta \ |alpha| le |eta|

与0型相比, 多了产生式左部的模要≤右部的

2型 上下文无关文法

α→βα∈VNalpha ightarrow eta \ alpha in VN

α只能是终结符

3型 正则文法

A→αB∣α右线性orA→Bα∣α左线性A ightarrow alpha B|alpha quad 右线性 \ or\ A ightarrow Balpha|alpha quad 左线性

最严格, 很少出现

LL(1)文法

  • 无二义性
  • 无左递归

判断

找到产生式中有 | 或的部分, 判断每个部分的 First 集无公共元素, 如果存在 ε(空串) 哪就要再判断右部的各部分的First集和左部的Follow集无公共元素

A→α∣β(...)First(α)∩First(β)∩.....=∅∀x∈α,β...,x≠∅First(α)∩First(β)∩.....∩Follow(A)=∅∃x∈α,β...,x=∅A ightarrow alpha | eta (...) \ First(alpha) cap First(eta) cap..... = emptyset quad orall x in {alpha,eta...}, x eq emptyset \ First(alpha)cap First(eta)cap ..... cap Follow(A) = emptyset quad exists x in {alpha, eta ...}, x=emptyset

习题相关

消除左递归

消除左递归的目的在于, 消除文法推导的二义性(公共前缀), 把左递归变为右递归

A→Aα∣β⇒{A→βA′A′→αA′∣εA ightarrow Aalpha | eta Rightarrow left{ egin{array}{l} A ightarrow eta A' \ A' ightarrow alpha A' | arepsilon end{array} ight.

消除回溯

目的同上

A→δβ1∣δβ2∣δβ3∣β4∣...∣βnto{A→δA′∣β4∣...∣βnA′→β1∣β2∣β3A ightarrow delta eta_1 | delta eta_2 | delta eta_3 | eta_4 | ... |eta_n \ to \ left{ egin{array}{l} A ightarrow delta A' | eta_4|...|eta_n \ A' ightarrow eta_1 | eta_2 | eta_3 end{array} ight.