《编程语言实现模式》笔记(一)词法和句法分析

  1. 云栖社区>
  2. 博客>
  3. 正文

《编程语言实现模式》笔记(一)词法和句法分析

沙漠之鹰123 2016-04-21 13:34:48 浏览1471
展开阅读全文

《编程语言实现模式?可以理解为编程语言的《设计模式》,这本书的中文翻译通俗易懂,非常适合没有基础的人阅读。 本节主要介绍第一部分,词法分析和句法分析。

 

1.为什么需要学习这些模式

因为需要自定义DSL(领域自定义语言). 
人的智能非常强大,能够灵活地处理各种问题。计算机虽然迅速,但远远不及人类灵活。因此才有编程语言作为桥梁,建立人和机器的沟通方式。 
然而,通用语言功能强大,但针对特定的应用环境,可能不够简洁,同时有很多噪音,也可能难以被领域专家理解。更夸张的情况是,一些方法用通用语言非常难实现,而使用DSL则容易得多,比如正则表达式。 
在我们还不能构造出足够智能的机器前,使用DSL简洁流畅地反映人的算法和概念,便是一种折中的选择。

即使不去设计DSL,能理解DSL的原理和方法,对编程水平的提高都非常有帮助。

设计DSL看起来有难度,但当有足够的经验之后,就会发现其实有很多固定的模式可以借鉴,通过学习和熟悉这些模式,就能够更快速,方便,精确的构造自己的DSL和语言应用。

2.词法分析

字母的组合构成单词,单词的组合构成句子,所有正确的句子的组合则构成一门语言。 
对语言来说,如何判定句子是否正确?规定句子是否正确的规则称为文法。 
为了能够正确理解句子,就需要先将句子拆分成多个单词。对自然语言这叫做分词;对编程语言,则叫做词法分析。 
通常来说,一个TOKEN可能是数字,符号,单词,或是字符串。因而通过正则表达式,可以流式的切分并确定TOKEN的类型。 
值得指出,TOKEN的类型由于二义性,并不能在词法分析,而需要在语法分析时确定。

3.语法分析

在完成词法分析后,就是语法分析的阶段。语法分析的目标是将文本翻译为句法树。

LL(1)模式

语法分析就像贪吃蛇,词法分析得到的单词就像一颗颗的糖豆,最简单的语法分析可以理解为一次吃一颗糖豆。 
如果没有递归子结构,形成的结果更像一个链表,而非树结构。 
一旦语言支持嵌套结构,就需要递归下降语法分析器。如果使用本模式,生成的将是直接调用自身而无限递归的函数。 
递归下降的问题是,无法识别左递归,否则将陷入无限循环。另外,由于只向前看一个单元,可能并不能直接判断出当前的文法。

LL(k)模式

为了解决这个问题,可能需要向前多看几个单元。往前看的单元越多,贪吃蛇就在遇到交叉时顺着不同的路径看的更远,从而越知道该选择哪条路径。而做解析决策的能力越强,语言就更容易编写。 
最简单的方式,就是使用数组来缓冲所有的输入符号,以整数输入作为下标的指针。使用环形缓冲区能够方便地保存数据。

回溯解析器

有时,当文法要求语言能够支持任意多的重复结构时,要求LL(k)中的缓冲要无限大,这是不可能的。为了解决这个问题,需要采用回溯解析。 
其概念就像走迷宫,既然不能只看不走,那么就尝试去走每一个可能的选项,直到找到合适的为止。这样等价于任意地向前看。 
回溯可以设计为遇到成功的,就不尝试其他路径;也可以不论是否成功,都尝试全部路径,最后选择最长,最短,或其他自定义的筛选方法。 
回溯解析的性能远远不及LL(k),其中一大原因是重复。可能两个路径A和B, B路径中又包含了A路径。这样A路径就可能探查两遍。为了避免重复,可以通过消耗少量的内存引入记忆机制。

记忆解析器

记忆解析器使用了类似动态规划的概念,记录在某一位置时,使用某条文法的尝试结果,如成功,失败或其他的匹配特征。这样就能大大减少重复,使得回溯解析能尽可能地达到LL(k)模式的性能。

谓词解析器

有时,通过纯粹的文法很难判断选择哪一条匹配路径,因而可以通过嵌入判断逻辑,借助运行时信息调整解析策略。 
谓词解析的常用实现,是在文法中嵌入代码(如通用语言),解析引擎在运行时执行这些代码,来调整决策。

3.语言优化

生成AST结构之后,就可以对树进行操作了。主要的操作有两部分,遍历和规约。 
节点结构本身的设计值得考量,基本上有两种风格:

  • 同构弱类型:所有的节点类型一致,只通过标识符区分操作,通过列表保存子节点。 优点是开发方便,缺点是少了运行时检查。
  • 异构强类型:节点类型不一致,但都继承于一个基类。如果方法很多,会产生大量的节点类型。对于编程的工作量可能较大。另外,也不适合自动工具生成时嵌入自定义代码。

遍历

所谓遍历,看似很容易。但有一些需要注意的点。

  • 访问和执行是其实是分离的,先访问不一定代表先执行。根据执行代码相对于访问代码的位置,可以生成前序,中序和后序遍历。
  • 遍历中肯定要执行操作,对操作的描述可以放在节点定义文件中,也可以设计外部访问器

规约

在生成句法树后,可能一些树结构是冗余或无效的,也可能可以被优化为更好的结构,例如: 
0*(x+5) 由于任何数字乘以0都为0,所以应该直接被规约为0。 
规约涉及到两个问题,首先要识别特定的树结构,这就需要对树进行模式匹配,ANLNR已经有现成的工具和语法支持这类操作。

 

4.总结

编译原理的书看似很枯燥(确实很枯燥),所以一定要去实践,实践后再去看这些概念,就会觉得非常漂亮了。
目前已经采用这些技术,开发了面向序列模式发现和抽取的一套DSL。不久后将会发布。未来将开发针对树结构的分析DSL。
下一部分的内容,是该书的后半部分,程序的解释执行。然而这一部分,我还没有深入去研究,因此估计周期会比较长了。

网友评论

登录后评论
0/500
评论
沙漠之鹰123
+ 关注