编译原理 chapter2 语言及其文法学习课件.ppt

*字母表是一个有限的符号集（龙2p72）*符号的出现次数*如果将连接运算看作是两个串的乘积**每一个式子表示规则上述形式描述了句子的构成规则，简称为规则从这个例子中，可以提取一些句子的组成规则文法中的符号分为两类，其中尖括号括起来部分……，未用尖括号括起来部分。（cy）如何把这些文法知识“教给”计算机？（cy）首先，让计算机知道有两种不同类型的符号（cy）其次，把这些构成规则教给计算机（cy）于是，得到文法的形式化定义（cy）如何定义语言的文法？对语言在形式上进行方方面面的限制，才能适合于计算机处理计算机语言——形式化的语言，不能像日常的自然语言那样随意——计算机（自动机）可处理的语言能够形式化表示的事务才能由计算机自动化处理产生这些句子的规则也称为产生式(Production)图中的规则还包括……**参见形式语言p220→表示“consistof”（参见形式语言p78）Α表达式的含义：语言是串的集合。字母表是一种特殊的语言，即该语言中的每个串都是一个字母，也就是说串的长度都是1（cy）α中至少包含ＶN中的一个元素*参见形式语言p220→表示“consistof”（参见形式语言p78）Α表达式的含义：语言是串的集合。字母表是一种特殊的语言，即该语言中的每个串都是一个字母，也就是说串的长度都是1（cy）α中至少包含ＶN中的一个元素*参见形式语言p220→表示“consistof”（参见形式语言p78）Α表达式的含义：语言是串的集合。字母表是一种特殊的语言，即该语言中的每个串都是一个字母，也就是说串的长度都是1（cy）α中至少包含ＶN中的一个元素*参见形式语言p220→表示“consistof”（参见形式语言p78）Α表达式的含义：语言是串的集合。字母表是一种特殊的语言，即该语言中的每个串都是一个字母，也就是说串的长度都是1（cy）α中至少包含ＶN中的一个元素*参见形式语言p220→表示“consistof”（参见形式语言p78）Α表达式的含义：语言是串的集合。字母表是一种特殊的语言，即该语言中的每个串都是一个字母，也就是说串的长度都是1（cy）α中至少包含ＶN中的一个元素***根据语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择反映文法描述语言的能力*形式语言与自动机(p227)Type1Grammars无法生成空串（cy）如果不考虑空串的因素，i型语言（即i型文法生成的语言）集合将完全包含(i+1)型语言集合，i=0,1,2四种文法之间的逐级“包含”关系如下：**龙2p116对句子结构的分析可以用树来表示自顶向下看，句子是由主语和谓语组成，这句话可以表示为?句子???主语??谓语?用尖括号括起来的东西称为语法成分上述形式描述了句子的构成规则，简称为规则图中的规则还包括……thatfiltersouttheorderinwhichproductionsareappliedtoreplacenonterminals***这里，“other”表示任何其他语句*这里，“other”表示任何其他语句**满足，肯定无二义性不满足，也未必就是有二义性的大部分程序设计语言的语法构造可以用CFG来描述，因此本章重点介绍一下CFG**文法的形式化定义 G=(VT,VN,P,S)VT：终结符集合VN：非终结符集合P：产生式集合S：开始符号例：G=({id,+,*,(,)},{E},P,E)P={E→E+E, E→E*E,E→(E),E→id}G:E→E+EE→E*EE→(E)E→id约定：不引起歧义的前提下，可以只写产生式产生式的简写对一组有相同左部的α产生式α→β1,α→β2,…,α→βn 可以简记为：α→β1|β2|…|βn读作：α定义为β1，或者β2，…，或者βn。β1，β2，…，βn称为α的候选式(Candidate)例E→E+EE→E*EE→(E)E→idE→E+E|E*E|(E)|id符