- 1、本文档共109页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第6章 上下文无关语言 Gbra:S?S(S)|ε L(Gbra)不是RL,是CFL高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。。BNF(巴科斯范式:Backus normal form,又叫Backus-naur form)。第6章 上下文无关语言 主要内容关于CFL的分析派生和归约、派生树CFG的化简 无用符、单一产生式、空产生式CFG的范式 CNFGNFCFG的自嵌套特性 第6章 上下文无关语言 重点CFG的化简。CFG到GNF的转换。 难点CFG到GNF的转换,特别是其中的用右递归替换左递归的问题。6.1 上下文无关语言 文法G=(V,T,P,S)被称为是上下文无关的。 如果除了形如A?ε的产生式之外,对于?α?β∈P,均有|β|≥|α|,并且α∈V成立。关键:对于?A∈V,如果A?β∈P,则无论A出现在句型的任何位置,我们都可以将A替换成β,而不考虑A的上下文。 6.1.1 上下文无关文法的派生树 算术表达式的文法 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 6.1.1 上下文无关文法的派生树 算术表达式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↑2 E?E+T?E+T/F?E+T/F↑P?E+T/F↑2?E+T/P↑2?E+T/y↑2? E+F/y↑2? E+P/y↑2? E+x/y↑2? T+x/y↑2? F+x/y↑2? P+x/y↑2?x+x/y↑2 E?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 6.1.1 上下文无关文法的派生树文法Gexp1句子x+x/y↑2的结构。 SSS(S)()()6.1.1 上下文无关文法的派生树S - SS | (S) | () (())()SSS(S)()()6.1.1 上下文无关文法的派生树派生树(derivation tree) 一棵(有序)树(ordered tree) 树的每个顶点有一个标记X, 且X∈V∪T∪{ε} 树根的标记为S; 如果非叶子顶点v标记为A,v的儿子从左到右依次为v1,v2,…,vn,并且它们分别标记为X1,X2,…,Xn,则A?X1X2…Xn∈P;如果X是一个非叶子顶点的标记,则X∈V;如果顶点v标记为ε,则v是该树的叶子,并且v是其父顶点的惟一儿子。 SSS(S)()()6.1.1 上下文无关文法的派生树别称生成树分析树(parse tree)语法树(syntax tree) 顺序v1,v2是派生树T的两个不同顶点,如果存在顶点v,v至少有两个儿子,使得v1是v的较左儿子的后代,v2是v的较右儿子的后代,则称顶点v1在顶点v2的左边,顶点v2在顶点v1的右边。 SSS(S)()()6.1.1 上下文无关文法的派生树结果(yield) 派生树T的所有叶子顶点从左到右依次标记为X1,X2,…,Xn,则称符号串X1X2…Xn是T的结果。 一个文法可以有多棵派生树,它们可以有不同的结果。句型α的派生树:“G的结果为α的派生树”。SSS(S)()()6.1.1 上下文无关文法的派生树派生子树(subtree) 满足派生树定义中除了对根结点的标记的要求以外各条的树叫派生子树(subtree)。如果这个子树的根标记为A,则称之为A子树。 惟一差别是根结点可以标记非开始符号。6.1.1 上下文无关文法的派生树定理6-1 设CFG G=(V,T,P,S),S?*α的充分必要条件为G有一棵结果为α的派生树。证明:证一个更为一般的结论:对于任意A∈V,A?*α的充分必要条件为G有一棵结果为α的A-子树。 充分性:设G有一棵结果为α的A-子树,非叶子顶点的个数n施归纳,证明A?*α成立。 6.1.1 上下文无关文法的派生树设A-子树有k+1个非叶子顶点,根顶点A的儿子从左到右依次为v1,v2,…,vm,并且它们分别标记为X1,X2,…,Xm 。 A?X1X2…Xm∈P 。 以X1,X2,…,Xm为根的子树的结果依次为α1,α2,…,αm 。 X1,X2,…,Xm为根的子树的非叶子顶点的个数均不大于k。 6.1.1 上下文无关文法的派生树 X1?*α1X2?*α2…Xm?*αm而且α=α1α2…αm6.1.1 上下文无关文法的派生树 A?X1X2…Xm ?*α1X2…Xm ?*α1α2…Xm … ?*α1α2…αm6.1.1 上下文无关文法的派生
您可能关注的文档
最近下载
- 优质工程创优监理方案.pdf
- 第1-4单元期中重难点检测(试题)-2024-2025学年数学三年级上册北师大版.docx VIP
- 大疆 精灵 Phantom 4 Pro V2.0 快速入门指南 用户手册.pdf
- XX省传染病监测预警与应急指挥信息平台项目监测预警信息平台采购需求.docx VIP
- 最满意的三项工作和最不满意的一项工作3篇.docx
- 第1-4单元期中重难点卷(试题)-2024-2025学年数学三年级上册北师大版.docx VIP
- 送阅件-兖矿集团审计风险部.PDF
- 公司人力资源管理诊断报告.pptx
- NB∕T 31021-2012 风力发电企业科技文件归档与整理规范.pdf
- 辽宁省名校联盟 2024年高三 10 月份联合考试 物理试卷(含答案解析).pdf
文档评论(0)