编译原理 概念小结

BNF : 用来表示语法 eg. ->

字母表（符号集）：字母表是元素的非空有穷集合。字母表中的元素 称为符号或字符，因此字母表也称为符号集，用大写字母A或希腊字母∑表示

符号串：由字母表中的符号组成的任何有穷序列称为符号串，也称为串或字符串。用小写希腊字母表示符号串，如如 ω =STR

符号串的连接：设 ω 和 υ是两个符号串，如果将符号串 υ 直接拼接在符号串 ω 之后，则称此操作为符号串 ω 和 υ的连接，记作 ω υ。

eg. ω=abc，υ =xyz则 ω υ=abcxyz

符号串的方幂：设 ω 是某字母表上符号串，把 ω 自身连接 n 次得 到符号串 υ ，即 υ = ω ω … ω (n个 ω ) ，称 υ 是符号 串 ω 的n次幂，记作 υ = ω ^n。

符号串集合的乘积：设A、B 是两个符号串集合，AB表示A与B的乘积，则有定义 AB={ ω υ| ( ω ∈A)∧( υ∈B) }

如：设A={ab,c}, B={d,ef}, 则 AB={abd, abef, cd, cef}

符号串集合的方幂：设A是符号串集合，A自身的乘积可以用方幂表示。A0= { ε } A^1=A A^2=AA A^3= A^2A =AAA

符号串集合的并（并集）

符号串集合的闭包：

文法：一部文法G是一个四元组 G =（ VN, VT, S, P）

语言的非形式化定义：给定一部文法G, 从G的开始符号S出发，反复使 用产生式对非终结符进行替换，最后所得到的终结符 号串的全体，即为文法G所描述的语言L(G)。

如：设有文法G： S → P | aPb，P → ba | bQa，Q → ab ；

L(G)={ba, baba, abab, ababab}

直接推导=>：有 ν = α Aβ=> α γβ= ω ( α ,β,γ∈(VN∪VT)*),当且 仅当P中存在一条规则A ->γ，称 ν 直接推导出 ω （或 ω 直接归约到 ν ），记作： ν => ω 。

直接推导序列： 则 ν 经过n步(n>0)可以推导出ω ，记作:ν =(+)>ω 。当ν=>ω 或 ν=ω ，记作： ν(*)=>ω

句型：设有文法G[S]，若 S =(*)> α ( α ∈(VT∪VN)*)，则称 α 为G[S]的句型

句子：设有文法G[S] , 若S =(*)>α ( α∈VT*) ，则称 α 为G[S]的句子。

最左(右)推导

规范推导/规范句型/规范归纳：最右推导也称为规范推导 。仅用规范推导得到的句型称为规范句型 。规范推导的逆序为规范归约。

递归文法：设有文法G，A→ γ是G的产生式，若 γ 具有 α A β的形式，或 γ =(+)>α A β ，则称G是递归文法。

语言：文法 G所产生（描述）的语言L(G)： L(G) = { α | α ∈VT*∧ S =(+)> α ，S是文法 Ｇ 的开始符号 }

文法等价：若 L(G1)= L(G2)，则称文法G1和G2是等价的

EBNF：扩充BNF，假如{} () []

语法图：