摘 要

随着计算机技术的日益发展和不断普及，人类已经进入一个高速发展的信息化时代，信息化标志之一的计算机软件已经在人们的生活中起着不可替代的作用。计算机软件开发中的一个必要过程是编译，编译是从源代码（通常为高级语言）到能直接被计算机或虚拟机执行的目标代码（通常为低级语言或机器语言）的翻译过程。编译作为软件生产过程中必不可少的一环，其重要性不言而喻。

Yacc(Yet Another Compiler Compiler)，是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。本文介绍了Yacc以及编译技术的一些特点及其使用，并基于Yacc实现了一门语言的编译器。按照编译器的结构,对编译器实现过程中的各个部分如词法分析,语法分析,中间表示的转化及代码生成,进行了深入的分析，提出了切实可行的系统开发方案。将系统按编译器的各个部分进行划分，实现了词法分析器，语法分析器，中间代码生成和中间代码解释执行的各个模块。开发完成以后对系统进行了调试和测试，根据测试结果，该系统的基本功能已经实现，在Linux和Window系统正确运行，能够将源语言程序编译，并解释执行得到正确结果。

关键词：Lex；Yacc；编译器

Abstract

With the development and the growing popularity of computer technology, mankind has entered the information era of rapid development of information technology where computer software plays an irreplaceable role in people's lives. Compile is a necessary process in computer software development which compiled object code (usually lower or machine language) from source code (usually high-level language) can be executed directly to the computer or virtual machine. As compiler software production process is an essential part, its importance is self-evident.

Yacc (Yet Another Compiler Compiler) is a compiler on Unix/Linux used to generate a compiler (compiler code generator). This thesis describes the features of Yacc and compiler technology as well as some of their use, and implements a language compiler based on Yacc. According to the structure of the compiler, the compiler implementation process in various parts such as lexical analysis, parsing, transformation and intermediate representation of code generation, in-depth analysis, the practical system development program. The system is divided according to various parts of the compiler and each module implements lexical analyzer, parser, code generation and execution of intermediate code. After the completion of the development of the system debugging and testing, the basic functions of the system has been implemented in Linux and Window system. Moreover, it is able to compile the source language code, and interpret the object code to correct results.

Key words: Lex, Yacc, compiler

目录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 2

1.3 本文所做的工作 2

1.3.1基于Lex的词法分析 3

1.3.2基于Yacc的语法分析 3

1.3.3中间代码的生成 3

1.3.4中间代码的解释执行 3

第2章 系统开发环境和关键技术 4

2.1 开发环境 4

2.2 语法分析方法 4

2.2.1 LR分析法 5

2.2.2 LALR 分析法 5

2.3 Lex和Yacc 6

2.3.1 Lex 6

2.3.2 Yacc 7

第3章 编译程序的分析与设计 9

3.1 词法分析器的分析与设计 9

3.1.1 源语言词法规则 9

3.1.2 源语言词法分析的设计 10

3.2 语法分析器的分析与设计 11

3.2.1 源语言文法 11

3.2.2 源语言语法分析器的设计 12

3.3 中间代码生成的分析和设计 14

3.3.1 中间指令集 14

3.3.2 中间代码生成的设计 15

第4章 编译程序的实现与测试 18

4.1 词法分析器的实现与测试 18

4.1.1 词法分析器的实现 18

4.1.2 词法分析器的测试 20

4.2 语法分析器的实现与测试 23

4.2.1 语法分析器的实现 23

4.2.2 语法分析器的测试 27

4.3 中间代码生成 28

4.4 中间代码的执行 29

4.4.1 中间代码解释器 29

4.4.2 中间代码的测试 30

总结和体会 34

参考文献 35

致谢 36

附录 37

第1章 绪论

1.1 研究背景及意义

今天，复杂而的软件架构支撑着全球经济，编译器和高级语言正是这些软件的基石。强大而优雅的编译技术在硬件综合等领域同样有着“连城”的价值。与半导体技术一样，编译器和高级语言处于信息时代的核心地位。

编译器的技术是计算机科学的基础，编程语言在实际软件开发生活中的重要性不言而喻。了解编译器内部实现是很有意义而且有意思的事情，原因很多：首先，编译原理是一门经过长期实践完善的理论，它涵盖了很多算法，都是非常经典的算法。从前端到后端，编译器设计到的很多算法，都很强大、快速。 比如日常经常要用到的正则表达式解析字符串的算法，学习和理解编译的知识，可以更加深刻地理解和应用这些算法。又比如明白正则表达式能够表示何种语言，不能表示何种语言，何时性能最好，何时性能不好等，这样才能够在实践中更加科学地加以运用。其次，现在正处在一个编程语言爆发的时代，我们所熟悉的语言每个版本都有很多新特性，并且还有各种新型语言、脚本、DSL和其他基于格式化文本的协议层出不穷。如果掌握这部分知识就会在这个时代更具有主动性。