编译原理-求FOLLOW集合

2024-03-01 16:50
文章标签 编译 原理 集合 follow

本文主要是介绍编译原理-求FOLLOW集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

  • 为什么需要求FIRST集合:因为一个产生式存在多个候选式,选择哪一个候选式是不确定的,所以这就产生了回溯。回溯需要消耗大量的计算、存储空间,所以我们需要消除回溯。而消除回溯的其中一种方法叫作“预测”,即根据栈顶非终结符去预测后面的候选式,那预测方法就是求第一个非终结符,来判断是否和读头匹配,以达到预测的效果
  • 为什么需要求FOLLOW集合:求FOLLOW集合的目的和FIRST集合的目的是一样的,但是应该对的情形不一样,当出现了下列情形时,求FIRST集合已经达不到要求了

微信公众号:JavaWeb架构师

但是我们观察后发现,当F推出ε时,下面的E推出的a是能进行匹配的,在F这个位置求到a,就是在求FOLLOW集合

FOLLOW集合定义

  • 文字定义:FOLLOW(A)集合是所有紧跟A之后的终结符或#所组成的集合(#是句尾的标志),称FOLLOW(A)是A的随符集

  • 公式定义:
    设G是上下文无关文法,A ∈ VN,S是开始符
    微信公众号:JavaWeb架构师
    则:
    微信公众号:JavaWeb架构师

  • 注意

    • 当A是最右部的时候,# 加入 FOLLOE(A)

计算FOLLOW集合步骤

  • 求解非终结符A的随符集FOLLOW(A)
  • 1)对S,将 # 加入 FOLLOW(S),然后再按后面的处理
  • 2)若B → αAβ是G的产生式,则将FIRST(β) - ε 加入FOLLOW(A)
  • 3)若B → αA是G的产生式,或B → αAβ是G的产生式(β 多次推导后得到ε ),则将FOLLOW(B) 加入到FOLLOW(A) 【因为把B用αA替换之后,B后面紧跟的字符就是A后面紧跟的字符】
  • 4)反复使用2)-3),直到FOLLOW集合不再增大为止

  • 注意

    • 这里的文法G必须是消除左递归且提取了左因子(点击查看提取左因子的办法)

例题

  • 对如下文法G,E为开始符,求E、T、F的随符集
1.E  →  TE'
2.E'  →  +TE'
3.E'  →  ε
4.T  →  FT'
5.T'  →  *FT'
6.T'  →  ε
7.F  →  i
8.F  →  (E)

解:

---------------FOLLOW(E)---------------
FOLLOW(E) = {)} ;   // 8. 规则2)
又 ∵  E是开始符,所以FOLLOW(E) = { #,) } ;     // 规则1)---------------FOLLOW(T)---------------
FOLLOW(T) = FIRST(E') - ε; // 1.  规则2)
FIRST(E') = {+,ε};     // 2. 3.  
当E' = ε时,E  →  TE' 就是 E  →  T,所以FOLLOW(E)也要加入FOLLOW(T),
∴ FOLLOW(T) = {+, #,)}
同理,FOLLOW(E')也需要加入到FOLLOW(T)中,
FOLLOW(E') = FOLLOW(E) = { #, )};   // 1. 规则3)
∴ FOLLOW(T) = {+, #,)}---------------FOLLOW(F)---------------
与FOLLOW(F)相关的式子有:
T'  →  *FT'
T  →  FT'先,T'  →  *FT'
∴ FOLLOW(F) = FIRST(T') - ε;
FIRST(T') = {*,ε}
当T'为ε时,也要把FOLLOW(T')加入FOLLOW(F)中,
FOLLOW(T') = {+, #,)},∴ FOLLOW(F) =  {+,*, #,)}再,T  →  FT',
∴ FOLLOW(F) = FIRST(T') - ε;
当T'为ε时,也要把FOLLOW(T)加入FOLLOW(F)中,
∴ FOLLOW(F) =  {+,*, #,)}

    • 形如 T’ → *FT’,求FOLLOW(T’)时,针对本句,可以忽略3),因为是还是再求FOLLOW(T’)
    • 对于产生了ε的,一定要记得3)
    • FIRST求解的时候,关注点在左部,进行推导;FOLLOW求解的时候,关注点在右部,看跟随

其它

  • 课件下载:
关注下方微信公众号,
回复:
FOLLOW.code
  • 欢迎加入交流群:451826376

  • 更多信息:www.itcourse.top

完整教程PDF版本下载

这篇关于编译原理-求FOLLOW集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

Nacos注册中心和配置中心的底层原理全面解读

《Nacos注册中心和配置中心的底层原理全面解读》:本文主要介绍Nacos注册中心和配置中心的底层原理的全面解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录临时实例和永久实例为什么 Nacos 要将服务实例分为临时实例和永久实例?1.x 版本和2.x版本的区别

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事

电脑系统Hosts文件原理和应用分享

《电脑系统Hosts文件原理和应用分享》Hosts是一个没有扩展名的系统文件,当用户在浏览器中输入一个需要登录的网址时,系统会首先自动从Hosts文件中寻找对应的IP地址,一旦找到,系统会立即打开对应... Hosts是一个没有扩展名的系统文件,可以用记事本等工具打开,其作用就是将一些常用的网址域名与其对应

Dubbo之SPI机制的实现原理和优势分析

《Dubbo之SPI机制的实现原理和优势分析》:本文主要介绍Dubbo之SPI机制的实现原理和优势,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Dubbo中SPI机制的实现原理和优势JDK 中的 SPI 机制解析Dubbo 中的 SPI 机制解析总结Dubbo中

Android NDK版本迭代与FFmpeg交叉编译完全指南

《AndroidNDK版本迭代与FFmpeg交叉编译完全指南》在Android开发中,使用NDK进行原生代码开发是一项常见需求,特别是当我们需要集成FFmpeg这样的多媒体处理库时,本文将深入分析A... 目录一、android NDK版本迭代分界线二、FFmpeg交叉编译关键注意事项三、完整编译脚本示例四

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

Spring框架中@Lazy延迟加载原理和使用详解

《Spring框架中@Lazy延迟加载原理和使用详解》:本文主要介绍Spring框架中@Lazy延迟加载原理和使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录一、@Lazy延迟加载原理1.延迟加载原理1.1 @Lazy三种配置方法1.2 @Component