当前位置：首页 > news >正文

编译原理复习---基本概念+推导树

news 2024/12/21 23:37:56

适用于电子科技大学编译原理期末考试复习。

本文只适合复习不适合预习，即适合上课听过一点或自己学过一点的同学。

1. 编译原理概述

编译原理是计算机科学的一个重要分支，它涉及将高级编程语言编写的源代码转换为机器能够理解和执行的低级代码的过程。这个过程包括多个阶段，每个阶段都有特定的任务和目标。

编译过程的主要阶段

词法分析：将源代码分解为一系列的记号（tokens）。词法分析器（Lexer）负责识别源代码中的单词、关键字、运算符和其他基本语言元素，并将它们转换为内部表示形式。

语法分析：根据语言的语法规则，分析记号序列的结构。语法分析器（Parser）构建出抽象语法树（Abstract Syntax Tree，AST），它代表了程序的语法结构。

语义分析：检查源代码是否有意义，如变量和函数的使用是否正确。语义分析器（Semantic Analyzer）负责类型检查、作用域分析和其他语义相关的任务。

中间代码生成：将语法树转换为中间代码表示。中间代码是一种与具体机器无关的代码形式，它简化了后续的优化和目标代码生成过程。

代码优化：对中间代码进行变换以提高代码的效率。优化器（Optimizer）应用各种优化技术，如常量折叠、死代码消除等，以改进程序的性能。

目标代码生成：将优化后的中间代码转换成特定机器代码。目标代码生成器（Code Generator）根据目标机器的特性，生成最终的可执行代码。

目标代码优化：不学。

2. 基本概念

2.1 字母表

字母表∑是一个非空有穷符号(字母、数字、标点符号...)集合。

例如，二进制字母表{0, 1}、ASCLL字符集、Unicode字符集。

字母表的运算

字母表的乘积：如果有两个字母表 ∑1 和 ∑2，它们的乘积 ∑1∑2 是由所有可能的两个符号的连接组成的集合，其中第一个符号来自 ∑1，第二个符号来自 ∑2。例如，如果 ∑1 = {0, 1}，∑2 = {a, b}，那么 ∑1∑2 = {0a, 0b, 1a, 1b}。

字母表的幂：字母表 ∑ 的 n 次幂 ∑^n 是由长度为 n 的所有可能的符号串组成的集合。例如，如果 ∑ = {0, 1}，那么 ∑^3 = {000, 001, 010, 011, 100, 101, 110, 111}。

字母表的正闭包：字母表 ∑ 的正闭包 ∑+ 是由 ∑ 中的符号组成的所有非空符号串的集合。例如，如果 ∑ = {a, b}，那么 ∑+ = {a, b, aa, ab, ba, bb, aaa, aab,...}。

字母表的克林闭包：字母表 ∑ 的克林闭包 ∑* 是由 ∑ 中的符号组成的所有符号串的集合，包括空串。例如，如果 ∑ = {a, b}，那么 ∑* = {ε, a, b, aa, ab, ba, bb, aaa, aab,...}。

2.2 串

设∑是一个字母表， $\forall x \in \sum^{*}$ ，x称为是∑上的一个串，即串是字母表中符号的一个有穷序列。

串s的长度，通常记作|s|，是指s中符号的个数，例如，|aab|=3。

空串是长度为0的串，用 $\varepsilon$ (epsilon)表示，| $\varepsilon$ |=0。

串的运算

串的连接：设 $s_1 = a_1a_2\cdots a_m$ ， $s_2 = b_1b_2\cdots b_n$ ，则 $s_1$ 和 $s_2$ 的连接 $s_1s_2=a_1a_2\cdots a_mb_1b_2\cdots b_n$ ，连接后的串长为m + n。例如 $s_1="ab"$ ， $s_2 = "cd"$ ，则 $s_1s_2="abcd"$ 。

串的幂：把连接看作是乘法运算，幂运算就是同一个串重复相连。

2.3文法

文法（Grammar）是一种形式化的规则系统，用于描述一种语言的结构和语法规则。它定义了一组产生式规则，这些规则指定了如何将符号序列转换为另一组符号序列。

2.3.1 终结符与非终结符

终结符：终结符是文法中的基本符号，它们是不能再进行推导的符号。终结符号可以是字母、数字、标点符号等具体的符号。例如，在编程语言中，关键字、运算符、常量等都可以看作是终结符。

非终结符：非终结符是文法中的符号，它们可以通过推导规则进行推导，最终得到终结符号或其他非终结符号。非终结符通常代表语言中的语法结构或语法规则。例如，在编程语言中，表达式、语句、函数等都可以看作是非终结符。

2.3.2 文法的形式化定义

一个文法G通常被定义为一个四元组（N, Σ, P, S），其中：

N是非终结符号（Nonterminal Symbols）的集合。

Σ是终结符号（Terminal Symbols）的集合，Σ与N无交集。

P是一组产生式规则（Production Rules），形式为α → β，其中α和β是由终结符号和非终结符号组成的字符串，且α中至少包含一个非终结符号。

S是起始符号（Start Symbol），属于N。

在不引起歧义的情况下，一组产生式就代表一种文法。

2.3.3 文法的类型

根据乔姆斯基（Chomsky）的分类，文法可以分为四种类型：

0型文法（无约束文法）：也称为短语文法，产生式规则没有额外限制。

1型文法（上下文有关文法）：产生式规则满足|β| ≥ |α|，除了S → ε的情况。

2型文法（上下文无关文法）：产生式规则的左侧是一个非终结符号。

3型文法（正规文法）：产生式规则的形式为A → aB或A → a，其中A和B是非终结符号，a是终结符号。

由于上下文无关文法受到的限制最小，所以是应用最广泛，被研究的最多的文法，我们要研究的也是这个文法。

为什么要叫做上下文无关文法呢？