文法和语言

文法的引入

终结符 $V_T$ ，非终结符 $V_N$ ，语法规则 $P$ ，开始符号 $S$
文法的EBNF表示：采用特殊的符号表示文法：

如：<无符号整数>→{<数字>} $_1^3$ 与<无符号整数>→<数字>|<数字><数字>|<数字><数字><数字>相同。

字母表和符号串

字母表 $\Sigma$ ：元素的非空有穷集合。字母表每个元素称为符号。
符号串：由字母表上0个或多个符号组成的任何有穷序列。
空串：不包含任何符号的串，记作 $\varepsilon$
$\Sigma$ 上全部有穷长符号串的集合记作 $\Sigma^*$
集合的乘积运算
符号串的幂运算： $x^0=\varepsilon,x^1=x,x^2=xx,\dots$
正闭包 $A^+=A^1\cup A^2\cup\dots\cup A^n\cup\dots$
闭包 $A^*=A^0\cup A^+$

文法和语言的形式定义

文法G为一个四元组 $G=(V_N,V_T,P,S)$
句型：若 $S\Rightarrow^*x$ ，且 $x\in(V_N\cup V_T)^*$ ，则称x是文法G的句型。（文法开始符号推导出的任意字符串）
句子：仅由终极符组成的句型称为句子。
语言L(G)：由文法G的一切句子的集合。

给定一种文法，唯一确定一种语言；给定一种语言，能确定其文法，但不唯一。
若L(G1)=L(G2)，则称两文法等价。

文法和语言分类

0型文法： $\alpha→\beta,\alpha\in V^*V_NV^*,\beta\in V^*,V=V_N\cup V_T$
1型文法（上下文相关文法）： $\alpha U\beta→\alpha u\beta$ ，其中 $U\in V_N,\alpha,\beta\in V^*,u\in V^+,V=V_N\cup V_T$ ，即只有在上下文为ab时，才把U替换为u

另一等价定义：一个0型文法G中所有产生式 $a→b$ 都满足如下条件： $|a|\le|b|(a,b\in V^+)$ ，则称G为1型文法。
2型文法（上下文无关文法）： $A→u,A\in V_N,u\in V^*,V=V_N\cup V_T$
3型文法（正则文法）： $U→a$ 或 $U→aW\enspace U,W\in V_N,a\in V_T^*$

左线性文法和右线性文法都成为线性文法，两者等价。

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

最左推导：在推导的任何一步都是对α中的最左非终结符进行替换。得到左句型。
最右推导（归约推导）：在推导的任何一步都是对α中的最右非终结符进行替换。得到右句型（归约句型）
左分析：由文法开始符号S到句子x的最左推导中所用规则序列。（语法树自顶向下生长，又称自顶向下分析）
右分析：最右推导的逆序列。（自底向上分析）
若一个句子无二义性，其各种推到得出的语法树是相同的。
短语：一棵子树所有叶子从左至右排列起来形成一个相对于子树根的短语。
直接短语：仅有父子两代的一棵子树的短语。
句柄：一个句型分析树中最左最下那棵只有父子两代的子树所有叶子自左至右排列

歧义文法及实用文法限制与扩充

一个文法存在某个句子，对应两棵以上不同的语法树，或两个不同的最左（右）推导，则称文法是歧义文法。
文法起义不等价于语言歧义。
简化文法
1. 不存在 $P→P,P\in V_T$
2. 每个非终结符都是可达和可终止的。
空规则：上下文无关文法中某些规则可具有形式 $A→\varepsilon$

词法分析

单词的描述工具

正规式中的符号
对任一正则文法，存在一个定义同一个语言的正规式；每个正规式存在一个生成同一语言的正则文法。

有穷自动机

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

有穷自动机和正则文法的等价性

DFA： $M=(K,\Sigma,f,S,Z)$ ，其中K为状态的有穷非空集， $\Sigma$ 为输入字母表，f为 $K×\Sigma$ 到K的一个映射（读入一个符号，转入一个状态）， $S\in K$ 是开始状态， $Z\subseteq K$ 为终止状态集。
NFA：任意时刻可属于多个状态，可以有多个开始状态，映射函数的值可以是多个状态或空集。
格局运动（表示FA识别正则句子的过程）
NFA确定化（带空转换与不带空转换）
NFA构造等价正则式
1. 新增两个状态x, y：x为新的初态节点，用 $\varepsilon$ 弧连接原来所有初态节点，y为终态节点，同样用 $\varepsilon$ 弧连接。
2. 转换
3. 重复，直到剩x和y
正则式构造等价的NFA：机械的方法。

DFA最小化

不断划分，直到DFA没有等价状态。

自顶向下语法分析

自顶向下语法分析概述

带回溯的自顶向下语法分析：不断试探、左递归和间接左递归会导致分析过程无法终止。
上下文无关文法特性—自嵌入性：一个文法G是自嵌入的，若存在一个非终极符A，有 $A\Rightarrow^*\alpha A\beta\enspace \alpha,\beta\in V^+$ 非空。
自顶向下语法分析主要问题：回溯、消除左递归
消除回溯方法：每次选择确定，如LL(1)
消除左递归方法：
- 重排规则顺序
- 左递归变为右递归
  1. 消除直接左递归：
  2. 消除间接左递归：代入法，直接带入然后利用消除直接左递归解决。

LL分析法

LL(K)的含义：从左向右扫描字符串并建立最左推导，同一非终极符的不同规则通过向前看K个符号决定。
LL(1)文法
1. 定义1：设G是不带 $\varepsilon$ 规则的文法，若对所有 $A→a_1|a_2|\dots|a_n$ 的规则，有 $FIRST(a_i)\cap FIRST(a_j)=\phi$ ，则G为LL(1)文法。
2. 定义2：一个文法G是LL(1)文法，当且仅当对文法中形如 $A→a_1|a_2|\dots|a_n$ $A \to a_{1} ∣ a_{2} ∣ \dots ∣ a_{n}$ 都满足LL(1)条件，即
  1. $FIRST(a_i)\cap FIRST(a_j)=\phi,i\ne j$
  2. 如果 $a_i\Rightarrow^*\varepsilon$ ， $FIRST(a_j)\cap FOLLOW(A)=\phi,i\ne j$
3. 对于相同左部的产生式，如果其SELECT集有交叉，则不为LL(1)文法。
文法的变换：将非LL(1)文法转换为LL(1)文法
1. 左递归文法的变换，消除左递归
2. 提取左公共因子变换
3. 角替换：一规则右部的最左出现称位规则的角，对非终极符的角，用其规则右部替换。
LL(1)分析器

递归子程序法

根据产生式各候选式的结构，为其编写递归函数。是一种确定的自顶向下的语法分析方法。

约定：文法必须为LL(1)文法。

自底向上语法分析&LR分析

自底向上语法分析

归约推导就是右推导，得到的句型是归约句型；归约归约是最左归约，是归约推导的逆过程，每次都对句柄归约成相应的非终结符号。
过程：对输入串压栈，栈顶符号串形成句柄则进行归约；最后栈中只剩开始符号则句子合法。
LR分析程序的实质：分析表+DFA
LR分析法无需消除左递归，也无需消除左公共因子。

LR分析器概述

LR分析器组成：总控程序、分析表、分析栈
- 分析表：动作表（状态S遇到输入符号a的动作）、状态转换表（状态S遇到 $X\in V_N$ 应进入的下一状态）
- 分析栈：文法符号栈、状态栈
工作原理：任一时刻由栈顶状态和当前输入符号决定下一步动作。

LR(0)分析法

拓广文法：在原文法的基础上，引入新的开始符号使得新的开始符号为单一规则的左部。
活前缀和可归前缀：
并非所有句型都是规范句型，在CFG中，每个句子都有规范推导，但每个句型不一定具有规范推导。（比如非规范推导得出来的句型）
LR(0)项目类型：
直接构造识别活前缀的DFA：把拓广文法的第一个项目作为初始状态集的核，通过求核的闭包核转换函数，求出LR(0)项目集规范族，可直接构造识别活前缀的DFA。
LR(0)文法存在冲突的项目集：
1. 移进—归约冲突
2. 归约—归约冲突
注，在增广文法第一个项目中识别#的归约与其他移进不冲突。
LR(0)文法定义：若一个文法的LR(0)项目集规范族不存在含移进归约和归约归约冲突的项目集，则成为LR(0)文法。

SLR(1)分析法

当不是LR(0)文法时，通过向前查看一个输入符号来协助解决冲突的分析方法，称位SLR(1)分析法。

冲突解决：当对某句柄进行规约时，根据句柄后面符号判断规约是否正确。后面符号可由句柄对应的非终极符的Follow集求得。
核心思想：在不是LR(0)的项目集中，对于冲突的位置判断冲突是否可以解决，即看Follow集，如能解决则为SLR(1)文法。

语法制导翻译和中间代码生成

语法制导翻译

在语法分析中，根据每个产生式所对应的语义子程序进行翻译的方法。描述语义动作时，需要赋予每个文法符号X( $V_T$ 和 $V_N$ )以不同的值，统称为属性值。

属性分为综合属性和继承属性。
综合属性：从其子结点的综合属性值计算得来，用于自下而上信息传递
继承属性：由语法树中该结点的父结点和位于其左边的兄弟节点的属性值计算出来，用于自上而下传递信息。
- 非终结符即可有综合属性也可由继承属性，但文法开始符号没有继承属性。
- 终结符只有综合属性，由词法分析程序提供。
例：类型定义的语法制导定义

例：生成变量说明的文法

属性文法

属性文法是一个三元组 $A=(G,V,F)$ ，其中：G是一个上下文无关文法；V是有穷的属性集；F关于属性的断言或一组属性的计算规则。例：
对声明语句的文法进行改写：

翻译文法如下：

从文法上来看， $@SET\_TYPE$ 应有两个属性：Type和ID
属性文法的求值规则：当翻译文法的符号具有属性，并带有属性求职规则时，就成为属性文法。求值规则定义如下：
1. $V_T,V_N,$ 动作符号都可以有一个有穷的属性集
2. 每个非终结符和动作符号的属性类型可分为综合属性和继承属性
3. 继承属性求值规则
  1. 产生式左部的非终结符，继承属性继承前面产生式该符号已有的继承属性值
  2. 产生式右部的符号，继承属性由产生式其他符号属性值进行计算。
4. 综合属性求职规则
  1. 终结符号综合属性具有指定初始值，由词法分析提供。
  2. 产生式右部非终结符号综合属性值取自后面以该非终结符号为产生式左部时求得的综合属性
  3. 产生式左部非终结符号综合属性由产生式中左或右部某些符合属性值计算得到

S-属性文法的自底向上翻译

文法符号仅使用综合属性的语法制导翻译称位S-属性定义。其翻译器可以借助LR语法分析器及生成器来实现。增加值栈（属性栈）用来存放综合属性值，即保存已经分析过的子树信息。
LR分析器分析S属性文法（对于移进、规约进行属性栈的扩充）

L-属性文法的自顶向下翻译

一个语法制导定义是L-属性定义，如果对于属性文法中的任意产生式 $A→X_1X_2\dots X_i\dots X_n$ ，其每个语言规则每个属性都是综合属性，或是 $X_i$ 的一个继承属性，这一继承属性只依赖A的继承属性和 $X_i$ 的左面符号的属性。

中间代码形式

逆波兰表达式（后缀式）
三元式格式：OP, OP1, OP2。不必考虑临时变量的分配
树形表示（三元式的翻版，运算符为根，中序遍历为原表达式）
间接三元式
四元式：OP, OP1, OP2, RESULT

语句翻译

赋值语句的翻译
布尔表达式翻译：回填拉链法
控制语句的翻译

符号表

符号表的作用
1. 保存各类标识符的属性
2. 检查语义的正确性（先定义后使用、实参形参个数等）
3. 作为目标代码生成阶段地址分配的依据
建立和访问符号表的时机
1. 词法分析创建，只含有标识符名字，其他属性在语义分析阶段填入
2. 语义分析时创建
3. 语法分析阶段只检查源程序语法正确性，一般不适用符号表。
符号表的组织和内容
1. 名字域
2. 属性域
3. 目标地址、类型、维数及参数个数

目标程序运行时的存储组织

程序运行时的存储组织

从用途上来看，可以分为：目标代码区（存放目标代码）、静态数据区（存放编译时确定存储空间的数据）、运行栈区（用来存放运行时确定存储空间的数据）、运行堆区（用来存放运行时用户动态申请数据空间的数据）。

静态存储分配

静态存储分配中，编译时就给它们分配固定的存储空间，目标程序运行时，总是使用这些在编译时分配好的存储单元作为其数据空间。
所需满足条件：不允许过程有递归调用；不允许有可变大小数据项；不允许用户动态建立数据实体。
静态存储分配把内存看成一个一维数组，一旦分配，运行期间一直被某个变量占用。

栈式动态存储分配

栈式动态存储分配中，一个程序运行时所需数据区大小未知，运行中进入一个程序模块，模块所需数据区必须已知。运行时，每当进入一个程序块就为其分配一个新的数据区。
栈式动态存储分配策略是将程序数据空间设计为一个栈：
1. 每当程序调用一个过程就在栈顶为被调过程分配一个新的数据空间：保留块开始地址、为当前块分配存储、为每个局部量分配相对地址
2. 每当调用结束便释放栈顶空间。
活动记录：一段连续的存储区，存放程序模块一次执行所需全部信息。进入一个程序模块就要在运行栈顶创建一个活动记录，包括模块内定义的局部变量所需的存储空间、全局数据区指针以及形参、隐参。
活动记录的结构：

SP：基地址指针，指向最新活动记录的起点。

top：指向当前最新的活动记录的顶端。

动态链：老sp反映运行中模块间调用关系，子程序的动态链不唯一，Pi如果没有非正常出口，则会返回到Pi-1中。

display表：依次存放现行层、直接外层……直至最外层每个过程的最新活动记录起始地址。