U4_3 语法分析-自底向上分析-LR0/LR1/SLR分析

2024-01-01 09:12

本文主要是介绍U4_3 语法分析-自底向上分析-LR0/LR1/SLR分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、LR分析法
    • 1、概念
    • 2、流程
    • 3、LR分析器结构及分析表构造
      • 1)结构
      • 2)一些概念
  • 二、LR(0)分析法
    • 1、流程
    • 2、分析动作
      • 1)移近
      • 2)归约(reduce)
    • 3、总结
      • 1)LR分析器
      • 2)构造DFA
      • 3)构造LR(0)的方法(三步)
    • 4、局限性
  • 三、LR(1)分析法
  • 四、SLR(1):简单LR分析法
    • 1、基本思想
    • 2、分析思路
      • 1)构建表
      • 2)SLR求ACTION表
    • 3、局限性
  • 五、彩蛋

一、LR分析法

1、概念

是一种自底向上的分析方法(1965年 D.Knuth 提出)。
L:从左向右分析 (left to right)
R:产生“最右推导”(right-most derivation)
k=0:不向前查看符号     k=1:向前查看1个符号
从左到右扫描(L)自底向上进行归约(Right-most Derivation)(一定是规范归约), 是自底向上分析方法的高度概括和集中
历史 + 展望 + 现状 => 句柄

2、流程

根据文法不断进行移进或者规约
在这里插入图片描述
规约后回退状态,且得到的终结符也需要回退
在这里插入图片描述

3、LR分析器结构及分析表构造

1)结构

状态栈、分析表、控制程序
在这里插入图片描述
栈顶状态概括了从分析开始到该状态的全部分析历史和展望信息

2)一些概念

符号串 X 1 X 2 . . . . . X m X_1X_2..... X_m X1X2.....Xm:从开始状态( S 0 S_0 S0)到当前状态( S m S_m Sm)所识别的规范句型的活前缀。

规范句型前缀: 将输入串的剩余部分与其连接起来就构成了规范句型。
如: x 1 x 2 . . . . . x m a i . . . a n x_1x_2..... x_ma_i... a_n x1x2.....xmai...an为规范句型( x i x_i xi已处理, a i a_i ai未处理)

对于句型 α β t αβt αβt β β β表示句柄, 如果 α β = u 1 u 2 … u r αβ= u_1u_2…u_r αβ=u1u2ur那么符号串 u 1 u 2 … u i ( 1 ≤ i ≤ r ) u_1u_2…u_i(1≤i≤r) u1u2ui(1ir)即是句型 α β t αβt αβt的活前缀。
在这里插入图片描述

活前缀: 若分析过程能够保证栈中符号串均是规范句型的前缀,则表示输入串已分析过的部分没有语法错误,所以称为规范句型的活前缀。

二、LR(0)分析法

1、流程

根据状态转移图得出状态转移表
在这里插入图片描述
状态栈:# S 0 x 1 S 1 x 2 . . . . . . x i − 1 S i − 1 x i S i S_0x_1S_1x_2...... x_{i-1}S_{i-1} x_iS_i S0x1S1x2......xi1Si1xiSi
S i − 1 S_{i-1} Si1—当前状态(栈顶状态)
x i x_i xi— 新的栈顶符号
S i S_i Si----新的栈顶状态(状态转移)

2、分析动作

1)移近

A C T I O N [ S i , a ] = s ACTION[S_i,a] = s ACTION[Si,a]=s (s表示 s h i f t shift shift,移进)
动作: 将 a a a推进栈,并设置新的栈顶状态 S j S_j Sj
S j = G O T O [ S i , a ] S_j= GOTO[S_i,a] Sj=GOTO[Si,a],将指针指向下一个输入符号

2)归约(reduce)

A C T I O N [ S i , a ] = r d ACTION [S_i,a] = r_d ACTION[Si,a]=rd (r表示 reduce,按规则d规约)
条件:某个项目集形如 A → β A→β Aβ.
动作: 将符号串β(假定长度为 n n n)连同状态从栈内
弹出, 把 A A A推进栈, 并设置新的栈顶状态 S j S_j Sj
S j = G O T O [ S i − n , A ] S_j= GOTO[S_{i-n},A] Sj=GOTO[Sin,A]

3、总结

1)LR分析器

构造LR分析器的关键是构造其分析表
构造LR分析表的方法是:

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

2)构造DFA

在这里插入图片描述
构造DFA:
4. 确定 S S S集合,即 L R ( 0 ) LR(0) LR(0)项目集规范族,同时确定 S 0 S_0 S0
5. 确定状态转移函数GOTO

LR(0) 是DFA的状态集,其中每个状态又都是项目的集合

项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目
在这里插入图片描述

3)构造LR(0)的方法(三步)

  1. 将文法拓广
    目的:使构造出来的分析表只有一个接受状态,这是为了实现的方便。
    在这里插入图片描述
  2. 根据文法列出所有的项目
  3. 将有关项目组合成集合,即DFA中的状态;
    所有状态再组合成一个集合,即LR(0)项目集规范族

举例分析:
在这里插入图片描述
3 将有关项目组成项目集,所有项目集构成的集合即为LR(0)
为实现这一步,先定义:
• 项目集闭包closure
• 状态转移函数GOTO
在这里插入图片描述
在这里插入图片描述

4、局限性

会存在两种冲突,导致LR(0)识别不出来

  1. Shift-Reduce冲突
    在这里插入图片描述
  2. Reduce-Reduce冲突
    在这里插入图片描述
    因此需要采用偷看解决问题, L R ( 0 ) → L R ( 1 ) LR(0) → LR(1) LR0LR1

三、LR(1)分析法

通过“偷看”一个右侧符号,在遇到冲突时辅助决定。
思路:将状态区分的更加细致,构造LR(1)的状态机。

优点就是可以将状态区分的更加细致,构造LR(1)的状态机。
优势:功能强大!任何LR(0)、LL(1)、确定型CFL、LL(k)、LR(k)都有LR(1)的等价文法。

主要问题:状态爆炸,实用性差。

四、SLR(1):简单LR分析法

1、基本思想

由DFA构造出的SLR分析表,在造表时, 只需向前看一个符号就能确定分析的动作是移进还是归约,所以称为SLR(1)分析表,简称SLR分析表,使用SLR分析表的分析器叫SLR分析器,兼有LR(0)和LR(1)的优点,放弃一些精度。

在LR(0)的基础上,只针对冲突进行处理。

当发生 S-R冲突时,根据FOLLOW集合确定S还是R

2、分析思路

1)构建表

先构造LR(0)的自动机,GOTO表。

2)SLR求ACTION表

  1. 求出文法每个非终结符的FOLLOW集合
  2. 若项目 A → α . a β ∈ k A→α.aβ ∈k Aα.aβk,且 a ∈ V t a ∈V_t aVt ,则置 A C T I O N [ k , a ] = s ACTION[k,a] = s ACTION[k,a]=s (移进)
  3. 若项目 A → α . ∈ k A→ α.∈k Aα.k, 那么对输入符号 a a a,若 a ∈ F O L L O W ( A ) a∈FOLLOW(A) aFOLLOW(A),则置 A C T I O N [ k , a ] = r j ACTION[k,a]=r_j ACTION[k,a]=rj,其中 A → α A→ α Aα为文法 G ’ G’ G的第j个产生式。
  4. 若项目 E ’ → E . ∈ k E’→E.∈k EE.k, 则置 A C T I O N ACTION ACTION[ k , k , k,#] = a c c e p t =accept =accept
  5. 空白格,均置error
    在这里插入图片描述
    看到 f o l l o w follow follow应该做规约(已经跳出表达式了)

3、局限性

在这里插入图片描述
F O L L O W ( R ) FOLLOW(R) FOLLOW(R)中有=,应该做规约,但是碰到=,E中表达式应该移进,因此还是冲突。

对文法G,若应用上述算法所造出的分析表具有多重定义入口,分析动作不唯一, 则文法G就不是SLR的,需要用别的方法来构造分析表。如下图
在这里插入图片描述

五、彩蛋

L L ( k ) LL(k) LL(k)是无二义性的, L L ( k ) LL(k) LL(k)文法识别的语言都是确定型下推自动机所识别的语言,但反之,不能保证任何一个确定型下推自动机 D P D A DPDA DPDA L L ( k ) LL(k) LL(k)等价

LL(k)文法总是一个LR(k)文法 L L ( k ) LL(k) LL(k) L R ( k ) LR(k) LR(k)的子集
在这里插入图片描述
定义上看,LR(0), LR(1), LR(k), SLR(1), LALR(1)等,要求构造出来的分析表是“确定性”的,也就是分析表不允许存在冲突,无二义性!
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

这篇关于U4_3 语法分析-自底向上分析-LR0/LR1/SLR分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/558795

相关文章

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用,例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具,该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明,MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能,MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境,如果是隔离环境,无法连接互联网时,请先按照 离线环境安装依赖的指导进行依赖包的安装,然后按照本文的指导继续操作。如果网络环境可以连接互联网,请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

三相直流无刷电机(BLDC)控制算法实现:BLDC有感启动算法思路分析

一枚从事路径规划算法、运动控制算法、BLDC/FOC电机控制算法、工控、物联网工程师,爱吃土豆。如有需要技术交流或者需要方案帮助、需求:以下为联系方式—V 方案1:通过霍尔传感器IO中断触发换相 1.1 整体执行思路 霍尔传感器U、V、W三相通过IO+EXIT中断的方式进行霍尔传感器数据的读取。将IO口配置为上升沿+下降沿中断触发的方式。当霍尔传感器信号发生发生信号的变化就会触发中断在中断

kubelet组件的启动流程源码分析

概述 摘要: 本文将总结kubelet的作用以及原理,在有一定基础认识的前提下,通过阅读kubelet源码,对kubelet组件的启动流程进行分析。 正文 kubelet的作用 这里对kubelet的作用做一个简单总结。 节点管理 节点的注册 节点状态更新 容器管理(pod生命周期管理) 监听apiserver的容器事件 容器的创建、删除(CRI) 容器的网络的创建与删除

PostgreSQL核心功能特性与使用领域及场景分析

PostgreSQL有什么优点? 开源和免费 PostgreSQL是一个开源的数据库管理系统,可以免费使用和修改。这降低了企业的成本,并为开发者提供了一个活跃的社区和丰富的资源。 高度兼容 PostgreSQL支持多种操作系统(如Linux、Windows、macOS等)和编程语言(如C、C++、Java、Python、Ruby等),并提供了多种接口(如JDBC、ODBC、ADO.NET等

OpenCV结构分析与形状描述符(11)椭圆拟合函数fitEllipse()的使用

操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆,该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意,由于数据点靠近包含的 Mat 元素的边界,返回的椭圆/旋转矩形数据