论文部分内容阅读
高级程序设计语言推动了计算机的发展和应用,其中编译器起着举足轻重的作用。编译器是每一个开发人员必须熟悉并应用的首要系统软件。它的设计与实现是个很大的软件工程,其依赖的相关编译原理以及技术也十分复杂;它是计算机科学中理论与实践相结合的完美典范。本文详细设计和实现了C语言编译器的词法分析器和语法分析器,其中语法分析器又分为LR(1)和LL(1)分析法两种语法分析器。在设计与实现C编译器词法分析器中,将C语言文法中的所有终结符号划分为字符串类,数值类和其他符号类,每一类作为独立的模块来设计与实现。在字符串模块中使用了类似有限状态机的方法来解析关键字。词法分析器中字符串存储的实现使用了哈希表和存储区相结合的方式,以单链表形式管理所有的存储区,把字符串存入存储区的地址放入哈希表,并以其哈希值作为索引。设计了词法分析错误处理和缓存区管理。词法分析器将为语法分析器提供扫描符号。首先对语法分析阶段使用的产生式,FIRST和FOLLOW集合进行编码。依据移进-归约的思想,设计了LR(1)语法分析的结构和归约算法。在算法中归约产生式从选候选产生式中匹配筛选,并使用C文法符号的FIRST和FOLLOW集合作为移进和归约的判断条件。然后在这些算法之上创造性的设计了三个数据结构:产生式集合表,符号到产生式集合的映射表和终结符与非终结符表。依靠这些设计实现了LR(1)语法分析器。本文使用递归下降法来实现C编译器的自顶向下语法分析器。从根结点开始,利用FIRST集合选择相应的产生式,FOLLOW集合判断产生式的返回和出错进行语法分析。针对LL(1)语法分析中遇到的产生式左递归,公共左公因子和FIRST集合冲突问题分别以迭代循环右展开,提取公共左公因子先执行和“预扫描-回滚”方法解决。基于以上所有设计与实现,将C语言编译器的词法分析器和语法分析器整合。系统实现了对C89所有文法的语法分析,能够生成源程序的语法树,以及对语法错误的识别和报错。运行结果显示系统所有功能都达到了预期的要求。