《编译原理》作业--简易计算器

Jun. 1st, 2016


编译原理 FOLLOW集合 语法分析

这几天搞定了《编译原理》的大作业,一个简易的计算器,可以实现简单的变量声明、计算以及输出的动作,具体如下:

到目前为止做的还不完善,因为偷懒(其实是分两种类型的话语义的部分还没有想清楚),所以在计算的过程中所有的中间值全部都是浮点型,当然也就不满足整数不可以转换成浮点数这个要求,而且这样做可能导致精度问题,因此计算完成后还会有误差。

一步一步地按照编译器的构造过程来,因为只需要完成相应的动作,所以到语义分析阶段就停止了,用C++来实现。

词法分析 -> 语法分析 -> 语义分析

首先是词法分析,对于这道题而言,真正需要状态转换的只有三种元素:变量名(由字母和数字组成)数(由数字和小数点组成)空白符(包括空格、换行符、制表符等)。其余的都是单个字符,一步转换就可以到达接受态。而上述的三种中每一种的状态数也都很少,所以可以直接根据正则表达式做出DFA来,如图:

然后就是语法分析,这里用的是LL(1)文法,大致分为以下几步

  1. 写出产生式
  2. 消除左递归和左因子
  3. 求出每一个非终结符的FIRST和FOLLOW集合
  4. 确认是否为LL(1)文法(若不是要重新设计产生式)
  5. 根据两集合做出LL(1)转换表
  6. 用栈或者递归的方式实现语法分析

这里主要说一下FOLLOW集合的问题,之前一直对FOLLOW集合的求取不太理解。书上求解FOLLOW集合的过程是这样的:

  1. 对于开始符号$S$,有\$在$FOLLOW(S)$中
  2. 若$A\to \alpha B\beta$,则$FOLLOW(B)=FOLLOW(B)\cup (FIRST(\beta)-{\epsilon})$
  3. 若$A\to \alpha B$,或$A\to \alpha B\beta$,且$\beta \Rightarrow^{\ast}\epsilon$,则$FOLLOW(B)=FOLLOW(B)\cup FOLLOW(A)$
  4. 重复以上步骤,直至$FOLLOW(A)$不再增大(对$\forall A\in V_N$)

首先,FOLLOW集合记录的是可能跟在某个非终结符之后的终结符的集合,思考整个算法的执行过程,可以发现:

第一步相当于初始化,第二步实质性地向$FOLLOW$集合中添加元素,第三步将某个非终结符$FOLLOW$集合中的元素扩散到整个文法中。算法的整个执行过程相当于从开始符号$S$开始,对于每个非终结符都尝试不同的产生式(最终可能产生一棵无穷大的树,叶子节点代表这个文法所能表示的所有句子),然后对这个树的所有内部节点的每个非终结符,遍历所有由它产生的子节点,将可能跟在由这个非终结符所产生的短语(终结符的集合,比如$A\to abc$,$a,b,c$都是终结符,$abc$叫做一个短语)后的第一个终结符加到其$FOLLOW$集合中。

为什么要从开始符号$S$开始寻找FOLLOW集合中的元素?从第4步的描述我们可以看出来,算法的执行次数是不确定的,影响它的因素包括产生式的数量和复杂程度,以及每个非终结符对应的FIRST集合的大小等。只要在算法终止之前执行且仅执行一次即可。

第2步和第3步的具体作用是什么?对于第2步来说,对于产生式右边的非终结符$B$,如果在它的右边还有符号$\beta$的存在(包括非终结符和终结符),那么$\beta$的FIRST集合中的所有元素都可能出现在非终结符$B$的后面,当然,如果这个符号是$\epsilon$,相当于不存在,也就没有要加入的元素了。第3步告诉我们,对于产生式$A\to \alpha B$,如果产生式右边的非终结符$B$后面没有符号了,那么所有可能出现在$A$后面的字符,也都有可能出现在$B$的后面。这两步作为一个整体,可以保证对于每一个通过第2步改变FOLLOW集合的$B$,都会在算法条件满足之前,通过这样一个传递的过程改变它所产生的某些非终结符的FOLLOW集合的大小。

为什么第3步不是$FOLLOW(A)=FOLLOW(A)\cup FOLLOW(B)$呢?因为算法进行的趋势是由非终结符(开始符号$S$)逐渐通过各个产生式展开成句子的过程,这跟LL(1)文法推导的次序是相同的,否则就是自底向上分析了。通过这种方式,$FOLLOW$中的元素也应该是由左向右(即由开始符号到句子)的方向传递的,同时也与第2步有关,非终结符以在产生式右端的身份获得了一些元素,再通过在产生式左端的身份将该元素传递下去。倘若反向,考虑这样一个文法,某个产生式中,非终结符$B$通过第二步改变了$FOLLOW$集合,但是当它作为产生式头的时候,就不会再去改变它所产生的非终结符的$FOLLOW$集合,而且无论循环多少次都是这样。比如有$A\to B$,$B\to num$.且$B$只出现在这两个产生式里,那么算法执行完毕,$B$的$FOLLOW$集合中的元素一定为空,而它应该包含$FOLLOW(A)$中的元素。

想清楚这些问题,应该就很清楚具体怎么操作了,对于这道题,做出的结果是这样的:

然后先检查一下是否符合LL(1)文法,主要是检查这一条:

若$A\to \alpha_1\vert \dots\vert \alpha_n$,且$\epsilon \in FIRST(\alpha_i)$,$1\le i\le n$,则$FIRST(\alpha_i)\cap FOLLOW(A)=\varnothing$

这个地方用反证法比较好理解一些,假设$FIRST(\alpha_i)$与$FOLLOW(A)$有相同的元素$a$,也就是说$a$也在$FIRST(A)$中,那么在匹配终结符时,就不知道$A$到底应该匹配$a$还是$\epsilon$了,因为这两种分别符合$a\in FIRST(A)$和$a\in FOLLOW(A)$的要求。

然后就开始构造LL(1)表了,书上的构造过程是这样的:

假设$A\in V_N$,且$A\to \alpha_1| \dots | \alpha_n$,若使用$A$进行匹配,面临的符号是$a$,则 若$a\in FIRST(\alpha_i)$,$1\le i\le n$,使用$\alpha_i$进行匹配 若$a$不属于任何一个$FIRST(\alpha_i)$集合,则若$\epsilon \in FIRST(\alpha_i)$且$a\in FOLLOW(A)$,让$A$与$\epsilon$匹配 否则进行错误处理

于是就建出表来了:
至于具体的实现的两种方式,一种是栈,一种是递归,当然都是基于LL(1)表的,我在做的过程中,一开始使用了栈实现,没有显式地构造语法树,想着在语法分析的时候直接进行语义分析,但是实现到最后还是出了一些问题,就是无法在建树的过程中实现对树的前序遍历,导致对非终结符属性的赋值顺序出现了问题,而且在语义分析时基本没有用到栈里的信息,或者说不知道该怎么用...于是就放弃了,改用递归实现,可以比较清楚地把相应的语义分析的语句加到合适的位置上,然后就搞定啦~

对于每一个产生式都有相应的语义动作,要特别注意这些语义的位置。 其中维护了一个变量的表,指示了变量的信息,包括类型、名字、值及是否被赋值,在执行声明、赋值、输出语句的时候都要跟这个表打交道。

最后是错误处理部分,分为词法错误、语法错误和语义错误。词法错误说明是某个输入符号的问题,指明出错的具体位置(所处的行和列);语法错误说明是某个token的问题,要指出token的类型和对应的值;语义错误主要处理变量是否声明和赋值,以及是否重复声明的过程。而且发现如果前面按照正常的流程进行分析,最后进行错误处理时只用改动很少部分代码,而且很容易修改。

代码在这里:View Code in Github Repository

有集奇葩说蔡康永说了这么一句话

我现在评论一个人会不会写作的时候,我认为那个人写多了,然后把它改少,是比较有可能变成一个好作家。

这个作业很早就布置下来了,当时信心满满说很快就能搞定,然后也确实写了词法和语法分析的部分,但现在看来可谓全是漏洞,当然现在的程序也不完善,比如我在开头说的数字的问题。

尝试永远是必不可少的,可我总是希望跳过这一步骤,总想一气呵成,可是现实告诉我,不是这样。况且尝试并不是坏事,说不定以后的某个功能用之前尝试了但没有被采用的方法会更好,正是因为说不定,尝试才变得有意义,而尝试所花费的时间,可以看作是让以后更加舒服的代价吧。