编译器前端回顾(上)

在设计编译器的前端时,程序驱动的主干是字符串的匹配,所回答的基本问题是输入文本是否能够匹配预定义规则,因而返回值是是或否

对于回答是的情况,说明输入文本落在了预定义规则划分的范围内。可当规则的描述具有一定规模、较为复杂的时候,又需要知道具体匹配到了哪些规则,这时才会涉及到翻译的问题,常称作语法制导翻译,原因是输入文本的匹配以及翻译前后的字符串的表示问题都围绕语法规则来展开。

对于回答否的情况,说明输入文本落在了预定义规则划分的范围外。使用者关心的问题会是文本的哪个部分在匹配哪个规则的时候出了问题,设计者需要以易于理解的方式准确、高效地回答使用者关心的这个问题。错误的处理看似是一个边角料的问题,对编译器的设计者而言,与翻译问题是同一个层面的问题,无法回避。

对输入文本进行建模,一方面是以基本的概念对其进行抽象,摒弃不关心的部分,规定清楚边界;另一方面是运用定义的基本概念对输入文本进行描述。听起来这个方法论同前面提到的匹配基本问题的方法论是相似的,概念即是规则,概念即是边界,这是理解与交流的基础,是广为认可的方法论。

在建模输入文本时,设计者引入了字符、字符表、字符串和语言等基本概念,忽略了字符的样式、大小、空间位置、书写方向、颜色等。规定字符为基础元素,字符表为字符的集合;字符串为按照一种次序依次连在一起的字符的复合元素,空串是没有任何字符的复合元素,语言是由字符表中任意的字符组成的某些字符串所构成的集合。在此基础上,对复合元素字符串引入了前缀操作、后缀操作和连接操作,对集合语言引入了并操作、连接操作和闭包操作。

将每一个输入文本都看作一个字符串,当作一种语言,理解起来简单,但语言的数量就等于了输入文本的数量,无法提前预定义规则去解决匹配的问题。将每一个输入文本的每个字符当作一个字符串,这些字符串构成的语言也就是字符表本身,能够描述所有的基于此字符表的输入文本,这样的语言预定义规则是确定的,语言的边界就是字符表的边界。通过以上两个角度,能够看到对输入文本切割的太粗或者太细,所得到的语言都距离人们习惯的自然语言相去甚远。如何选取文本的切割粒度,是门艺术,所持的原则是,让编译器所翻译的语言尽量靠近自然语言。之所以说是艺术,因为无法找到度量,能够说明按集合理论建模出的语言多么靠近自然语言,其中的难度在于自然语言是自然演变的,且在不断地发生着变化,并不存在一种符号系统对其自身再作出完整的描述,因为任何的符号系统一旦建立都是确定不变的,用不变去描述变化,其中总存在着的误差,永远无法弥合。

如何将输入文本切割为合适粒度的字符串集合?就需要通过设计预定义规则对其进行描述。这样的规则系统就是上下文无关文法。一个文法是一个产生式的集合,一个产生式通过非终结符的替换,能够推导出一个句子,而一个句子可以是整个输入文本或者只是部分的输入文本。产生式规定了切割的粒度。

产生式是值得深入讨论的模型,看似简单,却又千变万化。产生式的左端是非终结符号,规定可以被替换成右边的字符序列。产生式的右端是终结符和非终结符组成的字符串。终结符来自于字符表,而非终结符来自于字符表之外,单独构成另外的一个集合。

观察单个的产生式,像是一个变量的定义,也像是一个函数的定义,像是一个类的定义,总之像是一种定义,就是拿一个符号来代表一组固定序列的符号。文字上人们称其为替换,逻辑上人们称其为抽象。看到产生式的左边,将其替换(展开)为右边的操作称作推导。看到产生式右边,将其替换(合并)为左边的操作称作归约。

观察单个产生式的左边和右边的非终结符,存在一种特殊的形式:递归,即产生式右边的非终结符里包含产生式左边的符号。对于某个非终结符如果存在一个递归的展开(A → Aa ),那么一定还要有一个非递归的展开(A → b ),否则推导无法结束。容易联想到,在数学递推公式中等于在说,必须给定初始条件,否则推导无法结束。此外,这也往往作为检查递归程序是否正确的重要一点。

根据左边的符号在右边出现的位置不同,分三种情况,开头、中间和结尾。出现在开头,被称作左递归。出现在结尾,被称作尾递归。出现在中间,就是普通的递归。左递归是设计文法时要避免的,含有左递归的文法无法进行自上而下的分析。消除左递归需要引入新的非终结符并利用空串,添加新的产生式。普通递归和尾递归在文法设计时没有特殊之处,可在设计解析器的时候,尾递归往往可以进行优化,即返回当前调用的上下文,清除当前栈帧,而进行新的调用,减少调用栈的层次。这样的优化虽然对执行本身起到了好处,但却给调试工具引入了麻烦。

观察两个产生式之间的关系,有三种:并、嵌套和不相关。并指的是两个产生式具有相同的左端。嵌套指的是一个产生式的左端出现在另一个产生式的右端中。不相关是指不存在并和嵌套关系的关系。并的关系是对称的偏序关系,嵌套的关系是不对称的偏序关系。文法推导的过程中需要做两个选择,其一,存在并关系的产生式中选哪一个;其二,一个产生式的多个嵌套产生式中选哪一个。这也是文法产生二义性的来源。第一个选择可以就输入符号的情况加以选择,在自上而下的分析方法中表现为向前看几个符号的问题,在自下而上的分析方法中表现为不同项集之间的状态转移问题,此外,还有二义文法中利用优先级和结合性来额外处理的问题。第二个选择可以规定从左到右展开还是从右到左展开,从左到右的方法称作LL,从右到左的方法称作LR。第一个L是指的从左到右扫描输入文本,第二个是指的推导的展开次序。自下而上的分析方法虽然是归约式的,但其逆过程等价于一个从右到左的推导过程,因而常常被称作LR的。

产生式模型的构建,将设计语言的问题转换为了设计产生式的问题,如何设计非终结符,如何规定非终结符的右端,选择设计多少个产生式,这是一个相对开放而又复杂的问题,并不在编译原理课程的讨论范围内。编译原理中关注和解决的问题是如何在给定了产生式集合的情况下,生成一个自动机,高效地完成匹配任务。

编译原理中介绍了两种自动机,一种是不带栈的有穷状态自动机,另一种是带栈的有穷自动机。不带栈的有穷状态自动机通常被称作有穷状态机,通常包含一个状态转换的驱动程序、一个状态转换表、输入字符串和输出。带栈的有穷状态机通常被称作下推自动机,除了包含有穷状态机中的四种东西外,还包含一个不限大小的栈。虽然驱动程序和状态转换表两种自动机都有,但内容相似却不同,下推自动机的驱动程序中不只是移动输入和转移状态,还包括弹栈和入栈的操作。Lex可以用来将一组正则表达式生成一个有穷状态机,被用作词法分析器。Yacc可以用来将一组产生式生成一个下推自动机,被用作语法分析。正则文法能够表达的三种操作都能够用上下文无关无法表达,反之却不可以。如何选择哪些部分应该用正则表达,哪些部分应该用产生式表达,基本原则是如果能用正则就尽量用正则,如果不能则用产生式,例如括号、语句块、条件分支、循环、嵌套、递归等。

若输入文本有错,报告错误的一个原则是,尽可能多、准确、快速地报告错误。若要达到多的目标,就要用到恐慌模式的思想,即碰到一个错误,记录下来,不要退出程序,消化错误,继续向前解析。采用的办法往往是丢弃掉一些输入,找到较为清晰的同步词法单元。若要达到准确的目标,就要用到短语层次的恢复策略,为不同的状态转移动作设计专门的报错例程。若要达到快速的目标,主要还是在于保证匹配算法本身的效率,与报告错误的处理关系不是太大,但也要尽量减小错误恢复的空间开销。

发布人

jeremy1990

现居北京,就职于亚马逊中国,软件工程师。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注