- 1、本文档共141页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
# gid fid f* g* g+ f+ f$ g$ 算符优先分析法 1) 构造优先函数的算法不是唯一的。 2)存在一组优先函数,那就存在无穷组优先函数。 算符优先分析法 * 可以看出: ① 句柄总是在栈顶形成。这是因为在分析的过程中一旦形成某产生式的右部就立即进行归约,而从左到右扫描输入,最早形成的自然是最左的直接短语; ② 栈中保留的总是一个右句型的前缀(加上若干终结符形成句型),称为活前缀; ③ 如果将每次归约逻辑上认为是构造对应产生式的树,则分析的全过程逻辑上就是从下到上构造一棵分析树;反之,如果将每次归约逻辑上认为是剪去假想分析树上对应产生式的孩子,则分析的全过程逻辑上就是从下到上为分析树剪句柄。 * 可以看出: ① 句柄总是在栈顶形成。这是因为在分析的过程中一旦形成某产生式的右部就立即进行归约,而从左到右扫描输入,最早形成的自然是最左的直接短语; ② 栈中保留的总是一个右句型的前缀(加上若干终结符形成句型),称为活前缀; ③ 如果将每次归约逻辑上认为是构造对应产生式的树,则分析的全过程逻辑上就是从下到上构造一棵分析树;反之,如果将每次归约逻辑上认为是剪去假想分析树上对应产生式的孩子,则分析的全过程逻辑上就是从下到上为分析树剪句柄。 * 可以看出: ① 句柄总是在栈顶形成。这是因为在分析的过程中一旦形成某产生式的右部就立即进行归约,而从左到右扫描输入,最早形成的自然是最左的直接短语; ② 栈中保留的总是一个右句型的前缀(加上若干终结符形成句型),称为活前缀; ③ 如果将每次归约逻辑上认为是构造对应产生式的树,则分析的全过程逻辑上就是从下到上构造一棵分析树;反之,如果将每次归约逻辑上认为是剪去假想分析树上对应产生式的孩子,则分析的全过程逻辑上就是从下到上为分析树剪句柄。 算符优先分析 直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性 算符优先分析法的局限性 由于算符优先分析法去掉了单非终结符之间的归约,尽管在分析过程中,当决定是否为句柄时采取了一些检查措施,但仍难完全避免把错误的句子得到正确的归约。 如文法: S ?S;D|D D ?D(T)|H H ?a|(S) T ?T+S|S 对串(a+a)能正确归约 自底向上优先分析概述 简单优先分析法 优先关系表:所有符号(VT和VN)的优先关系; 规范归约:确定句柄 算符优先分析法 优先关系表:终结符号(VT)的优先关系; 结构归约:确定最左素短语 简单优先分析法 定义两个集合 1)firstV firstV(P)={Q | P ?+Qa…, Q ?VN∪ VT而a? (VN∪ VT )*} 2)lastV lastV(P)={Q | P ?+…aQ, Q ?VN∪ VT而a? (VN∪ VT )*} 构造集合firstV(P): 若有P?a…或P ?Qa…,则a,Q?firstV(P) 若有P ?Q…,firstV(Q) 包含于firstV(P) 构造集合lastV(P): 若有P? … a或P ? … aQ,则a,Q?lastV(P) 若有P ? … Q,lastV(Q)包含于lastV(P) 算符优先分析法 优先关系计算 a??b 直接查看产生式的右部,对有形如A?…ab…或A ?…aBb…的产生式,则a??b。 a·b 求出每个非终结符B的firstVT(B),对有形如A ?…aB…的产生式,对任何b?firstVT(B), 有a·b。 a·b 求出每个lastVT(B) ,对有形如A ?…Bb…的产生式,对任何a?lastVT(B), 有 a·b 。 算符优先分析法 构造集合firstVT(P): 若有P?a…或P ?Qa…,则a?firstVT(P) 若有P ?Q…,firstVT(Q) 包含于firstVT(P) 构造集合lastVT(P): 若有P? … a或P ? … aQ,则a?lastVT(P) 若有P ? … Q,lastVT(Q)包含于lastVT(P) 自底向上优先分析概述 简单优先分析法 对一个文法按照所有符号(VT和VN)的优先关系,确定归约的句柄; 规范归约 分析准确、规范 效率低、实用价值不大 算符优先分析法 对一个文法只按照终结符号(VT)的优先关系,只要找到可归约串就归约; 非规范归约,结构归约 分析不是非常准确、规范 分析速度快、特别适用于表达式的分析 算符优先分析 直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性 优先函数 由于优先函数比优先矩阵更节省存储空间,因此我们往往采用优先函数表示算符之间的优先关系。 定义 两个优先函数f和g,它们可以将终结符号映射到整数。
文档评论(0)