04-语法分析（单词序列-＞语法单位）

语法分析（单词序列->语法单位）

自顶向下语法分析方法

确定的自顶向下语法分析

确定：根据输入符号能唯一确定选择那个产生式向下推导

• first集：产生式右部能推出的首个终结符集合（若右部是$\epsilon$，则$\epsilon$属于first集）

• follow集：产生式左部非终结符，在全部产生式中紧跟在该非终结符后面的终结符集合（若该非终结符是起始符，则#属于follow集）

• select集

  • 若产生式右部能推出是$\epsilon$：select集就是该产生式的first集合刨去$\epsilon$，并上follow集
  • 若产生式右部能推出不是$\epsilon$：select集就是该产生式的first集

不确定的自顶向下语法分析

不确定：带回溯的分析方法，穷举试探方法

LL（1）文法

LL（1）文法判别步骤

1. 求出能推出空的非终结符

   

2. 求出每个非终结符的first集

   

3. 求出每个非终结符的follow集

   

4. 求出每个产生式的select集

   

5. 判定文法是否是LL（1）文法：左部相同的产生式的select集是若没有相同的元素则是LL（1）文法

LL（1）预测分析分析

1. 构造预测分析表

	终结符1	终结符2
非终结符1	以非终结符1为左部 select集有终结符1的产生式
非终结符2

2. 分析过程表

步骤号	分析栈	剩余匹配串	使用的产生式或匹配

分析栈：倒着入栈，以保证栈顶是要替换的非终结符

匹配：分析栈栈顶与剩余串首部一样则匹配

查表：分析栈栈顶非终结符与剩余串首部终结符查表

接受：若最后的“#”匹配则说明接收

当前句型：分析栈与已匹配串的正确拼接，当前句型发生改变输出

某些非LL（1）文法转换到LL（1）文法

• 消除左公因子：右部相同的产生式，左部前缀相同

  1. 若有间接左公因子，转变为直接左公因子
     • 以非终结符打头的就有可能是间接作公因子
     • 将所有以该非终结符为左部的都替换到该产生式，等价替换，不能丢失信息（可以去除多余非终结符的所有产生式）
  2. 将有左公因子的产生式合并到一起
  3. 将公因子提取出来
  4. 新引入非终结符代替不是公因子部分
  5. 新产生式是该新引入的非终结符推出不是公因子部分

• 消除左递归：产生式右部非终结符与左部首个非终结符相同

  1. 若有间接左递归，转变为直接左公递归
     1. 将所有非终结符排序（起始符排最后）
     2. 先消除第一个的直接左递归
     3. 找以第二个为左部，右部有第一个的产生式进行替换，并检查当前有没有直接左递归，以此类推
  2. 将有左公递归的非终结符的所有并到一起
  3. 根据$A\longrightarrow A \alpha |\beta$ 改为有递归$A\longrightarrow \beta A'$、$A'\longrightarrow \alpha A'|\epsilon$

自底向上语法分析方法

可规约前缀：采取规约动作前符号栈的内容，即含有一个句柄的前缀

活前缀：可规约前缀的前缀，可规前缀是特殊的活前缀

LR（0）分析步骤

对已有文法进行拓广

引入新的起始符号推出旧的起始符号，$S'\longrightarrow S$，为了解决起始符号再其他产生式的右部出现引起的规约结束标准不明确现象

构造识别可规约前缀的DFA：项目规范族的构造自动机

概念

项目：产生式右部加点，表示圆点左部是符号栈中已经出现的部分，右部是没出现的部分，特殊的$A\longrightarrow\epsilon$ $A\longrightarrow·$

移进项目：点后面是终结符的项目

待约项目：点后是非终结符的项目

规约项目：点在最后的项目

接受项目：特殊的规约项目$S'\longrightarrow S·$

项目集：项目的集合

族：多个项目集

项目集的闭包运算：将原项目集中的待约项目，将以点后非终结符为左部的右部以点开始的项目加进来，直到没有待约项目

GO运算：将项目集针对某个符号进行点的右移，然后再对项目集进行闭包运算

LR（0）的项目集规范族构建

1. 以拓广后的产生式，点在最前面的项目为核做闭包运算
2. 对点后有符号的项目做GO运算
3. 直到没有新的项目集出现

SLR（1）

移进规约冲突：项目集中既有移进项目又有规约项目，移进项目点后非终结符和规约项目左部follow集没有重复元素，若下一个符号是移进项目点后非终结符，则移进，若下一个符号是规约项目左部follow集的元素，则规约

规约规约冲突：项目集中有多个不同的规约项目，解决方法规约项目左部的follow集没有重复元素，若下一个符号是规约项目左部follow集的元素，则规约

改进的SLR（1）：对所有的规约项目都求左部的follow集

LALR（1）

同心集：项目集一样，只是向前搜索符不一样

有同心集能合并的项目集进行合并后没有冲突的文法是LALR（1）否则是LR（1），LALR（1）是特殊的LR（1）

合并冲突只能是规约规约冲突

LR（1）

多个向前搜索符用斜杠隔开

新的项目集的闭包运算：将原项目集中的待约项目，将以点后非终结符为左部的右部以点开始的项目加进来，并且求核的点后符号的符号的向前搜索符，即点后符号的后面与向前搜索符的连接的first集，直到没有待约项目

新GO运算：将项目集针对某个符号进行点的右移，并且将向前搜索符带过来，然后再对项目集进行新闭包运算

对于移进规约冲突解决方法：移进项目点后非终结符和规约项目左部follow集有重复元素，规约项目遇到向前搜索符才规约

1. 以拓广后的产生式，点在最前面的项目为核做闭包运算，向前搜索符是#
2. 对点后有符号的项目做GO运算
3. 直到没有新的项目集出现

根据DFA构造分析表

ACTTON部分：非终结符和#

$S_n$：移进，转化到n状态

$r_n$：规约，用n号产生式规约

acc：接受状态

GOTO部分：终结符

进行LR分析

1. 0状态（初始状态）入状态栈，#入符号栈，符号栈和状态栈共享栈顶
2. 根据状态栈顶状态和剩余串的最左面符号进行查表
3. 出现规约项目，先将出栈，再进栈，goto部分填写转移到的状态，为出现规约项目则接着从剩余串中入栈