当前位置：首页 > ds >正文

【编译原理】总结

ds 2025/5/13 23:04:00

核心

闭包，正则闭包

产生式（规则）

文法 G[S]=( $V_{N}$ ， $V_{T}$ ，P，S) 一组规则的集合

$V_{N}$ ：非终结符

$V_{T}$ ：终结符

P：产生式

S：开始符号

推导

归约

规范（最右）推导

规范（最左）归约

句型

句子

语言

仅含终结符号的句型是一个句子

语言是所有句子的集合

短语

简单（直接）短语

句柄

任意句型的最左简单（直接）短语为句柄

根据语法树，短语--子树，简单短语----只有父子两代的子树

正则文法与状态转换图

右线性文法

左线性文法（归约）

正规式

DFA

M=(S, $\sum$ ,f,S0,F)

S0：唯一的初始状态

f：从 $S\times \sum$ 到S的单值部分映射

F：终止状态集合

NFA

M=(S, $\sum$ ,f,S0,F)

S0：非空的初始状态集

f：从 $S\times \sum^{*}$ 到 $2^{S}$ 的子集的映像

正规式R与NFA

NFA->正规式

确定的自上而下分析

LL(1)文法的条件

文法不含左递归
对文法中每个非终结符的各个产生式的候选首符号集两两不相交
对文法中每一个非终结符，若存在某个候选首符号集包含 $\varepsilon$ ，则 $FIRST(A)\cap FOLLOW(A)=\Phi$

消除左递归

（1）直接左递归

$\textbf{P}\rightarrow \textbf{P}\alpha |\beta \\ P\rightarrow \beta \textbf{P'} \\ \textbf{P'} \rightarrow \alpha \textbf{P'} | \varepsilon$

（2）间接左递归

消除文法中全部左递归算法（前提：文法不含回路）

把文法中非终结符，按某种顺序进行排列（顺序任意）
对每个非终结符用排在它前面的其他非终结符的产生式表示出来，并消除产生式中的左递归
化简所得文法，即去掉多余产生式

FISRT集

FOLLOW集

根据所给语言，构造文法

构造一右线性文法，与如下文法等价：先写语言，状态转换图，右线性文法

NFA->DFA 子集构造法

$\varepsilon -closure(I)$ $move(I,\alpha )$

$I_{\alpha }=\varepsilon -closure(move(I,\alpha ))$

NFA确定化

DFA最小化划分

正规式R与NFA（构造正规式R的DFA）

消除直接左递归

$\textbf{P}\rightarrow \textbf{P}\alpha |\beta \\ P\rightarrow \beta \textbf{P'} \\ \textbf{P'} \rightarrow \alpha \textbf{P'} | \varepsilon$

基本知识点

【编译原理】一二章-CSDN博客

【编译原理】第三章词法分析-CSDN博客

【编译原理】第四章自上而下语法分析-CSDN博客

【编译原理】第五章自下而上语法分析-CSDN博客

课后题

【编译原理】第四章习题-CSDN博客

【编译原理】第三章习题_(1) {0,1}上的含有子串010的所有串;-CSDN博客

练习

求FIRST集、FOLLOW集，判断是否为LL(1)文法，构造LL(1)分析表

FIRST集：

E: {'(', 'i'}

E': {+, -, ε}

T: {'(', 'i'}

T': {'*', '/', ε}

F: {'(', 'i'}

A: {+, -}

M: {*, /}

FOLLOW集：

E: {$, )}

E': {$, )}

T: {+, -, $, )}

T': {+, -, $, )}

F: {*, /, +, -, $, )}

A: {'(', 'i'}

M: {'(', 'i'}

该文法是LL(1)文法，因为所有产生式的FIRST集不相交，且对于可以推导出ε的产生式，其FIRST和FOLLOW集无交集

非终结符	+	-	*	/	(	)	i	$
E					E→TE'		E→TE'
E'	E'→ATE'	E'→ATE'				E'→ε		E'→ε
T					T→FT'		T→FT'
T'	T'→ε	T'→ε	T'→MFT'	T'→MFT'		T'→ε		T'→ε
F					F→(E)		F→i
A	A→+	A→-
M			M→*	M→/

LL(1)分析器是一种自顶向下的语法分析器，使用一个分析栈和输入缓冲区来进行分析。其工作原理如下：

1. 初始化时，栈底放置结束符$，然后将开始符号压入栈顶。输入缓冲区存放待分析的字符串，末尾加上$。

2. 不断从栈顶取出符号X：

a. 如果X是终结符，检查是否与当前输入符号匹配。如果匹配，弹出X并消耗输入符号；否则报错。

b. 如果X是非终结符，查找分析表M[X, a]（a是当前输入符号），若表中有产生式X→α，将X弹出，将α逆序压入栈中；若表中无条目，报错。

3. 重复步骤2，直到栈中只剩下$，输入缓冲区也只剩下$，此时接受输入字符串；否则报错。

LL(1)分析器通过预测产生式来展开非终结符，每一步都根据当前栈顶符号和输入符号选择正确的产生式，因此要求文法满足LL(1)条件，即分析表每个条目至多有一个产生式，避免冲突。