编译原理复习笔记

本篇复习笔记对应的课本是《编译原理》蒋立源
参考了老师的PPT，以及总结了课后习题和考试题

🌱1. 绪论

🍀1.1 程序的翻译

🎯高级语言和低级语言

• 低级语言(Low level Language)
  • 字位码、机器语言、汇编语言
  • 特点:与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错
• 高级语言
  • Fortran、Pascal、C语言等
  • 特点:不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。

🎯翻译流程

一般这种翻译工作有二种途径

1. 编译： 编译程序，汇编程序
2. 解释: 解释程序

🎯 源程序，目标程序，翻译程序

三者的概念：

• 源程序
  用汇编语言或高级语言编写的程序称为源程序
• 目标程序
  用目标语言所表示的程序
  目标语言:可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。
• 翻译程序
  将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。

三者的关系：

即源程序是翻译程序的输入，目标程序是翻译程序的输出。

🎯 翻译程序, 汇编程序, 解释程序

• 编译程序
  如果翻译程序的源语言是高级语言，目标语言是低级语言(机器语言或汇编语言)，这种翻译程序称为编译程序(Compile)。
• 汇编程序
  如果翻译程序的源语言是汇编语言，目标语言是机器语言，这种翻译程序称为汇编程序(Assemble) 。
• 解释程序
  按源程序的动态顺序逐句地进行分析解释并执行直至结束。
  解释程序边翻译边执行，不生成目标程序。交互式的工作方式，便于调试,但执行效率低，执行时也要解释。
  编译程序生成目标程序,链接形成可执行文件运行，所有翻译工作在运行之前完成。执行效率高。

汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。

• 编译程序是一个与源语言和计算机有关的概念。
  不同的源语言有不同的编译程序
  同一种源语言可以有不同的编译程序(高级语言或汇编语言书写)
• 源程序的执行分为两个阶段:
  编译阶段和运行阶段
• 如果编译阶段生成的目标程序不是机器代码程序,而是汇编程序,源程序的执行则分三个阶段: 编译阶段、汇编阶段和运行阶段.

🎯 源程序的编译和运行

• 编译或汇编阶段
  
• 运行阶段
  
• 解释程序的工作过程
  解释程序(Interpreter)：(类似于口译，不生成目标代码)对源程序进行解释执行的程序。
  特点:与编译系统比较，解释系统较简单、可移植性好，易于查错，但速度慢
  
• 编译解释系统
  
  例如java语言
  

🍀1.2 编译程序的组成

🎯 编译过程

• 编译过程的定义
  将高级语言程序翻译为等价的目标程序的过程。
• 翻译和编译工作的比较
  
• 编译过程的划分
  
  1?? 词法分析
  任务:根据词法规则分析和识别单词
  
  2?? 语法分析
  任务:根据语法规则(即语言的文法)，分析并识别出各种语法成分(如表达式、语句、函数等），并进行语法正确性检查。
  
  3?? 语义分析及中间代码的生成
  任务:依据语义规则对识别出的各种语法成份分析其含义，并进行初步翻译，生成中间代码。
  静态:分析语法成份的含义，进行语义上的正确性检查
  动态:根据相应语义，生成中间代码(介于源语言和目标语言之间的中间语言形式)
  生成中间代码的目的：利于代码优化;利于目标代码的移植
  
  4?? 代码优化
  任务:对中间代码进行加工变换，以得到高质量的目标代码
  
  5?? 目标代码的生成
  任务:把中间代码变换成特定机器上的低级语言代码
  
• 总结
  

🎯 编译过程的逻辑结构

• 每个阶段中都要有∶符号表管理和错误检查处理
  符号表管理
  填表:把源程序中的信息和编译过程中所产生的信息登记在表格中
  查表:在随后的编译过程中同时又要不断的查找这些表格中的信息
  错误处理
  诊察错误，并能报告用户错误性质和位置
  出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。
  
• 编译程序的前端和后端
  
  

🌺1.3 习题

1-1. 什么是源程序、目标程序、编译程序和解释程序？编译程序和解释程序的区别是什么？

解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。

🌱2. 上下文无关文法和语言

🍀2.1 文法和语言的表示

🎯 语言定义的方法
语言的定义可采用下列三种方法

1. 枚举法——把该语言的所有句子列出放在一集合内。(有限个句子时)
2. 有限条规则———描述语言的全部句子。
   (有限或无限个句子)，即文法表示
3. 装置———检验和识别句子。(有限或无限个句子）即自动机

🍀2.2 文法和语言的定义

🎯基本概念和术语

• 字母表:元素的非空有穷集合，元素称符号
  例: ∑ = { 0 , 1 } \sum=\{\mathbf{0}, \mathbf{1}\} ∑={0,1}

• 符号串:字母表中的符号所组成的任何有穷序列
  特别：空符号串 $\epsilon$(不包含任何符号)

• 字母表 $\sum$ 上的符号串的递归定义
  (1) $\epsilon$ 是 $\sum$ 上的符号串
  (2) 若 $x$ 是 $\sum$ 上的符号串, 且 $a\in \sum$, 则xa或 $ax$ 是 $\sum$ 上的符号串
  特别: $\mathbf{\epsilon }\mathbf{x}=\mathbf{x}\mathbf{\epsilon }=\mathbf{x}$
  (3) 若 $y$ 是 $\sum$ 上的符号串,
  当且仅当 $y$ 可由 (1) 和 (2) 产生
  问题：符号串是又穷的序列，但是根据这个递归定义来看，应该是无穷的呀？
  

• 符号串的前缀、后缀和子串
  前缀: 设x是一符号串，从x的尾部删去若干个(包括0个)符号之后所剩余下的部分称为x的前缀;若x的前缀不是x本身，则称为x的真前缀。
  后缀:设x是一符号串，从x的头部删去若干个(包括0个)符号之后所剩余下的部分称为x的后缀;若x的后缀不是x本身，则称为x的真后缀。
  子串:从一个符号串中删去它的一个前缀和一个后缀之后所剩下的部分称为此符号串的子串。
  若x的子串不是x本身,则称为x的真子串
  

• 符号串的长度: 符号串所含符号的个数

• 符号串的连接和方幂:
  连接: 设有符号串x, y，把y的符号写在x的符号之后所得的符号串,叫做x与y的连接，记xy
  方幂:设有符号串x，则x的n次自身连接称为x的
  n次方幂,记为x"
  特别的$x^0=\epsilon$

• 符号串集合 $\mathbf{A}$ 与 $\mathbf{B}$ 的和与积:
  和: A + B = { w ∣ w ∈ A \mathbf{A}+\mathbf{B}=\{\mathbf{w} \mid \mathbf{w} \in \mathbf{A} A+B={w∣w∈A 或 $\mathbf{w}\in \mathbf{B}\}$
  积: A B = { x y ∣ x ∈ A \mathbf{A B}=\{\mathbf{x y} \mid \mathbf{x} \in \mathbf{A} AB={xy∣x∈A 且 $\mathbf{y}\in \mathbf{B}\}$

• 符号串集合的方幂：
  设有符号串集合 $\mathbf{A}$
  则定义 A 0 = { ε } A^{0}=\{\varepsilon\} A0={ε}
  ${\mathbf{A}}^{\mathbf{l}}=\mathbf{A}$
  ${\mathbf{A}}^2=\mathbf{A}\mathbf{A}$
  ${\mathbf{A}}^{\mathbf{n}=\underset{\text{n个?}}{\underbrace{\mathbf{A}\mathbf{A}\dots ...\mathbf{A}}}}$

• 符号串(符号）集合的正闭包
  设 $\mathrm{A}$ 为堑号集合, 则定义 $\mathrm{A}$ 的正闭包 ${\mathrm{A}}^{+}$为:
  ${\mathbf{A}}^{+}={\mathbf{A}}^1\cup {\mathbf{A}}^2\cup {\mathbf{A}}^3\cup \dots \dots .{\mathbf{A}}^{\mathbf{n}}\cup \dots \dots$
  例: 设 A = { b , c } \mathbf{A}=\{\mathbf{b}, \mathbf{c}\} A={b,c}
  贝刂 A + = { b , c } ∪ { b b , b c , c b , c c } ∪ … … \mathbf{A}^{+}=\{\mathbf{b}, \mathbf{c}\} \cup\{\mathbf{b b}, \mathbf{b c}, \mathbf{c b}, \mathbf{c c}\} \cup \ldots \ldots A+={b,c}∪{bb,bc,cb,cc}∪……
  = { b , c , b b , b c , c b , c c , b b b , b b c , b c b , b c c , c b b , b c b , c c b , c c c =\{\mathbf{b}, \mathbf{c}, \mathbf{b b}, \mathbf{b c}, \mathbf{c b}, \mathbf{c c}, \mathbf{b b b}, \mathbf{b b c}, \mathbf{b c b}, \mathbf{b c c},\mathbf{cbb},\mathbf{b c b},\mathbf{ccb},\mathbf{c c c} ={b,c,bb,bc,cb,cc,bbb,bbc,bcb,bcc,cbb,bcb,ccb,ccc…}
  $A^{+}$是由A中的元素构成的符号串(除$\epsilon$)的集合

• 符号串(等号）集合的闭包 $A^{?}$
  设 $\mathrm{A}$ 为等号集合, 则定义 $\mathbf{A}$ 的闭包 ${\mathbf{A}}^{?}$ 为:
  A ? = A 0 ∪ A + = { ε } ∪ A + \mathbf{A}^{*}=\mathbf{A}^{0} \cup \mathbf{A}^{+}=\{\varepsilon\} \cup \mathbf{A}^{+} A?=A0∪A+={ε}∪A+
  A*由A中的元素构成的所有符号串的集合

🎯 文法和语言的形式定义

• 文法的形式定义
  有穷语言：逐一列举句子
  无穷语言：文法是以有穷的集合刻画无穷集合的工具
  文法 是对语言结构的定义和描述 （或称“语法”）
  注意：从一组规则可以推导出不同的句子，文法是在形式上对句子结构的定义和描述，而未涉及语义问题

• 规则,产生式
  一有序对$(U,x)$记为$U::=X或U>x$
  规则的左部:U是符号(有的文法也可为符号串)
  规则的右部:x是有穷符号串
  表示:U定义为x

• 文法 G[Z]
  规则的非空有穷集合
  Z:开始符号(识别符号) ，至少在一条规则的左部出现。

• 字汇表V：规则左右部中所有符号组成的集合
  非终结符号:需要定义的语法范畴，组成非终结符号集合$V_n$
  终结符号:规则中不属于$v_n$，的符号,组成终结符号集合$V_t$

非终结符号以< >括起,但当是大写字母是时常省略
$V=V_{n}U{V}_t$

• 文法的四元组表示
  $G=(V_n,V_t,P,Z)$
  其中
  Vn : 非终结符号集
  V: 终结符号集
  P:规则的集合
  Z:文法的开始符号
• 文法的BNF(巴斯科范式)表示
  规则中有相同的左部时：
  V→ x
  V → y
  …
  V → z
  写成：V →x|y|…|z （’|’表达‘或’）
• 元符号
  → ( ::= ） ， | < >
• 元语言元符号处理的语言
  由元符号组成的巴科斯范式(元语言公式)是用以描述算法语言的元语言

🎯 推导形式的定义

• 直接推导
  如果U→u是G中的一条规则,$\mathbf{x},\mathbf{y}\in {\mathbf{V}}^{?}$
  则将规则U→u用于符号串r=xUy上得到符号串w =xuy
  记为: xUy => xuy (r=>w) ; 称符号串w是符号串r的直接推导,或符号串 r直接产生了符号串w,也称w直接归约到r.
  
• 推导（长度为n）
  设u0,u1,…un(n>0)均∈V*,且有
  r=u0=>u1=>……=>u n-1=>un=w
  记为r =+>w (一步或一步以上）
  则称以上序列为长度n的推导,
  也称r产生w(w归约为r)
  特例: r=w(0步推导)

🎯 语言形式的定义

• 句型
  设有文法G[Z],如果有Z=*>x , x ∈V*, 则称x是文法G的一个句型。
  凡是由识别符号推导出来的字汇表V上的终结和非终结符号组成的符号串叫做句型
  

• 句子
  如有Z=+>x , x∈Vt*, 则称x是文法G的一个句子.
  由Z推导的终结符号组成的符号串为句子。

• 语言L(G[Z])
  文法G[Z]产生的所有句子的集合。, 称文法G[Z]所定义的语 L(G[Z])={x|x∈Vt*且Z=+>x}
  
  
  

🎯 递归规则和递归文法

• 递归规则
  形如U→xUy U∈Vn, x,y∈V*
  左右具有相同的非终结符号的规则
  特别:U→Uy (x=ε)左递归规则
  U→xU (y=ε)右递归规则
  U→xUy (x,y≠ε)自嵌入递归规则
  递归规则是对其左部的非终结符号进行递归定义

• 文法的递归性
  1)直接递归性:文法中至少包含一条递归规则
  2)间接递归性:文法的任一非终结符号经一步
  以上推导产生的递归性。
  3)文法的递归性原则:文法具有直接递归性或
  间接递归性,否则,文法无递归性。
  
  

🍀2.3 句型的分析

🎯规范推导和规约 (🔥 重要概念)

• 最左(右)推导
  在任一步推导V=>w中，都是对符号串V的最左(右）非终结符号进行替换,称最左（右）推导。

• 规范推导
  即最右推导。

• 规范句型
  由规范推导所得的句型.。

• 规范归约
  规范推导的逆过程，称规范归约或最左归约。
  
  

🎯 短语、简单短语和句柄 (🔥 重要概念)

• 短语:文法G[Z], ω =xuy是一句型,x,y∈V*， 如有 Z=*>xUy,且U=+>u., U∈Vn, u ∈V+ ，称u是一个相对于非终结符号U句型ω的短语.
• 简单短语:文法G[Z], ω =xuy是一句型, 如有 Z=*>xUy,且U=>u,U∈Vn, u ∈V+ ，称u是一个相对于非终结符号U句型ω的简单短语
• 句柄:句型最左边的简单短语为该句型的句柄

短语或简单短语必须是针对某一句型来说的， 并且是该句型的一个子串.
短语或简单短语必须是相对某一非终结符号的.
两个条件缺一不可.
一句型可以有几个短语和简单短语.
一句型只有一个句柄(无二义性的文法)。
最左归约归约的是当前句型的句柄

🎯 语法树

• 语法树（Syntax Tree）—— 描述一个句型或句子的语法结构
  树：若干个结点组成的有限集
  
  m—— 结点n的直接前驱或父结点
  n—— 结点m的直接后继或子结点
  根—— 仅有的一个没有任何前驱的结点
  树—— 无回路性和连通性

几个结论:
1、对每个语法树,至少存在一个推导过程
2、对于每个推导,都有一个相应的语法树(但不同的推导可能有相同的语法树）。
3、树的末端结点形成所要推导的句型。但这个句型也可能对应两棵不同的语法树，这就是文法的二义性问题.

• 语法树和子树
  根:开始符号
  子树:某一非终结符号(子树的根)及其下面的分支
  叶:树的末端结点
  语法树的全部末端结点（自左向右）形成当前句型
  
  🎯 子树与短语、句柄 (🔥 重要概念)
  短语:子树的末端结点形成的符号串.
  这个短语相对的句型:整个树的末端结点.
  非终结符号:子树的根
  简单子树:只有一层分支的子树
  简单短语:简单子树的末端结点形成的符号串
  句柄:最左简单子树的末端结点形成的符号串
  规约:语法树由下向上生长, 通过规则替换到达开始符号的过程。

一个句型最左归约所归约的是当前句型的句柄。
这个过程非常重要，因为源程序都是符号串形式的，这就需要把它归约为开始符号才算正确。
最左归约关键是找当前句型的句柄,这个问题,到语法分析时再着重讲解。
二义性文法最左归约的句柄的不唯一性。

🎯 文法的二义性

• 文法二义性的判定
  如果文法G的某一个句子存在两棵或两棵以上不同的语法树，则称句子是二义性的.
  如果一文法含有二义性的句子，则称该文法是二义性的，否则该文法是无二义性的.
  
  特别注意：
  ①文法的二义性：
  某一句子有二个不同的最左（右）推导
  或二个不同的最左（规范）归约
  ②文法的二义性是不可判定的：不存在一种算法，只能用一些简单条件来判定
  ③特例：若一文法G既含左递归又含右递归，则G必是二义性文法.(是经验)

🎯 文法二义性的消除

• 不改变文法中的原有规则，仅加入一些语法的非形式规定
  
• 构造一个等价的无二义性文法，把排除的二义性规则合并到原文法中（增加新的非终结符）
  
  特别说明： 文法的二义性不等同于语言的二义性

1. 通常我们说文法的二义性，而不说语言的二义性，因为有两个文法G1和G2，其中一个是二义性，另一个无二义性，但却有L(G1)=L(G2)，即两个文法所产生的语言是相同的；
2. 语言的二义性指的是它不存在无二义性的文法，通称为先天二义性的语言。

🍀2.4 文法的实用限制和其他表示方法

🎯文法的实用限制

• 不含无用产生式
  设G=（Vn，Vt，P，S）是一文法，G中的符号
  x∈Vn∪Vt是有用的，则 x 必满足
  ①存在α、β∈V*，有S=*> αxβ （无用：不可到达）
  ②存在ω∈Vt* 使αxβ=*> ω （无用：不可终止）
  称符号x是有用的，否则是无用的
  无用产生式: 产生式的左部或右部含有无用符号。
  
• 不含有害规则
  形如 U→U 的规则 (原因: ①不必要②引起二义性)
  

🎯 ε-产生式的消除 (🔥 常考题型)
如某L(G)中不含ε,可消除G中的全部ε产生式;
如某L(G)中含ε,肯定不能消除G中的全部ε产生式;

消除步骤:
1.算法2.3,找出G中满足A=*>ε的所有A,构成集合W;
2.算法2.4,若ε不属于L(G),构造不含ε产生式的等价文法G’;
算法2.５,若ε属于L(G),构造仅含S① →ε产生式的等价文法G1(S① );

• 算法2.3
  
• 算法2.4
  
  
• 算法2.5
  
  

🎯 文法的其他表示方法

• 扩充的BNF表示
  BNF:元符号 < , > , ::=(→), ∣
  扩充的BNF(EBNF): < , > , ::=(→), ∣, ( , ) ,{,},[,]
  
  
  
  
  
  🎯 语法图
  
  

🍀2.5 文法和语言的Chomsky分类

文法是一个四元组G=（Vn，Vt，P，Z）
乔姆斯基根据文法中产生式的不同，将文法分为四类,每一种文法对应一种语言。

• 0型文法
  文法G中规则呈
  α→β α∈V+，β∈V*
  也称短语结构文法（phrase structure grammar, PSG）,确定的语言为0型语言L0（说明： 对产生式基本无限制）
  0型文法的能力相当于图灵机，可以表征任何递归可枚举集，且任何0型语言都是递归可枚举的

• 1型文法
  ${\alpha }_{1}A{\alpha }_2\to {\alpha }_1\beta {\alpha }_2$ α1，α2∈V*，A∈Vn，β∈V+
  也称上下文有关文法(context-sensitive grammar, CSG)。
  确定的语言为1型语言L1,也称上下文有关语言。
  等价定义： 对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外(α, β ∈V+)。
  例如：aUb→aABBaab

• 2型文法：
  文法G中规则呈：
  A→β A∈Vn，β∈V+
  也称上下文无关文法（context-free grammar，CFG)。非确定的下推自动机识别
  确定的语言为2型语言L2或上下文无关语言。
  该文法相当于对1型文法中的规则形式加以限制，即 要求α1和α2必须为空。
  在语法分析中用于描述语法类
  例：文法G[S]：S→AB A→BS|0 B→SA|1

• 3型文法
  文法G中规则呈：
  A→aB或A→a A、Ｂ∈Vn, a∈Vt,
  称G为右线形正则文法。
  A→Ba或A→a A、Ｂ∈Vn, a∈Vt,
  称G为左线形正则文法。
  以上两者统称为3型文法或正规文法，确定的语言为3型语言L3或正规（正则）语言。
  正则语言可用有限自动机来识别。
  在词法分析中用于描述单词符号
  
  四类文法之间的逐级“包含”关系
  

说明:
①由于对规则的限制逐渐增加,
因此L0、L1 、 L2 、 L3的语言范围逐渐减小。
②一个文法是正则的,必然是上下文无关的，上下文无关文法有足够的能力描述程序设计语言的语法结构。
③本课主要讨论正则文法和上下文无关文法。

🌺 2.6 习题

设有字母表 A 1 = { a , b , ? ? , z } , A 2 = { 0 , 1 , ? ? , 9 } \mathrm{A}_{1}=\{\mathrm{a}, \mathrm{b}, \cdots, \mathrm{z}\}, \mathrm{A}_{2}=\{0,1, \cdots, 9\} A1?={a,b,?,z},A2?={0,1,?,9}, 试回答下列问题：
(1) 字母表 ${\mathrm{A}}_1$ 上长度为 2 的符号串有多少个?
(2) 集合 ${\mathrm{A}}_1{\mathrm{A}}_2$ 含有多少个元素?
(3) 列出集合 ${\mathrm{A}}_1{\left({\mathrm{A}}_1\cup {\mathrm{A}}_2\right)}^{?}$ 中的全部长度不大于 3 的符号串。

(1) 答: $26^{?}26=676$
(2) 答: $26^{?}10=260$
(3) 答: { a , b , c , … , Z , a 0 , a 1 , … , a 9 , a a , … , a z , … , z Z , a 00 , a 01 , … , Z Z Z } \{\mathrm{a}, \mathrm{b}, \mathrm{c}, \ldots, \mathrm{Z}, \mathrm{a} 0, \mathrm{a} 1, \ldots, \mathrm{a} 9, \mathrm{aa}, \ldots, \mathrm{az}, \ldots, \mathrm{zZ}, \mathrm{a} 00, \mathrm{a} 01, \ldots, \mathrm{ZZZ}\} {a,b,c,…,Z,a0,a1,…,a9,aa,…,az,…,zZ,a00,a01,…,ZZZ}, 共 $26+26^{?}36+26^{?}36^{?}36=34658$ 个

试分别构造产生下列语言的文法。
(1) { a n b n ∣ n ? 0 } \left\{a^{n} b^{n} \mid n \geqslant 0\right\} {anbn∣n?0};
(2) { a n b m c p ∣ n , m , p ? 0 } \left\{a^{n} b^{m} c^{p} \mid n, m, p \geqslant 0\right\} {anbmcp∣n,m,p?0};
(3) { a n # b n ∣ n ? 0 } ∪ { c n # d n ∣ n ? 0 } \left\{a^{n} \# b^{n} \mid n \geqslant 0\right\} \cup\left\{c^{n} \# d^{n} \mid n \geqslant 0\right\} {an#bn∣n?0}∪{cn#dn∣n?0};
(4) { w # w r # ∣ w ∈ { 0 , 1 } ? , w r \left\{w \# w^{r} \# \mid w \in\{0,1\}^{*}, w^{r}\right. {w#wr#∣w∈{0,1}?,wr 是将 $w$ 中的符号按逆序排列所得的符号串 $\}$;
（5）任何不是以 0 开始的所有奇整数所组成的集合;
（6）所有由偶数个 0 和偶数个 1 所组成的符号串的集合。

(1) { a n b n ∣ n ? 0 } \left\{a^{n} b^{n} \mid n \geqslant 0\right\} {anbn∣n?0};
解: 对应文法为 G ( S ) = ( { S } , { a , b } , { S → ε ∣ a S b } , S ) \mathrm{G}(\mathrm{S})=(\{\mathrm{S}\},\{\mathrm{a}, \mathrm{b}\},\{\mathrm{S} \rightarrow \varepsilon \mid \mathrm{aSb}\}, \mathrm{S}) G(S)=({S},{a,b},{S→ε∣aSb},S)
(2) { a n b m c p ∣ n , m , p ? 0 } \left\{a^{n} b^{m} c^{p} \mid n, m, p \geqslant 0\right\} {anbmcp∣n,m,p?0}
解: 对应文法为 G ( S ) = ( { S , X , Y } , { a , b , c } , { S → a S ∣ X , X → b X ∣ Y , Y → c Y ∣ ε } , S ) \mathrm{G}(\mathrm{S})=(\{\mathrm{S}, \mathrm{X}, \mathrm{Y}\},\{\mathrm{a}, \mathrm{b}, \mathrm{c}\},\{\mathrm{S} \rightarrow \mathrm{aS}|\mathrm{X}, \mathrm{X} \rightarrow \mathrm{bX}| \mathrm{Y}, \mathrm{Y} \rightarrow \mathrm{cY} \mid \varepsilon\}, \mathrm{S}) G(S)=({S,X,Y},{a,b,c},{S→aS∣X,X→bX∣Y,Y→cY∣ε},S)
(3) { a n # ? b n ∣ n ? 0 } ∪ { c n # ? d n ∣ n ? 0 } \left\{\mathrm{a}^{\mathrm{n}} \# \mathrm{~b}^{\mathrm{n}} \mid \mathrm{n} \geqslant 0\right\} \cup\left\{\mathrm{c}^{\mathrm{n}} \# \mathrm{~d}^{\mathrm{n}} \mid \mathrm{n} \geqslant 0\right\} {an#?bn∣n?0}∪{cn#?dn∣n?0}
解: 对应文法为 G ( S ) = ( { S , X , Y } , { a , b , c , d , # } , { S → X \mathrm{G}(\mathrm{S})=(\{\mathrm{S}, \mathrm{X}, \mathrm{Y}\},\{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}, \#\},\{\mathrm{S} \rightarrow \mathrm{X} G(S)=({S,X,Y},{a,b,c,d,#},{S→X,
$\mathrm{S}\to \mathrm{Y},\mathrm{X}\to \mathrm{a}\mathrm{X}\mathrm{b}|\#,\mathrm{Y}\to \mathrm{c}\mathrm{Y}\mathrm{d}|\#\},\mathrm{S})$
(4) { w # w ? # ∣ w ∈ { 0 , 1 } ? , w r \left\{\mathrm{w} \# \mathrm{w}^{*} \# \mid \mathrm{w} \in\{0,1\}^{*}, \mathrm{w}^{r}\right. {w#w?#∣w∈{0,1}?,wr 是 $\mathrm{w}$ 的逆序排列 $\}$
解: G ( S ) = ( { S , W , R } , { 0 , 1 , # } , { S → W # , ? W → 0 ? W 0 ∣ 1 ? W 1 ∣ # } , S ) \mathrm{G}(\mathrm{S})=(\{\mathrm{S}, \mathrm{W}, \mathrm{R}\},\{0,1, \#\},\{\mathrm{S} \rightarrow \mathrm{W} \#, \mathrm{~W} \rightarrow 0 \mathrm{~W} 0|1 \mathrm{~W} 1| \#\}, \mathrm{S}) G(S)=({S,W,R},{0,1,#},{S→W#,?W→0?W0∣1?W1∣#},S)
(5) 任何不是以 0打头的所有奇整数所组成的集合
解: G ( S ) = ( { S , A , B , I , J } , { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } , { S → J ∣ I B J , ? B → 0 ? B ∣ I B ∣ e \mathrm{G}(\mathrm{S})=(\{\mathrm{S}, \mathrm{A}, \mathrm{B}, \mathrm{I}, \mathrm{J}\},\{0,1,2,3,4,5,6,7,8,9\},\{\mathrm{S} \rightarrow \mathrm{J}|\mathrm{IB} J, \mathrm{~B} \rightarrow 0 \mathrm{~B}| \mathrm{IB} \mid \mathrm{e} G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J∣IBJ,?B→0?B∣IB∣e, $\mathrm{I}\to \mathrm{J}|2|4|6|8,\mathrm{J}$ $\to$ $1|3|5|7|9\},\mathrm{S})$
（6）所有偶数个 0 和偶数个 1 所组成的符号串集合
解: 对应文法为 $\mathrm{S}\to 0\mathrm{A}|1\mathrm{B}|\mathrm{e},\mathrm{A}\to 0\mathrm{S}|1\mathrm{C},\mathrm{B}\to 0\mathrm{C}|1\mathrm{S},\mathrm{C}\to 1\mathrm{A}\mid 0\mathrm{B}$

试描述由下列文法所产生的语言的特点（文法的开始始符号均为 $\mathrm{S}$ ）。
$$\begin{array}{llll}\text{?(1)?}\mathrm{S}\to 10\mathrm{S}0& \mathrm{S}\to \mathrm{a}\mathrm{A}& \mathrm{A}\to \mathrm{b}\mathrm{A}& \mathrm{A}\to \mathrm{a}\\ \text{?(2)?}\mathrm{S}\to \mathrm{S}\mathrm{S}& \mathrm{S}\to 1\mathrm{A}0& \mathrm{A}\to 1\mathrm{A}0& \mathrm{A}\to \epsilon \\ \text{?(3)?}\mathrm{S}\to 1\mathrm{A}& \mathrm{S}\to \mathrm{B}0& \mathrm{A}\to 1\mathrm{A}& \mathrm{A}\to \mathrm{C}\\ \mathrm{B}\to \mathrm{B}0& \mathrm{B}\to \mathrm{C}& \mathrm{C}\to 1\mathrm{C}0& \mathrm{C}\to \epsilon \\ \text{?(4)?}\mathrm{S}\to \mathrm{b}\mathrm{A}\mathrm{d}\mathrm{c}& \mathrm{A}\to \mathrm{A}\mathrm{G}\mathrm{S}& \mathrm{G}\to \epsilon & \mathrm{A}\to \mathrm{a}\\ \text{?(5)?}\mathrm{S}\to \mathrm{a}\mathrm{S}\mathrm{S}& \mathrm{S}\to \mathrm{a}& & \end{array}$$

(1) $\mathrm{S}\to 10\mathrm{S}0\mathrm{S}\to \mathrm{a}\mathrm{A}\mathrm{A}\to \mathrm{b}\mathrm{A}\mathrm{A}\to \mathrm{a}$
解：本文法构成的语言集为: L ( G ) = { ( 10 ) n a b m a 0 n ∣ n , m ? 0 } L(G)=\left\{(10)^{n} a b^{m} a 0^{n} \mid n, m \geqslant 0\right\} L(G)={(10)nabma0n∣n,m?0} 。
(2) $\mathrm{S}\to \mathrm{S}\mathrm{S}\mathrm{S}\to 1\mathrm{A}0\mathrm{A}\to 1\mathrm{A}0\mathrm{A}\to \epsilon$
解: $\mathrm{L}(\mathrm{G})=\{1^{\mathrm{n}\mathrm{l}}{0}^{\mathrm{n}\mathrm{l}1}{1}^{\mathrm{n}2}{0}^{\mathrm{n}2}?1^{\mathrm{n}\mathrm{m}}{0}^{\mathrm{n}\mathrm{m}}\mid {\mathrm{n}}_1,{\mathrm{n}}_2,?,{\mathrm{n}}_{\mathrm{m}}?0$; 且 ${\mathrm{n}}_1,{\mathrm{n}}_2,?{\mathrm{n}}_{\mathrm{m}}$ 不全
为零 $\}$ 该语言特点是：产生的句子中, $0、1$ 个数相同, 并且若干相接的 1后必 然紧接数量相同连续的 0 。
(3) $\mathrm{S}\to 1\mathrm{A}\mathrm{S}\to \mathrm{B}0\mathrm{A}\to 1\mathrm{A}\mathrm{A}\to \mathrm{C}\mathrm{B}\to \mathrm{B}0\mathrm{B}\to \mathrm{C}\mathrm{C}\to 1\mathrm{C}0\mathrm{C}\to \epsilon$ 解：本文法构成的语言集为:
L ( G ) = { 1 p 1 n 0 n ∣ p ? 1 , n ? 0 } ∪ { 1 n 0 n 0 q ∣ q ? 1 , n ? 0 } L(G)=\left\{1^{p} 1^{n} 0^{n} \mid p \geqslant 1, n \geqslant 0\right\} \cup\left\{1^{n} 0^{n} 0^{q} \mid q \geqslant 1, n \geqslant 0\right\} L(G)={1p1n0n∣p?1,n?0}∪{1n0n0q∣q?1,n?0}, 特点是具有 $1^p{1}^n{0}^n$ 或 $1^{\mathrm{n}}{0}^{\mathrm{n}}{0}^q$ 形式, 进一步, 可知其具有形式 $1^{\mathrm{n}}{0}^{\mathrm{m}},\mathrm{n},\mathrm{m}?0$, 且 $n+m>0$ 。
(4) $\mathrm{S}\to \mathrm{b}\mathrm{A}\mathrm{d}\mathrm{c}\mathrm{A}\to \mathrm{A}\mathrm{G}\mathrm{S}\mathrm{G}\to \epsilon \mathrm{A}\to \mathrm{a}$
该语言特点是：产生的句子中, 是以 ba开头 $\mathrm{d}\mathrm{c}$ 结尾的串,且ba、dc个数相 同。
(5) $\mathrm{S}\to \mathrm{a}\mathrm{S}\mathrm{S}\mathrm{S}\to \mathrm{a}$
解: L ( G ) = { a ( 2 n ? 1 ) ∣ n ? 1 } \mathrm{L}(\mathrm{G})=\{\mathrm{a}(2 \mathrm{n}-1) \mid \mathrm{n} \geqslant 1\} L(G)={a(2n?1)∣n?1} 可知: 奇数个 $a$

例题

① 证明G[S]: S→aSb|Sb|b 为二义性文法

解：找一个句子，可以生成两棵语法树
如aabbbb

②将下列文法改写成无二义性文法：
G[S]: S→SS|(S)|()

解：分析根源，再改写S→SS为
G’[S]: S→TS|T T→(S)|()

③写一个文法，使其语言L(G)是非零开头的正偶数集合

解：G[S]: S → XYZ|2|4|6|8
X → 1|2|3|4|5|6|7|8|9
Y → YX | Y0 |ε
Z → 0|2|4|6|8

测试
一． 填空（40分）

1. 编译系统一般可以分为 词法分析，语法分析，语义分析以及中间代码的生成，代码优化，目标代码的生成 等5大部分组成，其中 词法分析，语法分析，目标代码的生成 部分是每个编译程序必不可少的，而 语义分析以及中间代码的生成，代码优化 则是可有可无的。这5个部分在工作过程中都会涉及到 符号表管理 和 错误处理
2. 中间代码生成所依据的是语言的 语义 规则。
3. 在使用高级语言编程时，首先可以通过编译程序发现源程序的全部 语法 错误和 语义 错误。
4. 由于受到具体机器主存容量限制，编译程序几个阶段的工作往往被组合成 遍 。
5. 编译程序绝大多数时间花在 管理表格子/扫描 上。
6. 语法分析的依据是 语法 规则。
7. 高级语言源程序执行有两种方式：即 编译执行 和 解释执行 。
8. 编译程序各阶段的工作往往是 穿插 进行的。
9. 文法G产生的 句子 的全体构成该文法所描述的语言。
10. 乔姆斯基定义的4种形式的文法中，0型又称 短语结构文法 可由 Turing机 识别， 1型又称 上下文有关文法 可由 线性限界自动机 识别，2型又称 上下文无关文法
    可由 非确定下推自动机 识别，3型包括 右线性正则文法 和 左线性正则文法 ，又称为有限状态语言可由有限自动机 识别。
11. 最左推导是指 对于推导序列中的每个直接推导，都是对符号串V的最左非终结符号进行替换 。
12. 产生式是用于定义 语法范畴 的一种书写规则。
13. 高级语言经过编译生成的语言一般是 机器语言 和 汇编语言 。
14. 句柄是指当前句型的 最左边的简单短语 （最左直接短语） 。
15. 简单地说，文法中有用符号必须满足：1. 可以到达 2. 可以终止 。
16. 规范推导是指 最右推导 ，规范归约是指 最左规约，二者互为逆过程。

二． 写一个文法，使其语言是奇数集，且每个奇数不以0开头。 （20分）
解法1：
$G=S,A,0,1,2,3,4,5,6,7,8,9,P,S$
P : $S?>d_{1}A|d_3$, $A?>d_{2}A|d_3$
d1表示1-9的数字 d2表示0-9的数字，d3表示1，3，5，7，9中任意一个
解法2：
$G=(N,A,B,C,D,0,1,2,3,4,5,6,7,8,9,P,S)$
$N?>AB|B$
$A?>AC|D$
$B?>1|3|5|7|9$
$D?>2|4|6|8|B$
$C?>0|D$

解法3
G[S]:
S—> XYZ |1|3|5|7|9
X—>1|2|3|4|5|6|7|8|9
Y —> YX | Y0 | e
Z —>1|3|5|7|9

解法4
S->XY | 1|3|5|7|9
X->1|2|3|4|5|6|7|8|9|XX|X0
Y->1|3|5|7|9

解法5
G=({S,X},{0,1,2,3,4,5,6,7,8,9},P,S)
S->XS |1|3|5|7|9
X->1|2|3|4|5|6|7|8|9|XX|X0

三． 证明下列文法是二义性文法： S→iSeS∣iS∣i （20分）

对于句子iiiei有两个不同的语法树，所以该文法是二义性文法

四． 写出下面语言的上下文无关文法： $L_1$={$a^n{b}^n{c}^i|n>=1,i>=0$} (20分)

G1:
$N?>S|SA$
$S?>aSb|ab$
$A?>c|Ac$(或者A->c|cA)

G2:
$N?>S|SA$
$S?>aSb|ab$
$A?>Ac|\epsilon$ 消除ε ,得到答案1

G3:
S->aSbC| aSb|ab|abC
C->cC|c

🌱词法分析

🍀3.1 设计扫描器时应考虑的问题

🎯词法分析的基本概念
词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。
词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序。
词法分析是整个编译工作的基础。

设计与实现扫描器需重点解决?
结构：3型文法描述一个语言中各种单词的结构
识别：状态转换图、有限自动机、正则表达式来识别源程序中的各个单词

🎯 词法分析器的功能与实现方式

• 功能
  输入:符号串形式的源程序
  输出:单词符号串
• 实现方式
  1. 词法分析作为单独的一遍
     特点
     ①大部分编译时间花在扫描字符上，独立出来便于集中处理。（简单化）
     ②单词的词法规则简单，可建立特别适用于这种文法的有效技术，实现词法分析的自动生成。(扩大实用性）
     ③整个编译程序结构简单，清晰，产生中间文件，占内存。（功能单一化、结构清晰化）
  2. 词法分析作为一个独立的子程序，供语法分析程序调用
     特点:
     ①语法分析调用时，返回一个单词符号。
     ②无中间文件，省内存，编译效率高。
     
     

🎯源程序的输入及预处理
1、预处理
构造预处理子程序（输入缓冲区）
(1)作用:消除无用空白、回车、注释行、区分标号区、续行号（FORTRAN）等.
(2)功能:词法分析器调用时，在输入缓冲区内处理出确定长的字符串放入扫描缓冲区.

2、扫描缓冲区的结构：
两个半区，两个指示器，互补使用

起点指示器：指向当前正在识别的单词的开始位置
扫描指示器： 用于向前搜索以寻找单词的终点
两个半区互补使用：规定单词的长度不能超过半区的长度。

🎯 单词符号的内部表示
单词符号的内部表示（词法分析器的输出形式）

• 单词符号的种类
  
• 单词符号的表示形式（二元式）
  二元式：（单词类别，单词自身值）
  
  
  🎯 识别标识符的若干约定和策略
  1、约定：
  (1)标识符中的字符个数超过最大允许长度，截去尾部。
  (2)不超过最大长度的标识符，则按“尽可能长”的原则匹配（Greedy Method:贪婪法）。

2. 超前搜索技术
   所谓超前搜索技术（超前读字符）：是仅向前读取字符，和判别该字符是什么，不作处理.当判明后再回过来处理已读过的字符。
   
3. 零层等号和零层逗号（超前搜索技术）
   根据可嵌套的括号由外向内进行编号。
   作用：超前搜索技术中作为某些语句的判定条件来使用
   如：含有零层等号的有赋值语句、DO语句、语句函数定义句、某些逻辑IF语句等。既含有零层等号又含有零层逗号的只有DO 语句。
   基本思想：结合语句各自的特征寻找判定条件

🍀3.2 正则文法和状态转换图

🎯 由正则文法构造状态转换图 （🔥 常考题型）

• 状态图： 是一个由正则文法确定的有限的方向图
  结点对应状态，用圆圈表示。
  状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。
  一张转换图只包含有限个状态，含有一个初始状态和若干个终止状态。

• 右线性文法的状态图
  
  
  小结：
  1）右线性文法的状态转换图对符号串W的识别的方法是一个自顶向下的分析算法
  2）推导过程中产生的句型都是规范句型
  3）右线性文法的状态转换图能识别的恰好是对应文法的全部句子

• 左线性文法状态图
  
  
  总结：
  1）左线性文法的状态转换图对符号串W的识别的方法是一个自底向上的分析算法
  2）规约过程中产生的句型都是规范句型
  3）左线性文法的状态转换图能识别的恰好是对应文法的全部句子

• 状态转换矩阵
  
  
  
  
  
  

🍀3.3 有限自动机

🎯 确定的有限自动机

• DFA的组成
  DFA M=（K，∑，f，S0，Z）
  K: 状态的集合（有限个状态）
  ∑: 允许输入的字符的集合 Vt
  f: 状态转换函数，单值函数K×∑→K
  S0: 初始状态S0∈K
  Z：终止状态集Z ∈ K

• DFA的特点
  确定性、有限性
  

• f 定义的推广
  输入符号拓展到字符串
  
  

• 有限自动机的功能
  识别句子
  

• DFA可非形式地表示成状态图和状态矩阵
  

• 正则文法生成的语言和DFA生成语言的关系
  
  🎯 非确定的有限自动机(NFA M′)

• NFAM’的 组成
  

• NFAM’ 的特点
  不确定、有限性
  

• f ’ 的推广
  

• NFA M’ 所能识别的语言
  

• 状态转换图
  

🎯 DFA M与NFA M ′的等价性

• NFA M’ 和 DFA M 生成的语言
  

• 读ε不动作(动作)的NFA M ′
  
  
  

• 具有E动作的NFAM’
  
  
  

• 读e动作的NFAM’ 的确定化
  
  
  例题
  

• DFA状态数的最小化
  
  
  
  

🍀3.4 正则表达式和正规集

🎯 正规表达式与正规集

• 正规式的递归定义
  设有字母表∑, 单词： ∑上字符按照一定方式组成的字符串 (VT就是∑)；
  每一类单词可用一个正规式描述；
  每一类的全体单词组成相应的正规集。
  
• 两个正规式相等
  
• 正规式的操作（公理）
  🎯 正规文法和正则式
  
  
  
  ?? 求文法对应的正则式
  

🎯 正规式和FAM

• 正规式与FA的等价性
  
• 正则式与FA的转换 (e->NFAM’)
  
  ?? 构造正规式相应的DFA
  
  
• DFAM->e
  
  
• DFA->正则文法和正则式
  
  
  
  ?? 例题：正则文法->正则式
  
  
  ?? 例题：正规式->DFA
  

🍀3.5 词法分析程序的实现

🎯 词法分析程序的编写
正则文法-> 状态转换图-> 程序框图

• 单词符号的正则文法
  

• 单词的类别编码
  
  几点重要限制说明
  1)所有关键字都是保留字;用户不能用它们作自己的标识符
  2)关键字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。
  3)如果关键字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔

• 状态转换图
  
  

• 程序的编写
  语义变量及语义函数
  
  

🎯 词法分析程序的自动生成
LEX:美国Bell实验室用C语言研制的一个UNIX操作系统下的词法分析程序自动生成工具。

• LEX概述
  

• LEX源程序
  
  
  
  
  
  

• LEX的实现
  
  

• 词法分析器
  

• 处理二义性问题的两个原则
  
  
  
  ?? 例题
  
  

🌺 3.6 习题

（教材3-3）假定有一个猎人带着一只狼、一头山羊和一棵白菜从河的左岸摆渡到右岸，而岸边只有一条小船，其大小仅能装载人和其余三样东西中的一件，也就是说，每一次猎人只能将随行者中的一样带到彼岸，若狼和山羊单独在一起，羊会被狼吃掉，若山羊和白菜单独在一起，白菜会被羊吃掉。用状态转换图描述猎人可能采取的将上述三样东西带到右岸的安全摆渡方案。

（教材3-6）试构造一右线性文法，使得它与如下的文法等价S → AB A→UT U→a|aU T→b|bT B→c|cB 并根据所得的右线性文法，构造出相应的状态转换图。

该文法产生的语言是 L = { a m b n c k ∣ m , n , k > = 1 } L=\{a^mb^nc^k|m,n,k>=1\} L={ambnck∣m,n,k>=1}
因此可以构造如下的文法：
V n = { S , A , B , C } V_n=\{S,A,B,C\} Vn?={S,A,B,C} V t = { a , b , c } V_t=\{a,b,c\} Vt?={a,b,c}
$P=S\to aA,A\to aA|bB,B\to bB|cC,C\to cC|c$

（教材3-7）对于如题图所示的状态转换图：
（1）写出相应的右线性文法；
（2）指出它接受的最短输入串；
（3）任意列出它接受的另外四个输入串；
(4) 任意列出它拒绝接受的四个输入串；

1. 右线性文法$G[A]$ 为：
   $A\to 0D,D\to 0B，B\to 0A，D\to 1C,B\to 1C,C\to 0A,C\to 1F,F\to 0E,F\to 1A,E\to 0B,E\to 1C$
2. 最短输入串 011
3. 四个输入串是：011、0011、0110、000011、0000110
4. 拒绝接受的输入串1000，11100，11001，10101 （任何以1开头的字符串都拒绝接受）

（教材3-8）对于有限自动机M=(K,∑,f,S0,Z)，其中，K={S0,S1,S2,S3,S4,S5}，∑={a,b}，Z={ S1, S4,S5},f由如下的状态转移矩阵给出：

试分别找出一个长度最小的输入串，使得
（1）在识别此输入串的过程中，每一状态至少经历一次
（2） 每一状态转换至少经历一次。

（教材3-9）对于下列的状态转换矩阵：

（1）分别画出相应的状态转换图； （2）写出相应的3型文法； （3）用自然语言分别描述它们所识别的输入串的特征。

(教材3-12) 将以下状态转换矩阵描述的NFA确定化和最小化。

（教材3-13）将如题图所示的具有ε动作的NFA确定化。

（教材3-22）分别构造识别如下正规语言的DFA：
（1）（（0*|1）（1*0））*
（2）（b|a（aa*b）*b）*

🌱4.自顶向下的语法分析

自顶向下的分析过程特点：

1. 同一非终结符的多个候选式存在共同的前缀，将导致回溯现象（消除直接和间接左递归）
   
2. 左递归文法会使递归下降分析器陷入无限循环（消除回溯）
   
3. 不能指出出错的具体原因

🍀4.1 消除文法的左递归

方法1??： 用扩充的BNF表示
引人一对元语言符号 { 、 } \{、\} {、}, 用以表示花括号 { x } \{x\} {x} 中的符 号串 $\mathrm{x}$ 可出现任意多次 (包括零次), 并把形如
$$\mathrm{A}\to \mathrm{A}\alpha \mid \beta$$
的产生式 (其中, $\beta$ 不以 $\mathrm{A}$ 打头)等价地改写为
A → β { α } A \rightarrow \beta\{\alpha\} A→β{α}

方法2??：引入新的非终结符号
对 $\mathrm{A}$ 引人一个新的非终结符号 ${\mathrm{A}}^{\prime }$, 并把式等价地写成
$$\begin{array}{rl}& \mathrm{A}\to \beta {\mathrm{A}}^{\prime }\\ & {\mathrm{A}}^{\prime }\to \alpha {\mathrm{A}}^{\prime }|\epsilon \end{array}$$

?? 消除直接左递归总结

消除直接左递归的一般形式

上述的方法可以消除产生式中的直接左递归，但是不能消除经多步推导出现的左递归。
下面介绍方法3和方法4，可以一次性消除所有的左递归。

方法3?? ： 消除左递归算法

输入：不含循环推导（即形如A?+ A的推导）和ε-产生式的文法G
输出：等价的无左递归文法

1)  按照某个顺序将非终结符号排序为A1，A2，...，An.
2)  for ( 从1到n的每个i ) {
3)      for ( 从1到i -1的每个i ) {
4)           将每个形如Ai→ Ajγ的产生式替换为产生式组Ai→δ1γ∣δ2γ∣...∣δkγ，其中Aj→δ1∣δ2∣... ∣δk，是所有的Aj产生式
5)      }
6)      消除Ai产生式之间的立即左递归
7)  }

方法4?? : 文法的矩阵表示

首先引入文法的矩阵表示：
设 $\mathrm{G}$ 是一前后文无关文法, 它的 ${\mathrm{V}}_{\mathrm{N}}$ 中含有 $\mathrm{n}$ 个非终结符号 ${\mathrm{X}}_1,{\mathrm{X}}_2,?,{\mathrm{X}}_{\mathrm{n}}$, 对于 $\mathrm{G}$ 的每 一产生式
$${\mathrm{X}}_{\mathrm{i}}\to {\gamma }_1\left|{\gamma }_2\right|?\mid {\gamma }_{\mathrm{m}}$$
我们可将它的各候选式 ${\gamma }_1,{\gamma }_2,?,{\gamma }_{\mathrm{m}}$ 分为两类：把以非终结符号打头的 ${\gamma }_{\mathrm{i}}$ 归为一类;而将以 终结符号打头的归为另一类。例如, 若某个 ${\gamma }_{\mathrm{k}}$ 以 ${\mathrm{X}}_{\mathrm{j}}$ 打头, 就把 ${\gamma }_{\mathrm{k}}$ 写成 ${\mathrm{X}}_{\mathrm{j}}{\alpha }_{\mathrm{j}\mathrm{i}}\left({\alpha }_{\mathrm{j}\mathrm{i}}\in {\mathrm{V}}^{+}\right)$。此 时, 若将元语言符号 $\to$ 及|形式地用 “=”及 “ $+$ ”表示, 即可将此产生式写成
$${\mathrm{X}}_{\mathrm{i}}={\mathrm{X}}_1{\alpha }_{1\mathrm{i}}+{\mathrm{X}}_2{\alpha }_{2\mathrm{i}}+?+{\mathrm{X}}_{\mathrm{n}}{\alpha }_{\mathrm{n}\mathrm{i}}+{\beta }_{\mathrm{i}}$$
其中, ${\beta }_i$ 是那些以终结符号打头的诸候选式之“和”。此外, 若此产生式不含以某一非终结符号 ${\mathrm{X}}_{\mathrm{j}}$ 打头的候选式, 则相应的 ${\alpha }_{\mathrm{j}\mathrm{i}}$ 为 $?$ 。这样, 我们就可将 $\mathrm{G}$ 的诸产生式写成如下的矩阵方程。
$$\left({\mathrm{X}}_1{\mathrm{X}}_2?{\mathrm{X}}_{\mathrm{n}}\right)=\left({\mathrm{X}}_1{\mathrm{X}}_2?{\mathrm{X}}_{\mathrm{n}}\right)??\begin{array}{cccc}{\alpha }_{11}& {\alpha }_{12}& ?& {\alpha }_{1\mathrm{n}}\\ {\alpha }_{21}& {\alpha }_{22}& ?& {\alpha }_{2\mathrm{n}}\\ ?& ?& & ?\\ {\alpha }_{\mathrm{n}1}& {\alpha }_{\mathrm{n}2}& ?& {\alpha }_{\mathrm{n}}\end{array}?+\left({\beta }_1{\beta }_2?{\beta }_{\mathrm{n}}\right)$$
或
$$\mathbf{X}=\mathbf{X}\mathbf{A}+\mathbf{B}$$
上式 即为文法 $G$ 的一种矩阵表示。不过, 需要注意的是, 对上面各式中所出 现的运算符应作如下的理解: 乘法运算表示字符串的连接, 加法运算表示选择。矩阵方程 (4.12) 有形如
$$\mathbf{X}={\mathbf{B}\mathbf{A}}^{?}$$
的解。显然, 要计算矩阵 $\mathbf{A}$ 的闭包 ${\mathbf{A}}^{?}$ 一般是很困难的, 但可设法予以回避。事实上, 由于
$${\mathbf{A}}^{?}=\mathbf{I}+\mathbf{A}+{\mathbf{A}}^2+?=\mathbf{I}+\mathbf{A}{\mathbf{A}}^{?}$$
其中
$$\mathbf{I}=?\begin{array}{ccccc}\epsilon & ?& ?& ?& ?\\ ?& \epsilon & ?& ?& ?\\ ?& ?& ?& & ?\\ ?& ?& ?& ?& \epsilon \end{array}?$$
若设
$${\mathbf{A}}^{?}=\mathbf{Z}=?\begin{array}{cccc}{z}_{11}& z_{12}& ?& z_{1n}\\ z_{21}& z_{22}& ?& z_{2n}\\ ?& ?& & ?\\ z_{n1}& z_{n2}& ?& z_{nn}\end{array}?$$
则可得如下两个矩阵式
$$\begin{array}{rl}& \mathbf{X}=\mathbf{B}\mathbf{Z}\\ & \mathbf{Z}=\mathbf{I}+\mathbf{A}\mathbf{Z}\end{array}$$

• ?例题

消除下列文法的左递归
$$\begin{array}{rl}& \mathrm{S}\to \mathrm{S}\mathrm{a}|\mathrm{A}\mathrm{b}|\mathrm{a}\\ & \mathrm{A}\to \mathrm{S}\mathrm{c}\end{array}$$

显然,其中 $\mathrm{S},\mathrm{A}$ 都是左递归的非终结符号。首先写出此文法的矩阵表示
$$(SA)=(SA)\left[\begin{array}{ll}a& c\\ b& ?\end{array}\right]+(a?)$$
$${\left[\begin{array}{ll}a& c\\ b& ?\end{array}\right]}^{?}=\mathbf{Z}=\left[\begin{array}{ll}{z}_{11}& z_{12}\\ z_{21}& z_{22}\end{array}\right]$$
则有
$$\begin{array}{c}(\mathrm{S}A)=(\mathrm{a}?)\left[\begin{array}{ll}{\mathrm{z}}_{11}& {\mathrm{z}}_{12}\\ {\mathrm{z}}_{21}& {\mathrm{z}}_{22}\end{array}\right]\\ \left[\begin{array}{ll}{\mathrm{z}}_{11}& {\mathrm{z}}_{12}\\ {\mathrm{z}}_{21}& {\mathrm{z}}_{22}\end{array}\right]=\left[\begin{array}{ll}\mathbf{\epsilon }& ?\\ ?& \epsilon \end{array}\right]+\left[\begin{array}{ll}\mathrm{a}& \mathrm{c}\\ \mathrm{b}& ?\end{array}\right]\left[\begin{array}{ll}{\mathrm{z}}_{11}& {\mathrm{z}}_{12}\\ {\mathrm{z}}_{21}& {\mathrm{z}}_{22}\end{array}\right]\end{array}$$
于是, 我们就得到了与文法 (4.16) 等价的文法
$$\begin{array}{ll}\mathrm{S}\to {\mathrm{a}\mathrm{z}}_{11}& \mathrm{A}\to {\mathrm{a}\mathrm{z}}_{12}\\ {\mathrm{z}}_{11}\to {\mathrm{a}\mathrm{z}}_{11}\left|{\mathrm{c}\mathrm{z}}_{21}\right|\epsilon & {\mathrm{z}}_{12}\to {\mathrm{a}\mathrm{z}}_{12}\mid {\mathrm{c}\mathrm{z}}_{22}\\ {\mathrm{z}}_{21}\to {\mathrm{b}\mathrm{z}}_{11}& {\mathrm{z}}_{22}\to {\mathrm{b}\mathrm{z}}_{12}\mid \epsilon \end{array}$$
删除其中的无用产生式, 我们有
$$\begin{array}{rl}& \mathrm{S}\to {\mathrm{a}\mathrm{z}}_{11}\\ & {\mathbf{z}}_{11}\to {\mathrm{a}\mathrm{z}}_{11}\left|{\mathrm{c}\mathrm{z}}_{21}\right|\epsilon \\ & {\mathrm{z}}_{21}\to {\mathrm{b}\mathrm{z}}_{11}\end{array}$$

🍀4.2 回溯的消除及LL(1)文法

问题背景： 不能准确的选定候选式
回溯的原因：若当前符号为 $a$, 需要对 $A$ 展开, 而 $A\to {\alpha }_1\left|{\alpha }_2\right|\dots \mid {\alpha }_n$, 那么要知道哪个 ${\alpha }_i$ 是获得以a开头串的候选式, 即通过查看当前符号来选择合适的候选式$a_i$
解决：对文法的任何非终结符号，当要匹配输入串时，它能根据面临的输入符号准确地指派唯一的候选式。
目标：候选式所产生的首字符的交集不为空，即可选定的候选式不唯一。

?? 回溯的消除
方法1??： 提取左公因子
$$\begin{array}{rl}& \mathbf{A}\to \mathbf{\delta }{\mathbf{\beta }}_1\left|\mathbf{\delta }{\mathbf{\beta }}_2\right|\mathbf{\delta }{\mathbf{\beta }}_3|\dots |\mathbf{\delta }{\mathbf{\beta }}_n\left|{\gamma }_1\right|{\gamma }_2|\dots |{\gamma }_m\\ & \begin{array}{l}\text{?(其中每个?}{\gamma }_m\text{?不以?}\delta \text{?开头?)?那么,?可以改成?}\\ \mathbf{A}\to \mathbf{\delta }{\mathbf{A}}^{\prime }\left|{\gamma }_1\right|{\gamma }_2|\dots |{\gamma }_m\\ {\mathbf{A}}^{\prime }\to {\mathbf{\beta }}_1\left|{\mathbf{\beta }}_2\right|{\mathbf{\beta }}_3|\dots |{\mathbf{\beta }}_{\mathrm{n}}\end{array}\end{array}$$

方法2?? 借助First集和Follow集
对于每一$A?{\alpha }_1\left|{\alpha }_2\right|\dots \mid {\alpha }_n$要求$a_i$可推导到的首字母（终结符号）不同即可。如果有ε 出现，则需要考虑到A后面的符号。

🌿 First集和Follow集
First ? ( α i ) = { a ∣ α i = ? a δ \operatorname{First}\left(\alpha_{\mathbf{i}}\right)=\left\{a \mid \alpha_{\mathbf{i}}={ }^{*} a \delta\right. First(αi?)={a∣αi?=?aδ, 且 $a\in V_{\mathbf{T}},{\alpha }_i,\delta \in V^{?}\}$
当 ${\alpha }_i=>?\epsilon$ 时, 则 $\epsilon \in \mathrm{First}\left({\alpha }_i\right)$
Follow(A) = { a ∣ S # = > ? α A a δ =\left\{a \mid S \#=>* \alpha A a \delta\right. ={a∣S#=>?αAaδ, 且a $\in V_T,\alpha ,\delta \in V^{?}\}$
若 $S=>?\alpha A$ 则 # Follow(A)。

🌿无回溯的条件
对于G中的每一个 $A\in V_N,A\to {\alpha }_1\left|{\alpha }_2\right|\dots \mid {\alpha }_1$
(1) $\mathrm{First}\left({\alpha }_{\mathbf{i}}\right)\cap \mathrm{First}\left({\alpha }_{\mathbf{j}}\right)=\Phi (\mathbf{i}=\mathbf{j}$ 时 $)$ $({\alpha }_{\mathrm{i}}$ 和 ${\alpha }_{\mathrm{j}}$ 至多有一个能推出 $\epsilon )$
(2)若有 ${\alpha }_i$ 能推乎出 $\epsilon$, 则
$$\mathrm{First}\left({\alpha }_j\right)\cap \text{?Follow(A)?}=\Phi (i=j\text{?时?})$$

?? LL(1)文法的基本概念
LL(1)文法确定的是确定的自顶向下的分析技术
🌿LL(1)的含义
第一个L表明自顶向下是从左到右扫描输入串。
第二个L表明分析过程中将使用最左推导
1表明只需要向右看1个符号就可以决定如何推导，即选择哪个产生式进行推导

🌿 LL(1)文法需要满足的规则

1. 提取左公因子, 文法不含左递归
2. 对于G中的每一个 $A\in V_N,A\to {\alpha }_1\left|{\alpha }_2\right|\dots \mid {\alpha }_n$
   （1）$\mathrm{First}\left({\alpha }_i\right)\cap \mathrm{First}\left({\alpha }_j\right)=\Phi$ ( $i=j$ 时 )
   （2）若有 ${\alpha }_i$ 能推导出 $\epsilon$, 则$\mathrm{First}\left({\alpha }_j\right)\cap$ Follow(A) $=\Phi (\mathbf{i}=\mathbf{j}$ 时 $)$

🌿 LL(1)分析法
假设面临的输入符号为a, 要用非终结符A进行匹配, $\left(\mathrm{A}\to {\alpha }_1\left|{\alpha }_2\right|\dots \mid {\alpha }_n\right)$

1. 若 $\mathrm{a}$ 属于First $\left({\alpha }_{\mathbf{i}}\right)$, 则指派 ${\alpha }_{\mathbf{i}}$ 执行匹配;
2. 若 $\mathrm{a}$ 不属于任何一个First $\left({\alpha }_{\mathbf{i}}\right)$, 则：
   （1）若 $\epsilon$ 属于First $\left({\alpha }_i\right)$ 且a属于Follow $(A)$, 则指派 ${\alpha }_i$ 进行匹配；
   （2）否则, a的出现是一个语法错误。

🍀4.3 递归下降分析法

对每一个非终结符号U,编写一个子程序F(U)
F(U): boolean
true: 分析过程正常
false: 分析过程出错

对于文法G[E]:
E->T|EAT
T->F|TMF
T->(E)|I
A->+|-
M->*|/

步骤1?? 消除左递归
改写方法1：
E-> T{AT}
T->F{MF}
F->(E)|i
A->+|-
M->*|/
改写方法2:
E->TE’
E’->ATE’|$\epsilon$
T->FT’
T’->MFT’|$\epsilon$
F->(E)|i
A->+|-
M->*|/

步骤2?? 消除回溯

产生式	FIRST(a)	FOLLOW(A)
E->TE’	(,i	), #
E’->ATE’	+,-	), #
E’->ε	ε
T->FT’	(,i	+,-, ), #
T’->MFT’	*,/	+,-, ), #
T’->ε	ε
F->(E)	(	+,-, ), #
F->i	i
A->+	+	(, i
A->-	-
M->*	*	(, i
M->/	/

步骤2?? 递归子程序

🍀4.4 预测分析法

LL(1)分析器的描述
逻辑结构：
一张分析表M: 包含文法的全部信息
一个分析栈：用于存放分析过程中的文法符号
总控程序：控制分析过程（不同的文法可用一个）

A: 处于分析栈中
a: 处于输入串中
M[A,a]: 分析栈中面临输入符号a时应采取的动作

🌿LL(1)分析过程

1. 初始格局： #,S依次入栈，
   
2. 反复执行，任何时候按栈顶Xm和输入的$a_i$依据分析表，执行下述三个动作之一。
   （a）若${\mathbf{X}}_{\mathbf{m}}\in {\mathbf{V}}_{\mathbf{n}}$- 若 $\mathbf{M}\left[{\mathbf{X}}_{\mathbf{m}},{\mathbf{a}}_{\mathbf{i}}\right]$ 对应一产生式 则 ${\mathbf{X}}_{\mathbf{m}}$ 退栈,产生式右部符号按反序进栈。(相当于进行一步推条)右部为 $\epsilon$, 不进栈
   若 $\mathrm{M}[{\mathrm{X}}_{\mathbf{m}},{\mathrm{a}}_{\mathbf{i}}$ ] 为error: 出错处理
   （b）$X_m\in V_T$
   若$X_m=a_i=\#$ ,则$X_m$出栈，输入符号指针指向下一个位置
   若$X_m=a_i$ 调error
   （c）若$X_m=\#$
   若$X_m=a_i=\#$ 分析成功，结束
   若$X_m=a_i$ 调error

🌿 构造FIRST的算法
1?? 构造字符的FIRST集
(一)对于G[S],$x\in V_n\cup V_t$ ,计算FIRST(X)
（1） 若$x\in V_t$ ,则$FIRST(x)=x$
（2）若$x\in V_n$, 若$x\to a\alpha ,a\in V_t$ 若有$x\to \epsilon$,则$\epsilon \in FIRST(x)$
（3）对$x?>Y_1{Y}_2{Y}_3....Y_k$ (且$Y_1\in V_n$) 反复使用如下的规则，直到每一个FIRST(x）不再增大为止。
a) 若$Y_1\in V_n$
把 F I R S T ( Y 1 ) ? { ε } FIRST(Y_1)- \{\varepsilon \} FIRST(Y1?)?{ε}加入到FIRST(x)中
b) 若$Y_1,Y_2,...Y_{i?1}\in V_n(2<=i<=k)$
且对于任意的j,$\epsilon \in FIRST(Y_j)(1<=j<=i?1)$ 则把所有的 F I R S T ( Y i ) ? { ε } FIRST(Y_i)-\{\varepsilon\} FIRST(Yi?)?{ε} 元素加入FIRST(x)中
c)若对于任何的j,$\epsilon \in FIRST(Y_j)(1<=j<=k)$ 则把元素 $\epsilon$ 加入到FIRST(x）中
2?? 构造产生式的FIRST集
（二）构造$FIRST(\alpha ),\alpha =X_1{X}_2...X_n,X_i\in V,\alpha \in V^{?}$
a) 置$FIRST(\alpha )=$
b） F I R S T ( X 1 ) ? { ε } FIRST(X_1)-\{ \varepsilon\} FIRST(X1?)?{ε} 加入$FIRST(\alpha )$
c) 若$\epsilon \in FIRST(X_1)$,则 F I R S T ( X 2 ) ? { ε } FIRST(X_2)-\{ \varepsilon\} FIRST(X2?)?{ε} 加入
若$\epsilon \in FIRST(X_2)$,则$FIRST(X_3)?\epsilon$ 加入
…依次类推
若$\epsilon \in FIRST(X_i)1<=i<=n$, 则$\epsilon \in FIRST(\alpha )$

🌿 FOLLOW(A)的算法
a) 令$\#\in FOLLOW(S)$ S为文法的开始符号
b) 对$A?>\alpha B\beta 且\beta =\epsilon$, 则将 F I R S T ( β ) ? { ε } FIRST(\beta) -\{\varepsilon \} FIRST(β)?{ε} 加入$FOLLOW(B)$中
c) 反复，直至每一个FOLLOW(A) 不再增大，对$A?>\alpha B$ 或 $A?>\alpha B\beta$(且$\epsilon \in FIRST(\beta )$)
则$FOLLOW(A)中的全部元素加入FOLLOW(B)$

🌿构造分析表的算法
由每一个产生式$A?>a_1|a_2|....|a_n$确定$M[A,a]矩阵a\in V_t$
a) 任何$a\in FIRST(a_i)$,将$A?>a_i$ 规则填入$M[A,a]$
b) 若$\epsilon \in FIRST(a_i)$,则对于任一个$b\in FOLLOW(A)b\in V_t或\#将A?>\epsilon 规则填入M[A,b]$
c) 其他空白为出错

🌿 例题1

G[E]:
E->TE’
E’->ATE’ | $\epsilon$
T->FT’
T’->MFT’
F->(E) | i
A-> +|-
M->|/
试用LL(1)分析法分析输入串i+ii 是否是文法的句子

LL1分析表

分析过程

🌺 4.5 习题

4-1 消除下列文法的左递归
(1) G[S]:S→SA|A A→SB | B| (S) | () B→[S] | [ ]
(2) G[S]:S→AS|b A→SA|a
(3) G[S]:S→(T) |a|ε T→S|T,S

4-2 (教材4-3)对于如下文法，画出无左递归无回朔的递归下降分析程序框图。
（1）P→begin d;X end
? X→d;X|sY
? Y→;sY|ε
（2）
<程序>→begin<语句>end
<语句>→<赋值语句>|<条件语句>
<赋值语句>→<变量>:=<表达式>
<条件语句>→if<表达式>then<语句>
<表达式>→<变量>
<表达式>→<表达式>+<变量>
<变量>→i

4-3（教材4-4）求下列文法的FIRST集和FOLLOW集。
G[S]:
S→aAB|bA|ε
A→aAb|ε
B→bB|ε

4-4（教材4-8）对于如下文法：
G[S]: S→Sb|Ab|b
A→Aa|a
（1）构造一个与G等价的LL(1)文法G′；
（2）对于G′，构造一个相应的LL(1)分析表。

4-5（教材4-9）设已给文法
G[S]:
S→SaB|bB
A→S|a
B→Ac
（1）求出每个非终结符号的FIRST集和FOLLOW集；
（2）将它改写为LL(1)文法。

🌱5. 自底向上的语法分析

🍀5.1 简单优先分析法

🌿 简单优先关系
设 $\mathrm{G}=\left({\mathrm{V}}_{\mathrm{n}},{\mathrm{V}}_{\mathrm{t}},\mathrm{P},\mathrm{S}\right)$ 是化简的文法,
$$\mathrm{V}={\mathrm{V}}_{\mathrm{t}}\cup {\mathrm{V}}_{\mathrm{n}}{\mathrm{S}}_{\mathrm{i}},{\mathrm{S}}_{\mathrm{i}}\text{?属于V?}$$
若 $\mathrm{G}$ 中存在伩样的规范句型,
$$\alpha =?{\mathrm{S}}_{\mathrm{i}}{\mathrm{S}}_{\mathrm{i}}?$$
则此相令的 ${\mathrm{S}}_{\mathrm{i}},{\mathrm{S}}_{\mathrm{i}}$ 和 $\alpha$ 的句柄之间的关系?是 下述情况之一。

1） 若$S_i$在句柄中，而$S_j$不在句柄中。
则$S_i>S_j$, $S_j\in V_t$ 先被规约
2) 若$S_i$和$S_j$ 同时处于a的句柄中，
则$S_i=Sj$ 同时被规约
3） 若$S_j$在句柄中，而$S_i$不在句柄中，
则$S_i<S_j$ 后被规约
(4) 若 ${\mathrm{S}}_{\mathrm{i}}$ 和 ${\mathrm{S}}_{\mathrm{j}}$ 均不在 $\alpha$ 句型的句柄中,
则可能在另一规范句型中满足上述的三种情况之一.
(5)若 $\mathrm{G}$ 中某 ${\mathrm{S}}_{\mathrm{r}}{\mathrm{S}}_{\mathrm{t}}$ 属于 $\mathrm{V}$, 不可能相邻地出现在某一规范句型中, 则 ${\mathrm{S}}_{\mathrm{r}}$ 和 ${\mathrm{S}}_{\mathrm{t}}$ 之间不存在任何仼先关系.

上述的关系不具有对称性，即$S_i<S_j$ 不意味着$S_j>S_i$
🌿 简单优先文法
若文法G中的任何两个符号之间至多存在一种优先关系，且任意两个不同的产生式均无相同的右部（无二义性），则称G为简单优先文法。

$\begin{array}{rl}\mathbf{G}[\mathbf{E}]& :\mathbf{E}\to {\mathbf{E}}_1\\ & {\mathbf{E}}_1\to {\mathbf{E}}_1+{\mathbf{T}}_1\mid {\mathbf{T}}_1\\ & {\mathbf{T}}_1\to \mathbf{T}\\ & \mathbf{T}\to {\mathbf{T}}^{?}\mathbf{F}\mid \mathbf{F}\\ & \mathbf{F}\to (\mathbf{E})\mid \mathbf{i}\end{array}$
$\begin{array}{clc}\text{?由?}{\mathrm{E}}_1\to {\mathrm{E}}_1+{\mathrm{T}}_1& {\mathrm{E}}_1\equiv +& +\equiv {\mathrm{T}}_1\\ \mathrm{T}\to {\mathrm{T}}^{?}\mathrm{F}& \mathrm{T}\equiv {}^{?}& ?\equiv \mathrm{F}\\ \mathrm{F}\to (\mathrm{E})& (\equiv \mathrm{E}& \mathrm{E}\equiv )\end{array}$

按照算法可以建立优先关系矩阵

🌿 简单优先分析的算法–寻找句柄

1. 结论：对于简单优先文法的任何规范句型$x_1{x}_2...x_n$而言，句柄是该句型中满足以下条件的最左子串$x_i{x}_{i+1}....x_{i+k}$
   满足以下条件的最左子串$x_i{x}_{i+1}...x_{i+k}$
   $X_{i?1}<X_i$
   $X_i=X_{i+1}=....=X_{i+k}$
   $X_{i+k}>X_{i+k+1}$
2. 算法：
   数据结构: (1) $\mathrm{S}$ 为分析栈， $i,j$ 为指示器
   (2) $\mathbf{Q},\mathbf{R}$ 为变量, 放 $\#,V_t,V_n$
   (3) R变量, 放输入串中的一个符号
   (4) $a_1{a}_2\dots \dots a_n$ #为要分析的输入串${\mathbf{X}}_{\mathrm{i}+\mathrm{k}}>{\mathbf{X}}_{\mathrm{i}+\mathrm{k}+1}$ 的位置
   (2) 回过来找句柄的头部(向梌为) 首孜 ${\mathbf{X}}_{\mathrm{i}?1}<{\mathbf{X}}_{\mathbf{i}}$ 满足的?置
   (3) 中间夹的全是优先级相等的
   
   
   
   

🌿 简单优先文法的局限性

1）多重定义优先关系——非简单优先关系
例如：
$U?>...S_i{S}_j....$
$S_i?>S_j....$
解决方案：改写文法
$\mathrm{G}[\mathrm{E}]:\mathrm{E}\to \mathrm{E}+\mathrm{T}\mid \mathrm{T}$
$\mathrm{T}\to {\mathrm{T}}^{?}\mathrm{F}\mid \mathrm{F}$
$\mathrm{F}\to (\mathrm{E})\mid \mathrm{i}$
不是简单优先文法，改写为
$\begin{array}{rl}\mathrm{G}[\mathrm{E}]& \mathrm{E}\to {\mathrm{E}}_1\\ & {\mathrm{E}}_1\to {\mathrm{E}}_1+{\mathrm{T}}_1\mid {\mathrm{T}}_1\\ & {\mathrm{T}}_1\to \mathrm{T}\\ & \mathrm{T}\to {\mathrm{T}}^{?}\mathrm{F}\mid \mathrm{F}\\ \mathrm{F}\to (\mathrm{E})\mid \mathrm{i}& \end{array}$

2） 文法的复杂性增加，改写不能解决
$\begin{array}{ll}\mathrm{U}\to \dots \dots {\mathrm{S}}_{\mathrm{i}}{\mathrm{S}}_{\mathrm{j}}\dots & {\mathrm{S}}_{\mathrm{i}}={\mathrm{S}}_{\mathrm{i}}\\ {\mathrm{S}}_{\mathrm{i}}\to \dots \dots .{\mathrm{S}}_{\mathrm{i}}& {\mathrm{S}}_{\mathrm{i}}>{\mathrm{S}}_{\mathrm{i}}\\ {\mathrm{S}}_{\mathrm{j}}\to {\mathrm{S}}_{\mathrm{j}}?\dots & {\mathrm{S}}_{\mathrm{i}}?{\mathrm{S}}_{\mathrm{j}}\end{array}$
解决方法：LR(K)分析法

3） 在实际的运算过程中，决定运算顺序的是终结符号之间的优先关系

🌿 简单优先关系矩阵构造
LEAD 关系：当且仅当G中存在形如
$A?>B....$ 的产生式时，有A LEAD B
且仅当$A{=}^{+}>B...$时，有A LEAD+ B
LAST 关系：当且仅当G中存在形如
$A?>....B$ 的产生式时，有A LAST B
且仅当$A{=}^{+}>...B$时，有A LAST+ B

🍀5.2 算符优先分析法

🌿 算符文法
算符文法(OG文法) (Operator Grammar) 设一文法 $G$, 若G中不吕U $?$… VW … 规则
$$\mathbf{V},\mathbf{W}\in {\mathbf{V}}_{\mathbf{n}}$$
OG文法：
(1) 不会含有两个非终结符号相邻的句型。
(2) 两个相邻运萛符之间的运算对象至多只有一个, 而不会出现运算对象个数不定的现象。
优先关系：两个终结符号间。

🌿 算符优先文法
设G是一OG文法, a, b∈Vt, U,V,W ∈Vn
(1)a = b 当且仅当OG有
形如U→….ab….或U→….aVb….的规则
(2)a < b 当且仅当OG有(先终结符，后非终结符，后大)
形如U→….aW….的规则
而且W=>b….或W=>Vb……
(3)a > b 当且仅当OG有(先非终结符，后终结符，前大)
形如U→….Wb….的规则
而且W=> …. a或W=>….aV
若a,b之间至多存在上述三种优先关系之一,OG为OPG文法.

例G[E]:
E→E+T∣T
T→T*F∣F
F→(E)∣i
①G[E]是OG文法 不含U→…VW…规则
②由F→(E)得 ( = )
由E→E+T T=>T*F 得 +< *
T =>(E) 得 + < (
T =>i 得 + < i

🌿 算符优先分析算法设计
(1)素短语
是这样一个短语,它至少包含有一个终结符号,并且除它自身之外,不再包含其它任何更小的素短语.
(2) 最左素短语
句型最左边的那个素短语.

(3)算符优先文法句型的一般形式
$\#N_1{a}_1{N}_2{a}_2\dots \dots N_n{a}_n{N}_{n+1}\#$
ai∈Vt Ni ∈Vn 可有可无
(4)最左素短语的确定
定理:
一个OPG句型的最左素短语是满足以下条件的最左子串:
$N_j{a}_j\dots ..N_i{a}_i{N}_{i+1}$ 其中:$a_{j?1}<a_j$
aj= a j+1 = … = a i-1 = ai
ai > a i+1
$a_{j?1}<a_j=a_{j+1}=\dots .=a_{i?1}=a_i>a_{i+1}$

🌿 OPG文法的分析算法
数据结构:
符号栈S—存放所有读进的符号(计数i, j)
K----符号栈使用深度
a-----工作单元
R,Q-----变量
分析算法:先找最左素短语的尾部( >)
再找最左素短语的头部( < )

算符优先关系矩阵



🌿 算符优先关系矩阵构造
1)算法分析

(1)a = b 查规则
当且仅当OG有
形如U→….ab….或U→….aVb….的规则

(2)a > b 或 a < b
对每个非终结符构造两个集合
U∈Vn
①FIRSTVT(U)=
{b∣U=>b…, 或U => Vb…, b∈Vt,V∈Vn }

则形如W→…aU…的规则 a < b
b ∈ FIRSTVT(U)
U∈Vn
②LASTVT(U)=
{a∣U=>…a, 或U =>…aV, a∈Vt, V ∈Vn }

则形如W→…Ub…的规则 a > b
a ∈LASTVT(U)


过程描述：
STACK栈
布尔数组F(U,b) U ∈Vn,b ∈Vt
F(U,b) 真 b ∈ FIRSTVT(U)
假 b ∈ FIRSTVT(U)
算法分析

构造OPG优先矩阵的算法






🌿 优先函数

🍀5.3 优先函数

1. 优先函数 θ ∈Vt
   f(θ ):栈内(入栈)优先函数
   g(θ ):栈外（比较）优先函数
   (θ1, θ2)
   若θ1 θ2 则f(θ1 )<g(θ2 )
   若θ1 θ2 则f(θ1 )=g(θ2 )
   若θ1 θ2 则f(θ1 )>g(θ2 )
   2)优先函数的构造
   (1)有向图法（Bell方法）
   ①对每一a∈Vt(包括#),使之对应两个结点fa,ga
   ②对于优先关系矩阵的关系
   a≥b 画一条从fa到gb的有向弧
   a ≤b 画一条从gb到fa的有向弧
   ③对每一结点赋一个数,其值为从该结点出发,所能到达的结点个数(包含自身),
   赋给fa的数为f(a), 赋给gb的数为g(b)
   ④检查优先函数有无矛盾,如有,则优先函数不存在.
   
   
   2)Floyd方法
   ①对每一个f和g赋初值,置f(θ)=g(θ)=1
   ②迭代,即每一(θ1, θ2)
   若θ1 θ2 但f(θ1 )<=g(θ2 ) ,
   则执行f(θ1 )=g(θ2 ) +1
   若θ1 θ2 但f(θ1 )>=g(θ2 ),
   则执行g(θ2 ) = f(θ1 ) +1
   若θ1 θ2 但f(θ1 ) ≠g(θ2 ),
   则令f(θ1 )和g(θ2 ) 中的最小者等于最大者
   ③重复,直至过程收敛为止.
   
   
   讨论:
   (1)简单优先分析所确定的可归约串是
   当前句型的句柄。
   (2)算符优先分析属于自底向上的语法分析,
   但不是严格的最左归约。
   (3)算符优先分析所确定的可归约串是
   当前句型的最左素短语.
   (4)算符优先分析只考虑终结符号之间的优先关系。
   (5)算符优先分析算法很容易程序实现。
   (6)算符优先分析是比简单优先分析更有效的分析法。

• 💦例题
  
  
  
  
  
  

🍀5.4 LR分析法

LR(K)的定义
L : 自左向右扫描输入符号
R: 产生一个最右推导（Rightmost）的逆过程
K: 向前看K个符号可以确定采用哪个产生式进行规约



🌿 可归前缀
形式为 βω [p]
其中: β∈V*
p为规则序号,
ω为第p条规则右部，B → ω

🌿 活前缀

最长的活前缀就是可归前缀
$\epsilon$ 是句型φβt 的活前缀


🌿 LR(0)分析法


🌿LR(0) 分析器






🌿LR(0) 分析表
ACTION[S,a]函数:栈顶状态S面临输入符号a时应采取的动作
Sj:移进,把下一状态j和现输入符号a移入栈
Rj:归约,按第j产生式归约
acc:接受
空白:出错
GOTO[S,x]函数: 栈顶状态S遇到当前文法符号x(x∈V)时应转向的下一状态

通过上述LR(0)分析表可见, 每一行不存在
下述项目—冲突项目
(1)既含移进项目,又含归约项目
(2)含有多个归约项目
这种文法称为LR(0)文法.

不满足条件可采用SLR(1), LR(1)分析法.
🌿LR(0) 项目
LR(0)项目: 给定文法的一个项目是一个在右部符号串中标
有一圆点的产生式
形式: A→α 1 · α2
A→α 1 α2 为一个产生式

表示: 已从输入串中看到了能由α 1推导出的符号串, 希望进一步看到由α2 推导出的符号串.
例:E →E+T 项目: E → · E+T E → E · +T
E →E+ · T E →E+T ·
归约项目:圆点在最后的项目
E →E+T ·
接受项目:开始符号的归约项目
S→E# ·
移进项目: 形如A → α·a β项目 a∈Vt
E → E · +T
待约项目: 形如A → α·B β项目 B∈Vn
E → E + · T

🌿LR(0) 分析器的构造
DFA M的一个状态 i
—由若干个LR(0)项目所组成的集合（项目集）Ci
DFA M 的状态集Q
Q={ C0 , C1 , C2, …… , Cn }=C
C 称为文法的LR(0)有效项目集规范族

（1）3种操作:
开始操作: S为开始符号, S→δ
则 S→·δ∈C0
闭包操作: closure(Ci) Ci的闭包
① Ci 的任何项目均属于closure(Ci)
②若A → α·X β且X∈Vn属于closure(Ci)
则X → ·λ 属于closure(Ci)
重复,直至 closure(Ci)不再增大.
③ Ci=closure(Ci)
转移操作: Go(Ci , x ) x∈V
Go(Ci , x ) = Cj = CLOSURE(J)
其中: J={A → αx· β∣ A → α · x β∈ Ci}

(2) 算法(求文法的LR(0)项目集规范族C)

①拓广文法, 保证唯一初态.
②生成初态项目集C0= closure(C0)= closure(S→ ·δ）
③ Ci转移操作, Go(Ci , x ) = Cj = CLOSURE(J)求出新状态Cj的项目集
重复以上过程,直至C不再增大为止。
(不出现新的项目集)

🌺 5.5 习题

4-6（教材4-13）对于文法G[S]:
S→A/
A→Aa|AS|/
(1) 构造G[S]的简单优先矩阵；
(2) 找出其中的多重定义元素，以验证G[S]不是简单优先文法。

4-8(教材4-31) 设已给文法G[E]:
E→E+T|T
T→T*F|F
F→P↑F| P
P→(E) |i
(1) 构造此文法的算符优先矩阵
(2) 用Floyd方式将所得的优先矩阵线性化。

4-9（教材4-33）对于算符文法
S→A[ ] A→[ A→aA A→B] B→a
（1）构造相应的优先矩阵；
（2）用Bell方法求优先函数；
（3）检验此优先矩阵能否线性化。

4-10（教材4-35）对于下列文法，试构造LR(0)项目集规范族及识别全部活前缀的DFA。
G[S]: S→aSb S→aSc S→ab

4-11（教材4-36）构造题4-10的LR(0)分析表，判定是否是LR(0)文法。

4-12（教材4-37）判定下列文法是哪一类LR文法，并构造LR分析表。
G[S]: S→(SR S→a R→，SR R→）

4-13（教材4-38） 下列文法是否是SLR（1）文法？若是，构造相应的SLR（1）分析表，若不是，则阐述其理由。
G[S]: S→Sab S→bR R→S R→a