形式语言与自动机2教学讲解教案.pdf

《形式语言与自动机2教学讲解教案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FL&A第二讲上下文无关文法与上下文无关语言FL&A上下文无关文法与上下文无关语言上下文无关文法的基本概念归约与推导上下文无关语言文法与语言的Chomsky分类语法分析树归约、推导与分析树之间关系文法和语言的二义性FL&A上下文无关文法的基本概念回顾：在第一讲中介绍过如下内容设=0,1，L=0n1nn1，如0011,000111,01L,而10,1001,,010L.如下是一个可接受该语言的上下文无关文法S01S0S1FL&A上下文无关文法的基本概念另一个例子EEOEE(E)EvE

2、dO＋OFL&A上下文无关文法的基本概念上下文无关文法(context-freegrammars)的四个基本要素1.终结符(terminals)的集合有限符号集，相当于字母表2.非终结符(nonterminals)的集合有限变量符号的集合3.开始符号(startsymbol)一个特殊的非终结符4.产生式(productions)的集合形如：EEOE开始符号产生式集合E(E)EvEd非终结符O＋终结符OFL&A上下文无关文法的基本概念上下文无关文法的形式定义一个上下文无关文法CFG(co

3、ntext-freegrammars)是一个四元组G=(V,T,P,S).非终结符的集合满足终结符的集合VT=产生式的集合SV开始符号产生式形如A,其中AV,(VT)*FL&A上下文无关文法的基本概念上下文无关文法举例(1)CFGG=({S},{0,1},P,S).其中产生式集合P为01S01S0S1(2)CFGG=({E,O},{(,),＋,,v,d},P,E).exp其中产式集合P为EEOEE(E)EvEdO＋OFL&A上下文无关文法的基本概念产生式集合的缩写记法形如A1,A2,…

4、,An的产生式集合可简缩记为A12…n，如S01S010S1S0S1EEOEE(E)EEOE(E)vdEvO＋EdO＋OFL&A归约与推导用于推理字符串是否属于文法所定义的语言一种是自下而上的方法，称为递归推理（recursiveinference），递归推理的过程习称为归约；另一种是自上而下的方法，称为推导（derivation）归约过程将产生式右部（body）形式的符号串替换为产生式左部（head）的符号推导过程将产生式左部的符号替换为产生式右部的符号FL&A归约与推导

5、归约过程举例对于CFGG=({E,O},{(,),＋,,v,d},P,E)，P为exp（1）EEOE（2）E(E)（3）Ev（4）Ed（5）O＋（6）O递归推理出字符串v(v＋d)的一个归约过程为（4）（6）（3）v(v＋d)v(v＋E)vO(v＋E)vO(E＋E)（5）（1）（2）（3）（1）vO(EOE)vO(E)vOEEOEEFL&A归约与推导推导过程举例对于CFGG=({E,O},{(,),＋,,v,d},P,E)，P为exp（1）EEOE（2）E(E)（3）Ev（4）Ed（5）O＋（6）O

6、从开始符号到字符串v(v＋d)的一个推导过程为（1）（6）（2）（3）EEOEEEE(E)v(E)（1）（5）（3）（4）v(EOE)v(E＋E)v(v＋E)v(v＋d)FL&A归约与推导推导关系对于CFGG=(V,T,P,S)，上述推导过程可用关系G描述.设,(VT)*，A是一个产生式，则定义A.G若G在上下文中是明确的，则简记为A.扩展推导关系到自反传递闭包定义上述关系的传递闭包，记为，可归纳定义如下：G基础对任何(VT)*，满足.G归纳设,,

7、(VT)*，若，成立，则GG.GFL&A归约与推导最左推导（leftmostderivations）若推导过程的每一步总是替换出现在最左边的非终结符，则这样的推导称为最左推导.为方便，最左推导关系用lm表示，其传递闭包用表示.lm如对于文法G，下面是关于v(v＋d)的一个最左推导：expEEOEElmEOElmvOElmvEE(E)Evlmv(E)lmv(EOE)lmv(vOE)Edv(v＋E)v(v＋d)O＋lmlmOFL&A归约与推导最右

8、推导（rightmostderivations）若推导过程的每一步总是替换出现在最右边的非终结符，则这样的推导称为最右推导.为方便，最右推导关系用rm表示，其传递闭包用表示.rm如对于文法G，下面是关于v(v＋d