编译原理的基本概念

编译原理的一些基本概念

语法描述的几个基本概念

字母表：一个有穷字符集，记为∑

字母表中每个元素称为字符

∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列

不包含任何字符的序列称为空字，记为ε

用∑*表示∑上的所有字的全体，包含空字ε

例如: 设 ∑={a， b}，则，∑*={ε,a,b,aa,ab,ba,bb,aaa,...}

∑* 的子集U和V的连接（积）定义为UV ＝ { αβ | α∈ U & β∈ V }

V自身的 n次积记为

乔姆斯基形式语言体系

四种类型文法描述能力比较

程序设计语言不是上下文无关语言，甚至不是上下文有关语言

对于现今程序设计语言，在编译程序中，仍然采用上下文无关文法来描述其语言结构