- 1、本文档共20页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
构造可配置词法分析器.
构造可配置词法分析器陈梓瀚
华南理工大学计算机软件学院软件工程级本科
一、问题概述随着计算机语言的结构越来越复杂,为了开发优秀的编译器,人们已经渐渐感到将词法分析独立出来做研究的重要性。不过词法分析器的作用却不限于此。回想一下我们的老师刚刚开始向我们讲述程序设计的时候,总是会出一道题目:给出一个填入了四则运算式子的字符串,写程序计算该式子的结果。除此之外,我们有时候建立了比较复杂的配置文件,譬如的时候,分析器首先也要对该文件进行词法分析,把整个字符串断成了一个一个比较短小的记号指的是具有某种属性的字符串,之后才进行结构上的分析。再者,在实现某种控制台应用程序的时候,程序需要分析用户打进屏幕的命令。如果该命令足够复杂的话,我们也首先要对这个命令进行词法分析,之后得到的结果会大大方便进行接下去的工作。
当然,这些问题大部分已经得到了解决,而且历史上也有人做出了各种各样专门的或者通用的工具、正则表达式引擎等来解决这一类问题。我们在使用这种工具的时候,为了更加高效地书写配置,或者我们在某种特殊情况下需要自己制作类似的工具,就需要了解词法分析背后的原理。本文将给出一个构造通用词法分析工具所需要的原理。由于实现的代码过长,本文将不附带实现。
究竟什么是把一个字符串断成一些记号呢?我们先从四则运算式子入手。一个四则运算式子是一个字符数列,可是我们关心的对象实际上是操作符、括号和数字。于是此法分析的作用就是把一个字符串断开成我们关心的带有属性的记号。举个例子:是一个合法的四则运算式子,如果输入是左括号数字一级操作符数字右括号二级操作符左括号数字一级操作符数字右括号的话,我们在检查结构的时候只需要关心这个记号的属性也就是左括号、右括号、数字、操作符等就行了,具体计算的时候才需要关心这个记号实际上的内容。如果式子里边有空格的话,我们也仅仅需要把空格当成是一种记号类型,在词法分析得出结果之后,将具有空格属性的记号丢弃掉就可以了,接下去的步骤不需变化。
但需要注意的是,词法分析得到的结果是没有层次结构的,所有的记号都是等价的对象。我们在计算表达式的时候把和看成了不同层次的操作符,类似的结构是具有嵌套的层次的。词法分析不能得出嵌套层次结构的信息,最多只能得到关于重复结构的信息。
二、正则表达式我们现在需要寻找一种可以描述记号类型的工具,在此之前我们首先研究一下常见的记号的结构。为了表示出具有某种共性的字符串的集合,我们需要书写出一些能代表字符串集合的规则。这个集合中的所有成员都将被认为是一种特定类型的记号。
首先,规则可以把一个特定的字符或者是空字符串认为是一种类型的记号的全部。上文所说到的四则运算式子的例子,左括号这种类型的记号就仅仅对应着字符,其他的字符或者字符串都不可能是左括号这个类型的记号。
其次,规则可以进行串联。串联的意思是这样的,我们可以让一个字符串的前缀符合某一个指定的规则,剩下的部分的前缀符合第二个规则,剩下的部分的前缀符合第三个规则等等,一直到最后一个部分的全部要符合最后一个规则。如果我们把这个字符串作为一个记号类型来处理的话,我们可以把这个字符串替换成个串联的规则:。首先,字符串的前缀符合规则,剩下的部分的前缀符合规则,等等,一直到最后一个部分的全部符合规则。
第三,规则可以进行并联。并联的意思就是,如果一个字符串符合一系列规则中的其中一个的话,我们就说这个字符串符合这一些规则的并联。于是这些规则的并联就构成了一个新的规则。一个典型的例子就是判断一个字符串是否关键字。关键字可以是,可以是,可以是等等。当然,一个关键字是不可能同时符合这些规则的,不过只要一个字符串符合这些规则的其中一个的话,我们就说这个字符串是关键字。于是,关键字这个规则就是、、等规则的并联。
第四,一个规则可以是可选的。可选的规则实际上是属于并联的一种特殊形式。加入我们需要规则和并联,我们会发现这两个规则有着相同的前缀,而且这个前缀恰好就是其中的一个规则。于是我们可以把规则改写成与和的并联的串联。但是规则指定的规则是空串,因此这个规则与的并联就可以看成是一个可选的规则。
第五,规则可以被重复。有限次的重复可以使用串联表示,但是如果我们不想限制重复的次数的话,串联就没法表示这个规则了,于是我们引入了重复。一个典型的例子就是程序设计语言的标识符。标识符可以是一个变量的名字或者是其他东西。一门语言通常没有规定变量名的最大长度。因此为了表示这个规则,就需要将个字母进行并联,然后对这个规则进行重复。
上述的种构造规则的方法中,后面的个方法被用于把规则组合成为更大的规则。为了给出这种规则的形式化表示,我们引入了一种范式。这种范式有以下语法:
:字符用双引号包围起来,空串使用代替。
:两个规则头尾连接代表规则的串联。
:两个规则使用 隔开
您可能关注的文档
- 杭州湾世纪城广告策划方案..doc
- 杭州太子湾公园园林设计分析..doc
- 杭州电子科技大学本科学生学籍管理规定(修订稿)..doc
- 杭州电子科技大学国家级计算机实验教学示范中心..doc
- 杭州电子科技大学经济学综合专业课考试大纲..doc
- 杭州蓝谷餐厅员工手册..doc
- 杭州都市经济圈发展规划重点项目(征求意见)20080421..doc
- 杭州新能源钢结构施工专项方案..doc
- 杭师大东城实验学校学科课时教学设计第一单元..doc
- 杭州高中2011届高三第三次月考数学文..doc
- 四川省德阳市罗江中学2025届高三考前热身化学试卷含解析.doc
- 山东省枣庄现代实验学校2025届高三下学期第五次调研考试化学试题含解析.doc
- 吉林省长春市十一高中等九校教育联盟2025届高三一诊考试生物试卷含解析.doc
- 2025届江苏省盐城市伍佑中学高考仿真模拟化学试卷含解析.doc
- 2025届广西贺州中学高考冲刺押题(最后一卷)生物试卷含解析.doc
- 安徽省池州市贵池区2025届高三第一次模拟考试生物试卷含解析.doc
- 宁夏银川一中2025届高三(最后冲刺)化学试卷含解析.doc
- 广东省广州市增城区四校联考2025届高考压轴卷化学试卷含解析.doc
- 2025届邯郸市第一中学高考生物必刷试卷含解析.doc
- 2025届安徽省安庆市石化第一中学高考仿真卷化学试卷含解析.doc
最近下载
- 山东省泰安市泰山区2023-2024学年上学期期中考试七年级英语试题.docx VIP
- 财务管理实务 财务管理实务 实训指导书.doc
- 2024年新人教版九年级上册化学全册教案.docx
- 上海通用汽车GVDP整车开发流程.pdf VIP
- 苏教版四年级上册同步奥数培优 第十四讲 智巧问题.pdf VIP
- 2024年江苏省苏州高新区招聘“两新”组织党建专职党务工作者6人历年【综合基础知识500题】高频考点模拟试题及参考答案解析.docx VIP
- 2024年武汉市东湖生态旅游风景区管理委员会公开招聘机关派遣制工作人员9人笔试备考试题及答案解析.docx VIP
- 人教版普通高中地理选择性必修2区域发展.pdf
- 人体解剖学常考重要知识点.doc
- 2023年江苏苏州相城区招考聘用两新组织党建专职党务工作者23人笔试历年难易错点考题荟萃附带答案详解.docx VIP
文档评论(0)