1.2.1. 语言、文法与机器¶

语言 就是字符串的一个集合。对字符串来说，最基本的能力就是判断它是否为某个给定语言的一部分。本学期，我们将研究各种类型的机器，看看它们能可靠地"识别"哪些语言，也就是说，可靠地判断任意给定的字符串是否属于该语言。与此同时，我们还会研究语言的其他表达或定义方式。这些方式包括 文法 ，以及其他"用于定义语言的语言"，比如 正则表达式 。

1.2.2. 语言层级¶

这是我们本学期大部分时间要做的事情的图示。到学期结束时，你将知道这张图中的一切如何与编译器的运行机制相关，以及相关问题求解起来有多难。

你熟悉编程语言，现在我们要更细致地研究编程语言是如何定义的：用文法，以及 自动机 （自动机是比你笔记本电脑更简单的计算机模型）。 "自动机"（Automata）只是"机器"（machine）的另一种说法。

我们从最中心的部分开始。我们将先考察较简单的语言和文法，然后再逐步了解编程语言是如何构成的。我们从 有限自动机 （也称为 有限状态机 ）开始。我们将看到，一台自动机表示一种简单的语言，而且某类文法（ 正则文法 ）能够表示同一种语言。我们还会考察 正则表达式 。记住，它们表示的是可以用不需要额外内存的程序来表示的语言。

然后我们加入内存，考察一种能够表示更大一类语言及其相应文法的机器（ 下推自动机 ）。

然后我们再加入更多的内存和能力，考察另一种机器（图灵机，Turing machine），以及它能表示的语言类型和相应的文法。

然后我们将考察你无法编写程序求解的语言。

1.2.3. 机器的能力¶

（注意：本学期我们会在课堂上详细讲解所有这些信息。但这张总览图可以帮助你把它们全部串起来。）

有限自动机（FA）——能识别整数、实数，但不能识别合法的算术表达式。

下推自动机（PDA）——能识别合法的算术表达式，但不能计算它并给出答案。

图灵机（TM）——能计算表达式，但不能编写一个程序，让它接受任意 Java 程序并告诉你该程序是否会停机。

1.2.4. 应用：编译器¶

• 我们的关注点——问题：给定某种语言（比如 Java 或 C++）中的一个程序，它合法吗？ 也就是说，它是一个语法正确的程序吗？

  如果正确，就继续生成可执行代码；如果不正确，就不要生成！

  C++ 编译器友好吗？它的报错信息有用吗？它是如何找出错误的？错误在哪一行？

• 问题：语言 L、程序 P——P 合法吗？

  你可能会去一家公司工作，设计一门新语言，也许这门语言是用来给机器人编程的。

• 还要考虑其他事情：不同编程语言的编译过程有何不同？（Java 与 C++？）

  请注意，从技术上讲，有些语言（如 C++）会被编译为汇编语言和机器语言，而另一些语言（如 Java）会被转换为面向虚拟机的字节码，然后再解释执行。我们会在本学期稍后进一步讨论这个问题，但请注意，本课程更侧重于让你到达可以解释执行或转换为汇编语言的阶段，我们并不专注于转换为汇编语言。那是编译器课程的课题。

1.2.5. 一些烧脑的想法¶

与形式语言相关的"元"（meta）概念有很多。下面是一些值得思考的问题。

语言的描述本身只是字符串。这意味着，比如，（作为字符串的）正则表达式的集合就是一个语言。这引出了这样一些问题：

• 正则表达式的集合（在我们层级中）属于哪类语言？

• Java（在我们层级中）属于哪类语言？

• 上下文无关文法属于哪类语言？

这里还有另一个有趣的"元"问题。对于任意给定的语言 \(L\) ，定义语言 co-\(L\) 为所有 不在 \(L\) 中的字符串。 co-\(L\) 是否总是与 \(L\) 属于（我们层级中）同一类语言？