PA10之开始:由PA6的Parser想到的一些问题

最近打算着实地开始将两年前结束的 CPPGM 的 PA6 解析器重新用起来,用于解析(文曲星上的)GVMaker 文件。选择 GVMaker 主要还是想要完成以前的一个愿望,而利用 PA6 的解析器则是为了让 CPPGM 这个课的参与能稍微再完整一些(虽然已经结束两年多了,)能够在一个比较完整但是整体规模(不光是语法,还包括之后的代码生成和运行时之类的)也不是很大的语言上做一个相对完整的编译器流程。而取名为 PA10 ,只是因为它在 PA9 之后而已。

这次主要是想清楚了两件事情:

  1. 意识到一次解析的过程和结果都能用来表示,过程是「决策树」,结果是「语法树」,而结果是过程的一个子集;
  2. 用了一个类来维护在遍历和修改这棵树时的各种状态,减少代码累赘。

现在分别说以上两点。

※ 决策树与语法树 ※

决策树的建立方法是这样的:在解析到一个规则时,每根据这条规则右边的产生式产生一个新的非终结符,就给当前结点添加一个子结点。也就是说一个结点可以有N个子结点。这决策树是在解析器试探输入文件时的调用栈所扫过的痕迹。

而相比之下,语法树和决策树一模一样,但是只是只在成功的情况下才保留子结点,否则则删除子结点。另外语法树的结点中还包括终结符,不像决策树的结点中只包括非终结符。

所以如果给了以下输入:

int a;

这个文件的全部内容就是声明一个全局变量 int a。它最后解出来的语法树也反映了这一点:

Parse Tree of

树中,“int”是一个“simple_type_specifier”,“a”是一个“id_expression”,加上分号,三者构成了一个“simple_declaration”,最后组成了一个“translation_unit”。

这个语法树所对应的决策树是这样的(其中绿色的结点对应着语法树中的结点):

Decision tree generated while parsing

可见在解析时,解析器进行了两次“declaration”的试探。其中第一次试探发现了“int a;”的声明,而第二次试探完成后发现并没有更多的声明,就结束了。

整个 parsing 的过程,也就是根据每次解析的结果成功与否不断对决策树进行调整,直到找到符合语法规则且吃掉了所有 token 决策树时将树输出的过程。

※ 记录(bookkeeping)的事情 ※

记录的事情有以下这些:

  • 表示当前这个非终结符走到了第几个分岔(即是决策树中的分岔),例如
    noptr-declarator-root:
        declarator-id attribute-specifier*      
    
  • 每个分支成功与否
  • 当前的 Token 的位置。
  • 当前的递归深度。递归深度并不一定等于分岔的位置,就是因为在一个非终结符所对应的一条规则中,如果出现了加号或是星号,就可能进行多次尝试。
  • 当前所正在生成的语法树结点以及父结点。

这几点在 PA6 的解析器中,都直接以变量的形式存在。这样每次新增一条语法规则时都太容易出错了。为了减少出错,这回把这些信息都存在一个称为 ParseState 的表示解析状态的类中。它与其它部分的联系是:

  • 从「整个解析器」的角度看,在进入最外一层(translation_unit)时:
    第一种可能是刚进入,此时的「决策树」是空的;或者
    第二种可能是接续上一次失败或成功的解析,将「决策树」前进一格,然后再进行尝试;
  • 从「非终结符」的角度看,在进入一个非终结符的这条规则时,相应地也有两种可能:
    第一种可能、刚进入时,需要往「决策树」中新加入这次尝试所走的分岔;
    而在第二种可能、也就是因循上一次解析时,需要从「决策树」中读出这回应该尝试的岔路;而在「因循上一次的决策」结束时,又要回到第一种情况,向决策树中添加新的结点;
    所以,就有两个地方会对「决策树」进行修改:第一个地方是完成一次解析后的「进一格」,第二个地方就是在非终结符中新增新和结点。
  • 从「一条规则」的角度看,在需要解析一个非终结符时:
    如果是首次出现的非终结符,那就需要将语法树中深入一层;
    而如果不是首次出现的非终结符,那就保持语法树的层次。
    也就是类似于在深度优先搜索时需要记下每一次访问到了第几个子结点那样的。
    而这个地方的处理也要和分岔的进位一起考虑起来。

因为在解析的过程中 ParseState 会一直被改变,比如他的 Token 位置会一直前进和后退,分岔和递归深度需要一直更新或回退。所以在设计时就有了以下函数:

ParseState::OnFirstNT() 此条规则中,所遇到第一个非终结符时的拷贝构造
ParseState::OnNextNT() 这条规则中,所遇到的其后的非结结符时的拷贝构造
ParseState::NextChoiceFrom() 是在这一条分岔走完时用的拷贝构造函数

PA10Parser::ConsumeToken() 是搭配 OnFirstNT 所使用的
PA10Parser::ConsumeTokenToParent() 是搭配 OnNextNT 的。(*)

PA10Parser::OnEntry() 在进入一个非终结符时需要做的事情
PA10Parser::OnExit() 在离开一个非终结符时需要做的事情

(*):这两个 ConsumeToken 的存在是因为一条规则中所沿用的 ParseState 有数据依赖关系,在而这些相依赖的 ParseState 会因为某时调用了 OnFirstNT() 而使得 AST 向下进了一层。对于非终结符来说,一定要进一层;但是对于 Token 来说,并不一定要进一层。所以才会有「对于 Token,在进一层之前,调用 ConsumeToken ,而在进一层之后,调用 ConsumeTokenToParent 」的现象。

以上这些,还要搭配正确的赋值,并且将每个非终结符中的不同分岔以一个 switch 语句括起来,才能正确地处理解析中的其它情况,比如说带有星号、加号、问号的规则。

总结起来

这个 parser 目前尝试过的最大的输入是 yan 的编译器,算上所有的包含命令,一共有大约 81000 个 token 。每次 parse 用时大约 20 秒。

此条目发表在Uncategorized分类目录。将固定链接加入收藏夹。