第3章上形式语言简介.pptVIP

第3章上 形式语言简介 3.1 文法和语言 3.2 推导与语法树 3.1 文法和语言 文法是程序语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。 3.1.1 文法和语言的概念 1．语言 通常我们用Σ表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么，对字母表Σ来说，Σ*上的任意一个子集都称为Σ上的一个语言，记为L(LΣ*)，该语言的每一个字符串称为语言L的一个语句或句子。 每一个形式语言都是某字母表上符号串的一个集合，反之字母表上符号串的一个集合可定义为一个形式语言。例如，C语言是其基本符号字母表上符号串的集合，而每个C语言程序是基本符号的符号串。再如，假定∑={a,b,c}，则 L1={a,b,c} L2={a,aa,ab} L3={c,cc} 均可表示字母表∑={a,b,c}上的一个形式语言。 当一语言是有穷集合时，可用上述枚举方法来表示语言。但如果语言是无穷集合，那就无法用这种枚举方法。我们要设计出表示无穷集合的强有力的工具。文法就是这样一种工具。 设∑={a,b}，则根据定义∑+表示a和b的所有可能的符号串的集合。下面用A表示∑+则A可表示成： A →a A →b ⑴ A →Aa A →Ab 其中，符号“→”读作“生成”。 显然，由A生成的符号串都属于∑+，另一方面，可用归纳法证明∑+ A，因此有A= ∑+。 考虑∑={a}上的符号串集合：A={a2n|n≥1} 显然aa ∈A；如果yaa ∈A，因此，A可按下法构造： A →aa A →Aaa ⑵ 考虑∑={a,b}上的符号串集合：A={abna|n ≥1} 显然A可表示为 A=aBa B={bn|n ≥1} 其中B是我们会构造的，于是可以写出： ① A → aBa ② B → b ⑶ ③ B →Bb 在这里A是所要构造的，B是辅助集合。这样A →aBa可理解为A可生成aBa。若用“ ”表示“推出”，则我们有 A aBa aBa aBba aBba aBbba aBbba abbba 于是得出：A推出符号串abbba，即abbba ∈ A。 2．文法 文法通常表示成四元组G=(VT，VN，S，ξ)，其中： (1)VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号； (2)VN为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN=Φ； (3)S为一文法开始符，是一个特殊的非终结符号，即S∈VN； (4)ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作 α→β或α::=β 读作“α是β”