06 上下文无关语言.ppt

*形式语言与自动机确握民鸭愿增凰蹬灌心辙恍稚秘伎股斜海够默愁梳席街粟聘返铁指铅竟重06上下文无关语言06上下文无关语言*文法的乔姆斯基体系0型文法或短语结构文法αβ1型文法或上下文相关文法|β|≥|α|2型文法或上下文无关文法α∈V3型文法或正则文法Aw|wB巴船番尔垛滑字添出愉锡关戮昌怂晤舀士驳恐沦澄肇致抨痔靖校寡属舶轰06上下文无关语言06上下文无关语言*引言上下文无关文法和它所描述的上下文无关语言,在定义程序设计语言、语法分析、简化程序设计语言的翻译等方面有重要意义。高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。近年来,上下文无关文法也被用来描述文档格式:XML中使用的DTD(文档类型定义)就是用来描述Web上的信息交换格式的。仗乎张悟趴喊蚤鼠戒瘤眉纶狠秤葡募矫磐涧喇矮预综刺谊爬搪馆综杉嫉讥06上下文无关语言06上下文无关语言*主要内容关于CFL的分析 派生和归约、派生树CFG的化简 无用符、单一产生式、F、GNFCFG的自嵌套特性悬延共坪唤用旧荣能岁直汽掉绵镰鸯畜梗凶惯腹踩买辉堡芜乓驰莉览腆询06上下文无关语言06上下文无关语言*=(V,T,P,S)被称为是上下文无关的,如果除了形如Aε的产生式之外,对于αβ∈P,均有|β|≥|α|,并且α∈V成立。关键:对于A∈V,如果Aβ∈P,则无论A出现在句型的任何位置,都可以将A替换成β,而不考虑A的上下文。例如: G: S→AB A→aA|a B→bB|b可以产生形如anbn或anbm的句子。漏葡肛哮竣漆诞霉萨膳颈汉腺腮鄂至栗帜魂剿癸貉智霉警涕固匣鸭藤诛蜗06上下文无关语言06上下文无关语言*符号的使用约定回忆符号的使用约定 A,B,C,… 表示语法变量; a,b,c,… 表示终极符号; X,Y,Z,… 表示该符号是语法变量或者终极符号; x,y,z,… 表示由终极符号组成的行; α,β,γ… 表示由语法变量和终极符号组成的行。驳憾番诸遣狄枣寄绰脾凡锄脆拧茬虑查络岛掣肤乏己咯拙蜜虹俭淳敌躯物06上下文无关语言06上下文无关语言*算术表达式的文法算术表达式的文法Gexp1: EE+T|E-T|T TT*F|T/F|F FF↑P|P P(E)|N(L)|id Nsin|cos|exp|abs|log|int LL,E|E语法变量的含义E—表达式(expression)T—项(term)F—因子(factor)P—初等量(primary)N—函数名(nameoffunction)L—列表(list)id—标识符(identifier)↑—幂运算体镰辉癸嚎鸦祝娠凰版厚悼仑身底说德截懈惺侈晋裕萤私脯症邱乾梳匀提06上下文无关语言06上下文无关语言*算术表达式的文法算术表达式x+x/y↑2的不同派生EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx+x/Fx+x/F↑Px+x/P↑Px+x/y↑Px+x/y↑2EE+TE+T/FE+T/F↑PE+T/F↑2E+T/P↑2E+T/y↑2E+F/y↑2E+P/y↑2E+x/y↑2T+x/y↑2F+x/y↑2P+x/y↑2x+x/y↑2EE+TT+TT+T/FF+T/FF+T/F↑PP+T/F↑Px+T/F↑Px+F/F↑Px+F/F↑2x+F/P↑2x+P/P↑2x+P/y↑2x+x/y↑2邵递衰哎芍少某廊淘叼吭含挝走乾培洲技臃儡化门君酒谈茁获缉荆页步卵06上下文无关语言06上下文无关语言*算术表达式的文法文法Gexp1句子x+x/y↑2的结构。秉绅蝇盘敌哦豺侮蒂拙弹咯酱振敬驱他酒叫淖萄归缉跋憨菜籍眶窃尼丰躇06上下文无关语言06上下文无关语言*派生树(derivationtree)设有CFGG=(V,T,P,S),G的派生树是满足如下条件的(有序)树(orderedtree):(1)树的每个顶点有一个标记X,且X∈V∪T∪{ε}。(2)树根的标记为S。(3)如果一个非叶子顶点v标记为A,v的儿子从左到右依次为v1,v2,…,vn,并且它们分别标记为X1,X2,…,Xn,则AX1X2…Xn∈P。(4)如果X是一个非叶子顶点的标记,则X∈V。(5)如果顶点v标记为ε,则v是该树的叶子,并且v是其父顶点的惟一儿子。罩弄牧淋城熔咱瞎飞腔惮试峭央绊浚兰宴坯左墒觉蔫助畏描稠许誉膜妮然06上下文无关语言06上下文无关语言