编译原理概述,语义概述

笔记摘自NEU编译原理网课

后缀表达式生成

中缀表达式转后缀表达式可以通过栈来实现。

  1. 依次读取输入的表达式，如果是操作数，则把它放入到输出中。
  2. 如果是操作符，栈为空的话直接将该操作符入栈；如果栈非空，则比较栈顶操作符和该操作符优先级，如果栈顶操作符优先级小于该操作符，则该操作符入栈；否则弹出栈顶操作符并将其放入到输出中，直到栈为空或者发现优先级更低的操作符为止。
  3. 如果是括号，比如’(‘和’)’，则特殊处理。如果是’(‘的话，直接入栈；如果是’)’，那么就将栈顶操作符弹出写入到输出中，直到遇到一个对应的’(‘，但是这个’(‘只弹出不写入到输出中。注意：”(“可以理解为优先级最高。
  4. 当表达式读取完毕后，如果栈中还有操作符，则依次弹出操作符并写入到输出中。

实例：$$9+(3-1)*3+10 / 2$$

  • “9”直接输出
  • “+”，”(“进栈
  • 3直接输出
  • “-“进栈
  • “1”直接输出
  • “)”，找到”(“之前的所有栈中运算符并输出，这里只有一个”-“
  • “*”进栈
  • “3”直接输出
  • “+”优先级低于”“，栈中所有优先级不高于”+”全部输出，”“和”+”输出，本”+”进栈
  • “10”直接输出
  • “/“进栈
  • “2”直接输出
  • 依次输出”+”，”*”，”+”，”/“

最后结果：
$$9\qquad 3\qquad 1\qquad-\qquad 3\qquad *\qquad +\qquad 10\qquad 2\qquad /\qquad+$$

解释程序 Interpreter

解释程序是一种翻译程序，将某高级语言翻译成计算机上的低级程序设计语言。

编译（Compile）的过程是把整个源程序代码翻译成另外一种代码，翻译后的代码等待被执行或者被优化等等，发生在运行之前，产物是另一份代码。

解释（Interpret）的过程是把源程序代码一行一行的读懂，然后一行一行的执行，发生在运行时，产物是运行结果。

编译程序与解释程序的主要区别：
前者有目标程序但是后者无目标程序；前者运行效率高，但是后者更便于人机交互。

编译器和解释器的区别：
编译器：输入源代码，源代码被编译成机器码，输出一个可执行程序，但可以不被执行。（存放在磁盘上等待被加载到内存中执行）
解释器：输入源代码，直接输出执行结果。一段程序在解释器中运行时可能会被编译多次，每次运行到这段程序时，都会重新编译一次，这样的开销是很大的。

其实 JVM 就是一个解释器，而不是一个单纯的编译器。输入 java 字节码 bytecode ，然后直接输出执行结果，而不是输出汇编代码。

编译程序总体结构

  • 词法分析：识别单词并分类。生成单词串TOKEN
  • 语法分析：组词成句及语法错误检查。生成语法树
  • 语义分析：分析各个语法成分的语义特征。生成语义树
  • 优化处理：提高目标程序质量的工作。生成优化语义树
  • 根据优化语义树进行目标代码生成，产生计算机可以识别的语言

错误处理

通常，源程序中的错误分为语法错误和语义错误两大类。

  • 语法错误
  • 源程序中不符合语法规则或词法规则的错误，可在词法分析或语法分析阶段检测出来。例如，“非法字符”之类的错误可在词法分析时检测出来
  • “括号不匹配”、“缺少；”之类的错误，可在语法分析时检测出来
  • 语义错误
  • 源程序中不符合语义规则的错误。一般可在语义分析阶段检测出来，有的语义错误却要在运行时才能检测出来。例如，说明错误、作用域错误、类型不一致等错误可在语义分析时检测出来。

相关术语

  • 前端（front end）：主要依赖于源语言而与目标机器无关的编译阶段。如：词法分析、语法分析、语义分析、中间代码生成、部分优化工作、与前端有关的出错处理工作和符号表管理工作。
  • 后端（back end）：依赖于目标机而一般不依赖于源语言，只与中间代码有关的编译阶段。如：目标代码生成，以及相关出错处理和符号表操作。
  • 遍（Pass）：对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。每一遍扫视可完成上述一个阶段或多个阶段的工作。具体扫描遍数需要根据语言特性和具体需求来确定，并不是越多越好也不是越少越好。

形式语言

  • 语言研究至少涉及三个方面：语义，语法和语用
  • 形式语言的基本观点是：语言是符号串的集合
  • 形式语言研究的基本问题是：研究符号串集合的表示方法，结构特性以及运算规律
  • 形式语言是字母表上的符号，按一定规则组成的所有字符号串集合。其中每一个符号被成为句子。
    • 字母表：元素（符号）的非空有限集合
    • 符号串：符号的有限序列
    • 符号串集合：有限个或无限个符号串组成的集合
    • 规则：以某种形式表达的在一定范围内共同遵守的章程和制度；这里指符号串的组成规则

编译程序的结构

  • 编译程序的总框
    按编译过程的划分，编译程序的结构可以划分为相应的模块。
    • 词法分析器（扫描器）：输入源程序，进行词法分析，输出单词符号。
    • 语法分析器（分析器）：对单词符号进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
    • 语义分析和中间代码产生器：按照语义规则对语法分析器导出的语法单位进行语义分析并将它们翻译成一定形式的中间代码。
    • 优化器：对中间代码进行优化处理。
    • 目标代码生成器：把中间代码翻译成目标程序。

符号串（集合）的运算

符号串的运算

设 $\alpha ，\beta $为两个符号串，则：

  1. 连接：$\alpha \bullet \beta = \alpha \beta$

  2. 或：$\alpha \mid \beta = \alpha （$或者$\beta）$

  3. 方幂：$\alpha^{n}=\alpha\alpha\alpha…\alpha $ （n个）$ = \alpha^{n-1}\alpha = \alpha\alpha^{n-1}$

    $\alpha^{0} = \varepsilon$（空字符串，表示什么也没有的空符号串。这里的$\alpha^{0} $不等于1，它表示的是$\alpha $符号串出现的次数）

  4. 闭包：
    $\alpha$ 的正闭包：$\alpha^{+} = \alpha^{1} \mid \alpha^{2} \mid \alpha^{3} \mid … \mid \alpha^{n} \mid …$
    $\alpha$ 的星闭包：$\alpha^{*} = \alpha^{0} \mid \alpha^{1} \mid \alpha^{2} \mid … \mid \alpha^{n} \mid …$

    闭包通常表示的一种句型，这个句型中会包含有某特符号串，一个句型可以演化出不同的句子。

符号串集合的运算

设 $A ，B $为两个符号串的集合，则：

  1. 乘积： $AB = {xy \mid x\in A 且 y\in B}$
  2. 和：$A\cup B= A+B = { x\mid x\in A 或 x \in B}$
  3. 方幂：$A_{n} = AA…A$ （n个）$AA^{n-1}=A^{n-1}A$

    $A^{0}=\varepsilon$，理由同上
    $A^{1} = A; A^{2}= AA;A^{3}=AAA…$

  4. 闭包：
    $A$的正闭包：$A^{+} = A^{1} \cup A^{2}\cup … \cup A^{n} \cup…$
    $A$的星闭包：$A^{*} = A^{0} \cup A^{1}\cup … \cup A^{n} \cup…$

例：设$A={a， b} ，则 A^{}=？$
$A^{} = { x \mid x=(a \mid b)^{n}， n \ge 0}$
推论：若$A$为任一字母表，则$A^{*}$为该字母表上所有符号串（包括空串）的集合。

字符串集合的文法描述

文法描述

  • 文法（grammar） 是有规则的有限集，其中的上下文无关文法可以定义为四元组：
    提供了规则集，就相当于给了一个文法$G(Z)$
    $$G(Z) = (V_{N}, V_{T}, Z, P)$$

其中：
$V_{N}$：非终结字符集（定义的对象集，如：语法成分等）**[说白了就是能被文法规则推导替换的句子]**
$V_{T}$：终结符集（字母表）**[说白了就是不能被文法规则推导替换的句子，最简化]**
$Z$：开始符号（研究范畴中最大的定义对象，一般是需要自行定义）
$P$：规则集（又称产生式集）**[说白了就是定义的推导规则]**

文法定义语言

给定文法$G(Z)$之后，得到$L(G)$则是通过文法G定义的语言：

$$L(G) = { x \mid Z \Rightarrow + x,x\in (V_{T})^{*} }$$

公式中间的加号应该是在右箭头上方的，表示的是连续推导的意思，至少推导一次！

从开始符号出发，对符号串中的定义对象，采用推导的办法（用其规则右部替换左部）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，最终的符号串就是一个句子。

标识符文法

标识符：指字母开头的字母，数字序列

$$G(Z)=(V_{n}, V_{T}, Z, P)$$
$V_{N}={I（标识符）,A（标识符尾）}$
$V_{T}={l（字母）,d（数字）}$
$Z=I$
$P：I\rightarrow lA \mid l;\qquad A\rightarrow lA \mid dA \mid \varepsilon;$

标识符文法求解

从终结符集开始，也就是我们常说的最底层开始。

  1. 求解A：$A = (l \mid d) A,A = (l \mid d)^{2} ,A = (l \mid d)^{3}…,A = (l \mid d)^{n}A,(n\ge 0)$
  2. 求解I：$I =lA \mid l = l(l \mid d)^{n}A,(n\ge 0)$

无符号整数文法

$$G(N)=({N}, d, {N}, P)$$
$P: N\rightarrow dN \mid d$
N是自然数

算术表达式文法

$$G(Z)=(V_{N}, V_{T}, Z, P)$$

$V_{N}={E（算术表达式）,T（项）, F（因式）}$

$V_{T}={i（变量或常数）,=,-,*,/,(,)}$

$Z=E$

$P:E\rightarrow T \mid E +T\mid E-T; \qquad T\rightarrow F\mid T*F \mid T/F; \quad F \rightarrow i \mid (E)$
层次嵌套结构：表达式 $\rightarrow $ 项 $\rightarrow$ 因式 $\rightarrow$ 表达式

主要语法成分定义

文法有两种基本运算：推导，归约。

设：$x,y \in (V_{N}+V_{T})^{*},A\rightarrow \alpha \in P$

  1. 直接推导（$\Rightarrow$） $xAy \Rightarrow x \alpha y$
    即：指用产生式的右部符号串替换左部非终结符。

    • 加推导（$\Rightarrow + 加号在箭头上面$）

    当且仅当$\alpha \Rightarrow \alpha_{1} \Rightarrow \alpha_{2} \Rightarrow \alpha_{3} \Rightarrow … \Rightarrow \beta$
    即：指一步或一步以上的直接推导运算。

    • 星推导（$\Rightarrow * 星号在箭头上面$）

    当且仅当$\alpha = \beta 或\alpha \Rightarrow \alpha_{1} \Rightarrow \alpha_{2} \Rightarrow \alpha_{3} \Rightarrow … \Rightarrow \beta$
    即：指零步或零步以上的直接推导运算。

  2. 直接归约（$\Rightarrow \bullet 点在箭头下面$）
    即：直接归约是直接推导的逆运算，用产生式的左部非终结符替换右部符号串。

    • 加归约（$\Rightarrow + \bullet 加号在箭头上面，点在箭头下面$）
      当且仅当$\alpha \Rightarrow \bullet \alpha_{1} \Rightarrow \bullet \alpha_{2} \Rightarrow \bullet\alpha_{3} \Rightarrow \bullet… \Rightarrow \bullet\beta$
      即：指一步或一步以上的直接归约运算。
    • 星归约（$\Rightarrow * \bullet 星号在箭头上面，点在箭头下面$）
      当且仅当$\alpha = \beta 或\alpha \Rightarrow \bullet\alpha_{1} \Rightarrow \bullet\alpha_{2} \Rightarrow \bullet\alpha_{3} \Rightarrow\bullet … \Rightarrow \bullet\beta$
      即：指零步或零步以上的直接归约运算。

      ※ 实用中最常见的两种运算：

最左推导($+ \Rightarrow l，加号在箭头上面，l在箭头下面$)：每次推导皆最左非终结符优先。
最左归约($+ \Rightarrow \bullet l，加号在箭头上面，l和\bullet在箭头下面$)：每次归约皆最左可归约串优先。

最左推导/归约是指对需要推导的式子转化成目标格式，需要进行的向右/向左推导，并不是说选择推导结果的最左侧选项。（格式要对上才能运算出最后结果）

句型，句子，语法树

设有文法：$G(Z)=(V_{n}, V_{T}, Z, P)$

  • 句型：是由文法开始符号加推导出的任一符号串。
    $若有：Z \Rightarrow + \alpha，则\alpha 是句型$
  • 句子：是由开始符号加推导出的任一终结符号串。
    $若有：Z \Rightarrow + \alpha，且 \alpha \in (V_{T})^{*}，则\alpha 是句型$
  • 语法树：句型(句子)产生过程的一种树结构表示。
    • 树根–开始符号；树叶—给定的句型(句子)。
语法树的构造算法

关于语法树：
子树 ：以任何具有分支的结点为根所形成的树，称为原树的子树。
简单子树 ：仅具有单层分支的子树。

  1. 置树根为开始符号

  2. 若采用了推导产生式： $A \rightarrow x_{1},x_{2},…,x_{n}$，则有子树：

  3. 重复步骤2，直到再没有推导产生式为止

    如此构造的语法树，其全体树叶（自左至右）恰好是给定的句型。

短语，简单短语，句柄

设文法 $G(Z) , x\alpha y$ 是一个句型，则:

  1. 短语
    若 $Z\Rightarrow + xAy \Rightarrow + x \alpha y \Rightarrow …$
    则 $\alpha$是句型关于 $xAy$ 的一个短语（$A$是$\alpha$的名字）
    任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语

  2. 简单短语
    若 $Z\Rightarrow + xAy \Rightarrow x \alpha y \Rightarrow …$
    则 $\alpha$是句型关于 $xAy$ 的一个短语（$A$是$\alpha$的名字）
    任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语

    其实就是两个式子是直接上下级

  3. 句柄
    一个句型的最左简单短语称为该句型的句柄

放个栗子：

两种特性文法

设有文法：$G(Z)=(V_{n}, V_{T}, Z, P)$

递归文法

设：$A \in V_{N};x,y \in (V_{N}+V_{T})^{}, $ 则：若$A \Rightarrow + xAy, $则称该文法具有*递归性
若：$A \rightarrow A\alpha,$ 称该文法具有直接左递归性，又称直接左递归文法；
若：$A \rightarrow \alpha A,$ 称该文法具有直接右递归性，又称直接右递归文法。

递归文法是定义无限语言的工具（递归文法定义的语言有无限个句子）

二义性文法

若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。

  • 一个栗子：算数表达式的另一种文法

$ G(E)^{‘}: E \rightarrow E+E \mid E-E \mid E*E \mid E/E \mid (E) \mid i $

其中$ i $是变量或者常数，针对于这个文法，句型$ i*i+i $有两个不一样的语法树。所以$ G(E)^{‘} $ 是二义性文法。

文法的等价替换

假设 $G_{1}, G_{2}$ 是两个文法，若 $L(G_{1}) = L(G_{2}), $ 则称$G_{1}, G_{2}$等价，记作 $G_{1}\equiv G_{2}$。文法的等价性是指他们所定义的语言是完全一致的。

如何判断是不是等价文法？
拿到两个文法之后，写出他们的所有语言，然后进行对照，如果完全一致，那么就说明写出来语言的两个文法是等价文法。必须完全一致！【间接说明了，描述一个语言所使用的文法也并不是唯一的】

文法的变换方法

必要的时候对文法进行改写，当然改写后的文法要与原文法等价。通常称为文法变换

  • 删除无用的产生式（文法的化简）
  • 删除 $\varepsilon$ 产生式【如果文法的右部推导出来的是一个空串，我们会把它删除】
  • 常用的三种文法变换的方法
    • 必选项法
    • 可选项法
    • 重复可选项法
文法的变换01——文法化简

文法的化简是指消除如下无用产生式：

  1. 删除 $A \rightarrow A$ 形式的产生式（自定己）
  2. 删除不能从其中推导出终结符串的产生式（不终结）
  3. 删除在推导中永不使用的产生式（不可用）

第二步的相关算法（删除不产生终结式的产生式）

$ V_{VT} $是一个用于存储以终结式为起点回推导的文法的集合

  1. 若有 $A \rightarrow \alpha $，且 $ \alpha \in (V_{T})^{*} $；则令 $A \in V_{VT} $；
  2. 若有 $B \rightarrow \beta $，且 $ \beta \in (V_{T}+V_{VT})^{*} $；则令 $ B \in V_{VT} $；
  3. 重复1，2两步，直到 $ V_{VT} $ 集合稳定没有变化为止
  4. 删除不存在于 $ V_{VT} $ 中的所有文法（整个文法连同其产生式一起删除）

第三步的算法实际上和第二步的思路基本一致，但是是从起始标识符开始正向推导筛选的过程

文法的变换02——删除 $\varepsilon$ 产生式

目的就是把所有的 $\varepsilon$ 全部干掉！！

  1. 首先构造出可以推出空出空串的非终结符集： $V_{\varepsilon}$
    • 若有 $ A \rightarrow \varepsilon$ ；则令： $A\in V_{\varepsilon}$
    • 若有 $ B \rightarrow A_{1} A_{2}…A_{n}…$，且全部 $A_{i}\in V_{\varepsilon}$ ；则令： $B\in V_{\varepsilon}$
    • 重复1，2两步，直到 $V_{\varepsilon}$ 集合稳定没有变化为止
  2. 删除 $G(Z)$ 中的 $ A \rightarrow \varepsilon$ 形式的产生式
  3. 依次改写 $G(Z)$ 中的产生式 $A \rightarrow X_{1} X_{2}…X_{i}$：若有 $X_{i}\in V_{\varepsilon}$ 则用 $(X_{i} \mid \varepsilon)$ 替换之（一个分裂为两个）

在真正进行分析的时候，我们一般认为终结符集（一般为小写字母表示）如果进行推导的话也可以推导出空集 $\varepsilon$

举一个栗子：

这里就提到了刚才在上面标注的，终结符集 $b$ 也可以运用步骤 1 中可推导出 $\varepsilon$ 的性质，在步骤 2 将 $B$ 划分为 $V_{\varepsilon}$ 中。

文法的变换03——常用的三种文法变换的方法

基本思想：扩展文法，引进新的描述符号

  1. 必选项法（圆括号”( )”法）
    $ (\alpha \mid \beta) = \alpha 或者 \beta $，必须是二者之一
    $ A \rightarrow a(\alpha \mid \beta) \Leftrightarrow a\alpha \mid a\beta \Leftrightarrow A \rightarrow a A^{‘}\qquad A^{‘} \rightarrow \alpha \mid \beta $

  2. 可选项法（花括号”〔 〕”法）
    $〔\alpha 〕 = \alpha 或者 \varepsilon $，可选也可不选
    $ S \rightarrow \alpha \mid \alpha \beta \Leftrightarrow \alpha〔\beta 〕\Leftrightarrow S \rightarrow \alpha S^{‘} \qquad S^{‘} \rightarrow \beta \mid \varepsilon $

  3. 重复和选项法（花括号法）
    $ { \alpha } = \varepsilon 或 \alpha 或 \alpha \alpha 或 \alpha \alpha \alpha … $
    $A \rightarrow A \beta \mid \alpha \Leftrightarrow \alpha {\beta } \Leftrightarrow A \rightarrow \alpha A^{‘} \qquad A^{‘} \rightarrow \beta \mid \varepsilon $

    此文法常用来消除文法的直接左递归

形式语言的分类

chomsky 把形式语言分为四类，分别由四类文法定义；四类文法的区别在于产生式的形式不同：

  1. 0 型语言 由 0 型文法定义，又称无限制文法。产生式形式为 $\alpha \rightarrow \beta$
  2. 1 型语言 由 1 型文法定义，又称上下文有关文法。产生形式为 $xAy \rightarrow x\beta y$
  3. 2 型语言 由 2 型文法定义，又称上下文无关文法。产生式形式为 $A \rightarrow \beta$
  4. 3 型语言 由 3 型文法定义，又称正规文法。产生式形式为 $A \rightarrow aB \qquad A \rightarrow a \qquad A \rightarrow \varepsilon$