没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记164(2006)97-102www.elsevier.com/locate/entcs无扫描布尔分析亚当·梅加奇计算机科学摘要无扫描广义解析技术允许解析器直接从统一的、声明性的规范中派生。不幸的是,为了在字符级别上唯一地解析现有的编程语言,需要超越通常的上下文无关形式主义的消歧扩展本文解释了布尔文法的无扫描分析器(上下文无关文法扩展为交集和否定)可以明确地指定这样的语言,并且还可以描述其他有趣的构造,例如基于缩进的块结构。sbp包实现了这种解析技术,并作为Java源代码公开提供。保留字:布尔文法,无扫描,GLR1介绍虽然无扫描解析3在[1]中首次引入,但直到与Visser [7]的Lang-Tomita广义LR解析算法[2,3]相结合,它才实用于一般用途不幸的是,大多数编程语言的上下文无关语法在字符级别上是模糊的,这促使引入了六个精心选择的消歧结构:跟随,拒绝,偏好,避免,关联性和优先级。2合取和布尔文法C_njunctivegam ars[8]augmet h ethuxtaposition(·)anddlanguage-union(|)上下文无关文法的运算符,并增加了一个 语言-intersection(&)1项工作由国家科学基金会研究生研究奖学金支持2 电子邮件地址:megacz@cs.berkeley.edu3也称为1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.10.00798A. Megacz/Electronic Notes in Theoretical Computer Science 164(2006)97操作符.布尔文法[10]通过允许使用语言补运算符(LCL)来进一步扩展合取文法,但要遵守一些基本的良构性约束4。应该注意的是,维瑟通过使用拒绝产生式从相反的方向得到了类似的结果,拒绝产生式与否定一起起作用。这篇论文继续重建简单的否定,以及在这个否定合取原语的交集,甚至指出,[七]《中国日报》3使用布尔结构现在我们来研究一下每个消歧结构,并解释如何将其转换为布尔表达式。PREFER和AVOID属性有效地在二义性分析之间做出上下文敏感的选择,从而将二义性上下文无关文法转化为非二义性上下文敏感文法。我们可以用有序选择运算符(>)替换PREFER和AVOID,这是一个元语法缩写,用于将低优先级表达式与高优先级表达式的补表达式5结合性和优先级特征在跨越多个非终结符时不能扩展为简单的上下文无关表达式,如[5]的示例4.5.11所示在这个例子中,加法和乘法表达式被定义为实数(R)和自然数(N)。A包容产生式(N→R) 但是对自然数的操作比对实数的相应操作具有更高的优先级。这种丰富的优先级指定可以以类似于有序选择运算符的方式表示:表达式与所有更高优先级的表达式的补数相匹配,即使是那些涉及来自多个非终结符的结果的表达式。REJECT属性的使用可以简单地转换为与rejected表达式的互补的如果将字符边界(相邻字符对)视为输入标记,则跟随从这个角度来看,跟随限制相当于将表达式与以有效的跟随边界结束的所有字符串的集合相交。4SBP:一个无扫描布尔分析器sbp包是Lang-Tomita广义LR解析算法[2,3]的实现,采用Johnstone Scottsbp的输入字母表通常是单个Unicode字符的集合例如,一个非终结符不能被定义为恰好产生它自己的补数。5 例如,a > b扩展为a|(&b)A. Megacz/Electronic Notes in Theoretical Computer Science 164(2006)9799尽管可以使用任何拓扑空间6。 一个有趣的结果是,可以解析由非离散字母构成的句子7解析器包括一个示例元语法;它支持交替(|)、整数检测(&)、复杂性()、整数检测-&带复杂性()、子表达式()、正则表达式(*,+,?)、带分隔符的重复(*/,+/)、最大重复字符(++,**)、有序选择(>)、提升操作符(如[12])、字符范围([a-z])和空格插入(/ws)。5示例5.1荡秋千语法歧义的一个典型例子是所谓的解决这种二义性的规则可以总结如下:如果else-branch可以被解析为多个语句的一部分,那么它应该被解析为最里面的合格语句的一部分。下面的语法通过要求只有当if语句的body本身不构成格式良好的Expr时,else-branch才能被用作给定if-state的一部分来if-语句的主体将构成一个独立的格式良好的Expr-分支,可以将else-分支分配给“then-branch”中的某个Expr=“if”“(“ Expr“)”Expr| “if”(“Expr“)”(Expr“else”Expr(“else” Expr)5.2压痕块结构除了消歧之外,布尔语法结构还有许多其他的应用。下面的示例通过对块施加格式良好性约束来分析具有基于缩进的块结构的语言所采用的技术受到[11]的启发。6一个提供了、、运算符和(或简单的=)测试的函数7 尽管我们还没有发现这种能力100A. Megacz/Electronic Notes in Theoretical Computer Science 164(2006)97我们从类C语言的一个简单片段的语法开始。语法使用与否定项的连接来排除名称恰好是关键字的标识符,就像[6]中一样。语句=Expr“()”|“while”Expr块Expr= ident|[0-9]++ident= [a-z]++&验证keywordskeywords=“while”|“如果”空字符类([])的补语是一种习惯用法,用于匹配任何字符。我们现在可以使用布尔语言操作来强加额外的结构。我们将通过定义语法块的非终结符来实现这一点,并将它与另一种生产,要求没有行在一个块可以缩进小于第一行。最后,我们使用有序选择操作符来优先选择=““*outdent =““突出““| “[]*“\n”block =“\n”删除BlockBody&“\n”升级[BlockBody =语句>语句块体块规则匹配开始新行的代码块。该规则需要一个换行符,后跟一定数量的空格,然后是一个BlockBody。这个产生式是用格式良好的产生式来表示的:换行符后面不能有突出部分。与用于匹配平衡括号的规则类似,rule匹配任何以缩进开头的文本,并且还包含比第一个缩进实例短的其他缩进实例(不相交)。在块生成的上下文中,这将描述任何包含缩进小于块中第一行的行的块。6相关工作这些语法分析器可以实现一般的语法分析,sglr[5]是一个针对ASF+SDF[4]框架设计的一个改进的语法分析器。Dparser [17]是ANSI C中GLR算法的一个实现,支持大多数Visser有几个GLR解析器需要一个tokenizer。[8]这些包括Elkhound[14]和野牛的GLR扩展。解析表达式语法(PEG)[15]包括有限形式的交集和补码,相应的算法[16]在解析字符级语法时是有效的。然而,许多有趣的上下文无关语法不是PEG,并且不能以这种方式解析。有些可以用作A. Megacz/Electronic Notes in Theoretical Computer Science 164(2006)971017未来方向当前的实现是用Java编写的它生成解析表(可以保存和恢复),但目前只支持解释这些表。发出等价于从这些表中解析的可编译源代码将是提高sbp性能的重要一步。与sglr解析器一样,sbp故意排除了对语义操作的支持,更倾向于保持语法定义与实现语言无关。一个后果是,解析需要输入中线性的空间,因为整个解析树(使用丢弃操作符移除模部分)必须在其任何部分被消耗之前构造。一个重要的未来方向是构造惰性解析森林的可能性,惰性解析森林可以由与解析器并发运行的进程递增地消耗和丢弃8可用性sbp的源代码可以在BSD许可证的条款下获得,http://research.cs.berkeley.edu/project/sbp/网站。引用[1] 丹尼尔·J·所罗门和戈登·V·科马克。无扫描NSLR(1)程序设计语言的解析。SIGPLAN '89,第170-178页。ACM Press,1989.[2] 朗伯纳德有效的非确定性分析器的确定性技术。自动机,语言和编程,Springer,1974年。[3] 富田,M。(1987年)。一个高效的增广上下文无关句法分析算法。Computational Linguistics,13(1-2),31[4] A. van Deursen,J. Heering and P. Klint(eds.),Language Prototyping:An Algestion SpecificationApproach,AMAST Series in Computing,Volume 5,World Scienti fic,1996年9月[5] 维瑟,埃尔科。语言原型的定义。博士论文,阿姆斯特丹大学,1997年9月。[6] M. G. J. van den Brand、J. Scheerder、J. Vinju和E.维瑟无扫描广义LR解析器的消歧滤波器。在计算机构造(CCSpringer-Verlag,2002.[7] Visser,E.(1997年b)。无扫描广义LR解析。技术报告P9707,程序设计研究小组,阿姆斯特丹大学。[8] 亚历山大·奥霍京 合取语法。 Journal of Automata,Languages and Combinatorics 6(4):519-535(2001)[9] 亚历山大·奥霍京布尔文法的LR解析。语言理论的发展2005:362-373。[10] 亚历山大·奥霍京 布尔文法。 语言理论发展2003:398-410。[11] 亚历山大·奥霍京关于简单过程语言的布尔文法的存在性。AFL 2005年会议记录。[12] 约翰斯通,阿德里安和斯科特,伊丽莎白。构造简化的派生树。伦敦大学CSD-TR-97-27(1997年)[13] 约翰斯通,阿德里安和斯科特,伊丽莎白。用于领域特定语言原型的广义归约修改的LR解析。 Proc. 第35届夏威夷系统科学国际会议(2002年1月),IEEE计算机学会,新泽西州102A. Megacz/Electronic Notes in Theoretical Computer Science 164(2006)97[14] Scott McPeak和George C. Necula Elkhound:一个快速、实用的GLR解析器生成器。会议论文集的建造商(CC04),2004年4[15] 布莱恩·福特。Packrat解析:简单,强大,懒惰,线性时间。函数式编程国际会议,2002年10月4-6日,匹兹堡[16] 布莱恩·福特。解析表达式语法:基于语法的语法基础。2004年1月14日至16日在意大利威尼斯举行的程序设计语言原理研讨会。[17] http://dparser.sourceforge.net/[18] 作者:Brian W.作者:Ritchie,Dennis M. C语言编程,第二版,Prentice Hall,Inc.,1988. ISBN 0-13-110362-8
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功