编译原理笔记，词法语法分析

词法分析

有穷自动机 DFA

$f: K \times \sum \to K$是一个单值函数，任何输入符号都唯一的确定了下一个状态

不确定的有穷自动机 NFA

至少一个初态节点，若干个终态节点 DFA是NFA的特例

子集法 NFA转换为DFA

对于状态集合$I$，定义两个运算

1. 集合$I$的$\epsilon-Closure(I)$，是一个状态集$I$中的任何状态经过任意条$\epsilon$弧能到达的状态集合 因为当输入符号为空时，则自动机停留在原来的位置上，所以有关系$\forall S \in I \ \ , S \in \epsilon-Closure(I)$

2. 状态集合$I$的$a$弧转换，表示为$move(I,a)$，定义为状态集合J，其中$J$是所有那些可以从$I$中的某一状态经过一条$a$弧而到达的状态的全体 有关系$\forall S_i \in I \ \ , move(I,a)=f(S_1,a)\bigcup f(S_2,a) \bigcup f(S_3,a)…$ 算法流程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

let C as a set save Status-Set
let K_0 = epsilon-Closure(0)
C <- epsilon-Closure(K_0)
while(if C have set not visit) {
	visit[T] = true
	for a in Char Set {
		U := epsilon-Closure(Move(T,a))
		if (U not in C) {
			C <- U
		}
	}
}

经过状态重新命名可以得到DFA

DFA的化简

化简 的DFA：没有多余状态，没有两个状态是互相等价的。 DFA可以通过消除无用状态和合并等价状态二转换成一个与之等价的最小状态的DFA

无用状态：从开始状态触发，任何输入串都无法到达 或者从这个状态没有通路到达终态 ![[Pasted image 20211230203930.png]] 如s4，s6，s8，可以直接消除

DFA中的状态等价条件：

1. 一致性条件-状态s和t必须同时为可接受状态或不可接受状态
2. 蔓延性条件-对于所有输入符号，状态s和t必须转换到等价的状态

分割法分解DFA状态： 步骤：

1. 先将终态和非终态分割，作为两个子集，作为一个划分
2. 在划分中对每个子集加上可输入字符，将可区别的状态拆分，得到新的划分
3. 重复直到划分不可以再分割

化简后的DFA便于在计算机上实现

由DFA化简为正规式

很简单 缩缩缩

由正规式生成NFA

$L(G)$表示文法G产生的语言的集合 $L(G1) = L(G2)$ 则两个文法等价 反正就是构造一个等价的$\mathbb{NFA}$

语法制导

按照语法结构构造 将正规式分解为子表达式   闭包：终态输入epsilon到达初态 分解方式不唯一 可以从头开始，也可以分部进行

处理步骤：

• 如$r_1 r_2$，顺序拼接两个NFA
• 如$r1^*$处理闭包，终态输入epsilon链接到初态
• 如$r_1|r_2$，由初态输入epsilon到两个NFA，由两个NFA输入epsilon到达终态

语法分析

自顶向下

文法特点：

1. 每个产生式右部都由终结符号开始
2. 若两个产生式都由相同的左部，右部都由不同的终结符开始 分析过程是唯一的

FIRST集 $FIRST(\alpha)={以\alpha为左部的，产生式右部的第一个非终结符集合}$ 为a的开始符号集

FOLLOW集 对于上下文无关文法，S是开始符号 $FOLLOW(A)={状态A后跟符号}$ 若A可以引导终止epsilon ，则加入#到FOLLOW集

构造算法

对文法中每一非终结符A，构造FOLLOW(A)的算法如下：反复使用如下规则，直至FOLLOW集不再增大为止。 ⑴若A是文法的开始符号,则把输入结束符＃加入FOLLOW(A)中； ⑵若B→αAaβ,a是终结符,则把a加入FOLLOW(A)中； ⑶若B→αAXβ,X是非终结符,则把FIRST(Xβ)加入FOLLOW(A)中； ⑷若B→αA或B→αAβ,且β可以推导至ε，则把FOLLOW(B)加入FOLLOW(A)中。

SELECT集 $SELECT(A \to a)=(FIRST(a)-{\epsilon})\bigcup FOLLOW(A)$

LL(1)文法：第一个L表示自顶向下分析是从左到右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需要向右看一个符号便可以决定如何推导。 充要条件: 对于每个非终结符A，的两个不同产生式 $SELECT(A \to \alpha)\bigcap SELECT(A \to \beta)=\varnothing$

非LL(1)文法到LL(1)文法的等价转换

LL(1)文法的性质： ① LL(1)文法是无二义性的； ② LL(1)文法不含左递归； ③ LL(1)文法没有公共左因子。

消除左递归 消除回溯：提取左公因子 改造成LL1文法

消除直接左递归：

例如： A→Aα|β 对A引入一个新的非终结符A′，把上式改写为： A →βA′
A′→αA′|ε 例2： E→E +T | T T→T * F | F F→i |（E） 改造为 E→TE′ E′→+T E′|ε T→FT ′ T′→* FT′|ε F→i |（E）

消除间接左递归

把式子带入，然后按照消除直接左递归的方法去消除 S → Aα|β ⑴ A → Sγ ⑵ 得到 S → Sγα|β ⑶ 消除左递归 S → βS′ S ′→γαS′|ε