day07_编译原理学习

标签：分析文法项目 day07 SLR 编译归约 LR 原理

第四章语法分析

LR文法的概述

LR文法的概念

LR文法是最大的，可以构造出相应移入-归约语法分析器的文法类
- L：对输入进行从左到右的扫描
- R：反向构造出一个最右推导序列
LR(k)分析
- 需要向前查看k个输入符号的LR分析
- k = 0 和 k = 1 这两种情况具有实践意义，当省略k时，k = 1

LR分析法的基本原理

自底向上分析的关键问题是正确认识句柄
句柄是逐步形成的，用“状态”表示句柄识别的进展程度
- LR分析器基于这样一些状态来构造自动机进行句柄的识别

LR分析器（自动机）的总体结构

LR分析表的结构
LR分析器的工作过程
- 初始化
- 一般情况下
  - （1）如果 $ACTION[s_{m}, a_{i}] = sx$ ，那么格局就变为：
  - (2) 如果表示 $ACTION[s_{m}, a_{i}] = rx$ 表示用第x个产生式 $A\rightarrow X_{m-(k-1)}...X_{m}$ 进行归约，那么格局变为：
  - （3）如果 $GOTO[s_[m-k],A]=y$ ，那么格局变为：
  - （4）如果 $ACTION[s_{m}, a_{i}] = acc$ ，那么分析成功
  - （5）如果 $ACTION[s_{m}, a_{i}] = err$ ，那么出现语法错误
LR分析算法

构造LR分析表

LR(0)分析

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目） $A\rightarrow \alpha_{1}\cdot \alpha_{2}$
- 项目描述了句柄识别的状态
- 产生式 $A\rightarrow \varepsilon$ 只生成一个项目 $A\rightarrow \cdot$

增广文法

如果G是一个以S为开始符号的文法，则G的增广文法G‘就是在G中加上新开始符号S'和产生式S' -> S而得到的文法
- 例
- 引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态
文法中的项目
- 后继项目
  - 同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目
  - $A\rightarrow \alpha \cdot X\beta$ 的后继项目是 $A\rightarrow \alpha X\cdot \beta$
- “等价”项目
  - 当一个项目中圆点位置后面是一个非终结符时，可能存在“等价”项目
  - 可以把所有等价的项目组成一个项目集 $(I)$ ，称为项目集闭包，每个项目集闭包对应着自动机的一个状态

LR(0)分析表的构造算法

CLOSURE()函数
- 计算给定项目集I的闭包
GOTO()函数
- 返回项目集I对应于文法符号X的后继项目集闭包
构造LR(0)自动机的状态集
- 规范LR(0)项目族（Canonical LR(0) Collection）
LR(0)分析表构造算法
LR(0)自动机的形式化定义
- 文法
- LR(0) 自动机
LR(0)分析过程中的冲突
- 表达式文法的LR(0)分析表含有移进/归约冲突
- 还有一种冲突——归约/归约冲突
- 如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法
- 不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法

SLR分析

SLR分析法的基本思想
表达式文法的SLR分析表
- 分析表构造算法
  - 如果给定文法的SLR分析表中不存在有冲突的动作，那么该文法称为SLR文法

LR(1)分析

提出

SLR只是简单地考察下一个输入符号b是否属于与归约项目 $A\rightarrow \alpha$ 相关联的 $FOLLOW(A)$ ，但是 $b\in FOLLOW(A)$ 只是归约 $\alpha$ 的一个必要条件，而非充分条件（只是合理，但是并不一定正确）
对于产生式 $A\rightarrow \alpha$ 的归约，在不同的使用位置，A会要求不同的后继符号
在特定位置，A的后继符集合是 $FOLLOW(A)$ 的子集

规范LR(1)项目

将一般形式为 $[A\rightarrow \alpha \cdot \beta ,a]$ 的项称为LR(1)项，其中 $A\rightarrow \alpha \cdot \beta$ 是一个产生式，a是一个终结符（这里将$视作一个特殊的终结符），表示在当前状态下，A后面必须紧跟终结符，称为该项的展望符(lookahead)
- LR(1)中的1指的是项的第二个分量的长度
- 在形如 $[A\rightarrow \alpha \cdot \beta ,a]$ 且 $\beta \neq \varepsilon$ 的项中，展望符a没有任何作用
- 但是一个形如 $[A\rightarrow \alpha \cdot ,a]$ 的项在只有在下一个输入符号等于a时才可以按照 $A\rightarrow \alpha$ 进行归约
  - 这样的a的集合总是 $FOLLOW(A)$ 的子集，而且它通常是一个真子集

等价LR(1)项目

当 $\beta \Rightarrow ^{+}\varepsilon$ 时，此时b = a叫做继承的后继符，否则叫自生的后继符。

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

LR(1)项目集闭包的计算

LR(1)分析表构造算法

LALR分析

LALR（lookahead-LR）分析的基本思想

寻找具有相同核心的LR(1)项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合
然后根据合并后得到的项集族构造语法分析表
如果分析表中没有语法分析动作冲突，给定的文法就称为LALR(1)文法，就可以根据该分析表进行语法分析
- 合并同心项集不会产生移进-归约冲突
- 合并同心项集后，虽然不会产生冲突，但可能会推迟错误的发现。LALR分析法可能会做多余的归约动作，但绝不会作错误的移进操作

LALR(1)的特点

形式上与LR（1）相同
大小上与LR(0)/SLR相当
分析能力介于SLR和LR(1)二者之间
- SLR < LALR(1) < LR(1)

二义性文法的LR分析

每个二义性文法都不是LR的
某些类型的二义性文法在语言的描述和实现中很有用
- 更简短，更自然（消除二义性，需增加非终结符）
应该保守地使用二义性文法，并且必须在严格控制下使用，因为稍有不慎就会导致语法分析器所识别的语言出现偏差

LR分析中的错误处理

语法错误的检测
- 当LR分析器在查询分析表并发现一个报错条目时，就检测到了一个语法错误
错误恢复策略
- 恐慌模式错误恢复
  - 从栈顶向下扫描，直到发现某个状态，它有一个对应于某个非终结符A的GOTO目标，可以认为从这个A推导出的串中包含错误
  - 然后丢弃0个或多个输入符号，直到发现一个可能合法地跟在A之后的符号a为止
  - 之后将 $s_{i+1}=GOTO(s_{i},A)$ 压入栈中，继续进行正常的语法分析
- 短语层次错误恢复
  - 检查LR分析表中的每一个报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误
  - 然后构造出适当的恢复过程

标签：分析,文法,项目,day07,SLR,编译,归约,LR,原理
From： https://blog.csdn.net/m0_74985290/article/details/142289290

第四章语法分析

LR文法的概述

LR文法的概念

LR分析法的基本原理

LR分析器（自动机）的总体结构

构造LR分析表

LR(0)分析

增广文法

LR(0)分析表的构造算法

SLR分析

LR(1)分析

提出

规范LR(1)项目

等价LR(1)项目

LR(1)项目集闭包的计算

LR(1)分析表构造算法

LALR分析

LALR（lookahead-LR）分析的基本思想

LALR(1)的特点

二义性文法的LR分析

LR分析中的错误处理

相关文章

赞助商

阅读排行

day07_编译原理学习

第四章 语法分析

LR文法的概述

LR文法的概念

LR分析法的基本原理

LR分析器（自动机）的总体结构

构造LR分析表

LR(0)分析

增广文法

LR(0)分析表的构造算法

SLR分析

LR(1)分析

提出

规范LR(1)项目

等价LR(1)项目

LR(1)项目集闭包的计算

LR(1)分析表构造算法

LALR分析

LALR（lookahead-LR）分析的基本思想

LALR(1)的特点

二义性文法的LR分析

LR分析中的错误处理

相关文章

赞助商

阅读排行

第四章语法分析