编译原理基础

β=abc的头，尾，固有头，固有尾分别为：

ε, a, ab, abc
ε, c, bc, abc
ε, a, ab
ε, c, bc

z=xxx…x称为x的方幂

x^0=ε, x^1=x, x^2=xx

A={a, b}, B={c, d} => AB={ac, ad, bc, bd}

闭包

∑={0, 1} => ∑*={ε, 0, 1, 00, 01, 10, 11, ….}

∑*称为∑的闭包，而∑^+ 称为∑的正闭包

∑*=∑^0 U ∑^1 U ∑^2 U ...

∑^+ = ∑ ∑* = ∑ *∑

ε ∈ ∑*

VN表示非终结符，VT表示终结符， P表示规则的集合，S为开始符

v = y a δ , w = y β δ 若 a -> β 则 w 是 v 的直接推导，记作： v => w

eg:

v=0S1，w=0011，直接推导为：0S1 => 0011，使用的规则为：S -> 01，此处 y=0，δ=1

句型与句子

S -> 01，v = 0S1 => 00s11 => 000s111 => 00001111 = w，记作 v =>* w

若符号串x是由识别符号推导出来的，即 S =>* x，则称 x 是文法 G[S] 的句型，若 x 都属于终结符，即 x ∈ VT*(终结符闭包)，则称 x 是文法 G[S] 的句子

文法描述的语言是该文发一切句子的集合

文法类型

0型文法

1型（上下文有关）文法

2型（上下文无关）文法

3型（正规）文法

A -> aB 或 A -> a，其中 A 和 B 都是非终结符，a ∈ VT*

eg：

G=({S, A, B},{0, 1}, P, S)，其中P由 S -> 0A, S -> 1B s -> 0, A -> 0A, B -> 1 为非终结符

语法树

由语法树可得句型 aabbaa ，则将其称为推导树的结果，也把推导树叫做句型 aabbaa 的语法树

推导分为最左推导和最右推导，其中最右推导为规范推导