首页 > 正在进行安全检测...

正在进行安全检测...

发布时间：1714397051 来源：文档文库

小中大

字号：

手机查看

新技术新工艺２０１５年　第６期　一种基于ＢＮＦ范式的ＬＡＬＲ（１）￣　分析器描述语言的设计＊　李　洋　，胥　亮。　（１．西安职业技术学院，陕西西安７１００７７；２．西安卫星测控中心，陕西西安７１００３２）　摘　要：常见的Ｉ　ＡＬＲ（１）语法分析器自动生成系统所支持的程序设计语言语法复杂，用户学习困　难。以此为出发点，设计了一种基于ＢＮＦ范式的ＬＡＬＲ（１）语法分析器描述语言，分析了该语言需满足　的需求，并给出了该语言的文法。该语言文法功能完备，使用简单，易于学习，为构造ＬＡＬＲ（１）语法分析　器的自动化实现提供了一种思路。　关键词：编译器；ＹＡＣＣ；ＢＮＦ；ＬＡＩ　Ｒ（１）　中图分类号：ＴＰ　３１２　文献标志码：Ａ　Ｉ　Ｉ　Ｙａｎｇ　，ＸＵ　ＩＡａｎｇ　Ｔｈｅ　Ｄｅｓｉｇｎ　ｏｆ　ａ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｌａｎｇｕａｇｅ　Ｄｅｓｃｒｉｂｉｎｇ　ＬＡＬＲ（１）Ｐａｒｓｅｒ　ｂａｓｅｄ　ｏｎ　ＢＮＦ　Ｐａｒａｄｉｇｍ　（Ｘｉ　ａｎ　Ｖｏｃａｔｉｏｎａｌ　ａｎｄ　Ｔｅｃｈｎｉｃａｌ　Ｃｏｌｌｅｇｅ，Ｘｉ　ａｎ　７１００７７，Ｃｈｉｎａ；Ｘｉ　ａｎ　Ｓａｔｅｌｌｉｔｅ　Ｃｏｎｔｒｏｌ　Ｃｅｎｔｅｒ，Ｘｉ　ａｎ　７１００３２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｓｙｎｔａｘ　ｏｆ　ｐｒｏｇｒａｍｍｉｎｇ　ｌａｎｇｕａｇｅ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　ｃｏｍｍｏｎ　ＬＡＬＲ（１）ｐａｒｓｅｒ　ｇｅｎｅｒａｔｏｒ　ｓｙｓｔｅｍ　ｉｓ　ｔＯＯ　ｃｏｍｐｌｅｘ　ｔｏ　ｌｅａｒｎ．Ａｓ　ａ　ｓｔａｒｔｉｎｇ　ｐｏｉｎｔ，ｔｈｉｓ　ｐａｐｅｒ　ｄｅｓｉｇｎｓ　ａ　ｋｉｎｄ　ｏｆ　ｌａｎｇｕａｇｅ　ｄｅｓｃｒｉｂｉｎｇ　ＬＡＩ　Ｒ（１）ｐａｒｓｅｒ　ｗｈｉｃｈ　ｉｓ　ｂａｓｅｄ　ｏｎ　ＢＮＦ　ｐａｒａｄｉｇｍ．Ｉｔ　ａｎａｌｙｓｅｓ　ｔｈｅ　ｄｅｍａｎｄ　ｗｈｉｃｈ　ｔｈｅ　ｌａｎｇｕａｇｅ　ｒｅｑｕｉｒｅｄ　ｔｏ　ｍｅｅｔ，ａｎｄ　ｇｉｖｅｓ　ｔｈｅ　ｌａｎｇｕａｇｅ　ｇｒａｍｍａｒ．Ｔｈｅ　ｌａｎｇｕａｇｅ　ｇｒａｍｍａｒ　ｉｓ　ｆｕｌｌ—ｆｅａｔｕｒｅｄ，ｓｉｍｐｌｙ　ｕｓｅｄ　ａｎｄ　ｅａｓｙ　ｔｏ　ｌｅａｒｎ，ｐｒｏｖｉｄｅｉｎｇ　ａ　ｗａｙ　ｔｏ　ｃｏｎｓｔｒｕｃｔ　ｔｈｅ　Ｉ　ＡＩ　Ｒ（１）ｐａｒｓｅｒ　ｇｅｎｅｒａｔｏｒ　ｓｙｓ～　ｔｅｒｎ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｙｎｔａｘ　ｐａｒｓｅｒ，ＹＡＣＣ，ＢＮＦ，Ｉ．ＡＩ　Ｒ（１）　编译器是软件开发的一种基础支撑＿Ｔ具口Ｊ，而　语法分析是编译器设计中的关键技术。语法分析方　法根据产生语法树的方向，可分为自底向上和自顶　向下２大类【２］。Ｉ　Ｒ分析法则是自底向上分析法中　系统，语法规则也较为简单，十分方便用户学习。　１　设计目标　ＢＮＦ是描述语法规则的一种形式化方法，是一　最重要的分析法之一。根据分析能力的差异，按从　强到弱的顺序来区分，Ｉ　Ｒ分析器包括ＳＬＲ（１）、ＬＲ　（１）、ＬＲ（０）和Ｉ　ＡＩ　Ｒ（１）分析器　Ｊ。通过对它们的　分析能力、分析表规模及有限状态机的规模等因素　进行比较分析发现，Ｉ　ＡＬＲ（１）分析法最具有工程应　用价值，但是ＬＡＬＲ（１）分析法几乎不能通过手工方　式构造ＬＡＩ　Ｒ（１）语法分析器，其语法分析表也不简　单；因此，需要自动生成Ｉ　ＡＬＲ（１）语法分析器的工　具　。　种用形式化符号精确描述程序设计语言语法的形式　系统。最好的选择就是使用ＢＮＦ范式描述目标语　言，但是因为ＢＮＦ范式复杂程度较高，只是简单的　点击几个按钮等无法使用户获得目标语法分析器；　因此，应当设计一种可以让用户用来描述目标语言　的语法分析器的文法，即本文所研究的基于ＢＮＦ范　式的程序设计语言。　本文根据ＹＡＣＣ和ＬＥＭＯＮ的文法设计的语　法分析器描述语言，为了保障本文法功能的完备、简　单易学习，还需要具备下述条件。　目前，较为常见的ＬＡＬＲ（１）语法分析器生成系　统有ＹＡＣＣ、ＬＥＭ（）Ｎ、ＣＵＰ和ＳａｂｌｅＣＣ等，这些系　统最主要的优点是功能强大，使用这些系统生成的　ＬＡＬＲ（１）语法分析器具有较大规模；但是，它们也　１）支持使用ＢＮＦ范式描述目标语法分析器。　ＢＮＦ范式应用的描述语法一般为产生式，产生式也　就是表达式，它代表的是语法符号间的推导关系，终　结符和非终结符构成了语法符号。所以，该语法分　析器描述语言的文法需要支持对终结符、非终结符　和产生式的描述。　具有一些不足之处，主要是支持的程序设计语言语　法一般比较复杂，这样学习的难度会加大，比如　ＬＥＭＯＮ和ＹＡＣＣ仅声明符就超过了２０个，即使　生成功能比较简单的语法分析器，也需要投入很多　２）支持算符优先分析法。产生式的数量与　ＬＡＬＲ（１）分析法、算符优先分析法有着密切关系，　将二者进行结合将对产生式数量的削减具有重要意　的精力与时间。本文将要介绍的一种基于巴科斯范　式（ＢＮＦ）的ＬＡＬＲ（１）语法分析器描述语言，其声明　符仅５个，语法简洁，较之于ＹＡＣＣ和ＬＥＭＯＮ等　７０　义，还可以减少项目集的数量，使目标语法分析器简　《新技术新工艺》设计与计算　
设计　计算　头文件写在包含段，在生成目标语法分析器的过程　中，在其“．ｃｐｐ”文件的开头位置将其完整复制。　比如，用户期望“ＩＯＳｔｒｅａｍ”库包含于在生成的　单化，提高分析速度　刮；因此，本语言需要支持算符　优先分析法，这也就意味着文法主要支持声明非终　结符、终结符和产生式的优先级别。　３）支持嵌入语义动作。在语法分析后，由于编　译器还需实现验证语言的语义合法性和中间代码生　成等相应的语义动作，因此，还需要在目标语法分析　器中嵌入语义动作Ⅲ；所以，为能够使用户方便地将　目标语法分析器“ｓｙｎｔａｘｅｒ”的“．ｃｐｐ”文件中，最终　包含段的内容会放在语法分析器“Ｓｙｎｔａｘｅｒ．ｃｐｐ”文　件的开头位置，可写作：　［ｉｎｃｌｕｄｅ］　＃ｉｎｃｌｕｄｅ＜ｉｏｓｔｒｅａｍ￣　ｕｓｉｎｇ　ｎａｍｅｓｐａｃｅ　ｓｔｄ；　产生式对应的语法分析过程与语义动作进行结合，　应在本语言中提供一种方式。　４）语法应简洁。如果关键字太多会使文法更加　复杂，用户的学习难度也会相应的提升；因此，为能　２．２声明段的语法　对目标语法分析器终结符和非终结符值的类型　和优先级进行声明，即为声明段起到的主要作用。　够减少用户使用负担，应当减少不重要的关键字，使　本文法语法更加简洁。　２．２．１　声明终结符、非终结符和产生式的优先级　２　基于ＢＮＦ范式的ＬＡＬＲ（１）语法分析器　声明格式：９，６ｌｅｖｅｌ终结符Ｉ非终结符　［分隔　符终结符Ｊ非终结符…］　ｌｅｖｅｌ用来定义目标语法分析器非终结符、终　结符及产生式的级别，它后面可以带非终结符和终　结符，并且非终结符和终结符由空格和制表符组成　描述语言的语法　本语言的语法采用段式结构，整篇源代码需包　含３个段：包含段、声明段和规则段。每个段由段名　和段内容２部分组成，不同的段可以采用不同的段　名进行标识，段名应单独放置在某一行中的位置，段　内容是从段名后第１行开始，到下一个段名的前一　行或整个文件结尾处的全部内容，段内容中包括目　的字符串隔开，非终结符和终结符的数量并不限制，　其优先级规则为如下４项：１）如果声明的终结符和　非终结符在同一行，那么其优先级是不存在差异的；　２）后声明的低于先声明的行的终结符和非终结符的　标语法分析器特征的描述内容。上述３个段的段名　依次为［ｉｎｃｌｕｄｅ］、［ｄｅｃｌａｒｅ］和［ｒｕｌｅｒ］，３个段在源程　序中的次序没有要求，因为本研究中每个段的功能　优先级；３）如果声明优先级语句不存在，则代表非终　结符、全部终结符及产生式的优先级相同；４）其候选　式中优先级最高的非终结符或者是终结符的优先级　属于产生式的优先级。　例如，上述源程序中，目标语法分析器的终结符　ＳＵＢ和ＡＤＤ低于终结符ＤＩＶ和ＴＩＭＥＳ的优先　级，但是ＳＵＢ和ＡＤＤ具有相同的优先级。　相对独立，推荐使用包含段、声明段和规则段的次序　（基于ＢＮＦ范式的语法分析器描述语言源程序示例　如下所示），这种段式结构能使源代码更清晰。　［ｉｎｃｌｕｄｅ］　＃ｉｎｃｌｕｄｅ“ｉｎｃｌｕｄｅ．ｈ”　２．２．２　目标语法分析器的终结符和非终结符类型　声明格式：　ｔｏｋｅｎｔｙｐｅ｛符号类型）　—￥［ｄｅｃｌａｒｅ］段声明　［ｄｅｃｌａｒｅ］　ｔｏｋｅｎｔｙｐｅ｛Ｔｏｋｅｎ｝　“　ｔｏｋｅｎ—ｔｙｐｅ”的主要功能是对目标语法分析　ｌｅｖｅｌ　ＡＤＤ　ＳＵＢ　ｌｅｖｅｌ　ＴＩＭＥＳ　ＤＩＶ　ｌｅｖｅｌ　ＬＰＡＲＥ　ＲＰＡＲＥ　器源程序中应用的Ｃ＋＋数据类型进行说明，由用　户对其类型进行定义。本文要强调的是声明语句中　必须要有大括号，且在整个源程序中单词类型声明　不得超过一次。　［ｒｕｌｅｒ］　ｐｒｏｇｒａｍ－－＞ｅｘｐｒ（Ａ）　例如，上述源程序中，Ｔｏｋｅｎ型是目标语法分析　器的非终结符与终结符的值。　２．２．３对语句的语法进行注释　对于程序设计语言来说，注释是语法成分必不　（　ｐｒｉｎｔｆ（“［ｒｕｌｅｒ］产生式：ｐｒｏｇｒａｍ－－￣ｅｘｐｒ（Ａ）”）；　）　ｅｘｐｒ（Ａ）一＞ｅｘｐｒ（Ｂ）ＳＵＢ　ｅｘｐｒ（Ｃ）￥表达式的减法运　算　｛　可少的一部分，而合理的注释对于增强代码的可读　性也具有重要意义；所以，该语法分析器描述语言也　应当可以注释源程序。其语法如下。　声明格式：￥任意字符…　注释语句内容为从“￥”起到所在行末之间的全　２．１包含段的语法　用户将目标语法分析器需要包含的声明语句与　《新技术新工艺》设计与计算　
新技术新工艺２０１５年第６期　部字符。　２．３规则段的语法　在本段中，用户可以应用ＢＮＦ范式对目标语法　为了方便用户寻找文法的起始符号，目标语法　分析器文法的起始符号需要是规则段第１个产生式　左侧的非终结符，使产生式之间的推导关系更清晰。　将由任意数量且不限大小写的２６个英文字母　共同组成的字符串，用小括号括起来便是别名，它可　以在对应的语义动作的Ｃ＋＋程序中直接被引用，　代表的是产生式中不同位置的终结符和非终结符。　在归约时产生式会执行１段Ｃ＋＋程序，这就　分析器进行描述，规定规则段实现的主要功能，也就　是说用户可以自行任意设置目标语法分析器的语义　动作和产生式，语法的具体表述如下。　声明格式：非终结符［别名］一＞终结符ｌ非终　结符ＥＮ名］［终结符ｌ非终结符ＥＮ名］…］｛语义　动作｝　是语义动作，这段程序中可以处理及计算别名代表　产生式的语法规则需要遵守ＢＮＦ范式的语法，　的终结符和非终结符的值，从而使语法分析和语义　多个目标语法分析器的产生式共同组成规则段内　容，但与ＢＮＦ范式之间的差异在于每个产生的最后　分析紧密结合起来，让语义动作执行模块可以包含　在生成的目标语法分析器中。　２．４关键字和标识符　都有１个语义动作，每个终结符和非终结符后都能　跟１个别名。　本语言的关键字和标识符见表１。　表１　基于ＢＮＦ范式的语法分析器描述语言的关键字和标识符表　３　结语　本文分析了ＬＡＬＲ（１）语法分析器难以实现的　原因，并通过研究Ｉ　ＡＬＲ（１）语法分析器自动构造实　ＥＪ３．电脑知识技术，２００９（２）：４３２—４３３　Ｅ５３刘三献．基于ＡＮＴ１　Ｒ的Ｇａｕｓｓｉａｎ词法分析器和语法　分析器的分析与设计［Ｄ］．兰州：兰州大学，２００９．　［６３余新待．ｃ／ｃ＋＋程序安全检查工具中数据流分析器的　设计与实现ＥＤ３．西安：西安电子科技大学，２０１０．　［７３袁一平．基于ＶＣ＋＋平台的Ｉ　Ｒ语法分析器的分析与实现　［Ｊ］．长春理工大学学报：自然科学版，２００７（４）：１３８－１４０．　现的需求，给出了一种基于ＢＮＦ范式的ＬＡＬＲ（１）　语法分析器设计语言，为ＬＡＬＲ（１）语法分析器的自　动化实现提供了一种思路。　参考文献　Ｅ１３向建华．基于基准划分的编译器优化自动测试框架ＥＤ３．　北京：北京交通大学，２００７．　＊西安职业技术学院教学改革基金资助项目　（ＸＺＹ２Ｏ１４ＺＤＯ２）　作者简介：李洋（１９８４一），女，讲师，硕士，主要从事软件工程　等方面的研究。　收稿日期：２０１４－１２—２６　Ｅ２３蒋立源，康幕宁．编译原理［Ｍ］．２版．西安：西北工业大　学出版社，２０００．　责任编辑郑练　Ｅ３３虞森林．ＬＥＭＯＮ语法分析生成器（ＬＡＩ　Ｒ（１）类型）源　代码情景分析ｌ－Ｍ］．杭州：浙江大学出版社，２００６．　Ｅ４３肖增良，何锫．一种通用高效语法分析器的设计与实现　７２　《新技术新工艺》设计与计算　

本文来源：https://www.2haoxitong.net/k/doc/068d04e633b765ce0508763231126edb6e1a766a.html

《正在进行安全检测....doc》

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档

文档为doc格式

相

关

案

例

正在进行安全检测...

相关推荐

推荐内容