编译原理听课笔记

发表于 更新于 分类于 ， 阅读次数：

文法：$G=(V,T,G,S)$，非终结符号$V$，终结符号$T$，产生式集$G$，开始符号集$S$.

句型：由文法开始符号可以经过若干步推导得到的文法符号串$\alpha$。
$$
\forall \alpha \in (V \cup T)^* \and S \xrightarrow{*} \alpha
$$
句子：由文法开始符号可以经过若干步推导得到的终结符号串$\omega$。

句型和句子区别：句子不含语法变量，句型可能含有语法变量。

语言：句子的集合。

BNF范式：一种书写产生式的格式。

2.4 文法的分类

若文法$G$满足文法定义的要求，则$G$是0型文法，$L(G)$为PSL（短语结构语言）。

0型文法（无限制文法）：对每个产生式$\alpha \rightarrow \beta$，都满足$\alpha \in (V \cup T)^*$且$a$含有至少一个非终结符号，且$\beta \in (V \cup T)^*$。能力相当于图灵机，计算机能处理的所有东西。

1型文法（上下文有关文法CSG）：在0型文法的基础上，每一个产生式$\alpha \rightarrow \beta$，都有长度$|\alpha| \le |\beta|$。线性界限自动机。

2型文法（上下文无关文法CFG）：在1型文法的基础上，每一个产生式$\alpha \rightarrow \beta$，$\alpha$只为一个非终结符。识别系统：不确定的下推自动机。

3型文法（正则文法RG）：必须满足左线性和右线性其中一个。有穷自动机。

非上下文无关语言结构

$$
L={a^nb^nc^n|n>0}
$$

不存在CFG，使$L(G)=L$。
$$
L={wcw|w\in {a,b}^+}
$$
抽象，变量先声明后引用。
$$
L_2={a^nb^mc^nd^m|n,m\ge 0}
$$
数量对应，上下文有关。

2.5 CFG的语法树

语法树

短语：一棵语法分析树子树的叶子自左向右排列形成一个相对于子树根的短语。

直接短语：只有父子两代的一棵子树。

句柄：一棵语法分析树最左那棵只有父子两代的子树。

2.6 CFG的二义性

解决方法：运算符号的优先级

第三章 词法分析

3.2.2 正则表达式

  • |表示或
  • *表示kleene闭包
  • +表示正闭包
  • ?表示0或1个

正规语言定义递归给出。

正则表达式与正则文法等价：给定任意正则文法，存在一个定义同一语言的正则表达式。

P8，23”18’例题：根据正则文法构造等价正则表达式，构造方程，解联立方程组，替换。

给定正则表达式r转换为正则文法G，使L(G)=L(r)：27”19’

3.2.4 有穷自动机DFA

定义3.4：确定性有穷自动机$M$是一个五元组$M=(Q,\Sigma,\delta,q_0,F)$。

  • $Q$是一个有穷状态集合
  • $\Sigma$字母表，他的每个元素称为输入符号
  • $\delta$是一个从$Q \times \Sigma$到$Q$的单值映射，$\delta(p,a)=q$表示状态为$p$读到$a$时转换到$q$状态
  • $q_0 \in Q$，称为初始状态
  • $F \in Q$，为终止状态集合

选用转移矩阵，因为易存储。

第四章 自顶向下语法分析

4.1 语法分析概述

检查语法分析器输出的单词序列是否是原语言中的句子，激是否符合语法规则

  • 自顶向下，从文法产生语言的角度。从根开始构造语法树
    • 递归子程序法
    • 预测分析法（LL(1)）
  • 自底向上，从自动机识别语言的角度
    • 算符优先分析法
    • LR(0)、SLR(1)、LR(1)、LALR(1)

4.2 自顶向下语法分析面临问题与文法改造

自顶向下基本思想

  • 从文法开始符号出发，寻求所给输入串的一个最左推导
  • 从树根S开始，构造所给输入符号的语法树

1. 二义性问题

文法$G$，若$L(G)$存在一颗具有两棵及以上分析树（最左推导）的句子，则称$G$是二义的。无法确定采用哪个最左推导。

解决办法：改造文法，引入新的文法变量。

消除左递归

提取左因子

2. 回溯问题

有多个候选式存在多个公共后缀，只能试探，不成功则回退。

3. 左递归引起无穷循环问题

语法存在推导$A \xrightarrow{*}\alpha A \beta$，则称$G$是递归的，当$\alpha = \varepsilon$称为左递归。若至少需要两步，称为间接递归，否则称为直接递归。

解决办法：直接左递归：写成右递归。

4.2.3 LL(1)文法

  1. 首终结符号：符号串的第一个符号，并且是终结符号。

从$A$推导出的首符号集$FIRST(A)= { \alpha|A\xrightarrow{}\alpha\beta,\alpha \in T, \beta \in (V \cup T)^ }$.

  1. 若$\alpha \xrightarrow{*}\varepsilon$，则$\varepsilon \in FIRST(\alpha)$

  2. 可以用$FIRST$集判断一个文法是否可以做确定的自顶向下分析。

第五章 自底向上语法分析

实际：归约

重点：LR分析器基本思想，LR(0)分析表构造，SLR(1)分析表构造，LR(1)分析表构造

难点：

自底向上语法分析概述

思想：利用产生式对输入串归约，若得到开始符号则合法。

核心：寻找句型中的归约对象——“句柄”

流程：从左到右扫描串并依次放入栈，若栈顶是产生式则不断规约，最后得到开始符号。

分析器四种动作

  1. 移进：将下一输入符号移入栈
  2. 归约：用产生式左侧非终结符替换栈顶句柄
  3. 接受：分析成功
  4. 出错：出错处理

移进-归约分析中的问题

  • 问题1，如何确定句柄
  • 问题2，确定优先级$E+E*E$

移进-归约冲突

$E+EE$即可移进$$又可归约

归约-归约冲突

存在两个可用的产生式

5.1.2 优先法

根绝归约先后次序为句型中相邻的文法符号规定优先关系

5.1.3 状态法

规矩当前分析状态确定句柄的头和尾，进行正确归约

5.2 算符优先分析法

构造优先级

image-20201211214601938

之后的跳了，直接看的LR分析法……

5.3 LR分析法，P16-34

LR(k)分析法可分析LR(k)文法产生的语言

L：从左向右扫描输入

R：最右推导对应最左规约

k：超前读入k个符号，以确定规约产生式

LR分析表

$s_n$：移进，并将状态$n$压入栈

$r_n$：用第$n$个产生式进行归约

构造LR分析表，P18

SLR(0)分析表的构造，P18-40

后面的跳了，看语法制导

语法制导翻译 P20-15·

语法分析器主要任务：检查语法结构的静态语义，称为静态语义分析或静态检查。

语法制导翻译：将静态检查和中间代码生成结合到语法分析中。