[编译原理词法分析..pptVIP

2.2 文法和语言的定义 如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 文法和语言的定义 语言的有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。） 文法即是以生成方式描述语言的，即语言中的每个句子可以用严格定义的规则来构造. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 文法和语言的定义 文法 G 定义为四元组（VT，VN，S，P）： VT ：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c…0,1..），代表语言中不可再分的基本符号，如汉语中的汉字、C语言中的标识符。 VN ：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C…），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，C语言中的语句、表达式、函数等 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 文法和语言的定义 S 是一个特殊的非终结符号，称为开始符号（start symbol） S 至少要在一条产生式中作为左部出现 P是一个产生式（production）的集合 产生式（重写规则、生成式）：形如α→β的（α，β）有序对，且α∈V+，β∈V* ，其中 V = （VT∪VN） α称为产生式的左部，不能为空ε β称为产生式的右部，可以为空ε（如：A → ε ） Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 文法和语言的定义 例1：文法 G = （VT，VN，S，P） VN = { S } VT ={ 0, 1 } P = { S→0S1, S→01 } 可以只写出产生式，通过产生式可以得到文法的其它部分 左部相同的产生式可以写在一起，如: S →0S1 | 01 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 文法和语言的定义 例2：文法 G = （VT，VN，S，P） VN = {标识符，字母，数字} VT = {a,b,c,…x,y,z,0,1,…,9} P = { 标识符→字母 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…, 数字→9 } S = 标识符 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 文法和语言的定义 推导（derivation）与归约（reduction）： 直接推导与直接归约 如果 A → γ 是 G 的一条产生式，则称用αγβ代替αAβ为一步直接推导，记为αAβ=αγβ；称用αAβ代替αγβ为一步直接归约，记为αγβ=αAβ 推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 200