语法分析

概念

工作依据

  • 源语言的语法规则

任务

  • 从源程序记号序列中识别出各类语法成分

  • 进行语法检查

输入

  • 记号流
  • 记号序列

输出

  • 分析树

错误处理

语法处理中出现错误需要错误处理

  • 错误位置
  • 错误性质

恢复的策略有

  • 紧急恢复

    出现错误程序即抛弃一个输入记号，直到扫描到记号属于某个指定的同步记号集合为止

  • 短语级恢复

  • 出错产生式

  • 全局纠正

分析方法

  • 自顶向下

    从树根到叶子来建立分析树

  • 自底向上

    从树叶到树根来建立分析树

对输入符号串的扫描顺序

自左向右

自顶向下的分析方法

递归下降分析

从文法的开始符号出发，进行推导，推出要分析的输入记号串的过程

是一个试探的过程，反复使用不同产生式谋求匹配输入符号串的过程

是最左推导

对输入串的扫描是自左至右进行的，只有使用最左推导，才能保证按扫描的顺序匹配输入串

推导

image-20230926103600002

image-20230926104930010

image-20230926105519593

image-20230926105539629


实现

  • 文法的每一个非终结符号对应一个递归过程，即可实现这种带回溯的递归下降分析方法
  • 每个过程作为一个布尔过程，一旦发现它的某个产生式与输入串匹配，则用该产生式展开分析树，并返回true，否则分析树不变，返回false

缺点

  • 可能会死循环 A->Ab
  • 回溯
  • 重复工作
  • 效率低，穷尽一切

递归调用预测分析

一种确定的、不带回溯的递归下降分析方法

c2d624f53d60877d95725031901ab0d1

克服回溯

能够根据所面临的输入符号准确地指派一个候选式去执行任务

对文法的要求

  • 不含左递归

  • image-20230926111417901

image-20230926111612536

image-20230926111626071

预测分析程序的构造

转换图

为预测分析程序建立转换图作为其实现蓝图

每一个非终结符号有一张图

边的标记可以是终结符号，也可以是非终结符号

在一个非终结符号A上的转移意味着对相应A的过程的调用

在一个终结符号a上的转移，意味着下一个输入符号若为a，则应做此转移

从文法构造转换图

  • 改写文法

    • 重写文法
    • [消除左递归](# 消除左递归)
    • 提取左公因子

  • 对每一个非终结符号A，做如下工作

    • 创建一个初始状态和一个终结状态
    • 对每一个产生式A -> X1X2…Xn创建一条从初态到终态的路径，有向边的标记依次为X1,X2,…,Xn
  • image-20230926115258676

    第一种：匹配终结符 - 指针后移，转移到下一个状态

    第二种：射出边上有非终结符A，立即转移到A的转换图上,A转换完后，返回到射出边的下一个状态，指针后移

    第三种：没有匹配到，为空，转移到下一个状态，但指针不动


image-20230926114743986

具体步骤

  • 消除左递归和空产生式，提取左公因子
  • 从文法产生转换图，进行转换图的化简
  • 根据转换图进行程序设计

非递归预测分析

使用一张分析表和一个栈联合控制，实现对输入符号串的自顶向下分析

image-20231010100717440

各部分作用

  • 输入缓冲区：存放被分析的输入符号串，串后随右尾标志符$

  • 符号栈：存放一系列文法符号，$存于栈底。分析开始时，先将$入栈，以标识栈底，然后再将文法的开始符号入栈

  • 分析表：二维数组M[A,a]，A∈VNA\in V_N，a∈VT∪{$}\in V_T \cup\{\$\}。根据给定的A和a，在分析表M中找到将被调用的产生式

  • 输出流：分析过程中不断产生的产生式序列

预测分析控制程序

根据栈顶符号X和当前输入符号a，分析动作有4种可能

  • X=a=$，宣告分析成功，停止分析

  • X=a≠\neq $，从栈顶弹出X，输入指针前移一个位置

  • X∈VTX\in V_T，但X≠aX\neq a，报告发现错误，调用错误处理程序，报告错误及进行错误恢复

  • 若X∈VNX\in V_N，访问分析表M[X,a]

    • M[X,a]=X→Y1Y2...YnM[X,a]=X\rightarrow Y1Y2...Yn

      先将X从栈顶弹出，然后把产生式的右部符号串按反序推入栈中（即按Yn、…、Yn-1、Y2、Y1的顺序)

    • M[X,a]=X→ϵM[X,a]=X\rightarrow \epsilon从栈顶弹出X

    • M[X,a]=error 调用出错处理程序

预测分析表的构造

FIRST集合

对任何文法符号串α∈(VT∪VN)∗\alpha \in(V_T\cup V_N)^*，FIRST(α\alpha)是α\alpha可以推导出的开头终结符号集合

FIRST(α)={a∣α→∗a...,a∈VT}若α→∗ϵ，则ϵ∈FIRST(α)FIRST(\alpha)=\{a|\alpha \to^* a...,a\in V_T\}\\ 若\alpha \to^* \epsilon，则\epsilon\in FIRST(\alpha)

image-20231010104527223

这个方法可以连续使用，直到每个集合不再增大为止

FOLLOW集合

假定S是文法G的开始符号，对于G的任何非终结符号A，集合FOLLOW(A)是在所有句型中，紧跟A之后出现的终结符号或$组成的集合

FOLLOW(A)={a∣S→∗...Aa...,a∈VT}特别地，若S→∗...A,则规定$∈FOLLOW(A)FOLLOW(A)=\{a|S\to ^*...Aa...,a\in V_T\}\\ 特别地，若S\to ^*...A, 则规定\$ \in FOLLOW(A)

image-20231010105401787

FOLLOW集合中不可能有空串

使用FIRST和FOLLOW构造分析表

image-20231010111616673

LL(1)文法

如果一个文法的预测分析表M不含多重定义的表项，则称该文法为LL(1)文法

LL(1)的含义
  • 第一个L表示从左至右扫描输入符号串
  • 第二个L表示生成输入串的一个最左推导
  • 1表示在决定分析程序的每步动作时，向前看一个符号

image-20231010113940708

自底向上分析方法

  • 对输入串的扫描：自左向右

  • 分析树的构造：自底向上

  • 分析过程：

    • 从输入符号串开始分析
    • 查找当前句型的“可归约串”
    • 使用规则，把它归约成相应的非终结符号
    • 重复

  • 关键：找出“可归约串”

  • 常用方法：

    • 优先分析方法（略）
    • LR分析方法

“移近-归约”分析方法

符号栈：存放文法符号

  • 1.把输入符号一个个地移进栈中
  • 2.当栈顶的符号串形成某个产生式的一个候选式时，在一定条件下，把该符号串替换(即归约)为该产生式的左部符号
  • 3.重复2，直到栈顶符号串不再是“可归约串”为止
  • 4.重复1～3，直到最终归约出文法开始符号S

规范归约是最右推导的逆过程，因此规范归约也被称为最左归约

句柄

最左直接短语（父子两代子树）

归约的过程实际上就是剪句柄的过程（逆向推导的过程）

一棵子树的所有叶结点自左至右排列起来，形成此句型相对于该子树根的短语

分析树中只有父子两代的子树的所有叶结点自左至右排列起来，形成此句型相对于该子树根的直接短语

分析树中最左边的那棵只有父子两代的子树的所有叶结点自左至右排列起来，就是该句型的句柄

规范归约

假定α\alpha是文法G的一个句子，我们称右句型序列αn\alpha_n，αn−1\alpha_{n-1}，…，α1\alpha_1，α0\alpha_0是α\alpha的一个规范归约，如果序列满足：

  • αn\alpha_n=α\alpha，α0\alpha_0=S
  • 对任何i(0<i≤n0<i\le n)，αi−1\alpha_{i-1}是经过把αI\alpha_I的句柄替换为相应产生式的左部符号而得到的

规范句型

最右推导得到的句型

特点：句柄之后没有非终结符号

利用句柄的最左性：与符号栈的栈顶相关

不同的最右推导，其逆过程也是不同

LR分析方法

LR(k)的含义

  • L表示自左向右扫描输入串
  • R表示为输入符号串构造一个最右推导的逆过程
  • k表示为做出分析决定而向前看的输入符号的个数，k=1可省略

基本思想

  • 历史信息 记住已经移进和归约出的整个符号串
  • 预测信息 根据所用的产生式推测未来可能遇到的输入符号

根据“历史信息”和“预测信息”，以及“现实”的输入符号，确定栈顶的符号串是否构成相对于某一产生式的句柄

LR分析程序的模型及工作过程

image-20231017105008473

分析表

LR分析控制程序工作的依据

  • goto[SmS_m,X]：状态SmS_m经X转移的后继状态
  • action[SmS_m,aia_i]：状态SmS_m面临输入符号aia_i时应采取的分析动作
    • shift S (移进）：把当前输入符号aia_i及状态S推进栈，向前扫描指针前移。这里，S=goto[SmS_m,aia_i]
    • reduce by A→βA\to \beta （归约）：若β\beta的长度为r，则从栈顶起向下弹出r项，使Sm−rS_{m-r}成为栈顶状态，然后把文法符号A及状态S推进栈。这里，S=goto[Sm−rS_{m-r},A]
    • accept：宣布分析成功，停止分析
    • error：调用出错处理程序，进行错误恢复

栈

  • S - state状态栈
  • X - 符号栈

这两个栈的变化是同步的

控制程序

image-20231017105951221

上图的二元式是每一步的结果，而不是栈（或者说只把栈里的S栈输出，没有输出每一步的符号栈X）

活前缀

一个规范句型的一个前缀，如果不含句柄之后的任何符号，则称它为该句型的一个活前缀

之所以称它们为活前缀，是因为在其右边增加某些终结符号之后，就可以使之成为一个规范句型

SLR（1）分析表的构造

共有两步

  • 为给定的文法构造一个识别它所有活前缀的DFA

  • 并根据该DFA构造文法的SLR（1）分析表

构造识别给定文法所有活前缀的DFA

活前缀与句柄之间的关系

  • 活前缀不含有句柄的任何符号
  • 活前缀只含有句柄的部分符号
  • 活前缀已经含有句柄的全部符号

分析过程中，分析栈中出现的活前缀

  • 第一种情况，期望从剩余输入串中能够看到由某产生式A→αA\to \alpha的右部$\alpha $所推导出的终结符号串
  • 第二种情况，某产生式$A\to \alpha_1 \alpha_2 的右部子串的右部子串\alpha_1 已经出现在栈顶，期待从剩余的输入串中能够看到已经出现在栈顶，期待从剩余的输入串中能够看到\alpha_2 $推导出的符号串
  • 第三种情况，某一产生式A→αA\to \alpha的右部符号串$\alpha $已经出现在栈顶，用该产生式进行归约

LR(0)项目 LR(0) item

image-20231017114332508

注意最后一行空符号串的处理方式

LR(0)转移函数go

image-20231024111619393

拓广文法

任何文法

G=(VT,VN,S,ϕ)G=(V_T,V_N,S,\phi)

都有等价的文法

G′=(VT,VN∪{S′},S′,ϕ∪{S′→S})G'=(V_T,V_N\cup \{S'\},S',\phi \cup \{S'\to S\})

称G’为G的拓广文法

拓广文法G’的接受项目是唯一的(即S′→S⋅S'\to S\cdot)

实际作用是使得归约开始符号只有一种可能

拓广文法内有左递归，不需要消除

LR(0)有效项目

image-20231017114938543

实际上，是将由LR（0）项目集（LR（0）项目集构成的是一个状态）构成的NFA转到DFA，理论基础就是这个

LR(0)有效项目集和LR(0)项目集规范族

文法G的某个活前缀γ\gamma的所有LR(0)有效项目组成的集合称为γ\gamma的LR(0)有效项目集

文法G的所有LR(0)有效项目集组成的集合称为G的LR(0)项目集规范族

有效项目集就是DFA的状态集

SLR(1)分析表的构造

特征

如果文法的有效项目集中有冲突动作，多数冲突可通过考察有关非终结符号的FOLLOW集合而得到解决

如项目集：I={X→α•bβ，A→α•，B→β•}I=\{X\to\alpha• b\beta，A\to \alpha•，B\to\beta•\}

  • 存在移进-归约冲突
  • 存在归约-归约冲突

冲突的解决：查看FOLLOW(A)和FOLLOW(B)

  • $FOLLOW(A)\cap FOLLOW(B)=\empty $
  • b∉FOLLOW(A)并且b∉FOLLOW(B)b\notin FOLLOW(A)并且b\notin FOLLOW(B)
  • 决策：
    • 当a=b时，把b移进栈里
    • 当a∈FOLLOW(A)a\in FOLLOW(A)时，用产生式A→αA\to\alpha进行归约
    • 当a∈FOLLOW(B)a\in FOLLOW(B)时，用产生式B→βB\to\beta进行归约

算法

image-20231024101936190

第五步勘误：是S′→⋅SS'\to \cdot S

定理

每一个SLR(1)文法都是无二义的文法，但并非无二义的文法都是SLR(1)文法

SLR（1）的缺陷

当遇到归约冲突时，无法进行分析

为了处理冲突，引入LR（1）分析

LR(1)分析表的构造

LR(k)项目

[A→α•β，a1a2...ak][A\to\alpha•\beta，a_1a_2...a_k]

  • A→α•βA\to\alpha•\beta是LR(0)项目
  • ai(i=1,2,...,k)a_i(i=1,2,...,k)是终结符号
  • a1a2...aka_1a_2...a_k称为该项目的向前看符号串

向前看符号串仅对归约项目[A→α•，a1a2...ak][A\to\alpha•，a_1a_2...a_k]起作用

归约项目[A→α•，a1a2...ak][A\to \alpha•，a_1a_2...a_k]意味着，当它所属项目集对应的状态在栈顶，且后续的k个输入符号为a1a2...aka_1a_2...a_k时，才允许把栈顶的文法符号串α\alpha归约为A

LR(1)有效项目

image-20231024110453942

LR(1)有效项目集和LR(1)项目集规范族

文法G的某个活前缀γ\gamma的所有LR(1)有效项目组成的集合称为γ\gamma的LR(1)有效项目集

文法G的所有LR(1)有效项目集组成的集合称为G的LR(1)项目集规范族

image-20231024111447217

LR(1)转移函数go

image-20231024111746569

算法：构造文法G的LR(1)项目集规范族

image-20231024111926407

注意C的初始化已包含[S′→⋅S,$][S'\to \cdot S,\$]的闭包

构造LR(1)分析表

image-20231024113954957

LALR(1)分析表的构造

描述LR(1)项目集特征的两个定义

同心集

如果两个LR(1)项目集去掉搜索符号之后是相同的，则称这两个项目集具有相同的心（core），即这两个项目集是同心集

项目集的核

除去初态项目集外，一个项目集的核（kernel）是由该项目集中那些圆点不在最左边的项目组成

LR(1)初态项目集的核中有且只有项目[S′→•S,$][S'\to•S,\$]

构造LALR(1)分析表的基本思想

  • 合并LR(1)项目集规范族中的同心集，以减少分析表的状态数
  • 用核代替项目集，以减少项目集所需的存储空间
  • go(I,X)仅仅依赖于I的心，因此LR(1)项目集合并后的转移函数可以通过go(I,X)自身的合并得到
  • 同心集的合并，可能导致归约-归约的冲突，但不会产生新的移进-归约冲突

构造LALR(1)分析表的构造

  • 首先构造LR(1)项目集规范族
  • 检查LR(1)项目集规范族
    • 含有冲突，则该文法不是LR(1)文法
    • 不存在冲突，该文法是LR(1)文法，检查是否存在同心集
      • 不存在，则LR(1)项目集规范族即LALR(1)项目集规范族；
      • 存在，合并同心集；
      • 检查合并后的项目集是否存在冲突
        • 有冲突，则该文法不是LALR文法
        • 无冲突，则该文法是LALR(1)文法，合并同心集得到的项目集规范族为LALR(1)项目集规范族

根据LALR(1)项目集规范族构造分析表

文法分析进化图

1
2
3
4
5
6
st=>start: LR(0)
op1=>operation: SLR(1)
op2=>operation: LALR(1)
e=>end: LR(1)

st->op1->op2->e

越靠下的文法分析范围越广，分析能力越强

靠上的文法属于靠下的文法范围，也就是说，若已证明某一文法是某种文法，那么它也是这种文法其下的文法

LR分析方法对二义文法的应用

定理：任何二义性文法绝不是LR文法，因而也不是SLR文法和LALR文法

if-else的处理课上不讲自学

LR分析的错误处理与恢复

LR分析程序可采取以下恢复策略

  • 首先，从栈顶开始退栈，可能弹出0个或若干个状态，直到出现状态S为止

    1. 状态S有相对于当前输入符号的转移

    2. goto表中有S相对于某非终结符号A的后继

  • 针对(1)：移进，分析继续

  • 针对(2)：跳过0个或若干个输入符号，直到出现符号a为止，a∈FOLLOW(A)a\in FOLLOW(A)；

    • 然后，把状态goto[S,A]压入栈顶，继续分析

A的选择：通常选择表示主要结构成分的非终结符号

这样就跳过了包含错误的一段终结符号串

消除左递归

image-20230926113353005

image-20230926114257892

image-20230926114312109

image-20230926114327289