编译原理

概述

什么是编译器 ？他的作用是什么？他的输入输出是什么？

编译器是一个程序，他将源程序翻译成等价的目标程序，输入数据是类似 C语言的高级语言，输出是类似汇编语言或者机器语言的低级语言。

编译器与解释器有什么区别 ？

对编译器来说，编译和运行时两个阶段。解释器则不需要将这两阶段分开；

编译器和解释器的根本区别在于是否生产目标代码。编译器会生成目标代码，然后运行，而解释器分析后直接运行生成结果；

编译器和解释器的存储组织方式不同，对编译器来说，在源程序被编译阶段，存储区要为源程序和目标程序开辟空间，存放需要使用的各种表，如符号表，在运行阶段需要存放目标代码和数据，编译阶段的信息不再需要。解释器在整个过程中源程序、符号表都需要存储在存储区中；

编译器比解释器效率高，因为编译器时一次翻译，多次运行。而解释器每次运行都需要逐行翻译。

编译器工作分为几个阶段 ？

一般分为 词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成这六个阶段。期间要有错误处理等。当然不是严格分为几个阶段。不同编译器不一样。

编译过程中的前端和后端如何划分，为什么要划分前后端 ？

前端主要依赖于源代码，与目标机器无关。后端主要依赖于目标机器，与源程序无关。前端包括词法分析，语法分析，语义分析和中间代码生成，还有某些优化工作。后端包括目标代码生成。

按照这种方式，可以实现不同机器使用同一源程序的编译器（前端相同，后端不同），也可以为同一期间生成几个语言的编译程序（前端不同，后端相同）。

文法和语言

什么是语法，什么是语义 ？

语法是一组规则，用来定义什么样的符号序列是合法的。语义进一步判断合法的符号是否能构成正确的程序。比如类型检查就无法从语法上判断，但是可以在语义分析阶段判断。

文法的分类有哪些 ？

乔姆斯基（Chomsky）于1956年建立了形式语言的描述，把文法分成四种类型，即0型（短语文法）,1型（上下文有关文法）,2型（上下文无关文法）,3型（正规文法）。

上下文无关文法（context-free grammar）是什么？

上下文无关文法由四个元素组成，一个终结符号集合、一个非终结符号集合、一个产生式集合、一个非终结符号为开始符号。

如何进行语法分析，有哪些基本方法？

语法分析分为两大类，自顶向下分析和自底向上分析。

自顶向下分析思想：从文法的开始符号出发，反复使用各种产生式，逐步向下推导，试图推导出句子。存在的问题：在推导中如何选择规则？采用回溯法可行，但是代价太高，还可能陷入死循环。

自底向上分析法思想：从输入符号串开始，逐步进行归约，直到规约到文法的开始符号。存在的问题：每次应归约当前句型的句柄，但如何找句柄，以及句柄是否唯一？对一个句型的短语、直接短语和句柄的判断，常用的方法是：（1）查看语法树的叶子结点（终结符或非终结符），如果叶子结点的父结点还有其他子结点，就将该父结点的所有子结点作为一个字符串集合来判断；（2）对子结点的判断要从左向右处理；向上判断短语是相对哪个非终结符的短语时，要一直处理到祖先结点。

词法分析

词法分析的主要任务是什么，输入输出是什么？

词法分析从左向右扫描每行源代码，识别出单词和属性，把单词转换成统一的内部表示给语法分析。还需要删除注释，空格，换行等非必要信息。 输入源程序代码，输出单词符号（token）。

单词符号（token）分为哪些 ？

关键字、标识符、常数、运算符、界限符（分号，括号等）。

语法分析

什么是自顶向下分析法 ？

自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析包括确定分析和不确定分析。