第二章文法和语言词法规则：自动机语法规则：上下文无关文法引言补充：文法的直观概念(1/5)直观文法举例(2/5)“我是大学生”的推导过程：<句子><主语><谓语><代词><谓语>我<谓语>我<动词><直接宾语>我是<直接宾语>我是<名词>我是大学生依次可以推导出句子“王明是大学生”、“我学习英语”等等程序设计语言对文法的要求(4/5)文法作用(5/5)2符号串及其运算（1）符号串：由字母表中的符号组成的任何有穷序列。说明:字母间的顺序不同顺序组成的符号串是不同的；（2）符号串长度符号串内所含符号的个数，若x=string,则|x|=6;其中不含任何符号的符号串称为空符号串ε，长度|ε|＝0符号串的运算(1/3)(3)符号串的连接（4）符号串集合的乘积（5）符号串的方幂（6）符号串集合的方幂（7）符号串集合的正闭包2.2产生式文法和语言2.2产生式文法和语言文法的形式定义文法定义举例1文法定义举例2用文法定义语言的中心思想是：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。例如文法G：E→E+E|E*E|(E)|i，其中唯一非终结符E可以看成是代表一类算术表达式。从E出发，进行一系列的推导，推出种种不同的算术表达式。如根据上述规则可推出(i+i)：E=>(E)=>(E+E)=>(i+E)=>(i+i)我们称这样的一串替换是从E推出(i+i)的一个推导，这个推导提供了一个证明，证明(i+i)是文法G所定义的一个算术表达式。有关推导的定义2.2.3句型、句子、语言语言的例子2.2.4文法的等价什么是递归文法？4.递归文法的优点：可用有穷条规则，定义无穷语言2.3文法的分类定义0型文法（或称短语文法,phrasestructuregrammar,PSG）定义1型文法（或称上下文有关文法,CSGContextSensitiveGrammar）接上页例子接上例上下文有关，顾名思义就是对非终结符进行替换时必须考虑上下文。例如，1型文法G的产生式也可写成αAβ→αγβ，其中α、β、γ都在(VN∪VT)*中，且γ≠ε，A∈VN，则说明了非终结符A必须在α、β这样一个上下文环境中才可以替换。上下文有关文法能生成anbncn类特征的语言。但它不能描述L={αcα|α∈(a|b)*}类语言。定义2型文法（或称上下文无关文法，CFGContextFreeGrammar）上下文无关文法的说明设G=(VN,VT,P,S)为一文法，若G的任何产生式A→α或A→αB，其中A、B∈VN，α∈VT*。对任何正规文法G，都可以设计一个不确定的有穷自动机NFA，它能够而且只能够识别G的语言。左线性文法2.3.2文法分类的意义文法分类的意义2.3.3文法举例2.3.3文法举例(2)2.3.3文法举例(3)2.3.4文法的构造（补充）文法的构造的分析（补充）文法构造的方法（补充）文法的构造举例(1/3)文法的构造举例（2/3）文法的构造举例（3/3）2.4文法及其语法树从根结点S开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生出下一代新结点，候选式中自左向右的每个符号对应一个新结点，并用这些符号标记其相应的新结点。每个新结点与其父结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左向右排列起来就是一个句型。接语法树构造举例文法和语言语法树例子2.5文法和语言的一些特性文法和语言文法和语言文法和语言文法和语言2.5.4最左推导/最右推导/规范推导语法树的特点文法和语言文法和语言二义性其它问题文法和语言文法和语言文法和语言自下而上的分析法自下而上的语法分析举例文法和语言自下而上分析法举例自下而上分析法存在的问题短语、直接短语、句柄解题方法接上例分析说明解题方法练习1题目练习１解答练习2题目练习２解答（１／２）练习２解答（２／２）3.7有关文法实用中的一些说明(1/2)有关文法实用中的一些说明(2/2)本章课后练习