【北航编译原理笔记】1. 基础知识 【北航编译原理笔记】2. 词法分析 【北航编译原理笔记】3. 语法分析 【北航编译原理笔记】4. 语义分析与符号表
翻译程序(三种): 编译程序 高级程序设计语言->机器语言 汇编程序 汇编语言->机器语言 解释程序 中间形式->机器语言
5+2 词法分析 语法分析 语义分析-生成中间代码 代码优化 生成目标程序 错误处理 符号表管理
乘积(笛卡儿积): A 2 = A ∗ A A^2 = A\ * \ A A2=A ∗ A. 幂次 正闭包: A + = A 1 U A 2 U . . . U A ∞ A^+ = A^1\ U\ A^2\ U\ ...\ U\ A^\infin A+=A1 U A2 U ... U A∞. 克林闭包: A ∗ = A 0 U A 1 U A 2 U . . . U A ∞ A^* = A^0\ U\ A^1\ U\ A^2\ U\ ...\ U\ A^\infin A∗=A0 U A1 U A2 U ... U A∞.
字母表: 符号的非空有限集 符号: 字母表中的元素 符号串: 符号的有穷序列 空符号串: 无任何符号的符号串 A 0 A^0 A0 或者 ε \varepsilon ε. 全集: 字母表的克林闭包
递归定义符号串 符号串的相等判断、长度比较、联接 符号串集合的乘积: A B = { x y ∣ x ∈ A , y ∈ B } AB = \{xy\ | x \in A, y \in B\} AB={xy ∣x∈A,y∈B}.
小写字母的s-z: 符号串 大写字母的A-R: 符号串集合 其他: 符号
语法（推导）树：自顶向下 or 自底向上
G = ( S ( 开 始 符 号 即 识 别 符 号 ) , V n ( 非 终 结 符 号 集 ) , V t ( 终 结 符 号 集 ) , P ( 规 则 集 合 ) ) G = (S(开始符号即识别符号), V_n(非终结符号集), V_t(终结符号集), P(规则集合)) G=(S(开始符号即识别符号),Vn(非终结符号集),Vt(终结符号集),P(规则集合)).
: : = ::= ::=与 → \rightarrow →都表示推导
扩充的BNF(巴科斯范式)表示: < , > , : : = , ∣ , { , } , [ , ] , ( , ) < , >, ::=, |, \{, \}, [, ], (, ) <,>,::=,∣,{,},[,],(,). 尖括号( < > )内包含的为必选项。 方括号( [ ] )内包含的为可选项。 大括号( { } )内包含的为可重复0至无数次的项。 括号 () 表示分组的意思 竖线( | )表示在其左右两边任选一项，相当于"OR"的意思。 ::= 是“被定义为”的意思。
竖线( | )表示在其左右两边任选一项，相当于"OR"的意思。::= 是“被定义为”的意思。
语法图也可以表示程序语言的语法.
注意区分以下两种推导: B → ∗ A B\ \xrightarrow{*}\ A B ∗ A. (A可以是B本身,至少0次推导) B → + A B\ \xrightarrow{+}\ A B + A. (A不可是B本身,至少1次推导)
直接递归 间接递归 左递归 右递归
给定文法 G [ Z ] G[Z] G[Z]: 句型: $ Z \xrightarrow{} w, w \in V^$. 句子: $ Z \xrightarrow{} w, w \in V^_t$. 语言: L(G[Z]): $ { w\ |\ Z \xrightarrow{+} w, w \in V^*_t }$.
$ Z \xrightarrow{+} w, w \in $.
无二义性文法的句子只有一棵语法树. 最右推导和最左推导都可能会产生不同的语法树(没有规定优先级),导致文法的二义性.
给定文法 G [ Z ] G[Z] G[Z], w = x u y ∈ V + w = xuy \in V^+ w=xuy∈V+,为给文法的句型: 若 Z → ∗ x U y Z \xrightarrow{*}xUy Z∗ xUy, U → + u U\xrightarrow{+}u U+ u,则u是句型w相对于U的短语 若 Z → ∗ x U y Z \xrightarrow{*}xUy Z∗ xUy, U → u U\xrightarrow{}u U u,则u是句型w相对于U的简单短语 其中 U ∈ V n , u ∈ V + , x , y ∈ V + U \in V_n, u \in V^+, x, y \in V^+ U∈Vn,u∈V+,x,y∈V+.
任意句型的最左简单短语称为该句型的句柄
任何句型本身一定是相对于起始符号(识别符号)的短语 一个句型只有一个句柄,可以有多个短语和简单短语
理论上已证明: 文法的二义性是不可判定的 现在解决办法: 提出限制条件(优先级)
有害规则: 自身推导自身,则会导致文法的二义性( U → U U\rightarrow U U→U) 多余规则: 始终用不到的规则(不可达) 不能推导出全部是终结符号串(不活动) 若文法中不含有以上类型的规则,则称文法是压缩过的
乔姆斯基 根据规则的不同,分成4类文法 0型文法: 其描述能力相当于图灵机，可使用任何的语法描述形式. 1型文法: 其描述能力相当于线性有界自动机，上下文有关文法.(式子左面可以有多个字符，但是必须有一个终结字符) 2型文法: 其描述能力相当于下推自动机，上下文无关文法.(式子左边只能有一个字符，而且必须是非终结字符) 3型文法(正则文法): 其描述能力相当于有限自动机，是"左线性"的.
