编译原理_复习内容（第1-2章）

第一章&第二章 引论与语法描述介绍

编译程序：将某一种高级语言程序 等价地转换为另一种底层编程语言程序 （如汇编或机器码）的程序

描述词法规则的有效工具是：正规式（r）和有限自动机（DFA）

标识符是语义概念，名字是语法概念

语法

• 词法规则（表示工具：有限自动机）：主要包含常数、标识符、基本字汇以及算子等元素
  • 语法规则（表示工具：上下文无关文法）：主要包括表达式、语句以及子程序或功能块等组成要素

语法规则 和 词法规则 定义了程序的形式结构

最左推导：任何一步 α => ß 都是对α中最左非终结符进行替换

在每一步中（step），符号串α都会被替换成ß，并且这个替换仅作用于α中的最右非终结符。通过这种规范推导得到的句型被称为normative sentence。

符号表达与概念：

• E：算术表达式
• i：变量
• 句型：设有文法G，S是它的开始符号。如 S=*=>α （从文法开始符号开始经过若干步推导推出α：包括一步推出S=>α和多步推出S=+=>α）则α称是一个句型，这里α可以是终结符和非终结符组成的串。
• 句子：仅含终结符的句型是一个句子
• 语言：文法产生的句子的全体是一个语言（假定G是一个文法，文法G所产生的句子的全体是一个语言，将它记为 L(G)。）
• 遍（pass）：