字母表 $\sum$ 是一个有穷的符号集合，符号包括了字母、数字、标点符号……
对于文法 $G$，可以定义为 $G = (V_T, V_N, P, S)$
对于含有相同左部的产生式，可以通过“或”运算简写
例如对于
可以简写为
从语言的规则推导生成语言的过程
根据规则，可以将符号串推成另一个符号串的过程称为推导。用产生式的右部替换产生式的左部
如果是经过多次推导得到，则记为 $a_0 \Rightarrow^n a_n$
$a_0 \Rightarrow^+ a_n$ 表示经过至少一步推导得到
$a_0 \Rightarrow^* a_n$ 表示经过任意步数推导得到
根据语言的规则识别语言的过程
根据规则，可以将符号串还原成。将产生式的右部替换为产生式的左部
对于 $\forall \alpha \rightarrow \beta \in P$，满足 $\alpha$ 中至少包含一个非终结符
对于 $\forall \alpha \rightarrow \beta \in P$，满足 $|\alpha| \leq |\beta|$
也可以理解为对于 $\forall \alpha A \beta \rightarrow \alpha \gamma \beta \in P$，其中 $\alpha$、$\beta$ 可以为 $\varepsilon$，满足 $\gamma \neq \varepsilon$(在 $A = S$ 的情况下，此等式可以成立)
对于 $\forall \alpha \rightarrow \beta \in P$，满足 $\alpha$ 是一个非终结符
对于 $\forall \alpha \rightarrow \beta \in P$，满足 $\alpha$ 是一个非终结符，而 $\beta$ 只能是空串、一个终结符号或者一个终结符号和一个非终结符号
分析树是推导的图形化表示
如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的
正则表达式(简称：RE)是一种描述正则语言的表示方法，正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 $r$ 定义(表示)一个语言，记为 $L(r)$。这个语言也是根据 $r$ 的子表达式所表示的语言递归定义的
加入 $r$ 和 $s$ 都是 RE，表示的语言分别是 $L(r)$ 和 $L(s)$，则
可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)
给一些RE命名，并在之后的RE中像使用字母表中的符号一样使用这些名字
具有一系列离散的输入输出信息和有穷数目的内部状态的系统
对于任意的一个输入，自动机都唯一地确定了下一个状态
定义 $M=(S, \sum, \delta, s_0, F)$ 为一个确定的有穷自动机
确定的有穷自动机可以通过状态图来表示
初始结点通常用 $\Rightarrow$ 表示，终态结点通常为双圈表示
确定的有穷自动机还可以使用表格来表示其状态，例如上述的状态图可以表示为
| 状态 | 0 | 1 | |
|---|---|---|---|
| $S_0$ | $S_1$ | $S_0$ | 0 |
| $S_1$ | $S_1$ | $S_2$ | 0 |
| $S_2$ | $S_1$ | $S_0$ | 1 |
通常，在表格对应行的右端通过01的标注表示这个状态为终态
对于 $\sum^*$ 中的任意符号串 $t$，如果在状态图中存在一条从初态到某一终态的路径，且这条路径上所有弧的标记符连接起来等于 $t$，则称 $t$ 可以被此 DFA 接受
收到一个符号，可能进入不同的状态
定义 $M=(S, \sum, \delta, s_0, F)$ 为一个确定的有穷自动机
NFA 也可以通过状态图来表示和表格进行表示，与 DFA 的状态图类似
参考下面两张图
步骤：
以下图为例
画出如下的表格
将序号代替状态，重新绘图
以上方的图为例，易得状态 1 和状态 2 是等价状态，所以合并得到
最终得到
从分析树的顶部（根节点）向底部（叶节点）方向构造分析树，可以看成是从文法开始符号S推导出词串w的过程
在最左推导中，总是选择每个句型的最左非终结符进行替换，即优先满足表达式左侧
在最右推导中，总是选择每个句型的最右非终结符进行替换，即优先满足表达式右侧
自顶向下的语法分析采用最左推导方式
当出现了类似如下的推导公式时
时，此时可以出现左递归的情况，这会导致无法正确的进行最左推导，因为可以出现下面的情况：
此时可以将上述的推导公式转换为
将左递归的公式转换为右递归即可
这样的操作的代价是
例如
此时可以产生这样的推导
这时，应该将改为先进行替换得到
当出现
之类的结构，当读入的第一个字符为 $a$ 时，无法确定应该选择哪个产生式的时候，应该进行左公因子提取，即改编为
$FIRST(A)$ 集表示非终结符 $A$ 能够推导出的所有等式的第一个终结符的集合
这条等式可以用下面三个原则来求算
对于一个产生式 $A \rightarrow B$而言
$FOLLOW(A)$ 集表示非终结符 $A$ 后可以跟随哪些终结符
这两条等式可以用下面三个原则来求算
表示使用某个产生式的选择符号
同时满足
满足 LL(1) 的文法有下面三个条件：
若文法存在语句
则
若满足
则为 LL(1)
首先需要根据 $SELECT$ 集来构建一个分析表。通过表的信息实现语法分析
以下面的表达式文法为例
首先，消除左递归，易得，前两个式子均为左递归
得到
得到各个符号的 FIRST 集：
首先根据2、4、5式得到
然后根据 FIRST 集的求出剩下的 FIRST 集
然后再求出 FOLLOW 集
首先
然后根据第一个等式得到
然后继续重复做，直到没有 FOLLOW 集发生更新为止，最终得到
再得到 SELECT 集
此时，判断是否为 LL(1) 文法
所以是 LL(1)文法
根据 SELECT 得出下表
| i | + | * | ( | ) | # | |
|---|---|---|---|---|---|---|
| E | $\rightarrow TE’$ | $\rightarrow TE’$ | ||||
| E’ | $\rightarrow +TE’$ | $\rightarrow \varepsilon$ | $\rightarrow \varepsilon$ | |||
| T | $\rightarrow FT’$ | $\rightarrow FT’$ | ||||
| T’ | $\rightarrow \varepsilon$ | $\rightarrow *FT’$ | $\rightarrow \varepsilon$ | $\rightarrow \varepsilon$ | ||
| F | $\rightarrow i$ | $\rightarrow (E)$ |
采用三列分析法来分析，使用 # 表示尾部，假设输入的串为 i+i*i
| 栈 | 剩余输入 | 输出 |
|---|---|---|
E# | i+i*i# | |
TE'# | i+i*i# | 匹配了表中的 $\rightarrow TE’$ |
FT'E'# | i+i*i# | $\rightarrow FT’$ |
iT'E'# | i+i*i# | $\rightarrow i$ |
T'E'# | +i*i# | |
E'# | +i*i# | $\rightarrow \varepsilon$ |
+TE'# | +i*i# | $\rightarrow +TE’$ |
TE'# | i*i# | |
FT'E'# | i*i# | $\rightarrow FT’$ |
iT'E'# | i*i# | $\rightarrow i$ |
T'E' # | *i# | |
*FT'E'# | *i# | $\rightarrow *FT’$ |
FT'E'# | i# | |
iT'E'# | i# | $\rightarrow i$ |
T'E'# | # | |
E'# | # | $\rightarrow \varepsilon$ |
# | # | $\rightarrow \varepsilon$ |
匹配成功
略
从分析树的底部(叶节点)向顶部(根节点)方向构造分析树，可以看成是将输入串w归约为文法开始符号S的过程，自底向上的语法分析采用最左归约方式（反向构造最右推导）
由于 SLR(1) 的操作和 LR(0) 分析法相似，且兼容，所以这里直接写 SLR(1) 的操作过程，LR(0) 文法也可以直接用此方法，得到的结果完全相同
以此文法为例
得到
LR分析法不适用于有多个开始符号的产生式，所以应当对上面的产生式进行处理得到
每行开头的为编号，后续通过编号来指代产生式
对于一个状态，首先，判断.后面是否为非终结符号。如果是，那我们就得找所有由此非终结符推出的产生式，并将它们添加进入此状态里。循环做即可。
使用 . 表示当前匹配到的位置
首先建立初状态，将第一个表达式加入初状态 State 0
此状态中有 $S’ \rightarrow .S$
检查 . 后是否为非终结符，得到 $S$，由于 $S$ 是非终结符，所以将 $S$ 的产生式加入此状态得到
再检查新加入的，得到 $L$ 也需要加入此状态
最后发现 $B$ 也是需要加入此状态的得到 State 0 的最终结果
接下来的每个状态都是从 State 转换过来的，即将小数点向后移动，可以得到不同的状态
根据其状态内的产生式，可以得到 State 0 可以有 $S, L, B, 0, 1$ 这五个转移方式
设定 State 1 是从 State 0 通过 $S$ 转移过来的
所以可以得到，仅
满足，所以 State 1 即只有此产生式，且不可以再转移
注意，State 1 是第一个产生式的最后的结果，所以此状态作为 Accept 状态，简称 acc
设定 State 2 是从 State 0 通过 $L$ 转移过来
所以可以直接得到的有
对于第三个式子，其满足条件(.后为非终结符)，所以需要把 $B$ 加入此状态
即得到
不断重复上述步骤，得到下面的图和结果
graph LR
A[State 0] -- S --> B[State 1]
A[State 0] -- L --> C[State 2]
A[State 0] -- B --> D[State 3]
A[State 0] -- 0 --> E[State 4]
A[State 0] -- 1 --> F[State 5]
C[State 2] -- * --> G[State 6]
C[State 2] -- B --> H[State 7]
C[State 2] -- 0 --> E[State 4]
C[State 2] -- 1 --> F[State 5]
G[State 6] -- L --> I[State 8]
G[State 6] -- B --> D[State 3]
G[State 6] -- 0 --> E[State 4]
G[State 6] -- 1 --> F[State 5]
I[State 8] -- B --> H[State 7]
I[State 8] -- 0 --> E[State 4]
I[State 8] -- 1 --> F[State 5]
B[State 1] --> Accept([Accept])
Accept通常状态不需要画出
由此图和上面的集合可以画出表格
| 状态 | ACTION | GOTO | |||||
| 0 | 1 | * | $ | S | L | B | |
| 0 | s4 | s5 | 1 | 2 | 3 | ||
| 1 | acc | ||||||
| 2 | s4 | s5 | s6 | r2 | 7 | ||
| 3 | r4 | r4 | r4 | r4 | |||
| 4 | r5 | r5 | r5 | r5 | |||
| 5 | r6 | r6 | r6 | r6 | |||
| 6 | s4 | s5 | 8 | 3 | |||
| 7 | r3 | r3 | r3 | r3 | |||
| 8 | s4 | s5 | r1 | 7 | |||
表的构建原则：
$ 状态标识匹配结束符(在LL(1)文法中，使用了 # 作为结束符，实际上两种方法均可作为结束符，只需要在题目中注明即可)sn 其中 n 为转移的目标状态3 即可s4. 在此产生式的最后既有满足条件的，又有不满足条件的时候
显然，前面的产生式为不满足条件的产生式，后面的产生式均为满足条件的产生式
若均满足下列条件，则认为可以通过 SLR 分析法处理，否则认为不可解若满足上述条件，则对于
ACTION列中的每一项 $a$
若 $a \in {a_1, a_2 \dots }$，则采用sn的标识方式，即
若 $a \in FOLLOW(B_i)$，则在所在列标注上rn，其中n指代第几号产生式，这条产生式为 $B_i \rightarrow \gamma_i$
rn 标注(若只有此条件的状态，则此时可以称文法为 LR(0) 文法)以 State 2 为例，有四个式子不满足条件，仅一个式子满足条件。其中 $S \rightarrow L.$ 为满足条件的式子，剩下四个均不满足条件。所以我们先求出 $S$ 的，满足等式
接着遍历所有ACTION内的符号，对于 $0$ 而言，其属于所以，写入s4
对于 $\$$ 而言，其属于 FOLLOW(S)，所以写上 $S \rightarrow L$ 这个产生对应的序号，即r2
略
即将上面的那些产生式带入实际的使用中
例如可以通过下面的文法来描述 C 语言的定义一个变量的过程
| 产生式 | 语义规则 |
|---|---|
| $S \rightarrow TL$ | L的类型为T |
| $T \rightarrow int$ | T为int |
| $T \rightarrow double$ | T为double |
| $L \rightarrow L, id$ | 创建一个新的，将其类型设置为相同的类型。并创建一个变量，其类型为的类型，名字为 |
| $L \rightarrow id$ | 创建一个变量，其类型为的类型，名字为 |
改为用属性来描述，则可以得到如下表格
| 产生式 | 语义规则 |
|---|---|
| $S \rightarrow TL$ | L.type = T.type |
| $T \rightarrow int$ | T.type = int |
| $T \rightarrow double$ | T.type = double |
| $L \rightarrow L, id$ | L(右).type = L.typeCreateVar(type = L.type, name = id.name) |
| $L \rightarrow id$ | CreateVar(type = L.type, name = id.name) |
对于一个产生式产生的语义规则中，如果产生式左部的属性是仅通过右部的属性得到的，则称此属性为综合属性。而如果产生式右部的属性是通过右部的属性或者左部的属性得到的，则称为继承属性
仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD
一个SDD是L-属性定义(L-SDD)，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假如存在一个产生式 $A \rightarrow X_1 X_2 X_3 \dots$，若存在一个 $X_i$，它的一个属性值与下面的有关
例如上面的图片即为 L-SDD
语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的CFG(上下文无关文法)
例如
嵌入规则如下
使用时，当在进行规约操作时，需要同时执行此程序片段
1 | |
(+, c, d, t1)(*, b, t1, t2)(+, t2, a, t3)(=, t3, , x)1 | |
(j>, a, b, 3)(j, , ,5)(j<, c, d, true)(j, , , 5)(j<, e, f, 7)(j, , , false)(jnz, g, , true)(j, , , false)1 | |
(j>, a, 0, 3)(j, , , 6)(+, x, 1, t1)(=, t1, , x)(j, , , 9)(-, x, 1, t2)(*, 4, t2, t3)(=, t3, , x)
为每个静态过程都逐段分配存储空间，每个过程的内存空间都相互独立且不相交
优点：处理上简单
缺点：对内存空间的使用不够经济合理
通过对过程间的调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间
将内存认为是一个栈空间
当一个过程被调用时，向栈中推入一个活动记录，当此过程结束时，该记录被弹出栈
用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树。在表示过程 p 的某个活动的结点上，其子结点对应于被 p的这次活动调用的各个过程的活动。按照这些活动被调用的顺序，自左向右地显示它们。一个子结点必须在其右兄弟结点的活动开始之前结束
暂略
暂略
暂略
暂略
划分方法：
例如对于代码
1 | |
可以划分出 6 个基本块
B1:
1 | |
B2:
1 | |
B3:
1 | |
B4:
1 | |
B5:
1 | |
B6:
1 | |
根据上面的基本块，再根据其转跳关系，可以绘制流图
graph LR
B1 --> B2
B2 --> B2
B2 --> B3
B3 --> B3
B3 --> B4
B4 --> B5
B4 --> B6
B5 --> B2
暂略
将基本块通过 DAG(有向无环图) 表示
例如对于代码
1 | |
可以绘制出如下的 DAG 图(通常在图上标注运算符号而不是字母，这里为了更容易理解标注了字母)
graph LR
b0((b)) --> a0((a))
c0((c)) --> a0((a))
b0((b)) --> b1((b))
d0((d)) --> b1((b))
c0((c)) --> c1((c))
d0((d)) --> c1((c))
c1((c)) --> e0((e))
b1((b)) --> e0((e))
若结果 e 是需要返回的值，即其他基本块需要使用的值，则通过 DAG 图可知，变量 a 是无用的，可以删除
得到新的图为
graph LR
b0((b)) --> b1((b))
d0((d)) --> b1((b))
c0((c)) --> c1((c))
d0((d)) --> c1((c))
c1((c)) --> e0((e))
b1((b)) --> e0((e))
所以可以得到优化后的代码为
1 | |
略
暂略
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。