编译原理（部分）

作者: 隨筆塗鴉 | 来源:发表于2019-06-26 22:06 被阅读0次

第1章引论

1.1 什么是编译程序

功能：高级语言程序（源程序）→【编译程序】→低级语言程序（目标程序）
过程：
需预处理的源程序→【预处理程序】→源程序→
【编译程序】→目标汇编语言程序→【汇编程序】→
可再装配的机器代码[＋可再装配目标文件]→
【装配/连接编辑程序】→绝对机器代码

1.2 编译过程和编译程序的结构

阶段：
源程序→【词法分析】→【语法分析】→【语义分析】→
【中间代码生成】→【代码优化】→【目标代码生成】→目标程序
=====================================================
结构：
【词法分析程序】＋【语法分析程序】＋【语义分析程序】＋
【中间代码生成程序】＋【代码优化程序】＋【目标代码生成程序】＋
【表格管理程序】＋【出错处理程序】
=====================================================
组合：
前端（front end）工作主要依赖于源语言而与目标机无关；
后端（back end）工作依赖于目标机而一般不依赖于源语言。

1.3 解释程序

区别：编译产生中间代码。

第2章文法和语言

2.2 符号和符号串

字母表：元素的非空有穷集合，元素称为符号，因此字母表也成为符号集。
符号串：字母表中的符号组成的任何有穷序列，讲究顺序，允许空符号串 $\epsilon$ ，其长度为 $0$ ，即 $|\epsilon|=0$ 。符号串有头/尾，头/尾非空称为固有头/尾。符号串有连接/方幂/集合运算，其中， $\epsilon$ 是连接运算的单位元，即 $s\epsilon=\epsilon s=s$ 。指定字母表为 $\Sigma$ ，则 $\Sigma^*$ 表示字母表上所有有穷长的串的集合，称为 $\Sigma$ 的闭包， $\Sigma^+$ 称为正闭包。

$\Sigma^*=\Sigma^0\cup\Sigma^1\cup\dots\cup\Sigma^n\cup\dots$
$\Sigma^*=\Sigma^0\cup\Sigma^+,\Sigma^+= \Sigma\Sigma^*=\Sigma^*\Sigma$

规则：也称重写规则、产生式或生成式，是形如 $\alpha\to\beta$ 或 $\alpha::=\beta$ 的 $(\alpha,\beta)有序对$ 。其中， $\alpha$ 称为左部， $\beta$ 称为右部，符号 $\to(::=)$ 读作“定义为”。
文法 $G$ 定义为四元组 $(V_N,V_T,P,S)$ ，其中， $V_N$ 为非终结符集/语法实体集/变量集， $V_T$ 为终结符集， $P$ 为产生式 $(\alpha\to\beta)$ 的集合， $\alpha,\beta\in(V_N\cup V_T)^*$ 且至少有一个 $\alpha$ 是非终结符， $S$ 为识别符/开始符，也是非终结符，至少要在一条产生式中作为左部出现。 $V_N\cap V_T=\emptyset$ ， $V=V_N\cup V_T$ ，称为文法 $G$ 的字母表/字汇表。 $G=G[S]$ 。
推导：直接推导 $\Rightarrow$ ，长度为 $n(n\geqslant1)$ 的推导 $\overset{+}{\Rightarrow}$ ，长度为 $n(n\geqslant0)$ 的推导 $\overset{*}{\Rightarrow}$ 。直接推导： $\alpha\to\beta,\text{both }\gamma\text{ and }\delta\in V^*,v=\gamma\alpha\delta,$ ，如果 $w=\gamma\beta\delta$ ，则 $v\Rightarrow w$ ，称 $v$ 直接产生 $w$ ，或 $w$ 是 $v$ 的直接推导，或 $w$ 直接归约到 $v$ 。若有 $v\overset{+}{\Rightarrow}w$ 或 $v=w$ ，则记作 $v\overset{*}{\Rightarrow}w$ 。

2.3 文法和语言的形式定义

对于文法 $G[S]$ ， $x$ 为符号串，若 $S\overset{*}{\Rightarrow}x$ ，则称 $x$ 是文法 $G[S]$ 的句型；若 $x$ 仅由终结符号组成，即 $S\overset{*}{\Rightarrow}x,x\in V_T^*$ ，则称 $x$ 为 $G[S]$ 的句子。
可用 $L(G)$ 表示文法 $G$ 所产生的语言——集合 ${\{x|S\overset{*}{\Rightarrow}x,x\in V_T^* \}}$ 。文法描述的语言是该文法一切句子的集合。若 $L(G1)=L(G2)$ ，则称文法 $G1$ 和 $G2$ 是等价的。
文法的类型：乔姆斯基（Chomsky）于1956年建立形式语言的描述，把文法分为四种类型，即0型、1型、2型和3型。设 $G=(V_N,V_T,P,S)$ ，产生式 $\alpha\to\beta$ ：

2.4 文法的类型

0型文法/短语文法，满足 $\alpha,\beta\in(V_N\cup V_T)^*$ 且至少有一个 $\alpha$ 是非终结符，能力相当于图灵机，0型语言都是递归可枚举的，反之递归可枚举集必是一个0型文法；
1型文法/上下文有关文法，除 $S\to\epsilon$ 外，满足 $|\beta|\geqslant|\alpha|$ ；
2型文法/上下文无关文法，满足 $\alpha$ 是一个非终结符且 $\beta\in(V_N\cup V_T)^*$ ，也表示成 $A\to\beta,A\in V_N$ ，用 $\beta$ 取代非终结符 $A$ 时，与 $A$ 所在的上下文无关；
3型文法/正规文法，满足 $A\to aB$ 或 $A\to a$ ，且 $a\in V_T^*=V_T\cup\{\epsilon \}$ ，其中 $A,B$ 都是非终结符。

2.5 上下文无关文法及其语法树

语法树/推导树，满足下列四个条件：

每个结点都有一个标记，是 $V$ 的一个符号；
根的标记是 $S$ ；
若一个结点 $n$ 至少有一个除自己外的子孙，且有标记 $A$ ，则 $A\in V_N$ ；
若结点 $n$ 的直接子孙从左到右的次序是 $n_1,n_2,\dots,n_k$ ，其标记分别为 $A_1,A_2,\dots,A_k$ ，则 $A\to A_1A_2\dots A_k$ 一定是 $P$ 中的一个产生式。

如果推导的任何一步都是对最左/最右的非终结符进行替换，则称为最左/最右推导。最右推导常称为规范推导，得到的句型称为右句型/规范句型。
如果一个文法存在某个句子对应两棵不同的语法树，或者说，若一个文法存在某个句子有两个不同的最左/最右推导，则说该文法是二义的。文法的二义性≠语言的二义性，存在 $G\neq G',L(G)=L(G')$ 的可能。如果产生上下文无关语言的每个文法都是二义的，则说此语言是先天二义的。理论证明，判定任给的一个上下文无关文法是否为二义的，或者该文法是否产生一个先天二义的上下文无关语言，都是递归不可解的问题——不存在一个算法，能在有限步骤内确切判定任给的一个文法是否为二义的。

2.6 句型的分析

定义： $G,S$ ， $\alpha\beta\delta$ 是文法的一个句型，若 $S\overset{*}{\Rightarrow}\alpha A\delta$ 且 $A\overset{+}{\Rightarrow}\beta$ ，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于非终结符 $A$ 的短语。特别地，若 $A\Rightarrow\beta$ ，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于产生式 $A\to\beta$ 的直接短语/简单短语。一个右句型的直接短语称为该句型的句柄。

2.7 文法应用的补充说明

文法中不能存在有害规则（形如 $U\to U$ ，引起文法的二义性）和多余规则（不可到达的和不可终止的）。
对于文法 $G=(V_N,V_T,S,P)$ ，为保证非终结符 $A$ 在句子推导中出现，须满足：

$A$ 必须出现在某句型中，即有 $S\overset{*}{\Rightarrow}\alpha A\beta,\alpha\text{ and }\beta\in(V_N\cup V_T)^*$ ；
必须能从 $A$ 推导出终结符号串 $t$ ，即 $A\overset{+}{\Rightarrow}t,t\in V_T^*$ 。

第3章词法分析

3.3 单词的形式化描述工具

3.3.1 正规文法

即3型文法， $A\to aB,A\to a,A\text{ and }B\in V_N,a\in V_T^*=V_T\cup \{\epsilon \}$ 。

3.3.2 正规式

……

3.3.3 正规文法等价于正规式

正规式转换成正规文法：

	正规式	文法产生式
规则1	$A\to xy$	$A\to xB,B\to y,B\in V_N$
规则2	$A\to x^*y$	$A\to xB,A\to y,B\to xB,B\to y$
规则3	$A\to x\|y$	$A\to x,A\to y$

正规文法转换成正规式：

	文法产生式	正规式
规则1	$A\to xB,B\to y$	$A=xy$
规则2	$A\to xA\|y$	$A=x^*y$
规则3	$A\to xz,A\to yz$	$A=(x\|y)z$

3.4 有穷自动机

确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。

3.4.1 DFA

$M=(K,\Sigma,f,S,Z)$ ：
$K$ 是有穷集，其每个元素称为一个状态；
$\Sigma$ 是有穷字母表，其每个元素称为一个输入符号，故又称输入符号表；
$f$ 是转换函数，是 $K\times\Sigma\to K的映像$ ，令 $f(k_i,a)=k_j,k_i\text{ and }k_j\in K$ ，当前状态为 $k_i$ ，输入字符为 $a$ 时，将转换到下一状态 $k_j$ ， $k_j$ 称作 $k_i$ 的一个后继状态；
$S\in K$ 是唯一的一个初态； $Z\subseteq K$ 是一个终态集，终态也称可接受状态/结束状态。
若 $t\in\Sigma^*$ ， $f(S,t)=P,P\in Z$ ，则称 $t$ 可为该DFA所接受/识别。
DFA $M$ 所能接受的符号串的全体记为 $L(M)$ 。 $\Sigma$ 上的一个符号串集 $V\in\Sigma^*$ 是正规的，当且仅当存在一个 $\Sigma$ 上的确定有穷自动机 $M$ ，使得 $V=L(M)$ 。

3.4.2 NFA

$M=(K,\Sigma,f,S,Z)$ ：
$K$ 是有穷集，其每个元素称为一个状态；
$\Sigma$ 是有穷字母表，其每个元素称为一个输入符号；
$f$ 是一个 $K\times\Sigma^*\to K$ 的全体子集的映像，
即 $K\times\Sigma^*\to2^K$ ，其中 $2^K$ 表示 $K$ 的幂集；
$S\subseteq K$ 是一个非空初态集； $Z\subseteq K$ 是一个终态集。
对于每个NFA $M$ ，都存在一个DFA $M'$ ，使得 $L(M)=L(M')$ 。对于任何两个有穷自动机 $M,M'$ ，若 $L(M)=L(M')$ ，则称两者是等价的。

3.4.3 NFA转换为等价的DFA

子集构造算法：

$\epsilon-closure(s)$ ：能够从NFA的状态 $s$ 开始只通过 $\epsilon$ 转换到达的NFA状态集合

$\epsilon-closure(T)$ ：能够从 $T$ 中某个NFA状态 $s$ 开始只通过 $\epsilon$ 转换到达的NFA状态集合，即 $\cup_{s\in T}\epsilon-closure(s)$

$moveTo(T,a)$ ：能够从 $T$ 中某个状态 $s$ 出发通过标号为 $a$ 的转换到达的NFA状态集合

NFA的开始状态集合用 $A$ 标记， $A=\epsilon-closure(0)$ ，然后反复依次读取字母表，每次记录变化的NFA状态集合同时进行标记，直到某个NFA状态集合包含终止符号，则最后一次读取字母表并记录和标记NFA状态集合。

例如（字母表为 $\{ a,b \}$ ，状态集合 $E$ 包含终止符）：

NFA状态	DFA状态	a	b
$\{ \dots \}$	A	B	C
$\{ \dots \}$	B	B	D
$\{ \dots \}$	C	B	C
$\{ \dots \}$	D	B	E
$\{ \dots \}$	E	B	C

3.4.4 DFA的化简

两个状态等价的条件：

一致性——两者必须同时为可接受/不可接受状态；
蔓延性——对于所有输入符号，两者必须转换到等价的状态里。

分割法：

首先把 $M$ 的状态分成两个子集，一个由终态组成，另一个由非终态组成，初始化划分为 $P_0=(\{s_1,s_2,s_3,s_4\} ,\{s_5,s_6,s_7\})$ ，两个子集任何状态之间都不等价；
读入输入符号 $a$ ，观察第一个子集，发现两组状态分别转换到终态和非终态，即这两组状态之间不等价，因此将其划分为 $P_1=(\{s_1,s_2\} ,\{s_3,s_4\} ,\{s_5,s_6,s_7\})$ ；
接着试图在 $P_1$ 中寻找一个子集和一个输入符号使得其状态可区别，然后得到 $P_2=(\{s_1,s_2\} ,\{s_3\} ,\{s_4\} ,\{s_5,s_6,s_7\})$ ；
继续上述过程，直到 $P_3=(\{s_1,s_2\}, \{s_3\}, \{s_4\}, \{s_5\}, \{s_6,s_7\})$ 不能再划分，令 $s_1$ 代表 $\{ s_1, s_2 \}$ 消去 $s_2$ ， $s_6$ 代表 $\{ s_6, s_7 \}$ 消去 $s_7$ ，得到化简之后的DFA。

3.5 正规式与有穷自动机的等价性

为NFA $M$ 构造正规式 $r$ ：

在 $M$ 的状态转换图上加两个结点 $x,y$ ，从 $x$ 结点用 $\epsilon$ 弧连接到 $M$ 的所有初态结点，从 $M$ 的所有终态结点用 $\epsilon$ 弧连接到 $y$ 结点，形成一个与 $M$ 等价的 $M'$ ，后者只有一个初态 $x$ 和一个终态 $y$ 。
逐步消去 $M'$ 中所有结点，最后只剩下 $x,y$ 结点，消去过程逐步用正规式来标记弧，规则如下：
（1） $r_1\text{ and }r_2\to r_1r_2$
（2） $r_1\text{ or }r_2\to r_1|r_2$
（3） $r_1\text{ and }r_2\text{ circle }r_2\text{ and }r_3\to r_1r_2^*r_3$

为正规式 $r$ 构造NFA $M$ ：

为 $\emptyset,\epsilon,a$ 构造NFA：
（1） $\text{for }\emptyset,\Rightarrow(x),((y))$
（2） $\text{for }\epsilon,\Rightarrow(x)\overset{\epsilon}{\rightarrow}((y))$
（3） $\text{for }a,\Rightarrow(x)\overset{a}{\rightarrow}((y))$
若 $s,t$ 为 $\Sigma$ 上的正规式，相应的NFA分别为 $N(s),N(t)$ ：
（1） $\text{for }r=s|t,\Rightarrow(x)\overset{\epsilon}{\rightrightarrows}\{N(s)\text{ or }N(t)\}\overset{\epsilon}{\rightrightarrows}((y))$
（2） $\text{for }r=st,$
（3） $\text{for }r=s^*,$

3.6 正规文法与有穷自动机的等价性

……

第4章自顶向下语法分析方法

4.1 确定的自顶向下分析思想

直观的文法特点：
（1）每个产生式的右部都由终结符号开始；
（2）若两个产生式有相同左部，则其右部由不同终结符开始。
不直观的文法特点：
（1）产生式右部不全是由终结符开始；
（2）如果两个产生式有相同左部，则其右部由不同终结符或非终结符开始；
（3）文法中无空产生式。

=======================================================

$FIRST$ 集合

$FIRST(\alpha)= \{ a|\alpha\overset{*}{\Rightarrow}a\beta,a\in V_T,\alpha,\beta\in V^*{\}}$

若 $\alpha\overset{*}{\Rightarrow}\epsilon$ ，则规定 $\epsilon\in FIRST(\alpha)$ 。

若 $X$ 是终结符号，则 $FIRST(X)=\{ X\}$ 。
若 $X$ 是非终结符号，且 $X\to Y_1Y_2\dots Y_k$ ，则令 $Y_i,i=1,2,\dots,k$ ，从 $i=1$ 开始逐个扫描 $Y_i$ ：如果 $Y_i\overset{*}{\rightarrow}\epsilon$ 不成立，则将 $FIRST(Y_i)$ 的所有符号都加入 $FIRST(X)$ ，然后停止扫描；如果 $Y_1\dots Y_k\overset{*}{\Rightarrow}\epsilon$ ，则将 $\epsilon$ 加入 $FIRST(X)$ ；
若 $X\to\epsilon$ 是产生式，则将 $\epsilon$ 加入 $FIRST(X)$ 。

=======================================================

$FOLLOW$ 集合

$FOLLOW(A)=$
$\{ a|S\overset{*}{\Rightarrow}\mu A\beta\land a\in V_T, a\in FIRST(\beta),\mu\in V_T^*,\beta\in V^+ \}$

若 $S\overset{*}{\Rightarrow}\mu A\beta\land\beta\overset{*}{\epsilon}$ ，则 $\#\in FOLLOW(A)$ 。

将 $\text{\$$$}$ 加入 $FOLLOW(S)$ ，其中 $S$ 是开始符号，而 $\text{\$$$}$ 是输入右端的结束标记。
若存在 $A\to\alpha B\beta$ ，则 $FIRST(\beta)$ 中除 $\epsilon$ 外的所有符号都在 $FOLLOW(B)$ 中。
若存在 $A\to\alpha B$ ，或存在 $A\to\alpha B\beta$ 且 $FIRST(\beta)$ 包含 $\epsilon$ ，则 $FOLLOW(A)$ 的所有符号都在 $FOLLOW(B)$ 中。

=======================================================

$SELECT$ 集合：

给定 $A\to\alpha,A\in V_N,\alpha\in V^*$ ：

$\text{if }\alpha\overset{*}{\nRightarrow}\epsilon,\text{then }$
$SELECT(A\to\alpha)=FIRST(\alpha)$
$\text{if }\alpha\overset{*}{\Rightarrow}\epsilon,\text{then }$
$SELECT(A\to\alpha)=(FIRST(\alpha)-\{\epsilon\})\cup FOLLOW(A)$

=======================================================

4.2 $LL(1)$ 文法的判别

对每个非终结符 $A$ 的两个不同产生式 $A\to\alpha,A\to\beta$ ，满足：
$SELECT(A\to\alpha)\cap SELECT(A\to\beta)=\emptyset$
文法 $G$ 是 $LL(1)$ 的，当且仅当 $G$ 的任意两个不同产生式 $A\to\alpha|\beta$ 满足条件：

$FIRST(\alpha)\cap FIRST(\beta)=\emptyset$ ；
若 $\epsilon$ 在 $FIRST(\beta)$ 中，则 $FIRST(\alpha)\cap FIRST(A)=\emptyset$ ；
若 $\epsilon$ 在 $FIRST(\alpha)$ 中，则 $FIRST(\beta)\cap FIRST(A)=\emptyset$ 。

4.3 某些非 $LL(1)$ 文法到 $LL(1)$ 文法的等价变换

4.3.1 提取左公因子

一般形式： $A\to\alpha\beta_1|\alpha\beta_2|\dots|\alpha\beta_n$
提取左公因子： $A\to\alpha A'$
引进非终结符： $A'\to\beta_1|\beta_2|\dots|\beta_n$
如果产生式右部以非终结符开始，可能存在隐式的左公因子，这种情况下，
用左部与之相同而右部以终结符开始的产生式完全替换其右部开始的非终结符。

4.3.2 消除左递归

消除直接左递归
$A\to A\alpha_1|A\alpha_2|\dots|A\alpha_m|\beta_1|\beta_2|\dots|\beta_n$
消除直接左递归后改写成：
$A\to\beta_1A'|\beta_2A'|\dots|\beta_nA'$
$A'\to\alpha_1A'|\alpha_2A'|\dots|\alpha_mA'|\epsilon$
消除间接左递归

以下文法为例：
$S\to Aa|b$
$A\to Ac|Sd|\epsilon$

对非终结符进行排序，先消除 $S$ 的立即左递归，
然后将 $S$ 代入 $A$ ，进行替换，消掉中间符号 $S$ ，
最后对 $A$ 消除直接左递归，得到最终消除结果。
$Sorting: S,A$
$\because A\to Ac|Aad|bd|\epsilon$
$\therefore S\to Aa|b$
$\ \ \ A\to bdA'|A'$
$\ \ \ A'\to cA'|adA'|\epsilon$

4.4 不确定的自顶向下分析思想

第6章 $LR$ 分析

6.1 $LR$ 分析概述

一个 $LR$ 分析器由3个部分组成：
1）总控/驱动程序，所有 $LR$ 分析器的总控程序都相同；
2）分析表/分析函数，不同文法/同一文法采用不同 $LR$ 分析器，分析表均不同，而分析表分为动作（ACTION）表和状态转换（GOTO）表，都用二维数组表示；
3）分析栈，包括文法符号栈和相应的状态栈，均是FILO。
分析器的动作由栈顶状态和当前输入符号来决定，其中， $LR(0)$ 分析器不需要向前查看输入符号。 $LR$ 分析器的工作过程如下：
1） $SP$ 为栈指针， $S[i]$ 为状态栈， $X[i]$ 为文法符号栈。状态转换表由关系GOTO $[S_i,X]=S_j$ 确定，意思是当栈顶状态为 $S[i]$ 遇到当前文法符号为 $X$ 时，应转向状态 $S_j$ ， $X$ 为终结符/非终结符。
2） $ACTION[S_i,a]$ 规定栈顶状态为 $S_i$ 遇到输入符号 $a$ 应执行的动作，有4种可能：
①移进
②归约
③接受acc
④报错

第7章语法制导的语义计算

7.1 基于属性文法的语义计算

7.1.1 属性文法

基本概念和术语
在文法 $G[S]$ 基础上，为文法符号关联有特定意义的属性，并为产生式关联相应的语义动作或条件谓词，称之为属性文法，并称该文法是这一属性文法的基础文法。例如：

$S\to ABC$ $\{ (A.num=B.num) and (B.num=C.num) \}$
$A\to A_1a\$ $\{ A.num:=A_1.num+1 \}$
$A\to a\ \quad\$ $\{ A.num:=1 \}$
$B\to B_1b\$ $\{ B.num:=B_1.num+1 \}$
$B\to b\ \quad\$ $\{ B.num:=1 \}$
$C\to C_1c\$ $\{ C.num:=C_1.num+1 \}$
$C\to c\ \quad\$ $\{ C.num:=1 \}$

上述属性文法可以接受的语言是 $L=\{a^nb^nc^n|n\geqslant1\}$ 。稍作修改：

$S\to ABC$ $\{ if \ (A.num=B.num) \ and \ (B.num=C.num)$
$\qquad\qquad\quad \ \ then \ \ \ print("accepted")$
$\qquad\qquad\quad \ \ else \quad print("refused"){\}}$
$A\to A_1a\$ $\{ A.num:=A_1.num+1 \}$
$A\to a\ \quad\$ $\{ A.num:=1 \}$
$B\to B_1b\$ $\{ B.num:=B_1.num+1 \}$
$B\to b\ \quad\$ $\{ B.num:=1 \}$
$C\to C_1c\$ $\{ C.num:=C_1.num+1 \}$
$C\to c\ \quad\$ $\{ C.num:=1 \}$

若输入串属于 $L$ ，则语义计算结果会执行 $then$ 语句，反之执行 $else$ 语句。

综合属性和继承属性
对关联于产生式 $A\to\alpha$ 的语义动作 $b:=f(c_1,c_2,\dots,c_k)$ ，若 $b$ 是 $A$ 的某个属性，则称其是 $A$ 的一个综合属性。从分析树的角度，计算综合属性是对父结点的属性赋值，是自底向上传递信息。
对关联于产生式 $A\to\alpha$ 的语义动作 $b:=f(c_1,c_2,\dots,c_k)$ ，若 $b$ 是产生式右部某个文法符号 $X$ 的某个属性，则称其是文法符号 $X$ 的一个继承属性。从分析树的角度，计算继承属性是对子结点的属性赋值，是自顶向下传递信息。

$S\to ABC$ $\{ B.in\_num:=A.num;C.in\_num:=A.num$
$\qquad\qquad\quad \ \ if \ (B.num=0) \ and \ (C.num=0)$
$\qquad\qquad\quad \ \ then \ \ \ print("accepted")$
$\qquad\qquad\quad \ \ else \quad print("refused"){\}}$
$A\to A_1a\$ $\{ A.num:=A_1.num+1 \}$
$A\to a\ \quad\$ $\{ A.num:=1 \}$
$B\to B_1b\$ $\{ B_1.in\_num:=B.in\_num;$
$\qquad\qquad\quad\ B.num:=B_1.num-1 {\}}$
$B\to b\ \quad\$ $\{ B.num:=B.in\_num-1 \}$
$C\to C_1c\$ $\{ C_1.in\_num:=C.in\_num;$
$\qquad\qquad\quad\ C.num:=C_1.num-1 {\}}$
$C\to c\ \quad\$ $\{ C.num:=C.in\_num-1 \}$

其中， $A.num,B.num,C.num$ 是综合属性， $B.in\_num,C.in\_num$ 是继承属性。对于前者进行自底向上计算，对于后者进行自顶向下计算。

7.1.2 遍历分析树进行语义计算

7.1.3 $S-$ 属性文法和 $L-$ 属性文法

只包含综合属性的属性文法称为 $S-$ 属性文法。
$S-$ 属性文法是 $L-$ 属性文法的一个特例。

编译原理（部分）

第1章 引论

1.1 什么是编译程序

1.2 编译过程和编译程序的结构

1.3 解释程序

第2章 文法和语言

2.2 符号和符号串

2.3 文法和语言的形式定义

2.4 文法的类型

2.5 上下文无关文法及其语法树

2.6 句型的分析

2.7 文法应用的补充说明

第3章 词法分析

3.3 单词的形式化描述工具

3.3.1 正规文法

3.3.2 正规式

3.3.3 正规文法等价于正规式

3.4 有穷自动机

3.4.1 DFA

3.4.2 NFA

3.4.3 NFA转换为等价的DFA

3.4.4 DFA的化简

3.5 正规式与有穷自动机的等价性

3.6 正规文法与有穷自动机的等价性

第4章 自顶向下语法分析方法

4.1 确定的自顶向下分析思想

4.2 文法的判别

4.3 某些非文法到文法的等价变换

4.3.1 提取左公因子

4.3.2 消除左递归

4.4 不确定的自顶向下分析思想

第6章 分析

6.1 分析概述

第7章 语法制导的语义计算

7.1 基于属性文法的语义计算

7.1.1 属性文法

7.1.2 遍历分析树进行语义计算

7.1.3 属性文法和属性文法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第1章引论

第2章文法和语言

第3章词法分析

第4章自顶向下语法分析方法

4.2 $LL(1)$ 文法的判别

4.3 某些非 $LL(1)$ 文法到 $LL(1)$ 文法的等价变换

第6章 $LR$ 分析

6.1 $LR$ 分析概述

第7章语法制导的语义计算

7.1.3 $S-$ 属性文法和 $L-$ 属性文法