概念辨析：

目标语言，可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言，也可以是某种机器的汇编语言。

翻译程序是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。

汇编程序：若源程序用汇编语言编写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就是汇编程序，这个翻译过程称为“汇编”（assemble）。

编译程序：若源程序用高级语言编写，经过翻译程序得到目标程序，这种翻译过程就是“编译”（compile）。

汇编程序和编译程序都是翻译程序，但是加工的对象不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系，因此汇编程序要做的翻译工作比编译程序简单得多。

源程序的编译和运行：

编译或汇编阶段：

源程序 -> 编译程序或汇编程序（同时也要输出错误信息） -> 目标程序
运行阶段：

输入数据 -> 目标程序 + 运行子程序 -> 输出数据

源程序的解释运行：

解释程序（interpreter）

对源程序进行解释执行的程序
工作过程

解释程序将源程序翻译成某种中间表示形式后直接执行，根据输入数据执行（中间表示）得到输出数据，同时输出错误信息（如果有）。

解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间表示形式后再加以执行;

编译程序(编译器)则是将源程序翻译成目标语言程序，然后在计算机上运行目标程序。

两种语言处理程序的根本区别是：在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程，而在解释方式下，解释程序和源程序(或某种等价表示)要参与到程序的运行过程中，运行程序的控制权在解释程序。

解释器翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立的目标程序。

源程序的编译-解释运行：

源程序 -> 编译程序 -> 源程序的中间表示形式 -> 解释程序（解释程序再读取输入、执行后得到输出）

编译器的前端分析部分与源语言有关：词法分析、语法分析、语义分析、中间代码生成

编译器的后端综合部分与目标机有关：代码优化、目标代码生成

表格管理、出错处理：

表格管理：编译程序在工作过程中需要保持一系列的表格，用来登记源程序的各类信息和编译各阶段的进展状况。例如，符号表。
出错处理程序

遍：对源程序（包括源程序的中间表示形式）从头到尾扫描一次，并作有关的加工处理，生成新的源程序中间形式或目标程序，通常称之为一遍。

上一遍的结果是下一遍的输入，最后一遍生成目标程序。

一遍扫描即可完成编译工作的称为一遍扫描编译程序。

如果看到说从源程序到目标程序到五个基本阶段，是指：

词法分析、语法分析、语义分析和中间代码生成、优化器、目标代码生成

程序语言

程序语言的语法定义：一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序。这些规则一部分称为词法规则则，另一部分称为语法规则（或产生规则）

词法规则：词法规则规定了字母表中哪样的字符串是一个单词符号，是单词符号的形成规则
语法规则：语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则

$A, B, C, …$：非终结符

$a, b, c,…$：终结符

$…,X,Y,Z$：终结符或非终结符

$…,w,x,y,z$：终结符号串

$\alpha,\beta,\gamma,\delta,…$：终结符或非终结符构成的符号串

对于产生式：

$P\rightarrow \alpha_1|\alpha_2|...|\alpha_n$

$\alpha_i$ 是 $P$ 的一个候选式。

直接推导：$v\Rightarrow w$

设 $\alpha \rightarrow \beta$ 是文法 $G=(V_N,V_T,P,S)$ 的规则，$\gamma$ 和 $\delta$ 是 $V^$ 中的任意符号串，若有符号串 $v,w$ 满足：$v=\gamma\alpha\delta,w=\gamma\beta\delta$，则说 $v$ 应用规则 $\alpha \rightarrow \beta$ 直接产生 $w$，或者说 $w$ 是 $v$ 的*直接推导。

直接推导的序列（其中 $\Rightarrow$ 至少出现一次）是推导，记为 $v\Rightarrow^+ w$

若有 $v\Rightarrow^+ w$ 或 $v = w$，则记为 $v\Rightarrow^* w$

句子和句型：

对文法 $G[S]$，如果符号串 $\alpha$ 由开始符号推导出来，即 $S\Rightarrow^ \alpha$，则 $\alpha$ 是 $G[S]$ 的句型。若 $\alpha$ 只由终结符组成，就是*句子</u>。

文法 $G[S]$ 产生的语言 $L(G)=\{x|S\Rightarrow^ x,x\in V_T^\}$

文法等价意味着它们识别的语言相同。

Chomsky 将文法分为四种类型。

最右推导是规范推导。

规范推导得到的句型是规范句型。

文法的二义性：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则是二义的。（因为一颗语法树只有一个最左/右推导！）

部分二义文法可以改造为无二义文法。

词法分析

词法分析在语法分析前进行，但是也可以和语法分析合起来作为一遍（类似函数调用，由语法分析调用词法分析）。

词法分析单独作为一遍：结构清晰、各遍功能单一，但是效率低

词法分析作为子程序与语法分析合为一遍：效率高

词法分析程序的功能：

词法检查
数字字符串转为二进制数值
删去空格字符和注释

词法分析输出的单词符号表示为二元组：（单词种别，单词符号的属性值）

一个标识符常将存放它的信息的符号表项指针作为属性值，常数也是如此。

词法分析器的设计与实现：

预处理：针对空白符、跳格符、回车符、换行符等编辑性字符的处理
识别单词符号时，对标识符的识别比较容易（因为标识符的出现都后跟算符或界符），但识别常数时需要超前搜索（如5.E08），对算符和界符也需要超前搜索（因为词法分析器会将多个字符合成一个单词符号，分析时需要划分）。

正则表达式和正则文法

正则表达式的例子：

a            {a}
a|b          {a,b}
ab           {ab}
(a|b)(a|b)   {aa,ab,ba,bb}

正则式转换为文法产生式：

$A \rightarrow r_1r_2$ ：$A\rightarrow r_1B,B\rightarrow r_2$
$A\rightarrow r^*r_1$ ：$A\rightarrow rB,A\rightarrow r_1,B\rightarrow rB,B\rightarrow r_1$
$A\rightarrow r_1|r_2$ ：$A\rightarrow r_1,A\rightarrow r_2$

NFA & DFA

NFA和DFA从功能上来说是等价的。

DFA是NFA的特例。对每一个NFA N，存在一个DFA D使得L(N) = L(D)。

DFA的最小化：

消除多余状态
合并等价状态：从终态和非终态开始划分

第三步，因为状态3输入a得到状态1，状态4输入a得到状态4，而状态1和4不是一组的

其实还有第5步的，省略了。因为对{6,7}，输入a得到的是状态1和2，而1和2是一组的。

对每一个右线性正则文法或左线性正则文法，都存在一个正则自动机与其等价；

对每一个正则自动机（就是FA，有穷自动机），都存在一个右线性正则文法和一个左线性正则文法与其等价。

文法产生式 到 正则式 的转化规则：

规则	文法产生式	正则式
规则1	$A\rightarrow xB,B\rightarrow y$	$A=xy$
规则2	$A\rightarrow xA\	y$	$A=x^*y$
规则3	$A\rightarrow x,A\rightarrow y$	$A=x\	y$

语法分析

语法分析器的作用：

接收词法分析器提供的符号串
检查符号串是否能由源程序语言的文法产生
用易于理解的方式提示语法错误信息

语言的结构是用上下文无关文法描述的，因此语法分析就是按照文法的产生式识别输入符号串是否是一个句子。

自顶向下语法分析

对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自顶向下地为输入串建立一棵语法树。

自顶向下分析一般都带回溯的。

自顶向下分析的缺点：不能处理具有左递归的文法。

巴科斯范式：只用到了两个元符号 $\rightarrow$ 和 $|$

扩充的巴科斯范式加入了几个元语言符号：

0次到多次：$\{\alpha\}$ 1次到多次：$\alpha\{\alpha\}$ 出现或不出现：$[\alpha]$

当文法满足上述两个条件时，就可以为它构造一个不带回溯的自顶向下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。

LL(1)分析法

LL(1)这个名字：第一个L代表从左到右扫描输入串，第二个L表示最左推导，1表示分析时每步需要向前查看一个符号。

消除直接左递归、改写成右递归。

消除左递归的一般算法：略

造成回溯的条件：文法中，对于某个非终结符号的规则其右部有多个选择，并且根据所面临的输入符号不能准确地确定所要的选择时，就可能出现回溯。

FOLLOW(A)是所有句型中出现在紧接A之后的终结符或#。

#的来源是：开始符号的FOLLOW集初始化时加入#。

当然，#还通常作为输入串的结束符。

当非终结符A面临输入符号a，且a不属于A的任意候选首符集（FIRST集）、但A的某个候选首符集包含 $\epsilon$ 时，只有当 $a\in FOLLOW(A)$ 时，才可能允许A自动匹配。

这是因为，当A的FIRST集包含 $\epsilon$ 时，说明A可以推导出 $\epsilon$，此时想象一下把语法树中的A下面引出一条箭头指向子节点 $\epsilon$，然后就会转到 FOLLOW(A) 的某一个节点（刚好是a），于是发现可以匹配。

课件P33 码字中。。。。。

实现LL(1)分析的一种有效方法是使用一张分析表和一个栈进行联合控制。

预测分析表：

预测分析表是一个M[A,a]形式的矩阵，其中A是非终结符，a是终结符或#。
矩阵元素M[A,a]中存放着一条关于A的产生式，指出A面临输入a时应采用的候选。
矩阵元素M[A,a]中也可能存放着一个“出错标志”，指出A根本不该面临输入符号a。

不想码字了，直接参考这篇，很好的：First集和Follow集的求法_zcb1592781470的博客-CSDN博客_first集和follow集的求法

当然还要注意了，FOLLOW集合中不能有 $\epsilon$。

LL(1)分析条件：

文法不含左递归
对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 $A\rightarrow \alpha_1|…|\alpha_n$，有 $FIRST(\alpha_i)\cap FIRST(\alpha_j)=\phi$
对文法中的每个非终结符A，若它存在某个候选首符集包含 $\epsilon$，则 $FIRST(A)\cap FOLLOW(A)=\phi$

如果一个文法G满足以上条件，则称该文法G为LL(1)文法。

自底向上语法分析

看到P69了！

LR文法比LL描述能力更强。

自底向上的语法分析方法，也称为移进-归约分析法。

较常用的自底向上分析法：

移进-归约分析
用栈实现移进-归约分析

最易于实现的移进-归约分析法：

算符优先分析法
算符优先分析法定义、优先分析表的确定、优先函数的定义
使用算符优先关系进行分析
算符优先分析中的错误恢复

最一般的移进-归约分析法：

LR分析法

移动归约分析法为输入串构造分析树时是从叶结点（底端）开始，向根结点（顶端）前进。

可以把该过程看成是把输入串 $\omega$ “归约”成文法开始符号的过程。
在每一步归约中，如果一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替该子串。
如果每一步都能恰当的选择子串，我们就可以得到最右推导的逆过程。

分析就是移动和归约过程的序列：

移进：将当前扫描的token移动到栈中
归约：将栈顶的符号串移除，用非终结符代替（对应某一产生式）

对于文法 G[S]，$\alpha\beta\delta$ 是G的一个句型。

短语：若 $S\Rightarrow^*\alpha A\delta$ 且 $A\Rightarrow^+\beta$ ，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于非终结符A的短语。
直接短语：在短语的基础上，$\beta$ 是A的直接推导，即，$A\Rightarrow \beta$
句柄：一个句型的最左直接短语称为 该句型的句柄 （句柄是相对于句型而言的）

用子树解释：

短语：就是某个子树的叶子节点的序列。
直接短语：就是二级子树的叶子节点的序列
句柄：就是最左直接短语。

参考这个：理解：语法树，短语，直接短语，句柄 - Raicho - 博客园

规范归约：

文法的最右推导是规范推导，自底向上分析是自顶向下最右推导的逆过程，叫规范归约。

句柄：

一个符号串的句柄是和一个产生式右部匹配的子串，而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。
形式定义：右句型（最右推导可得到的句型） $\gamma$ 的句柄是一个产生式 $A\rightarrow\beta$ 以及 $\gamma$ 的一个位置，在该位置可以找到串 $\beta$，而且用A代替 $\beta$ 可以得到 $\gamma$ 的最右推导的前一个右句型。
对于有二义性的文法而言，由于最右推导不一定唯一，因此句柄也不一定唯一。只有当文法没有二义性时，每个右句型才只有一个句柄。

句柄剪裁：

通过“剪裁句柄”可以得到最右推导的逆过程
在归约过程中用到的产生式序列的逆序就是输入串的最右推导

算符优先分析法

算符文法：

所有产生式的右部都不是 $\epsilon$ 或两个相邻的非终结符
设有一个文法G，如果G中没有形如 $A\rightarrow …BC…$ 的产生式，其中B和C为非终结符，则称G为算符文法(operator grammar)，也称为OG文法

算符优先文法的特点：

一旦我们构造了算符优先语法分析器，就可以忽略原来的文法，栈中的非终结符仅仅作为与这些非终结符相关的属性
难以处理像减号➖这样有不同优先级的符号
由于分析的语言的文法和算符优先语法分析器本身的关系不是很紧密，所以不能肯定语法分析器接受的就是所期望的语言

算符优先关系：

$a<b$：文法中有形如 $A\rightarrow …aB…$ 的产生式而 $B\Rightarrow^+ b…$ 或 $B\Rightarrow^+ Cb…$
$a=b$：文法中有形如 $A\rightarrow …ab…$ 或 $A\rightarrow …aBb…$ 的产生式
$a>b$：文法中有形如 $A\rightarrow …Bb…$ 的产生式而 $B\Rightarrow^+ …a$ 或 $B\Rightarrow^+ …aC$

算符的优先关系是有序的：

a>b 不能推出 b<a
a>b 有可能 b>a
a>b 且 b>c 不一定有 a>c

算符的优先关系，本质上是在不在同一个句柄中以及归约的优先顺序。

最左素短语：

一个算符优先文法G的任何句型的最左素短语是满足以下条件的最左子串 $N_ja_j…N_ia_iN_{i+1}$：

$a_{j-1}<a_j$
$a_j=a_{j+1}=…=a_i$
$a_i>a_{i+1}$

算符优先关系主要用于界定右句型的句柄：

< 标记句柄的左端；= 出现在句柄的内部；> 标记句柄的右端。
发现句柄的过程：
- 从左端开始扫描串，直到遇到第一个>为止。
- 向左扫描，跳过所有的=，直到遇到一个<为止。
- 句柄包括从上一步遇到的<右部到第一个>左部之间的所有符号，包括介于期间或者两边的非终结符。

这不就是层数的原因吗，层数越大归约的优先级就越高啊。

句柄也是这么来的啊。

因为非终结符不能影响语法分析，所以不需要区分它们，于是只用一个占位符来代替它们。

算符优先分析算法：

用栈存储已经看到的输入符号，用优先关系指导移动归约语法分析器的动作

如果栈顶的终结符和下一个输入符之间的优先关系是<或=，则语法分析器移动，表示还没有发现句柄的右端
如果是>关系，就调用归约

# 小于其他所有符号，# 和自己是优先级相等的关系。

LR分析法

规范归约（最左归约，即最右推导的逆过程）最重要的是寻找句柄。

LR(k)语法分析器适用于一大类上下文无关文法的语法分析。k省略时，假设k是1。

L指从左向右扫描输入字符串
R指构造最右推导的逆过程
k指的是在决定语法分析动作时需要想前看的符号个数

构造LR分析表的三种方法：

简单LR方法（SLR），最容易实现，功能最弱
规范LR方法，功能最强，代价最高
向前看LR方法（LALR），其功能和代价介于前两者之间

LR

一个LR分析器实质上是一个带先进后出存储器（栈）的DFA。

ACTION[s, a] 规定了当前状态 s 面临输入符号 a 时应采取什么动作。

GOTO[s, X] 规定了状态 s 面对文法符号 X（终结符或非终结符）时下一个状态是什么。

LR语法分析器的结构：ACTION表

每一项 ACTION[s, a] 所规定的动作是下面四种可能之一：

移进：把 (s, a) 的下一个状态 s' = GOTO[s, a] 和输入符号 a 推进栈，下一个输入符号变成现行输入符号（就是当前面临的、当前指向的输入符号）
归约：指用一个产生式 $A\rightarrow\beta$ 进行归约。此时 $\beta$ 是位于栈顶的，于是需要取出栈顶的 $\beta$，假设 $\beta$ 长度为r，取出之前的栈顶状态是 $S_m$，那么取出后栈顶状态变成 $S_{m-r}$；然后，把 $(S_{m-r},A)$ 的下一状态 $GOTO[S_{m-r},A]$ 和文法符号A推进栈。
接受：宣布分析成功，停止分析器的工作
报错：发现源程序含有错误，调用出错处理程序

这里强调一下栈的结构：一直很奇怪状态和符号怎么混在一起了，谁先谁后啊。其实，栈相当于分成了两部分，就是两个并列的栈，一个专门存储状态，一个专门存储符号。

显然，是GOTO定义了一个以文法符号为字母表的DFA。

LR(0)分析表

活前缀：规范句型的一个前缀，不含句柄之后的任何符号。

只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。

LR(0)项目

有效项目：我们说项目 $A\rightarrow\beta_1\cdot\beta_2$ 对活前缀 $\alpha\beta_1$ 是有效的，条件是存在规范推导 $S’\Rightarrow^*\alpha A\omega\Rightarrow\alpha\beta_1\beta_2\omega$

LR(0)分析表的构造：P59

编译原理复习