编译原理

问题:全体有限长字符串的有限体现在哪里?

答:全体有限长字符串的有限是指字符串的长度是有限的，而不是指字符串的个数是有限的，字符串可以为无限个。

问题:什么是词法分析?

回答:词法分析是计算机科学中将字符序列转换为单词序列的过程。词法分析器一般以函数的形式存在，供语法分析器调用。 完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。

问题:问题与语言的对应关系?

1．每个输入是一个串，任意串都可以是输入；

2．算法的任务是对输入串回答是与否；

3．一个问题是满足某性质的串的集合（语言）。

问题:什么是语言?

答:语言是一些有限长字符串的集合，该集合可以是无穷的，但集合里的每一个元素必须是有限长的。

问题:什么是正则语言?

回答:正规语言又称正则语言，是形式语言与自动机理论中讨论的最基本的语言系。通过它可以架起有穷自动机和正则表达式之间的一座桥梁。

设∑为有穷字母表，∑*为其Kleene闭包（见作用代数）。那么称字符串集L∈∑*为正规语言，当且仅当满足下列条件之一:

L可以被一个确定有穷自动机识别；

L可以被一个非确定有穷自动机识别；

L可以用正则表达式表达；

L可以用正则文法生成；

L可以由前缀文法生成；

问题:正则语言和上下文无关语言有什么关系?

答:每一个正则语言都是上下文无关的，也就是每一个正则语言都是一个上下文无关语言。

举一个语言的例子:

字母表:∑＝｛+，-，0，1，2，3，4，5，6，7，8，9｝

语言:A＝｛+，-，-1，0，10，31，989，．．．｝

∑*中所有串的字典序排列:

ε，+，-，0，1，2，3，4，5，6，7，8，9，-1，-2，．．．．

问:语言与字符的关系是什么?

答:一个语言是一些有限长字符串的集合。

问题:图灵机接受的语言叫什么?

图灵机接受的语言叫做递归可枚举语言（recursively enumerable language，r．e．）。

如何理解计算机语言?

计算机语言是指用于人与计算机之间通讯的语言，可以分成机器语言，汇编语言，高级语言三大类。一串串由＂0＂和＂1＂组成的指令序列交由计算机执行，这种计算机能够认识的语言，一台计算机全部的指令集合，就是机器语言；用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，需要一个专门的翻译程序（汇编程序），专门负责将这些符号翻译成二进制数的第二代计算机语言，就是汇编语言；将许多相关的机器指令合成为单条指令并且去掉了与具体操作有关但与完成工作无关的细节，大大简化了程序中的指令的计算机语言就是面向过程面向对象的高级语言。比如BASIC、C、C++、PASCAL、FORTRAN、智能化语言、动态语言（Python、PHP）；计算机语言下一个发展的目标就是面向应用，告诉程序需要做什么，程序就能自动生成算法，自动进行处理，就是非过程化的程序语言。

问题:问题与语言的对应关系?

1．每个输入是一个串，任意串都可以是输入；

2．算法的任务是对输入串回答是与否；

3．一个问题是满足某性质的串的集合（语言）。

问题:什么是等价关系?

答:等价关系是集合上的一种特殊的二元关系，它同时具有自反性、对称性和传递性。