第2章文法和语言第2章文法和语言(P12)学习重点形式语言(P12)形式语言2.1字母表和符号串(P12)2.1字母表和符号串2.1字母表和符号串2.1字母表和符号串2.1字母表和符号串2.1字母表和符号串2.1字母表和符号串2.1字母表和符号串2.1字母表和符号串例：例例文法G的形式定义：G=(Vn，Vt，P，Z)Vn(非终结符号集)是一个由非终结符号（一般是大写字母或用<汉字>）构成的非空有穷集合。Vt(终结符号集)是一个由终结符号（如小写字母、数字、标点符号等）构成的非空有穷集合。Vt∩Vn=φ，Ｖ＝Vt∪Vn，V是该文法的字母表或词汇表。P(产生式集)是一个由产生式或规则构成的非空有穷集合。产生式的形式为：α→β或α::=β产生式的左部α∈V+，即α不能为空，产生式的右部β∈V*，“→”或”“::=”含义相同，表示“定义为”或“由……组成”。Z是文法的识别符号或开始符号，Z∈Vn，要求Z至少必须在某个产生式的左部出现一次。2.2文法2.2文法2.2文法2.2文法2.2文法2.2文法2.2文法2.2文法2.2文法2.13文法和语言分类（P26）2.13文法和语言分类（P26）2.13文法和语言分类（P26）2.13文法和语言分类（P27）2.13文法和语言分类2.13文法和语言分类文法的四种分类2.13文法和语言分类直接推导（）：α→β是文法G的一个产生式，x,y∈V*，符号串xαy中的非终结符号α用β替换，从而得到符号串xβy，则表示为：xαyxβy其中“”读为“直接推导出”或“直接产生”。即称xαy直接推导出xβy,或xαy直接产生xβy。若从反方向看，则称xβy直接归约到xαy。显然，文法的产生式右部是其左部的直接推导。2.3推导推导（）：如果存在一直接推导序列α0α1……αn，则表示为：α0αn其中，“”读为“推导出”或“产生”，即α0推导出或产生αn。若从反方向看，则称αn归约到α0。n是推导长度，要求n>0。2.3推导广义推导（）：如果有α0αn或α0=αn,即n≥0，则表示为：α0αn其中，“”读为“广义推导出”或“广义产生”。若从反方向看，则称αn广义归约到α0。2.3推导2.3推导2.3推导2.4句型和句子（P18）2.4句型和句子2.4句型和句子2.5语言（P19）2.5语言2.5语言2.5语言2.5语言2.6递归规则与递归文法(P20)2.6递归规则与递归文法2.6递归规则与递归文法2.6递归规则与递归文法2.6递归规则与递归文法2.8语法树(P21)2.8语法树2.8语法树2.10由树构造推导过程（P23）2.10由树构造推导过程2.10由树构造推导过程2.10由树构造推导过程2.7短语、简单短语和句柄（P21）2.7短语、简单短语和句柄2.9子树和短语(P22)2.9子树和短语2.9子树和短语2.11文法的二义性（P23）2.11文法的二义性2.11文法的二义性2.11文法的二义性2.11文法的二义性2.12有关文法的实用限制（P25）2.12有关文法的实用限制2.12有关文法的实用限制2.12有关文法的实用限制2.12有关文法的实用限制小结习题（P27）作业1作业1作业2