第一章 绪论

计算机语言发展历程

• 第一代语言：机器语言
• 第二代语言：汇编语言
• 第三代语言：高级语言(如C，C++，Java等)
• 第四代语言：极高级领域语言(如SQL)
• 第五代语言：可视化配置语言
• 第六代语言：自然语言

什么是编译？

编译的本质是翻译（将源语言翻译成目标语言）

• 将汇编语言翻译成机器语言的过程称为汇编
• 将高级语言翻译成汇编语言或者机器语言的过程称为编译

编译器和解释器的区别：

• 编译器直接将源程序翻译成目标程序进行执行
• 解释器直接读取源程序逐行执行

编译器在计算机语言中的位置

计算机-宏

宏（Macro），是一种批量批量处理的称谓。计算机科学里的宏是一种抽象(Abstraction)，它根据一系列预定义的规则替换一定的文本模式。解释器或编译器在遇到宏时会自动进行这一模式替换。

编译系统的结构

源语言 -> 语义分析 -> 目标语言

词法分析 -> 语法分析 -> 语义分析

语法制导翻译：将语法分析、语义分析、目标代码生成合并到一起的编译器技术被称为”语法制导翻译“

词法分析概述

词法分析(lexical analysis/scanning)从左到右逐行扫描源程序的字符，识别出各个词素(lexeme)序列(即单词)，确定单词的类型，将识别出的单词转化为机内表示形式-词法单元(token)的形式

token的组成结构：token<种别码,属性值>

单词类型	种别	种别码
关键词	Select,from,where,then,if,else …	一词一码
标识符	变量名,数组名,函数名,过程名 …	多次一码
常量	整型,布尔型,浮点型,字符型 …	一型一码
运算符	算数(+ - * / %)关系(> < >= <= !=)逻辑(& | !)	一词一码或一型一码
界限符	; () {} …	一词一码

语法分析概述

语法分析器(syntax analysis/parser)从词法分析器输出的token序列中识别出各类短语，并构造语法分析树(parse tree)

语法分析描述了句子的结构

语法树对应句子：In the room,he broke a window with a hammer;

语义分析概述

语义分析(semantic analysis)使用语法树和符号表中的信息来检查源程序是否符合语言定义，其主要任务：

• 收集标识符的属性信息
  • 种属(Kind):简单变量、符合变量、过程
  • 类型(Type):整型、实型、布尔型、指针
  • 存储位置和长度
  • 值
  • 作用域
  • 参数和返回值类型
• 语义检查：是否符合语法规则

中间代码生成

前端编译器完成工作通常会输出一种或多种中间代码，常用的中间代码表示形式如下

• 三地址码(每个指令最多有三个操作数(operand))

  • 意义: 三地址指令序列唯一确定了运算完成的顺序
  • 表示形式
    • 四元式 (Quadruples): (op, y, z, x)
    • 三元式 (Triples)
    • 间接三元式 (Indirect triples)

• 语法结构树/语法树(syntax trees)

• 示例

  

代码优化

为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾

• 机器无关代码优化应用于中间代码阶段优化

• 机器相关代码优化应用于目标代码阶段优化

目标代码生成

• 目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言

• 目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器

符号表(Symbol table)

符号表数据结构为每个变量名字创建一个记录条目，记录的字段就是名字的各个属性。

文法

文法用于描述程序设计语言的语法结构（定义语言规则），文法解决了无穷语言的有穷表示问题

基础概念

∑表示字母表，字母表是一个有穷字符集合

乘积

字母表∑1和∑2的乘积

• ∑1∑2 = {ab|a ∈ ∑1, b ∈ ∑2}

• 例：{0, 1} {a, b} ={0a, 0b, 1a, 1b}

幂

字母表∑的n次幂

• ∑0 = {ε}

• ∑n =∑n-1 ∑ , n ≥ 1

例： {0, 1}3 ={0, 1} {0, 1} {0, 1} = {000, 001, 010, 011, 100, 101, 110, 111}

字母表的n次幂：长度为n的符号串构成的集合

正闭包

字母表∑的正闭包

∑+ = ∑ ∪ ∑2 ∪ ∑3 ∪ …

例：{a, b, c, d }+ = {a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}

字母表的正闭包：长度正数的符号串构成的集合

克林闭包

字母表∑的克林闭包

∑* = ∑0 ∪ ∑+ = ∑0 ∪ ∑ ∪ ∑2 ∪ ∑3 ∪ …

例：{a, b, c, d }* = {ε, a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}

字母表的克林闭包：任意符号串（长度可以为零）构成的集合

串

设∑是一个字母表，Vx∈∑*，x称为是∑上的一个串

• 串是字母表中符号的一个有穷序列

串s的长度，通常记作|s|，是指s中符号的个数

• 例: |aab|=3

• 空串是长度为0的串，用 ε（epsilon）表示

• |ε|= 0

串的运算

• 连接：如果 x和y是串，那么x和y的连接(concatenation)是把y附加到x后面而形成的串，记作xy
  • 空串是连接运算的单位元( identity)，即，对于任何串s都有，εs = sε = s
  • 设x,y,z是三个字符串，如果 x=yz，则称y是x的前缀，z是x的后缀
• 幂：串s的n次幂，将n个s连接起来
  • s0= ε， sn = sn-1s, n ≥1
  • s1 = s0 s = εs = s，s2 = ss，s3 = sss，…

文法的定义

1. 文法的形式化定义

   G = (Vt , Vn , P , S )

   Vt：终结符集合

   终结符（terminal symbol）是文法所定义的语言的基本符号，有时也称为token

   ➢例: Vt = { apple, boy, eat, little }

   Vn：非终结符集合

   非终结符(nonterminal) 是用来表示语法成分的符号，有时也称为“ 语法变量”

   ➢例: Vn = { <句子>, <名词短语>, <动词短语>, <名词>, … }

   P ：产生式集合

   产生式( production)描述了将终结符和非终结符组合成串的方法,产生式的一般形式：α→β,读作：α定义为β

   ➢α∈(Vt∪Vn)+：且α中至少包含Vn中的一个元素：称为产生式的头 (head )或左部(left side)

   ➢β∈(Vt∪Vn)* ：称为产生式的体(body)或右部(right side)

   ➢例：

   

   S ：开始符号

   S∈Vn。开始符号(start symbol)表示的是该文法中最大的语法成分

   ➢例：S = <句子>

   Vt ∩ Vn = Φ

   Vt ∪ Vn ：文法符号集

2. 产生式的简写

   对一组有相同左部的α产生式: α→β1, α→β2, … , α→βn

   可以简记为：α→β1| β2| … | βn

   读作：α定义为β1，或者β2，…，或者βn

   β1，β2，…，βn称为α的候选式(Candidate)

语言的定义

推导 (Derivations)和归约(Reductions)

• 推导

  给定文法G=(Vt , Vn , P , S )，如果 α→β ∈ P，那么可以将符号串γαδ中的α替换为β，也就是说，将γαδ重写(rewrite)为γβδ，记作 γαδ => γβδ。此时，称文法中的符号串 γαδ 直接推导(directly derive)出 γβδ

  简而言之，推导就是用产生式的右部替换产生式的左部

  如果α0=>α1，α1=>α2，α2=>α3，…，αn-1=>αn，则可以记作α0=>α1=>α2=>α3=> …=> αn-1=>αn，称符号串 α0经过n步推导出αn，可简记为α0 =>n αn

  ➢ α =>0 α

  ➢ =>+表示“经过正数步推导”

  ➢ =>*表示“经过若干（可以是0）步推导”

• 规约

  规约是推导的逆过程，他是用产生式的左部替换成产生式的右部的过程

句型和句子

• 句型：如果 S =>* α，α∈(VT∪VN)*，则称α是G的一个句型(sentential form),一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串

• 句子：如果 S =>* w，w ∈ Vt*，则称w是G的一个句子(sentence),句子是不包含非终结符的句型

语言

• 形式化定义

  由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G)。即L(G) = {w | S =>* w,w∈Vt* }

• 语言的运算

  

文法分类

Chomsky文法分类体系

• 0型文法 (Type-0 Grammar)

  无限制文法(Unrestricted Grammar)/短语结构文法(Phrase Structure Grammar, PSG )

  ∀α → β∈P，α中至少包含1个非终结符

  0型语言: 由0型文法G生成的语言L(G)

• 1型文法 (Type-1 Grammar)

  上下文有关文法(Context-Sensitive Grammar,CSG)

  ∀α → β∈P，｜α｜≤｜β｜(在0型文法基础上要求左部长度小于等于右部长度)

  产生式的一般形式： α1Aα2 → α1βα2 (β≠ε) (即CSG中不包含ε产生式)

  上下文有关语言（1型语言）: 由上下文有关文法(1型文法)G生成的语言L(G)

• 2型文法 (Type-2 Grammar)

  上下文无关文法 (Context-Free Grammar, CFG)

  ∀α → β∈P，α ∈ Vn (左部必须是一个非终结符)

  产生式的一般形式：A→β

  上下文无关语言（2型语言）: 由上下文无关文法 (2型文法) G生成的语言L(G)

• 3型文法 (Type-3 Grammar)

  正则文法 (Regular Grammar, RG)

  右线性(Right Linear)文法： A→wB 或 A→w (满足2型文法)

  左线性(Left Linear) 文法： A→Bw 或 A→w (满足2型文法)

  左线性文法和右线性文法都称为正则文法

  正则语言（3型语言）: 由正则文法 (3型文法) G生成的语言L(G)

  ​ 正则文法能描述程序设计语言的多数单词

• 四种文法之间的关系

  

上下文无关文法分析树

上下文无关文法用于描述语言的语法构造，也是应用最广发的一种文法

• CFG分析树定义

  

• 分析树是推导的图形化表示

  给定一个推导 S => α1 => α2 => … => αn ，对于推导过程中得到的每一个句型αi，都可以构造出一个边缘为αi的分析树

  • 例

    

• (句型的）短语

  给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语(phrase)，如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase)。

  

  • 例

    

• 二义性文法(Ambiguous Grammar)

  如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的

  • 例

    

    

    • 对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的
      • 满足，肯定无二义性
      • 不满足，也未必就是有二义性的

第二章 词法分析

正则表达式

正则表达式(Regular Expression，RE )是一种用来描述正则语言的更紧凑的表示方法

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义（表示）一个语言，记为L(r)。这个语言也是根据r的子表达式所表示的语言递归定义的

• 正则表达式的定义

  

• 正则语言

  可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

• RE代数定律

  

• 正则文法和正则表达式是相互等价的

  对任何正则文法G，存在定义同一语言的正则表达式r

  对任何正则表达式r，存在生成同一语言的正则文法G

• 正则定义（Regular Definition）

  给一些RE命名，并在之后的RE中想使用字符表中的符号一样使用这些名字

  

有穷自动机(FA)

有穷自动机 ( Finite Automata，FA )由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

• FA模型

  

• FA的表示

  转换图 (Transition Graph)

  • 结点：FA的状态

    • 初始状态（开始状态）：只有一个，由start箭头指向
    • 终止状态（接收状态）：可以有多个，用双圈表示

  • 带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

  

• FA定义（接收）的语言

  给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收

  由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L(M)

  

• 最长子串匹配原则(Longest String Matching Principle)

  当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配

  

• 有穷状态机的分类

  • 两种分类

    确定的FA (Deterministic finite automata, DFA)

    非确定的FA (Nondeterministic finite automata, NFA)

  • 确定的有穷自动机(DFA)

    形式化定义：目标状态确定唯一

    

    例：

    ​ 

    

      - DFA既可以用转换图表示，也可以用转换表表示，转换图和转换表的功能是等价的
    

  • 非确定的有穷自动机(NFA)

    形式化定义：目标状态不唯一，是一个集合

    

    例：

    ​ 

    

    带有“ε-边”的NFA

    

    • 带有和不带有“ε-边”的NFA的等价性

      

  • DFA和NFA的等价性

    • 对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D

    • 对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N

    DFA和NFA可以识别相同的语言

    例：

    ​ 

    

    • 正则文法和正则表达式是等价的

    • 正则表达式和NFA是等价的

    • 正则文法和NFA是等价的

    等价的NFA和DFA都可以识别同一语言，但是从表现形式上看，NFA要比DFA更直观，但是从计算机实现上来看，DFA要比NFA容易实现

    DFA的算法实现

    

从正则表达式到有穷自动机

正则表达式可以很容易描述符号序列，但是在真正构造分析器时实际上模拟的是DFA，因此这就涉及到了从正则表达式到有穷自动机的转换。

• 从正则表达式直接构造DFA是比较困难的；
• NFA相对于DFA比较直观，因此我们先从RE转换成等价的NFA；然后再将等价的NFA转换成DFA

1. 根据RE构造NFA

   

   

   - RE构造NFA可以逐步分解达成
   

1. 根据NFA构造DFA

   子集构造法（subset construction）实现从NFA到DFA的转换(DFA中每个状态都是NFA状态子集)，算法如下：

   

   计算 ε-closure (T)：

   

   例：

   

1. 从RE->NFA->DFA示例

   

   ---

   

1. 词法分析阶段的错误处理

   如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序，查找已扫描字符串中最后一个对应于某终态的字符

   • 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词

   • 如果没找到，则确定出错，采用错误恢复策略

   错误恢复策略

   • 恐慌模式(panic mode)

第三章 语法分析

语法分析的任务就是根据给定的文法识别输入串中的短语并构造分析树的过程，当各个短语分别分散在分析树的各个叶子节点，我们说输入的串构成一个句子。构造分析树通常有以下两种方法：

• 自顶向下的语法分析(Top-Down Parsing)
• 自底向上的语法分析(Down-Up Parsing)

自顶向下的语法分析(Top-Down Parsing)

从分析树的顶部（根节点）向底部（叶节点）方向构造分析树（通过文法匹配串）

可以看成是从文法开始符号S推导出词串w的过程，例：

每一步推导中，都需要做两个选择

• 替换当前句型中的哪个非终结符

• 用该非终结符的哪个候选式进行替换

为了解决这个问题，下面让我们看两个概念：

1. 最左推导(Left-most Derivation)

在最左推导中，总是选择每个句型的最左非终结符进行替换，例：

• 最右规约是最左推导的逆过程

如果 S =>*lm α，则称α是当前文法的最左句型(left-sentential form)

1. 最右推导(Right-most Derivation)

在最右推导中，总是选择每个句型的最右非终结符进行替换

• 最左规约是最右推导的逆过程

• 注：在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导

最左推导和最右推导的唯一性

• 分析树的推导结果是不唯一的，但是最左推导和最右推导结果是唯一的，因为最左/最右非终结符始终是唯一的

自顶向下的语法分析采用最左推导方式

• 总是选择每个句型的最左非终结符进行替换

• 根据输入流中的下一个终结符，选择最左非终结符的一个候选式

自顶向下语法分析的通用形式（计算机实现方式）

递归下降分析 (Recursive-Descent Parsing)

• 由一组过程组成，每个过程对应一个非终结符（即：文法中有多少个非终结符就有多少个过程）

• 从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析

过程A示例：

• 回溯会影响分析器的效率，需要回溯的分析器成为不确定的分析器

预测分析(Predictive Parsing)

• 预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式。

  • 可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类

• 预测分析不需要回溯，是一种确定的自顶向下分析方法

自定向下分析遇到的问题？

并不是所有文法都适合自顶向下分析方法，为了适应自顶向下分析方法，有时我们需要对文法进行改造。

1. 问题1：同一非终结符的多个候选式存在共同前缀，将导致回溯现象

   

   解决方法：提取左公因子(Left Factoring)

   算法：

   

   例：

   

2. 问题2：左递归文法会使递归下降分析器陷入无限循环

   

• 左递归定义：产生式右部最左非终结符和左部相同就会产生左递归

  含有A→Aα形式产生式的文法称为是直接左递归的 (immediate left recursive)

  如果一个文法中有一个非终结符A使得对某个串α存在一个推导A=>+Aα ，那么这个文法就是左递归的

  经过两步或两步以上推导产生的左递归称为是间接左递归的

  解决方法：消除左递归

  • 消除左递归算法

    

    消除直接左递归

    ​ 一般形式：

    

    ​ 例(消除直接左递归)：

    

    ​ 例(消除间接左递归-带入方法)：

    

LL(1)文法(应用预测分析技术)

S_文法

• 预测分析法的工作过程

  从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

• S_文法（简单的确定性文法，Korenjak & Hopcroft，1966）

  • 每个产生式的右部都以终结符开始

  • 同一非终结符的各个候选式的首终结符都不同

  • S_文法不含ε产生式

    • 为什么不能应用ε产生式：

      

      ε产生式的使用取决于当前非终结符后边可以跟随哪些终结符

非终结符的后继符号集(follow集)

​ 可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)，FOLLOW(A)={a| S =>* αAaβ, a∈Vt，α,β∈(Vt ∪ Vn)*}

​ 例：

产生式的可选集

​ 产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT(A→β)

​ 即遇到这些非终结符可以使用该产生式

• SELECT(A→aβ) = {a}

• SELECT(A→ε)=FOLLOW(A)

q_文法

每个产生式的右部或为ε，或以终结符开始

具有相同左部的产生式有不相交的可选集

q_文法不含右部以非终结符打头的产生式

串首终结符集(first集)

串首终结符:串首第一个符号，并且是终结符,简称首终结符

LL(1)文法

第一个“L”表示从左向右扫描输入

第二个“ L”表示产生最左推导

“1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作

• 同一非终结符的各个产生式的可选集互不相交可以为LL(1)文法构造预测分析器

FIRST集/FOLLOW集/SELECT集/预测分析表的构建方法

问题1:计算文法符号X的FIRST(X)

定义：

FIRST(X)：可以从X推导出的所有串首终结符构成的集合,如果 X =>* ε，那么 ε ∈ FIRST(X)

算法：

不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

• 如果X是一个终结符，那么FIRST(X) = {X}

• 如果X是一个非终结符，且X→Y1…Yk∈P(k≥1)，那么如果对于某个i，a在FIRST(Yi)中且ε在所有的FIRST(Y1),…,FIRST(Yi-1)中(即Y1…Yi-1 =>* ε)，就把a加入到FIRST(X)中。如果对于所有的j=1,2,…,k，ε在FIRST(Yj)中，那么将ε加入到FIRST(X)

• 如果X→ε ∈ P，那么将ε加入到FIRST(X)中

例：计算下面算术表达式文法每个非终结符的FIRST集？

问题2:计算串X1X2…Xn的FIRST集合

• 向FIRST(X1X2…Xn)加入FIRST(X1)中所有的非ε符号

• 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；

  如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推

• 最后，如果对所有的i，ε都在FIRST(Xi)中，那么将ε加入到FIRST(X1X2…Xn)中

问题3:计算非终结符A的FOLLOW(A)

定义：

FOLLOW(A)：可能在某个句型中紧跟在A后边的终结符a的集合

• FOLLOW(A)={a|S =>* αAaβ, a ∈ Vt，α,β ∈ (Vt ∪ Vn)*}

如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中

算法：

不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止

将$放入FOLLOW(S)中，其中S是开始符号，$是输入右端的结束标记

如果存在一个产生式A→αBβ，那么FIRST(β)中除ε之外的所有符号都在FOLLOW( B )中

如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST(β) 包含ε，那么 FOLLOW(A)中的所有符号都在FOLLOW(B)中

例：计算下面算术表达式文法每个非终结符的FOLLOW集？

• 一个终结符中的follow集合可能会依赖于另一个非终结符中的follow集合，比如E`的follow集合依赖于E的follow集合

问题4:计算产生式的SELECT集

产生式的SELECT集合算法依赖于FIRST集合和FOLLOW集合

例：算术表达式文法各产生式的SELECT集？

• 第2个产生式和第3个产生式的产生式具有相同的左部，select集合不相交
• 第5个产生式和第6个产生式的产生式具有相同的左部，select集合不相交

问题5:构建LL(1)文法的预测分析表

对于LL(1)文法，可以根据产生式的select集合构造文法的预测分析表。

例：算术表达式LL(1)文法的预测分析表

LL(1)文法的分析方法

递归的预测分析法

定义

• 递归的预测分析法是指：在递归下降分析中，根据预测分析表进行产生式的选择

• 根据每个非终结符的产生式和LL(1)文法的预测分析表，为每个非终结符编写对应的过程

  

算法示例

非递归的预测分析法

定义

非递归的预测分析不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析

下推自动机算法示例

输出对应着最左推导

表驱动的预测分析法

输入：一个串w和文法G的分析表 M

输出：如果w在L(G )中，输出w的最左推导；否则给出错误指示

方法：最初，语法分析器的格局如下：输入缓冲区中是w$，G的开始符号位于栈顶，其下面是$。下面的程序使用预测分析表M生成了处理这个输入的预测分析过程

递归的预测分析法VS非递归的预测分析法

预测分析法实现步骤

1）构造文法

2）改造文法：消除二义性、消除左递归、消除回溯

3）求每个变量的FIRST集和FOLLOW集，从而求得每个候选式的SELECT集

4）检查是不是LL(1)文法。若是，构造预测分析表

5）对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法

预测分析中的错误处理

预测分析中的错误检测

两种情况下可以检测到错误

• 栈顶的终结符和当前输入符号不匹配

• 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

预测分析中的错误恢复

恐慌模式

• 忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元
  • 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
  • 例如可以把FOLLOW(A)中的所有终结符放入非终结符A的同步记号集合
• 如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符

---

例-构造同步词法单元

​ Synch表示根据相应非终结符的FOLLOW集得到的同步词法单元

---

分析表的使用方法

如果M[A,a]是空，表示检测到错误，根据恐慌模式，忽略输入符号a

如果M[A,a]是synch，则弹出栈顶的非终结符A，试图继续分析后面的语法成分

如果栈顶的终结符和输入符号不匹配，则弹出栈顶的终结符

---

例：分析表工作原理

自底向上语法分析(Down-Up Parsing)

自底向上语法分析概述

从分析树的底部(叶节点)向顶部(根节点)方向构造分析树

可以看成是将输入串w归约为文法开始符号S的过程

自顶向下的语法分析采用最左推导方式

• 自底向上的语法分析采用最左归约方式（反向构造最右推导）

自底向上语法分析的通用框架

• 移入-归约分析(Shift-Reduce Parsing)

例(移入-归约分析)：

​ 栈内符号串 + 剩余输入 = “规范句型”

移入-归约分析的工作过程

在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止

然后，它将β归约为某个产生式的左部

语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止

移入-归约分析器可采取的4种动作

移入：将下一个输入符号移到栈的顶端

归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串

接收：宣布语法分析过程成功完成

报错：发现一个语法错误，并调用错误恢复子例程

移入-归约分析中存在的问题

移入-归约分析中每次规约的应该是直接短语

直接短语：高度为2的子树，直接短语一定是某个产生式的右部，但是产生式的右部不一定是直接短语

LR分析法概述

LR分析法

LR文法(Knuth, 1963) 是最大的、可以构造出相应移入-归约语法分析器的文法类

• L: 对输入进行从左到右的扫描

• R: 反向构造出一个最右推导序列

LR(k)分析

• 需要向前查看k个输入符号的LR分析
• k = 0 和 k = 1 这两种情况具有实践意义当省略(k)时，表示k=1

LR分析法的基本原理

如何正确识别句柄？

• 句柄是逐步形成的，用“状态”表示句柄识别的进展程度

  

LR分析器(自动机)的总体结构

• 例：LR分析表的结构

  • 

  • 

  • 

  • 

  • 

  • 

• LR分析器的工作过程

  • 

  • 

  • 

LR分析算法

输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数。

输出：如果w在 L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示。

方法：初始时，语法分析器栈中的内容为初始状态s0，输入缓冲区中的内容为w$。然后，语法分析器执行下面的程序：

​ LR分析算法最关键点在于分析表的构造

LR(0)分析

LR(0)项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）: A → α1·α2

增广文法(Augmented Grammar)

如果G是一个以S为开始符号的文法，则G的增广文法G’就是在G中加上新开始符号S’和产生式S’ → S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态

文法中的项目

后继项目（Successive Item）

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目

A→α·Xβ的后继项目是A→αX·β

• 这15个项目中是否会有某些项目是等价的？

  

  ​ 在一个项目中，原点后边存在非终结符时就存在等价项目

  ​ 可以把等价的项目组成一个项目集(I) ，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态

例：LR(0)自动机(如何根据文法构造LR0自动机？)

LR(0)分析表构造算法

1. 两个基本算法：

CLOSURE()函数(LR(0)每个状态都是项目集闭包)

• 计算给定项目集I的闭包: CLOSURE(I) = I ∪ {B→·γ | A→α·Bβ ∈ CLOSURE(I),B→γ∈P}

  

GOTO()函数

• 返回项目集I对应于文法符号X的后继项目集闭包: GOTO(I, X)=CLOSURE({A→αX·β | A→α·Xβ∈I})

  

1. 构造LR(0)自动机的状态集

规范LR(0)项集族(Canonical LR(0) Collection) C={I0}∪{I | 3J ∈ C, X ∈ Vn ∪ Vt, I=GOTO(J,X)}

1. LR(0)分析表构造算法

1. LR(0)自动机的形式化定义

1. LR(0)分析过程中的冲突

• 移进/归约冲突

  

  

• 归约/归约冲突

  

LR(0)存在冲突的根本原因是该文法并不会向前看多个字符，进而导致多分支冲突

SLR分析

• LR(0)分析过程中的冲突

  

• SLR分析法的基本思想

  

• 例子中的表达式文法的SLR分析表

  

• SLR分析法示例2

  

• SLR分析表构造算法

  

• SLR 分析中的冲突

  

  通过示例可以看到，SLR 分析仅利用follow集来处理冲突是不够的！

• SLR分析存在的问题

  SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A)，但b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件

LR(1)分析

• LR(1)分析法的提出

  

  LR(1)分析法引入了特定位置A的后继符集合概念

• 规范LR(1)项目

  

• 等价LR(1)项目

  

• 示例：LR(1)自动机(如果给给定文法构造LR(1)自动机？)

  

  

  如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的

• LR(1)项目集闭包

  

• LR(1)GOTO函数

  

• 为文法G’构造LR(1)项集族

  

• LR(1)自动机的形式化定义

  

• LR分析表构造算法

  

LALR分析法

• LALR(lookahead-LR)分析的基本思想

  

• 例：合并同心项集

  

• 示例：合并同心项目集产生问题案例

  

  

• LALR(1)的特点

  • 形式上与LR(1)相同

  • 大小上与LR(0)/SLR相当

  • 分析能力介于SLR和LR(1)二者之间

    SLR<LALR(1)<LR(1)

  • 合并后的展望符集合仍为FOLLOW集的子集

二义性文法的LR分析

• 二义性文法的特点

  

• 例1：二义性算术表达式文法

  

  

• 例2：二义性if语句文法的LR分析

  

  

  

• 二义性文法的使用

  应该保守地使用二义性文法，并且必须在严格控制之下使用，因为稍有不慎就会导致语法分析器所识别的语言出现偏差

LR分析中的错误处理

• 语法错误的检测

  当LR分析器在查询分析表并发现一个报错条目时，就检测到了一个语法错误

• 错误恢复策略

  • 恐慌模式错误恢复

  • 短语层次错误恢复

• 恐慌模式错误恢复

  

• 短语层次错误恢复

  • 检查LR分析表中的每一个报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误

  • 然后构造出适当的恢复过程

  

  

第四章 语法制导翻译

概念

• 什么是语法制导翻译?

  

• 语法制导翻译的基本思想

  • 如何表示语义信息？

    • 为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息

  • 如何计算语义属性？

    • 文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的
    • 对于给定的输入串x ，构建x的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值

• 两个概念

  将语义规则同语法规则（产生式）联系起来要涉及两个概念

  • 语法制导定义(Syntax-Directed Definitions, SDD)

  • 语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT)

• 语法制导定义(SDD)

  • SDD是对CFG的推广

    • 将每个文法符号和一个语义属性集合相关联
    • 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值

  • 如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值

  

• 语法制导翻译方案(SDT)

  SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内

  

  一个语义动作在产生式中的位置决定了这个动作的执行时间

• SDD与SDT

  • SDD

    • 是关于语言翻译的高层次规格说明
    • 隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序

  • SDT

    • 可以看作是对SDD的一种补充，是SDD的具体实施方案
    • 显式地指明了语义规则的计算顺序，以便说明某些实现细节

语法制导定义SDD

语法制导定义SDD是对CFG的推广

• 将每个文法符号和一个语义属性集合相关联

• 将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值

文法符号的属性

• 综合属性 (synthesized attribute)
• 继承属性 (inherited attribute)

综合属性(synthesized attribute)

例：

继承属性(inherited attribute)

例：

属性文法 (Attribute Grammar)

一个没有副作用的SDD有时也称为属性文法

• 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

SDD的求值顺序

SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值

按照什么顺序计算属性值？

• 语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值

依赖图(Dependency Graph)

• 依赖图是一个描述了分析树中结点属性间依赖关系的有向图

• 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点

• 如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

例:

属性值的计算顺序

• 可行的求值顺序是满足下列条件的结点序列N1, N2, … , Nk ：如果依赖图中有一条从结点Ni到 Nj的边(Ni→Nj), 那么i < j（即：在节点序列中，Ni排在Nj 前面）

• 这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topological sort)

例:

对于只具有综合属性的SDD ，可以按照任何自 底向上的顺序计算它们的值

对于同时具有继承属性和综合属性的SDD，不 能保证存在一个顺序来对各个节点上的属性进行求值

• 从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系

• 幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图

• 不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现

  • S-属性定义 (S-Attributed Definitions, S-SDD)
  • L-属性定义 (L-Attributed Definitions, L-SDD)

S-属性定义与L-属性定义

• S-属性定义

  

• L-属性定义

  L-属性定义(也称为L属性的SDD或L-SDD)的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左(因此称为L属性的，L是Left的首字母)

  一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi (1<= i <= n)的继承属性仅依赖于下列属性：

  • A的继承属性

  • 产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性

  • Xi本身的属性，但Xi 的全部属性不能在依赖图中形成环路

  每个S-属性定义都是L-属性定义

  例1：

  

  例2：

  

语法制导翻译方案SDT

SDT

• 语法制导翻译方案(SDT )是在产生式右部中嵌入了程序片段(称为语义动作)的CFG

  

• SDT可以看作是SDD的具体实施方案

• 本节主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可在语法分析过程中实现

  • 基本文法可以使用LR分析技术，且SDD是S属性的
  • 基本文法可以使用LL分析技术，且SDD是L属性的

将S-SDD转换为SDT

​ 

S-属性定义的SDT实现

​ 

扩展的LR语法分析栈

​ 

将语义动作中的抽象定义式改写成具体可执行的栈操作

​ 

示例：在自底向上语法分析栈中实现桌面计算器

• 

• 

• 

• 

• 

• 

• 

• 

• 

• 

将L-SDD转换为SDT

将L-SDD转换为SDT的规则

• 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
• 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

例：

L-属性定义的SDT实现

如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现

例：

• LL-在非递归的预测分析过程中进行语义翻译

• LL-在递归的预测分析过程中进行语义翻译

• LR-在LR分析过程中进行语义翻译

在非递归的LL预测分析过程中进行翻译

首先需要扩展语法分析栈

示例：

分析栈中的每一个记录都对应着一段执行代码

综合记录出栈时，要将综合属性值复制给后面特定的语义动作

变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作

示例：语义动作可以直接定义成代码片段

在递归的LL预测分析过程中进行翻译

算法

• 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量

• 非终结符A的代码根据当前的输入决定使用哪个产生式

• 与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的词法单元、非终结符及语义动作

  • 对于带有综合属性x的词法单元 X，把x的值保存在局部变量X.x中；然后产生一个匹配 X的调用，并继续输入

  • 对于非终结符B，产生一个右部带有函数调用的赋值语句c := B(b1 , b2 , …, bk)，其中， b1 , b2 , …, bk是代表B的继承属性的变量，c是代表B的综合属性的变量

  • 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用

示例

L-属性定义的自底向上翻译

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

示例

将语义动作改写为可执行的栈操作

• 给定一个以LL文法为基础的L-属性定义，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD
  • 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性，并在产生式后端放置语义动作计算综合属性
  • 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε
  • 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a’ ，并且将a’关联到M→ε 上。动作a'
    • (a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
    • (b) 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性

第五章 中间代码生成

中间代码输入程序片段，输出3地址码。

类型表达式

• 基本类型表达式

  integer

  real

  char

  boolean

  type_error (出错类型)

  void (无类型)

• 类型名类型表达式

  可以为类型表达式命名，类型名也是类型表达式

• 类型构造符(type constructor)类型表达式

  将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式

  • 数组构造符array

    若T是类型表达式，则array(I,T)是类型表达式(I是一个整数)

    类型	类型表达式
    int[3]	array(3,int)
    int[2][3]	array(2,array(3,int))

  • 指针构造符pointer

    若T是类型表达式，则pointer(T)是类型表达式，它表示一个指针类型

  • 笛卡尔乘积构造符X

    若T1和T2是类型表达式，则笛卡尔乘积T1XT2是类型表达式

  • 函数构造符→

    若T1、T2、…、Tn和R是类型表达式，则T1xT2x…xTn→R是类型表达式

  • 记录构造符record

    若有标识符N1、N2、…、Nn与类型表达式T1、T2、…、Tn，则record((N1 x T1 ) x ( N2 x T2 ) x … x (Nn x Tn))是一个类型表达式

• 例

  

声明语句的翻译

• 局部变量的存储分配

  对于声明语句，语义分析的主要任务就是收集标识符的类 型等属性信息，并为每一个名字分配一个相对地址

  • 从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)

  • 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址

  名字的类型和相对地址信息保存在相应的符号表记录中

• 变量声明语句的SDT

  

• 示例

  

  

简单赋值语句的翻译

• 赋值语句的基本文法

  ① S → id = E；

  ② E → E1 + E2

  ③ E → E1 * E2

  ④ E → -E1

  ⑤ E → (E1)

  ⑥ E → id

• 赋值语句翻译的任务

  

• 赋值语句的SDT

  

• 增量翻译(Incremental Translation)

  

• 示例

  

  

  

  

  

  

  

  

数组引用的翻译

• 赋值语句的基本文法

  S → id = E; | L = E;

  E → E1 + E2 | -E1 | (E1) | id | L

  L → id[E] | L1[E]

• 数组引用的翻译的目标

  将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址

• 数组元素寻址(Addressing Array Elements)

  

• 示例

  

• 带有数组引用的赋值语句的翻译

  

  

• 数组引用的SDT

  

  

控制流语句的翻译

• 控制流语句的基本文法

  P → S

  S → S1S2

  S → id = E; | L = E;

  S → if B then S1

  | if B then S1 else S2

  | while B do S1

• 控制流语句的代码结构

  

• 控制流语句的SDT

  

  

  

  

• 布尔表达式及其SDT

  • 布尔表达式的基本文法

    

    

  • 布尔表达式的SDT

    

• 小结

  任何SDT都可以通过下面的方法实现

  • 首先建立一棵语法分析树，然后按照从左到右的深度优先顺序来执行这些动作

  控制流语句SDT

  

文章作者 ChavinKing