编译原理科目分析和解题方法（转贴）

编译器

初步了解编译原理

　　考研的朋友很多都是计算机专业高年级（或者同等水平）的学生，对于编程已经不再陌生，甚至我们很多人都要把它作为一门安身立命的技术。这里先给大家出一个很小的题目，它不是考研试题，而是一个公司在一次招聘时出的考试题目，很有意思，题目是这样的：

　　以DOS为操作系统，使用C语言，编写一个函数，功能是取得当时的BP寄存器的值，只能使用标准的C语句（也就是不能使用扩充的宏等其他手段）。

　　如果大家在面试的时候遇到这道题目，头脑中能够马上反应出这到底考的是什么吗？这里实际上考的是编译程序的存储组织。

　　下面我们简单分析一下该题。我们知道C语言是栈式存储分配，局部变量的分配和参数传递都是通过栈来完成的，在调用函数的时候，首先把被调函数的参数从右向左依次压入栈，再把返回地址压入栈，然后转入被调函数内部，进入被调函数以后，首先执行固定的两条指令：

　　PUSH BP
　　MOVE BP, SP

　　这样，通过BP寄存器，加上或者减去一定的偏移量，就可以对传递来的参数和函数内新分配的局部变量进行寻址了。到这里，我们就找到答案了，这个题目所要求的函数内不需要做任何实际的工作，只需要声明一个整数类型的变量，那么显然这个变量就在栈顶，而它的下面的两个字节保存的就是在调用这个函数之前BP寄存器的值（也就是上面说的指令PUSH BP 所保存的内容），将这个值返回就可以了，也就是把这个整型变量的地址加2后的内容返回即可。

　　这里举这个小例子就是为了说明编译原理对于编程的重要性，它可以帮助我们更深刻地理解程序运行时内部的机制。
编译原理科目分析和解题方法(2)
2002年11月22日11:34:12　网易教育　前沿考试研究室

　　这里我们回顾一下我们学习编程的历程：最初通常是学习一门高级语言，比如C或者Pascal，这样就掌握了编写一些简单程序的方法；然后又学习了数据结构，这是一门非常重要的课程，学习了数据结构，我们的头脑中建立了“算法”的概念，对编程有了更深的理解，遇到问题的时候，我们知道应该寻找相应的数据结构模型，设计适当的算法来解决问题；此外，我们通常还要学习汇编语言，尽管大多数人并不会在实际中用汇编语言来进行开发，但实际上，这门课程是我们真正深入了解计算机内部的第一门课程。通过学习汇编语言，我们知道了每一条指令是如何在计算机内部运行的。而此时，我们已经可以编写很多程序了，但是我们还不知道高级语言最终是如何成为汇编语言，甚至机器语言的，这时，编译原理课程就可以帮助我们了解高级语言变成汇编语言的过程。更进一步，要想了解高级语言是如何变为机器语言，以及如何在CPU内部运行的，就要通过计算机组成原理的课程的学习了。这样，我们就可以清楚地认识到编译原理在计算机学科中所处的重要位置了。同时，我们也可以看出，它的复杂性和学习的难度都是很大的。

　　1 编译原理不好学

　　编译原理课程的一个明显特点是它的理论性很强，在学习的时候需要很强的逻辑思维能力。这门课程初看起来内容很多，而且又非常抽象，如果和“数据结构”比起来，就会发现，编译程序所涉及的算法要复杂得多，而且要深入地理解这些算法也很困难。比如在学习数据结构的时候，我们也会接触很多算法，经常会跟踪算法的执行过程，比如遍历二叉树等。而跟踪编译程序中的算法则要麻烦得多，从而要想深刻理解算法的思想就很困难。编译程序的构造方法确实非常精妙，就像一部走时精确的时钟，很多齿轮、部件协调地运转，以驱动指针准确地旋转；编译程序也是如此，一边扫描源程序，一边经过各个部件的运算，准确地输出为目标语言。

　　2 编译原理也不难学

　　上面说了编译原理不好学的原因，但如果我们弄清了这门课程的特点和规律，以及它作为一门考试科目的特点，就会发现攻克编译原理其实也不难：

　　1．编译原理课程各个部分之间的独立性很强，实际上就包括了词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。而且其中前两个部分是其中的重点，也是难点，需要掌握比较复杂的算法逻辑；其他部分相对来说知识性更强一些。另外，编译原理每个部分之间的方法也互相独立，在复习的时候，便于逐个击破。

　　2．实际上编译原理考试考查的内容相对来说是很稳定的，而且绝大多数题目的解法都非常机械，如果熟练掌握，考试的时候沉着冷静，不要粗心，做对是非常容易的。

　　具体举例说明一下，比如词法分析这一部分，如果仔细研究之后，就会发现，最重要的就是要掌握图0.1中的6个转换关系。比如给出一个正规式，然后要依次求出相应的NFA、DFA、最小化的DFA等，而这6种转换关系都有确定的方法，只要熟练掌握了相应的方法，无论怎么出题都应该能够套用。



　　再比如语法分析部分，这部分是整个编译原理考试中比重最大、难度也最大的一个部分。但仔细分析之后，我们会发现，语法分析只有两大类：自顶向下和自底向上，每类中又有几种不同的方法，每种方法都对应于一类文法。因此在复习的时候，首先弄清楚每种方法适用的具体条件，具体解法套用相应的步骤就可以了。

　　下面以自底向上得LR分析法为例加以说明。LR分析法通常包括了4种具体的分析方法：LR(0)、SLR(1)、LR(1)、LALR(1)分析法，这4种LR分析法的原理如图0.2所示。



　　这4种LR分析法的总控程序是相同的，只是分析表不同。因此复习的关键是掌握构造分析表的方法，以及使用分析表进行分析的方法。LR(0)是LR分析法的基础，首先要深刻地理解LR(0)分析法的思想，熟练掌握LR(0)文法的判断方法和LR(0)分析表的构造方法，这里再次强调，其方法是非常机械的，只要多加练习，就可以掌握得非常牢固，只有这样，在考场上才能游刃有余。

　　在掌握了LR(0)分析法后，就可以看出LR(0)分析法要求构造出的识别可归前缀的有穷自动机的各个状态不能有冲突项目，而SLR(1)分析可以部分地解决这个问题，其方法是向前多看一个输入符号，这样又需要掌握SLR(1)分析法，同样要注意其适用的文法限制和分析表的构造方法。要注意SLR(1)只是部分解决了LR(0)的缺陷，当我们需要进一步加强分析法的能力时，就到达了LR(1)分析法和LALR(1)分析法，大体的复习思路都是相同的。

　　这4种分析法都掌握后，最好仔细总结一下其内在的关系，使用的文法限制等。总之，这部分要掌握每种分析法适用的文法，并能构造出相应分析表，以及应该做到当给出一个该文法的句子，能够跟踪使用分析表进行分析。

　　其他各个章节也都有类似的特点，大家在复习的时候应该认真地进行总结，提纲挈领地抓出线索，熟练掌握具体的方法。一定要多做习题，千万不能觉得自己知道方法了，就不用亲手做了。尤其对于编译这样的学科，题目的规模很大，步骤繁多，而且前面的步骤一旦出错，后面都错。如果不熟练掌握的话，考试的时候必定慌乱，所以切忌眼高手低，一定要多加练习，才能到考场上沉着应对。

　　客观来说，如果这些大的方法（如DFA相关的转换、LR分析法）都掌握了，即使对编译原理本身的理解并不十分深刻，也可以应对考试。因为在考试中绝大部分都是常规题目，抓住这些常规题是效率最高的复习方法。

leonalgo

收到~~~