原文出处: 崤嶙的博客 编译器最基本的功能就是把高级语言(例如C/Fortran)编写的代码转化为机器指令(就是01串),从这个角度来说它本质上是个转换过程。经典的编译过程主要包括: 1、词法分析(Lexical Analysis) 2、语法分析 语法分析的输入是一连串的token(词法分析的输出),根据语言的语法规则不断解析最后得到一棵抽象语法树(AST, Abstract Syntax Tree),负责语法分析模块通常也被叫做Parser。在词法分析中,我们经常使用正则表达式来表示语言所接受的token的规则,类似的,在语法分析中,我们使用文法(Grammar)来表示语言的语法规则,这也早期计算机语言设计中的研究热点(同样也是大学里学习编译时最容易让人头晕的东西)。 编译里常说的文法指的是一种上下文无关文法(Context-Free Grammar),简单地说文法里包含终结符(terminal,就是26个字符、数字等等)、非终结符(nonterminal,实际是一种抽象)和产生式(production)。上下文无关文法要求每个产生式的左边必须恰好是一个非终结符,而右边是0个或多个终结符与非终结符的组合,最后整个文法还必须有一个起始符(某个终结符)。文法里还有些很重要的基本概念,例如推导(derivation)、归约(reduction)、二义性(ambiguity)、最左推导等等。 文法中最重要的基本概念是FIRST集和FOLLOW集的构造。根据这两个集合就可以很容易构造出一个预测分析表,每个行的名字是一个非终结符,每个列的名字是一个终结符,如果每个表格内没有两个以上的项,那么说明是一个LL(1)文法(Left-to-right parse, Leftmost-derivation, 1-symbol lookhead),简单地说就是向右边看一个符号就能确定下一步动作。当原文法不是LL(1)文法时,可以尝试通过消除左递归(Eliminate Left Recursion)和提取左因子(Left Factoring)对原文法进行变形得到等价的LL(1)文法。 第二种文法就是LR(k)文法(Left-to-right parse, Rightmost derivation, k-token lookhead)。这种文法的解释过程一般通过栈辅助实现,中间主要有两种动作:shift(就是将当前输入入栈)和reduce(选择产生式并从栈中弹出符号执行归约操作)。LR(0)的构成过程就是从起始符所在的产生式开始构造item,然后对每个item针对每个可能的input构造它的出边(同样还是一个item),最终所有的item形成一个有限状态机。接下来构造有限状态机,对于每个状态,如果出边是一个终结符,在对应表格记入shift操作,如果是非终结符则记入goto操作。如果S->x.这种item集,那么对每个终结符r,都记入(S, r)位置处为shift操作。 第三种SLR文法与LR(0)非常相似,区别在于生成分析表格时,对于S->x.这种item集,仅仅对于r输入FOLLOW(S)才在(S, r)位置处记入shift操作。 最后一种LALR(1)相对于LR(0)而言引入了活前缀,构造思路仍与LR(0)类似,但是构造出来的预测分析表更大。 综合起来,各文法表述能力:LL(0)<LR(0)<SLR<LALR(1)<LR(1)<LR(k),LL(1)<LR(1) 3、语义分析(Sematic Analysis) 4、中间代码(IR, intermediate Representation)生成 5、编译优化 6、目标代码生成 |
|