跟大家谈谈编译原理（续）

作者：来自：阅读次数： [大中小]
跟大家谈谈编译原理（续）感谢网友的支持，让我不得不把这篇文章好好的写出来。
上次跟大家粗略的谈了一下编译原理，相信大家已经了解到他的过程大致是：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成。而凭借我目前的能力，我只能讲述前两个方面的知识，而且只能说到我所了解的深度和广度，同时基于时间，我实在不能说得太多。
1．词法分析
首先必须明确，单词是语言的基本单位。词法分析是编译的第一个阶段，其中心任务就是识别出源程序中的单词，并告诉下一阶段（语法分析）这些单词是按照怎样的顺序组织的，并且要承担一定的语义分析任务（比如说保存变量的值、区分标识符的类型）。我们将单词常常划分为以下几种类型：（1）标识符 它可能在源程序中充当函数名，也可能充当变量名，甚至有可能充当标号（如果在程序中允许使用goto）。（2）关键字 它是语言的特征之一，如常见语言的关键字有：char、int、if、else、switch、case、while、for┉┉等等（3）运算符 即运算符号：+、-、*、/、&┉┉等（4）界限符 常见的有： ； ， ： （） 等等（5）常数
要知道当前单词是哪一种类型，就必须了解单词的词法规则描述。我们通常使用正规表达式来描述单词的构成，比如说标识符可以被定义为：letter(digit | letter)*，即以字母开头，后面紧跟字母或者数字（这也是C语言中对标识符的规定）。
那么究竟如何进行词法分析呢，关于这一点，一般的教科书首先都会告诉你关于自动机的概念和理论，当语言的词法比较复杂时，利用自动机却是十分有用，因为它能简化程序中的状态数。但我习惯于不去构造有穷自动机，而是手工直接编写代码，这也许不是一个好的习惯和作风，但分析的语言对象很小的时候是完全可以应付的。
我建议你为每种单词定义一个整型的类型号，你以后将发现这在自下而上的语法分析中很有用，简直就是必须这样做。
写出词法分析程序并不困难，然而你一定要好好的构思一下程序的整个结构，据我所知，在过滤空白字符上最容易出错，将空白字符的过滤代码放在程序的那一部分以及回退字符的处理是词法分析中值得注意的两个方面。
我总觉得词法分析实在是简单不过，然而我也不能保证自己编写的代码是高效而且优雅的，尤其在文件读写方面，我总觉得TC有很大的问题。
好了，词法分析到此结束，如果你还有什么问题请告诉我。（如果我能起作用）
2．语法分析这里的工作就是对词法分析的结果进行处理，词法分析的结果大概是这个样子，打个比方，源程序中有这样的语句：a=b+c；词法分析的结果是：ID=ID+ID；语法分析的结果是：expression；可能最终这个结果会被归约成：statement
做语法分析，你首先必须获得这个语言的语法描述，我们常常使用BNF范式来描述语言的文法。比如说C语言中的语句是如此定义的：语句可以是表达式语句、选择语句、分支语句、循环语句，其中选择语句可以是IF语句或者IF…..ELSE…..语句，选择语句是SWITCH……等等。那么它的BNF定义可能是：statement：：expression_statement | if_statement | switch_statement | circulate_statementif_statement：：IF expression statement | IF expression statement ELSE statement……..……..
我无法在这里给你详细解释，你需要自己去仔细学习和体会。
那么我们怎么做语法分析呢？前提条件是，词法分析已经得到了源程序的单词序列。语法分析方法总的来说有两大类：自上而下，自下而上。自上而下中常用的是递归子程序法和LL(1)分析法。递归子程序法是将每一个非终结符号的识别做成一个子程序以供调用，由于这些子程序常常互相调用，就像你在上面看到的一样，因此程序结构常常是递归的。这种方法很简单，但效率很低下，你也需要注意不能从词法分析的结果文件多读或少读了一个单词。
不好意思，这里先解释一下单词的类型，我们把单词分为两大类：终结符号和非终结符号，这是就语法中的产生式而言的（常常在产生式中使用大写表示终结符，小写表示非终结符），终结符号就是词法分析结果文件中的单词，是不能再扩展的。
LL(1)分析法的思想是：如果能够从语言的产生式中推导出从源程序得到的单词串，那么源程序就是正确的，否则就一定是错误的。
要理解这个思想，你必须了解推导，请自己去阅读相关编译原理的教科书。
使用LL(1)分析法会存在很多问题：首先，你要避免回溯，否则你将掉进一个很复杂的漩涡中；再次，不是所有语言都是LL(1)语言，也就是说你不能使用这种方法去分析所有的语言，这根本行不通。具体的这种方法是如何实现的你仍然要去看书。
下面谈的是自下而上的分析方法，也是功能最强大的分析方法。首先总体的说一下自下而上分析方法的基本思想：它基于一种称作“移进---归约”的技术（关于这种技术，我没有太多时间去跟你讲，还是希望你去看书），在其总控程序中依赖于一张分析表，依具体分析方法的不同而使用不同的分析表。
自下而上的分析方法又分为：LR(1)、SLR、LALR。LR(1)分析方法是这几种方法种功能最强大的，当然也是适用范围最广的。SLR分析方法又称为simple LR分析方法，即简单LR分析法，它是LR的一个变形版本。LALR分析方法应该说在实际的编译器中最常见的，因为它基本上能实现LR的功能，体积上又比它小。
这三种方法我分别作如下的简单介绍：LR(1)和SLR的不同主要体现在他们对待移动归约项目上所采取的不同策略，后者之所以称为简单，就在于它对凡是左部非终结符号中的FOLLOW集合中的元素都采取归约的方法，而前者则严格的将它限制在：只有当前符号是可归约项目的当前搜索符号中之一时才可以归约。究竟为什么要这样做，为什么LR(1)的这种处理方法是正确的，而SLR的处理方法有时是错误的，我希望你最好是去看书（我刚好也忘了）。^_^
LALR是在进行了LR分析的基础上所采取的一种简化状态数目的方法，即将LR分析表中的所有同心族进行合并，所谓同心族，就是两个项目集合除了右部的搜索符号不同外其它都是相同的。采用这种方法可以显著的减小分析表的体积，无疑可以缩减程序代码的执行时间，而且经过验证，这种方法对一般的语言都有效，这句话的意思是说：这样做在大部分情况下不会引起某种冲突。常见的冲突是“归约----归约”冲突。
但是不幸的是，一般的语言几乎都不是严格意义上的LR(1)文法，比如说任何包含IF……ELSE……结构的语言都不是LR(1)语言，那岂不是开玩笑，哪种语言不包括这种结构？别急，你只要在分析表中作简单的消除歧义的改动即可，这种结构下必须消除移进和归约的冲突，即处理一下什么时候移进，什么时候归约。
最后我再次声明，我不是编译领域的高手，因为这是我曾经的毕业设计，所以我比较了解其过程和细节，编译领域中最有难度也最有意思的也许应该是语义分析和代码优化，而纵观目前，我几乎没看见这方面的很好的教材，都只是泛泛而谈，此外，如果你不想手工作语法分析，也不想只是用用强大的语法分析工具YACC的话，那么编写出语法分析中几个至关重要的函数也许就最有挑战意义也最有收获了，要知道，如果你做出了那几个函数，你几乎可以不费吹灰之力做出任何语言的语法分析，很让人激动啊！
让我们一起努力，如果有朝一日我能够做到这些，我一定无偿共享我的一切！让我们彻底揭下编译原理领域的神秘面纱！
最后再次感谢许多不知名的网友的热情支持，本文错误和不足之处，请尽管提出，公开在CSDN上发建议，或者发送给我的邮箱：lgdpeter@proview.net.cn或者lgdpeter@163.com。
本文最后完成时间：2004年7月30日星期五作者：lgdpeter8(小刚)