1.介绍

解析就是识别语言式子中的元素和子结构。主要的解析模式有以下几种:

  • 模式一:从文法到递归下降识别器,将文法手动转化为解析器的过程。(后面3种模式用到该模式)
  • 模式二:LL(1)递归下降词法分析器,把字符流分解为词法单元(token),以供后面的解析模式使用。
  • 模式三:LL(1)递归下降语法解析器,最有名的队规下降语法解析模式。她只根据当前的输入字符来决定如何解析,并且对文法中的每条规则都提供了相应的解析方法。
  • 模式四:LL(k)递归下降语法解析器,是模式三的增强模式,最多向前k个输入字符来决定如何解析。

可见解析器包含了

  1. 识别token
  2. 词法分析器
  3. 语法分析器

总结:这里说是4个模式。。。觉得有点让人迷惑。其实上这4个模式就是解析器中识别器、词法分析器、语法解析器这些基本部件。可以共同合作完成解析功能。

2. 相关知识

2.1 解析树

确定词法单元(tokens)的功能称作语法分析,一般可以采用解析树。
例如:

2.2 构建递归下降语法解析器

解析器的任务是遇到某种结构执行某种操作。解析器不必构造具体的解析树,只要依靠一些专用函数从来匹配并且处理器对应的子结构即可。


match是比对函数,用于匹配词法单元token,如果存在if,return这些语句,可以通过往前看1个词法单元来判断,以跳转到不同的解析分支


这种解析方式从解析树顶部开始往下处理,直到叶子节点。因此叫做自顶向下语法解析器。这种即是模式三中的LL(1),1代表向前看1个token,第一个L代表从左到右解析输入内容,第二个L代表从左到右顺序遍历子节点。LL(1)无法解决做递归文法的识别,可以采用LL(K)

总结:以上方式是没有用到文法来识别token的,每次都需要手动match具体的词法单元,繁琐又容易出错。因此我们引入了DSL文法来构建语法解析器。

2.3 使用文法DSL来构建语法解析器

引入文法后我们可以用语法图来表示三种不同的语句

解析器一般不需要手工编写,只要使用ANTLR文法来自动生成即可。

2.4 LL(k)语法分析器

向前看多个的时候在实现时可以采用环形缓冲区,用一个数组配合下标取摸就好了。例如是k=3就可以模3.