Compilers 笔记(一)

开始学习 coursera 上关于 compilers 的东西,做一些笔记留作参考。

compilers 的组件包括:lexical analysis,parsing,semantic action、optimization 与 generator。传统 compilers 实现重在前面,但是现在词法分析和语法分析都有很多现成的工具了,比如 lex/yacc 或者 boost::spirit::lex 与 boost::spirit::qi。在词法分析的时候通常使用 regex 来进行匹配,但是我们通常需要一些扩展来使得词法分析不具有歧义性(比如我们通常会定义什么是 keyword、什么是 identifier,但是这两个 RE 之间存在交集):

  • 贪婪匹配,即每次使用 RE 中能匹配最长的 input 的
  • 优先级,比如 keyword 优先级高于 identifier

那么一个好的 lexical analysis 算法应该只需要单次遍历字符串,每个字符使用的操作越少越好。通常为了实现 RE,会使用有限状态自动机(FSA),从 RE 转换到 non-deterministic FSA 比较容易(但是匹配时一般需要记住所有可能的状态),之后往往会将 non-deterministic FSA 转换成为 deterministic FSA(查表即可),这样匹配时效率会更高。

lexical analysis 将字符串的 stream 处理成为了 token 的 stream(token 就是 lexeme + token class),parser 将其 parse 成为所谓的 parse tree。这部分 parsing 需要 grammar 来协助,这引入了更为 powerful 的 context-free grammar,这时如果给出 tree 之后进行 in-order traversal 就得到了我们观察到 token stream,但是问题是我们观测到 token stream 怎么重构出 tree。这里就连最简单的语法都可能导致一些问题,比如四则运算的顺序,比如嵌套的 if-then-else,我们总可以通过一定的策略修改语法,体现出优先级(比如将 +* 分成两个 production 来描述,+ 的那个只能 handle +,但必须通过 * 的那个进去,这样就导致 * 会优先被处理;又比如 if 里面细分为 matched 和 unmatched 版本,要求 unmatched 版本的 then 从句里面只能是 matched version)。但是这样往往会将语法弄得非常的复杂,通常的工具都是建议使用带歧义的语法,然后通过一些声明来帮助 parser 找到唯一的 parse tree,比如结合律、优先级等等。

一个有意思的事情是如何实现一个 parsing 的算法,比较容易的想法是 top-down parsing。通常我们会有若干个 production,我们为每个 production 创建一个函数,如果 parsing 成功返回 true,否则返回 false,这样我们使用这个 grammar 的 parser 的时候依次调用每个 production 看是否匹配上就 ok 了,值得注意的是因为每个 production 并不注意处理完后 token 的位置,往往我们得在调用者那里保留原始的位置,这样一旦某个 production fail 就能回退。每个 production 都有几条 rule,这个 production 的实现其实也很类似,依次每个 rule 去尝试就行了,注意某些 rule 可能引用了别的 production,这样就变成了递归调用,因此我们只需要提供一些 terminal 的 parser 就能形成我们最简单的 parsing 算法。这也被称为 recursive descent parsing。这个算法要求语法不存在 left recursion,比如 X \gets X0,这样可以不断的调用自己,类似的多个 production 的互指也能导致这个情况。解决这个问题的方法是重写语法避免 left recursion。

RD parsing 的一个问题是我们可能会尝试很多次才能找到匹配的 production,为此我们希望能够用某种方式加快找到正确 rule 的,这势必会对语法产生一些限制,我们知道 RD 可能同时有几个 production 能匹配到当前 input,这是因为语法并没有要求每个 rule 读入下个输入的类型不同,为此我们引入所谓的 LL(k) 语法(left-to-right leftmost grammar),往往 k = 1(实现方便,只需要看下一个 input token)。这相当于要求每个 production/rule 匹配下一个 input token 必须是不同的,这样我们根据下一个 input token 就能选择合适的 production/rule(如果没有这个 token,说明是非法匹配)。这个算法需要向前看一个 token 做 prediction,因此叫 predicative parsing,它首先为每个 non-terminal 建立一个 table,表示输入为什么 token 时用什么 rule 来匹配,看这一个 rule 的结果就知道 parsing 是否成功了。如果用户给出的语法并不满足 LL(k),我们可以将其重写(left factor),将具有相同前缀的 rule 合并,跟上一个新的 production 处理不同的后缀即可。实现 parsing 的时候我们不再使用 recursive call,我们可以使用一个 stack 来帮助我们:我们将展开的 production 放在栈里面,每次从栈顶取一个出来,如果是 nonterminal,根据 input 就能展开成新的序列(并不消耗 input),我们将新的序列压栈;如果栈顶是 terminal,我们就跟 input 匹配,成功从栈顶拿走消耗掉对应的 input 就行了。这样如果匹配完 input 之后栈空则说明成功 parse 了。

剩下的问题其实就是如何构造一个合适的跳转表了,为此我们引入 first set 和 follower set 的概念,前者表示一个 production 其可能的第一个 input,为了求出这个 set,我们可以依次看对应 rule 第一个是否为 terminal,是的话将对应 token 加入这个 set,否则看对应的 production 的 first set,我们可以得到这些 set 的相互关系;后者我们应该观察被考虑的 production 出现在哪些 production 里面,这样我们就知道它后面可能是哪些 terminal,或者后面一个 production 的 first set。由此,我们就能确定所有的 production 的两类 set。在构造 predicative table 的时候我们对于每个 production 因为我们知道对应第一个可能出现的 token 是什么,我们只需要将对应的 rule 去掉输入 token 那部分之后放在表内即可。比较特殊的情况是如果 follower set 里面包含最后的结束符,我们需要将对应的跳转弄成空串。如果构造这个表格出现一个空可以填两个结果,往往是语法不满足 LL(k) 的限制。实际上这个限制太强,导致实际中很少有满足这个要求的 CFG,比如存在 left recursion、有歧义等等都会违背 LL(k)。

那么还有没有别的 parsing 策略呢?当然是有的!使用 top-down 的方法的核心是我们一个一个可能来试(虽然 predicative parsing 试图避免这个事情,却对语法产生了较强的约束),我们是否可以 bottom-up 的来考虑这个问题呢?top-down 的本质是在做 derivation,我们是否可以反其道而行之(称为 reduction),即读入一部分数据后(shift),通过 reduction 建立一个 parse tree 的子树(直观来说就是将 terminal 合并成为了 production),这样在后面读入新的 token 后不断的 reduce 成为更大的树,这个算法称为 shift-reduce,可以看出来我们实际上是沿着 right-most derivation 的逆过程来完成对 parse tree 的重构的!

回到实现上来看这个想法的实现过程我们可以考虑将 shift 读入的 token 放在一个 stack 上,导致我们产生 reduction 的时候相当于从栈内取出若干个 token 或者已经 reduce 过的 production 进行进一步的 reduce 并将结果放回栈内。那么现在问题就是我们是否能只通过栈顶元素就能判断当前的栈内信息能会退到 start symbol?我们称这种 reduction 为所谓的 handle,如果我们每次都能找到正确的 handle,从而就能在合适的时候调用 reduce。这种算法可能出现问题的是两种冲突:shift-reduce conflict 指某个情况下既可以选择读入更多的输入也可以选择 reduce;另一种情况称为 reduce-reduce conflict 表示同时可以做两种 reduce。那么识别 handle 的一个重要的 trick 就是需要注意到栈上的数据构成的 prefix,这对我们决定后面的处理步骤非常重要。

对于前缀的处理比较常见的做法就是构造一个 NFA,我们可以如下构造一个 NFA 来帮助我们分析 viable prefix。我们提供一个新的 start symbol,并将其指向原先的 start symbol,这个 item 作为我们的 NFA 的起点,之后我们构造 NFA 的规则如下,如果是一个 terminal 开始的 rule,就只能通过这个 token shift(移动当前位置);如果是 production 就需要在碰到它时跳到它结束的地方,或者跳到这个 production 对应展开的节点上,我们需要 NFA 的原因是我们也不知道某个 production 会如何展开,这需要 epsilon 跳转。使用这个 NFA 只要是定义过的跳转就是合法的,否则是非法的。实际使用的时候这个 NFA 需要转换成为确定性的自动机,比较简单的就是将状态的集合作为 DFA 的状态,这里 DFA 状态就被称为 LR(0) items。

一般说来下面介绍的算法能处理的语法称为 SLR grammar,它是 LALR grammar 的子集,而 LALR 又是 LR 的子集,LR 是 unambiguous grammar 的子集。这个 LR(0) 是如下利用以上的概念的:借助 DFA 处理 stack,看看当前状态是啥,如果这个 DFA 包含可用的 reduction 就使用,否则看看是否存在 shift 下一个 token t 的 item,有就按照下一个输入的 token 做 transition。这样这个算法可能存在前面讨论的一些冲突情况。为了消解这些冲突,我们可以使用所谓的 SLR(减少冲突)。我们只需要要求 reduce 的情况是要求当前的输入的确是使用的 reduction X 的 follower。这个也就是我们确定 handler 的启发式规则,如果某个语法满足我们就称其为 SLR(1) grammar。通常 SLR 不能解决比如 +* 混合具有歧义的语法,但是这种情况相当于有两个 item 满足产生 shift-reduce conflict,通过优先级就能很好的处理这种情况的语法,也就是说 precedence declaration 的本质是帮助消解冲突。

那么一些基本的改进包括,我们不必每次重新把 DFA 从头到尾过一遍,我们可以在栈里面多记录走到这里 DFA 的状态,这样万一需要 reduce,我们只需要将 DFA 从之前一个那里走一步到新入栈的 production 即可。另外一些细节包括,我们需要为 DFA 建立一个跳转表,同时定义两种 action(对应 shift 和 reduce),这个 action 我们也能做成一个 table,这是基于每个 DFA 状态和 terminal 做的,表示当前状态为 s 下一个 token 是 a 时的行为,我们知道这个很简单,如果有 shift 的 item,我们查跳转表获得下一个状态,然后调用 shift 类型的 action;否则在满足 reduction 且产生的 production 的 follower 里面包含 a 时,且这个 production 不是 S’ 时进行 reduction(最后这个条件如果不满足表示已经 parse 结束了),

有了这部分知识后,我会继续看看 dragon book 上的相关章节加以巩固。之后继续 compiler 相关的学习。

—————-
And they did eat and drink, he and the men that were with him, and tarried all night; and they rose up in the morning, and he said, Send me away to my master.

Advertisements
Compilers 笔记(一)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s