第二章高级程序设计语言.pptVIP

第二章 高级语言及其语法描述 符号串集合V自身的n次（连接）积记为： Vn = V V…V =Vn-1V =VVn-1 (n个V) 规定 V0 = {?}. V的闭包：令： V* = V0 ∪ V1 ∪ V2 ∪ … 称 V*是V的闭包。 V的正则包（正闭包，正则闭包）：记V+ = VV*, 称 V+是V的正则包，即V+ =V1 ∪ V2 ∪ V3 ∪ …。 一个例子 有一个字母表：A={a,b,c} A0={ε} A1=？ A2=？ A3=？ A*=？ A+=? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第二章 高级语言及其语法描述 文法是描述语言的语法结构的形式规则（即语法规则）。 所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位)是完全独立于这种范畴可能出现的环境的。 特点：独立性 缺点：不能用来描述自然语言，但对于程序语言基本上够用，所以以后凡“文法”一词，若无特殊说明，均指上下文无关文法 引例 例子：对于英文句子：He gave me a book. 是由如下语法规则产生的： 2.3.1 上下文无关文法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第二章 高级语言及其语法描述 由语法规则“推导”出句子的过程 “推导” 过程对应的语法分析树 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第二章 高级语言及其语法描述 上下文无关文法的定义 一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。 形式上定义一个上下文无关文法Ｇ是一个四元式（ＶＴ，ＶＮ，Ｓ，P） 上下文无关文法的形式定义 形式上定义一个上下文无关文法Ｇ是一个四元式 （ＶＴ，ＶＮ，Ｓ，P）其中 ＶＴ是一个非空有限集，它的每一个元素称为终结符号； ＶＮ是一个非空有限集，它的每一个元素称为非终结符号，ＶＴ∩ＶＮ＝?； Ｓ是一个非终结符号，称为开始符号； P是一个产生式（有限）集合，每个产生式形式是A→?　，其中，Ｐ∈ＶＮ，　　 ? ∈（　ＶＴ∪ＶＮ）＊开始符号S至少必须在某一产生式的左部出现一次。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第二章 高级语言及其语法描述 上下文无关文法的定义 所谓终结符号乃是组成语言的基本符号，“终结”含义在于是具有独立意义的最小语法单位，即不能再分解了的语法单位，如， He， book，如程序语言中的基本字，标识符，常数，算符和界符等.如：{ *,+,a,b,c,(,),,,+,-} 终结符号一般用小写字母表示 上下文无关文法 所谓非终结符号（也称语法变量）用来代表语法范畴。如“算术表达式”、“布尔表达式”、“过程”等。一个非终结符代表一个一定的语法概念。因此非终结符是一