【北航编译原理笔记】1. 基础知识 【北航编译原理笔记】2. 词法分析 【北航编译原理笔记】3. 语法分析 【北航编译原理笔记】4. 语义分析与符号表
功能: 根据词法规则识别及组合单词,进行词法检查 对数字常数完成 数字字符串 -->二进制数值 转换 删去空格字符和注释
单词种类: 保留字, 标识符, 常数, 分界符 单词内部形式: 单词类别 + 单词值 单词类别: 按单词种类分类: 标识符, 无符号常数(整), 无符号浮点数, 布尔常数, 字符串常数, 保留字, 分界符. 保留字和分界符采用一符一类
常用状态图来作词法分析 先将正则表达式转化为非确定自动机(NFA: Non-deterministic Finite Automata)(存在某一个状态,对于同一个输入有不同的结果) 再将非确定自动机转化为确定自动机(DFA: Deterministic Finite Automata) 将确定自动机简化(直到不存在等价状态): 利用一致性状和蔓延性状态不断"分区",最终还在一个分区里的状态即可以简化 画图以及程序
状态图中: 双圈表示"终止符",圈内一般是非终止符,起始圈是新加进去的.
正则文法 和 正则表达式 的相互转化:
A → x B , B → y ⟺ A → x y A\rightarrow xB, B\rightarrow y \ \ \ \ \ \Longleftrightarrow A \rightarrow xy A→xB,B→y ⟺A→xy. A → x A ∣ y ⟺ A → x ∗ y A\rightarrow xA\ |\ y\ \ \ \ \ \ \ \ \ \ \ \ \ \Longleftrightarrow A \rightarrow x^*y A→xA ∣ y ⟺A→x∗y. A → x , A → y ⟺ A → x ∣ y A\rightarrow x, A\rightarrow y\ \ \ \ \ \ \ \ \Longleftrightarrow A \rightarrow x\ |\ y A→x,A→y ⟺A→x ∣ y.对于二义性问题:
最长匹配原则, 有更长则识别更长的优先匹配原则, 规则序列越前优先级越高, 写规则序列时要注意NFA的确定化: 集合 I I I的 ε − \varepsilon- ε−闭包: ( M M M是自动机, I I I是 M M M的状态集一个子集) 若 s ∈ I s \in I s∈I,则 s ∈ ε − C l o s u r e ( I ) s \in \varepsilon-Closure(I) s∈ε−Closure(I). 若 s ∈ I s \in I s∈I,则从 s s s出发经过任意条 ε \varepsilon ε弧而能到达的任何状态都属于 ε − C l o s u r e ( I ) \varepsilon-Closure(I) ε−Closure(I). ε − C l o u r e ( I ) \varepsilon-Cloure(I) ε−Cloure(I)是集合 I I I的 ε − \varepsilon- ε−闭包: J J J是从 I I I出发,沿 a a a弧到达的状态所组成的集合. I a = ε − C l o s u r e ( J ) I_a = \varepsilon-Closure(J) Ia=ε−Closure(J).
