阶段	输入	输出	描述体系
词法分析	源程序符号串	词法单元序列	正则文法
语法分析	词法单元序列	抽象语法书	上下文无关文法

1. 自顶向下
   1. LL 分析法
      1. First集合、Follow集合、分析表的构造
      2. 执行程序的运行
      3. LL(1)文法的充要条件
2. 自底向上

1 语法分析的功能、基本任务

• 功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查
• 基本任务：识别符号串S是否为某语法成分

2 自顶向下分析法

• 基本思想：若则否则。从根节点开始，一步一步往下推，看能不能退出来
• 主要问题
  • 左递归问题
    文法里面如果有 U := Ua，会推不出来，需要改写文法去掉左递归
  • 回溯问题
    文法里面如果有 U := Ua|b，当沿着一条路发现推不下去之后需要回溯回来重新走另一条路，效率低
• 主要方法
  • 递归子程序法
  • LL分析法

2.1 自顶向下分析的一般过程

给定符号串S，若预测它是某一语法成分，那么可根据该语法成分的文法，设法为S构造一棵语法树。

• 若成功，则S最终被识别为某一语法成分。即 其中 为某语言成分的文法。
• 若不成功，则 。
  例

  

1. 分析过程是带有预测的。U := Ua|b 时要预测走哪边
2. 分析过程是一种试探过程，是尽一切办法（选用不同规则）设法建立语法树的过程。由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。
3. 最左推导可以编出程序来实现，但在实际上价值不大，效率低，代价高。

2.2 自顶向下分析存在的问题及解决方法

2.2.1 左递归文法

有如下文法：令U是文法的任一非终结符，文法中有规则
∷ (直接) 或者 (简介)

方法 1-消除直接左递归：使用扩充的 BNF 表示来改写文法

1. 规则 1
   若：∷
   则可改写为：∷
   其中再若：
   则 ∷
   • 总把 安置成最后的选择！
     若有规则：∷
     则可以改写为：∷
     注意：不应写成∷
2. 规则 2
   若有文法规则：∷
   其特点是：具有一个直接左递归的右部并位于最后，这表明该语法类 U 是由 x 或 y…或 z 打头，其后跟随零个或多个 v 组成
   可以改写为 ∷

方法 2-消除直接左递归：将左递归规则改为右递归规则

3. 规则 3
   若：∷
   则可改写为：∷
   ∷

方法 3-消除所有左递归

1. 把G的非终结符整理成某种顺序 ，使得
   
   
   

for i:=1 to n do
	begin
	for j :=1 to i-1 do
		把每个形如Ai∷= Aj r的规则替换成
		Ai ∷= (δ1 |δ2 |……|δk ) r
		其中Aj∷=δ1 |δ2 |……|δk是当前Aj 的全部规则
		消除Ai 规则中的直接左递归
	end

3. 化简由 2 得到的文法，即去掉那些多余的规则。

2.2.2 回溯问题

• 造成回溯的条件
  文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确地确定所要的产生式，就可能出现回溯。
• 回溯带来的问题
  效率严重低下，只有在理论上的意义而无实际意义
• 效率低的原因
  1. 语法分析要重做
  2. 与语法分析同时进行的其他工作（语义分析）要推倒重来

[定义] 设文法G（不具左递归性），


表示能 能推出来的首个字符
为避免回溯，对文法的要求是:

需要他们能推出来的首个字符不能相交（即不能 ）
也即所有非终结符的产生式FIRST集互不相交

方法 1：改写文法

对具有多个右部的规则反复提取左因子

方法 2：超前扫描

当文法不满足避免回溯的条件时，即各选择的首符号相交时，可以采用超前扫描的方法，即向前侦察各输入符号串的第二个、第三个符号来确定要选择的目标
这种方法是通过向前多看几个符号来确定所选择的目标，从本质上来讲也有回溯的味道，因此比第一种方法费时，但是读的仅仅是向前侦察情况，不作任何语义处理工作。

2.2.3 总结

为了在不采取超前扫描的前提下实现不带回溯的自顶向下分析，文法需要满足两个条件：

1. 文法是非左递归的；
2. 对文法的任一非终结符，若其规则右部有多个选择时，各选择所推出的终结符号串的首符号集合要两两不相交。
   在上述条件下，就可以根据文法构造有效的、不带回溯的自顶向下分析器。

2.3 递归子程序法（递归下降分析法）

具体做法：对语法的每一个非终结符都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。
虽然没有左递归，但是还可能有其他递归，因此叫“递归子程序法”

说明：

• 非终结符号的分析子程序功能，是用规则右部符号串去匹配输入串。
• 要注意子程序之间的接口。在程序编制时，进入某个非终结符的分析程序前，其所要分析的语法成分的第一个符号已读入sym中了。
• 递归子程序法对应的是最左推导过程！

2.4 用递归子程序法构造语法分析程序的例子

2.5 LL 分析法

• LL(1)文法
  • 无左递归
  • 若 则
• LL－自左向右扫描、自左向右地分析和匹配输入串。
  ∴分析过程表现为最左推导的性质。

2.5.1 LL分析程序构造及分析过程

• 此过程有三部分组成
  • 分析表
  • 执行程序 (总控程序）
  • 符号栈 （分析栈）
    
• 在实际语言中，每一种语法成分都有确定的左右界符，为了研究问题方便，统一用‘＃’表示。

1 分析表：二维矩阵 M

2 符号栈（四种情况）

1. 开始状态
   
2. 工作状态
   
3. 出错状态
   
4. 结束状态
   

3 执行程序

执行程序主要实现如下操作:

1. 把 # 和文法识别符号 E 推进栈，并读入输入串的第一个符号 a，重复下述过程直到正常结束或出错。
2. 根据栈顶符号 X 和当前输入符号 a，执行如下操作：
   1. 若 ，分析成功，停止。E匹配输入串成功。
   2. 若 ，把 X 退出栈，再读入下一个符号。
   3. 若 ，转出错处理。
   4. 若 ，查分析表 。
      1. ，则将 弹出栈，将 逆序入栈。注： 在栈顶 （最左推导）
      2. 转出错处理
      3. 。a为X的后继符号，则将X弹出栈（不读下一符号）继续分析。

2.5.2 !!!分析表的构造

设有文法 :

1. FIRST 集：若则，该集合称为 的头符号集合
2. FOLLOW 集：为识别符号；特殊地：若则

1 构造 FIRST 集的算法

设 ，求

1. 求出组成 的每一个符号 的 FIRST 集合
   1. 若 ，则
   2. 若 且 ，则
   3. 若 且 ，则按如下顺序计算
      • 若 ，则将 加入
      • 若 ，则将 加入
      • 若 ，则将 加入
      • ...
      • 若 ，则将 加入
      • 若 ，则将 加入
      • 注意：要顺序从上往下做，一旦不满足条件，过程就要中断进行
2. 得到 ，即可求出

2 构造 FOLLOW 集的算法

求 FOLLOW(B)
设 ，连续使用以下规则直至 集合不在扩大

1. 若 B 为识别符号，则把"#"加入 中
2. 若 ，则把 加入
3. 若 或 且 则把 加入
   注意：FOLLOW 集合中不能有 !!!

3 构造分析表的算法

对于文法中任意一条规则 ，设 a 为任一终结符或#

1. 若 ，则将 放入 。
   表示 A 在栈顶，输入符号是 a，应选择 去匹配
2. 若 或 ，而且 ，则 即 放入
   表示 A 已匹配输入串成功，其后继符号终结符 a 由 A 后面的语法成分去匹配
3. 把所有无定义的 都标上 error

2.5.3 !!!LL(1)文法

• 定义：一个文法G，其分析表M不含多重定义入口（即分析表中无两条以上规则），则称它是一个LL(1)文法。

• 定理：文法G是LL(1)文法的充分必要条件是：对于G的每个非终结符A的任意两条规则A::=α|β,下列条件成立：

  1. Ф
  2. 若 , 则 Ф

• 用上述分析表的构造算法可以构造任何文法的分析表。但对于某些文法，有些M[A,a]中可能有若干条规则，这称为分析表的多重定义或者多重入口。

• 可以证明：如果 G 是左递归或二义的，那么M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。

• 反之，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的

• 左递归： 左递归由 ，则有 ，故有

• 二义文法：对文法所定义的某些句子存在着两（多）个最左推导，即在推导的某些步上存在多重定义，有两（多）条规则可用，所以分析表是多重定义的

• 有些文法可以从非 LL(1) 文法改写为 LL(1) 文法

• 但并不是所有的非 LL(1) 文法都能改写为 LL(1) 文法（如二义文法无法改写成 LL(1) 文法）

2.5.4 LL 分析的错误恢复

• 当符号栈顶的终结符和下一个输入符号不匹配，或栈顶是非终结符A，输入符号a，而M[A, a]为空白（即error）时，则分析发现错误。
• 错误恢复的基本思想是：跳过一些输入符号，直到期望的同步符号之一出现为止。
• 同步符号（可重新开始继续分析的输入符号）集合通常可按以下方法确定：
  1. 把 FOLLOW(A) 的所有符号加入A的同步符号集。如果我们跳读一些输入符号直到出现FOLLOW(A)的符号，之后把 A 从栈中弹出，继续往下分析即可。
  2. 只用 FOLLOW(A) 作为非终结符A的同步符号集是不够的(容易造成跳读过多，如输入串中缺少语句结束符分号时)。此时可将作为语句开头的关键字加入它的同步符号集，从而避免这种情况的发生。
  3. 把 FIRST(A) 的符号加入非终结符A的同步符号集中。
  4. 如果非终结符A可以产生空串，那么推导ε的产生式可以作为缺省的情况。这样做可以推迟某些错误检查，但不会漏过错误。
  5. 如果终结符在栈顶而不能匹配，则可弹出该终结符并发出一条信息后继续分析。这好比把所有其他符号均作为该符号的同步集合元素。

3 自底向上分析法

• 基本思想：若则否则。从输入符号串开始，通过反复查找当前句型的句柄（最左简单短语），并利用有关规则进行规约。若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子；否则有语法错误
• 主要问题
  • 句柄的识别问题
  • 若两个以上规则的右部都有相同的符号串且构成句柄，选哪个候选式
• 主要方法
  • 算符优先分析法
  • LR 分析法
• 分析过程(重复以下步骤)
  1. 找出当前句型的句柄 x （或句柄的变形）；
  2. 找出以 x 为右部的规则 X::= x ；
  3. 把 x 规约为X，产生语法树的一枝。

3.1 自底向上分析的一般过程 （移进-归约分析）

要点：设置符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约

分析过程：

1. 把输入符号串按顺序一个一个地移进符号栈（一次移一个）；
2. 检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约——将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号；
3. 分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。

这一方法简单明了，不断地进行移进规约。关键是确定当前句型的句柄。
说明：

1. 例子的分析过程是一步步地规约当前句型的句柄。该句子的唯一语法树为：
   
   注意两点：
   ① 栈内符号串 + 未处理输入符号串 = 当前句型
   ② 句柄都在栈顶
   实际上，以上分析过程并未真正解决句柄的识别问题。
2. 未真正解决句柄的识别问题
   上述分析过程中识别句柄的过程，主要看栈顶符号串是否形成规则的右部。
   这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。
   因为不能认为：对句型 xuy 而言，若有U∷= u，即U => u 就断定u是简单短语，u 就是句柄，而是要同时满足 。

3.2 LR 分析法

3.2.1 什么是 LR 分析

1. LR分析：从左到右扫描(L)自底向上进行规约(R)(是规范规约，也即最右推导）
   是自底向上分析方法的高度概括和集中
   历史 + 展望 + 现状 => 句柄
2. LR 分析法的优缺点:
   1. 适合文法类足够大，适用于所有上下文无关文法
   2. 分析效率高
   3. 报错及时
   4. 可以自动生成
   5. 但手工实现工作量大
3. LR 分析器有三部分：状态栈、分析表、控制程序
   • 状态栈：放置分析器状态和文法符号。
   • 分析表：由两个矩阵组成，其功能是指示分析器的动作，是移进还是规约，根据不同的文法类要采用不同的构造方法。
   • 控制程序：执行分析表所规定的动作，对栈进行操作。
     
4. 分析表的种类
   1. SLR 分析表（简单 LR 分析表）
      构造简单，最易实现，大多数上下文无关文法都可以构造出SLR分析表，所以具有较高的实用价值。使用SLR分析表进行语法分析的分析器叫SLR分析器。
   2. LR 分析表（规范 LR 分析表）
      适用文法类最大，所有上下文无关文法都能构造出LR分析表，但其分析表体积太大，实用价值不大。
   3. LALR 分析表（超前 LR 分析表）
      这种表适用的文法类及其实现上的难易程度在SLR和LR之间，在实用上具有吸引力。使用LALR分析表进行语法分析的分析器叫LALR分析器。
      例：UNIX——YACC
      
5. 说明
   1. 三种分析表对应三类文法
   2. 一个SLR文法必定是LALR文法和LR文法
   3. 仅讨论SLR分析表的构造方法

3.2.2 LR 分析器

1 逻辑结构

(1) 状态栈

状态栈里有

1. 状态:
   • 其中 为初始状态， 为栈顶状态。
   • 栈顶状态概括了从分析开始到该状态的全部分析历史和展望信息
2. 符号串：其中
   符号串是从开始状态（）到当前状态（）所识别出的规范句型的活前缀
   • 规范句型：通过规范归约得到的句型
   • 规范句型前缀：将输入串的剩余部分与其连结起来就构成了规范句型，如 为规范句型
     它是某个规范句型的前缀，且能与输入串剩余部分拼接成规范句型
   • 活前缀：若分析过程能保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀
     

(2) 分析表

1. 状态转移表 (GOTO表)
   
   
   
2. 分析动作表（ACTION 表）
   
   分析动作：
   1. 移进 (shift)
      
      动作：将 a 推进栈，并设置新的栈顶状态为 。
      Sj = GOTO[ Si , a ]，并将指针指向下一个输入符号。
   2. 规约 (reduce)
      ACTION[ Si , a ] = rd(d 是文法规则编号，且假设有 (d) A→β)
      动作：将符号串β(假定长度为 n ) 连同状态从栈内弹出，再把 A 推进栈，再压入新的栈顶状态为Sj(Sj = GOTO[ Si-n , A ])
   3. 接受(accept)
      ACTION[ Si , # ] = accept
   4. 出错 (error)
      ACTION[ Si , a ] = error a∈Vt

(3) 控制程序

1. 根据栈顶状态和现行输入符号，查分析动作表(ACTION表)，执行由分析表所规定的操作；
2. 并根据GOTO表设置新的栈顶状态（即实现状态转移）。

2 !!!LR 分析过程（不用改写去掉左递归）

合并 ACTION 和 GOTO 表，其中 r 的下标表示未来用第几条归约，s 的下标表示移近后要跳到哪个状态

由分析过程可以看到：

1. 每次规约总是规约当前句型的句柄，是规范规约！（而算符优先是规约最左素短语）
2. 分析的每一步栈内符号串均是规范句型的活前缀，且与输入串的剩余部分构成规范句型。

3 !!!构造 LR 分析表

构造LR分析表的方法是：

1. 根据文法构造识别规范句型活前缀的有穷自动机DFA。
2. 由DFA构造LR分析表。

(1) 构造 DFA

什么是 DFA：DFA 是一个五元式

• ：有穷状态集
  在此具体情况下，项目集规范族。
  项目集规范族：其元素是由项目所构成的集合。
• ：文法字汇表
• ：初始状态
• ：终态集合
  除 以外，其余全部是终态。
• GOTO：状态转移函数
  
  为项目集合
  
  表示当前状态 面临文法符号 时，应将状态转移到 。

构造 DFA 的方法：

1. 确定 S 集合，即 LR(0) 项目集规范族，同时确定S0
2. 确定状态转移函数GOTO

构造 LR(0) 的方法：
0. 一些概念
- LR(0)是 DFA的状态集，其中每个状态又都是项目的集合。
- 项目：文法 G 的每个产生式（规则）的右部添加一个圆点就构成一个项目。
项目的直观意义：指明在分析过程中的某一时刻的已经规约部分（点之前）和等待规约（点之后）部分。

1. 将文法扩充
   • 目的：使构造出来的分析表只有一个接受状态，这是为了实现上的方便。
   • 方法：修改文法，使识别符号（开始符号）的规则只有一条。
     
2. 根据文法列出所有的项目
3. 将有关项目组合成集合，即DFA中的状态；所有状态构成了 项目集规范族。
   例子：LR(0)的构造&DFA的构造

   
   
   

项目集闭包 closure 的求法：

状态转移函数 GOTO 的求法：

LR (0) 项目集规范族的构造算法:

关于自动机的说明：

1. 从 I0 到每一状态（除 I0 以外）的每条路径都识别和接受一个规范句型的活前缀。
   
2. 要求状态中每个项目对该状态能识别的活前缀都有效。
   
   

LR 文法

• 对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为LR文法。
• 并非所有的上下文无关文法都是LR文法。但对于多数程序语言来说，一般都可用LR文法描述

(2) 构造 LR 分析表

• GOTO表可由DFA直接求出
• ACTION表由项目集规范族求出
  根据圆点所在的位置和圆点后是终结符还是非终结符，把项目集规范族中的项目分为以下四种：
  

LR（0）文法

• 假若一个文法G的拓广文法G'的活前缀识别自动机中的每个状态(项目集)不存在下述情况：
  1. 既含移进项目又含归约项目
  2. 含有多个归约项目
     则称G是一个LR(0)文法。
• 若：
  1. 移进和归约项目同时存在。移进-归约冲突
  2. 归约和归约项目同时存在。归约-归约冲突
• LR(0)分析器的特点是不需要向前查看任何输入符号就能归约。即当栈顶形成句柄，不管下一个输入符号是什么，都可以立即进行归约而不会发生错误。
• LR(0)文法过于简单。即使是定义算术表达式这样的简单文法也不是LR(0)文法，所以没有实用价值！
  e.g. 移进归约冲突
  
  
  
  r1 r2 r3 r4 r5 都代表什么

求 SLR 文法 ACTION 表的一般方法

• 假定一个LR(0)规范族中含有如下的一个项目集（状态）
  ＝，，
  FOLLOW(A)和FOLLOW(B)的交集为空，且不包含b，那么，当状态I面临任何输入符号a 时:
  1. 若a = b，则移进；
  2. 若 ，用产生式 进行归约；
  3. 若 ，用产生式 进行归约；
  4. 此外，报错。
• 一般地，假定LR(0)规范族的一个项目集
  ，，，，，，，
  如果集合 两两不相交（包括不得有两个FOLLOW集合有 # ），则：
  1. 若输入 a 是某个 ，i = 1, 2,…, m，则移进；
  2. 若 ，则用产生式 进行归约；
  3. 此外，报错。
     ——冲突的SLR(1)解决办法。
• 说明：
  • 按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法（向前看了一步）。
  • 使用SLR表的分析器叫做一个SLR分析器。
  • 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的。

• SLR文法中，如果项目集 含项目 。而下一输入符号 ，则状态 i 面临 a 时，可选用“”进行归约（但是有前提的）。
• 但在有些情况下（非SLR文法），当状态 i 显现于栈顶时，栈里的活前缀未必允许把 归约为A，因为可能根本就不存在一个形如“”的规范句型。因此，在这种情况下用“”归约不一定合适。

3.3 算符优先分析（没大题有选择）

1. 这是一种经典的自底向上分析法，简单直观，并被广泛使用。开始主要是对表达式的分析，现在已不限于此，可以用于一大类上下文无关文法。
2. 称为算符优先分析是因为这种方法是仿效算术式的四则运算而建立起来的。做算术式的四则运算时，为了保证计算结果和过程的唯一性，规定了一个统一的四则运算法则，确定运算符之间的优先关系。
   运算法则:
   1. 乘除的优先级大于加减；
   2. 同优先级的运算符左大于右；
   3. 括号内的优先级大于括号外。
      于是： 4 + 8 – 6 / 2 * 3 运算过程和结果唯一。
3. 算符优先分析的特点:
   仿效四则运算过程，预先规定相邻终结符之间的优先关系，然后利用这种优先关系来确定句型的“句柄”，并进行规约。
4. 分析器结构:
   

3.3.1 分析过程

• 分析过程是从符号串开始，根据相邻终结符之间的优先关系确定句型的“句柄”并进行规约，直到识别符号E。

• 出错情况：

  1. 相邻终结符之间无优先关系。
  2. 对双目运算符进行规约时，符号栈中无足够项。
  3. 非正常结束状态。

• 重要说明

  1. 上述分析过程不一定是严格的最左规约（即不一定是规范规约）。也就是每次规约不一定是规约当前句型的句柄，而是句柄的变形，但也是短语。
  2. 实际应用中，文法终结符间优先关系一般不用矩阵表示，而是采用两个优先函数来表示：f — 栈内优先函数，g — 栈外优先函数
     若 a < b 则令 f ( a ) < g ( b )
     a = b f ( a ) = g ( b )
     a > b f ( a ) > g ( b )
  3. 可以设立两个栈来代替一个栈
     运算对象栈 (OPND)、运算符栈 (OPTR)
     好处是：便于比较，只需将输入符号与运算符栈的栈顶符号相比较。
  4. 使用算符优先分析方法可以分析二义性文法所产生的语言
     二义性文法若按规范分析，其句柄不唯一。

3.3.2 算符优先分析法的进一步讨论

1 算符优先文法(OPG)

• 算符文法（OG） 的定义
  若文法中无形如U∷= …VW…的规则，这里V, W∈Vn
  则称G为OG文法，也就是算符文法。
  算符文法不允许两个非终结符相邻！
• 优先关系的定义
  若G是一个OG文法，a, b∈Vt , U, V, W∈Vn分别有以下三种情况:
  1. a=b iff 文法中有形如 U∷=…ab…或U∷=…aVb…的规则。
  2. a<b iff 文法中有形如 U∷=…aW…的规则，其中 或 。
  3. a>b iff 文法中有形如 U∷=…Wb…的规则，其中 或 。

• 算符优先文法（OPG—Operator Precedence Grammar）的定义
  设有一OG文法，如果在任意两个终结符之间，至多只有上述关系中的一种，则称该文法为算符优先文法(OPG)。
• 对于OG算法的几点说明：
  1. 运算是以中缀形式出现的。
  2. 可以证明，若文法为 OG 文法，则不会出现两个非终结符相邻的句型。
  3. 算法语言中的表达式以及大部分语言成分的文法均是OG文法。

2 构造优先关系矩阵

• 求“ = ” 检查每一条规则，若有U::=…ab…或 U::=…aVb…, 则 a=b。
• 求“ < ”、“ > ”复杂一些，需定义两个集合
  • 若文法有规则W∷= ... a U... ，对任何b, b∈FIRSTVT( U )。则有：a < b
    或
  • 若文法有规则W∷=...U b... ，对任何a, a∈LASTVT( U )。则有：a > b
    或

(1) 构造FIRSTVT(U)的算法

1. 若有规则U∷= b…或U∷= V b… 则b∈FIRSTVT(U)（FIRSTVT的定义中一步推导）
2. 若有规则U∷= V…且 b∈FIRSTVT(V), 则b∈FIRSTVT(U)（FIRSTVT的定义中多步推导）
   说明：因为 或 ，所以有 或

上述算法的工作结果是得到一个二维的布尔数组F，从F可以得到任何非终结符号 U 的FIRSTVT：

(1) 构造 LASTVT(U) 的算法

1. 若有规则U::=…a 或 U::=…aV，则a∈LASTVT(U)
2. 若有规则U::=…V，且a∈LASTVT(V) 则 a∈LASTVT(U)
   
   

（3） 构造优先关系矩阵

3 算符优先分析算法的设计

• 先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的“句柄”并进行归约（归约的实际上是最左素短语，不一定是句柄）。
• 素短语：文法G的句型的素短语是一个短语，它至少包含有一个终结符号，并且除它自身以外不再含任何更小的素短语。

对于算符优先分析法：如何确定当前句型的最左素短语？

• 设有OPG文法句型为: # N1 a1 N2 a2 …Nn an Nn+1 #
  其中Ni 为非终结符(可以为空)，ai 为终结符。
• 定理：一个OPG句型的最左素短语是满足下列条件的最左子串：
  
  其中
• 根据该定理，要找句型的最左素短语就是要找满足上述条件的最左子串。
• 注意：出现在 aj 左端和 ai 右端的非终结符号一定属于这个素短语，因为我们的运算是中缀形式给出的（OPG文法的特点）

可以看出：

1. 每次规约的最左子串，确实是当前句型的最左素短语(从语法树可以看出来)
2. 规约的不都是真正的句柄(仅 i 规约为 F 是句柄，但它同时也是最左素短语)
3. 没有完全按规则进行规约，因为素短语不一定是简单短语

算符优先分析法的实现
基本部分是找句型的最左子串（最左素短语）并进行规约。

• 当栈内终结符的优先级＜或＝栈外终结符的优先级时，移进；
• 当栈内终结符的优先级＞栈外终结符的优先级时，表明找到了素短语的尾，再往前找其头，并进行规约。

4 算符优先分析算法的局限性

• 由于算符优先分析并未对文法非终结符定义优先关系，所以就无法发现有单个非终结符组成的“可规约串”。
• 忽略非终结符在规约过程中的作用，存在某种危险性，可能导致把本来不成句子的输入串误认为是句子。
  例如：有文法 E::=F+F F::=i
  “ i ”明显不是一个合法的句子。但按照下推自动机