首页 > 其他分享 >day05_编译原理学习

day05_编译原理学习

时间:2024-09-16 20:49:51浏览次数:12  
标签:文法 终结符 加入 day05 编译 如果 集合 原理 左部

第四章 语法分析

FOLLOW的计算和定义

    • 定义:被定义为\alpha从推导得到的串首符号的集合(其中\alpha是任意的文法符号)。
    • 算法:求解的方法:不断应用以下规则,直到没有新的终结符号或空集被加入到任何集合中为止。
      • 1)如果X是一个终结符号,那么= X;
      • 2) 如果X是一个非终结符,且X\rightarrow Y\textup{1}Y\textup{2}...Y\textup{k}(k \geq 1)是一个产生式,\alphaFIRST(Y\textup{i})中且\epsilon在所有的FIRST(Y\textup{1}-Y\textup{i})中,也就是说,Y\textup{1}...Y\textup{i-1}经零步或者多步推导可以得出\epsilon。如果对于所有的i= 1,2,...,k,\epsilonFIRST(Y\textup{i})中,那么就将\epsilon加入到FIRST(X ).
      • 3)如果X\rightarrow \epsilon是一个产生式,那么将\epsilon加入到
    • 例子:
    • 具体解题思路:求解文法中所有的产生式左部的FIRST集合,只需要看每个左部的所有产生式右部的首字符A。
      • 1. 如果A是终结符,那么将其加入到左部对应的 集合中。
      • 2. 如果A是非终结符,那么继续求解FIRST(A),并将FIRST(A)加入到左部对应的集合中去。
      • 3. 如果A \Rightarrow \epsilon,那么也将\epsilon加入其中。
      • 注意:如果产生式的右部由“|”连接,对于"|"左右两边的句型运用上述相同的规则。
    • 计算X\textup{1}X\textup{2}...X\textup{n}FIRST集合
  • FOLLOW

    • 定义:FOLLOW(A)可能在某些句型中紧跟在A右边的终结符号的集合。
    • 求解所有非终结符A的FOLLOW(A)集合时,不断应用以下规则,直到不再有新的终结符可以加入到任意的FOLLOW集合中为止。
      • 1) 将\$(是输入右端的结束标记)放入到FOLLOW(S)集合中,其中S为文法的开始符号
      • 2)如果存在一个产生式,那么FIRST(\beta )中除了\epsilon之外的所有符号都在中。
      • 3)如果存在一个产生式,或存在产生式FIRST(\beta )包含, 那么FOLLOW(A)中的所有符号都在 中.
    • 具体解题思路:求解所有非终结符的 FOLLOW集合:
      • 1. 先将结束标记 \$ 加入到开始符号FOLLOW 集中,即 FOLLOW(S) = {\$ ,...}。
      • 2. 再将所有非终结符中能推导出\epsilon的非终结符列举到一个集合中。
      • 3. 紧接着对于非终结符B,观察文法中所有产生式的右部是否存在B,如果存在,则判断B在产生式中的句型:
        • 如果是 ,直接将FOLLOW(A)加入到
        • 如果是则需要继续判断\beta是否是终结符
          • 终结符,那么就将其加入到FOLLOW(A)
          • 非终结符,那么就将FIRST(\beta )加入到 中,接着判断该非终结符是否在第二步中的非终结符集合中
            • 不在则进行下一轮判断。
            • 如果在,就将 FOLLOW(A) 加入到   中。
    • 根据 FOLLOW集构造表达式文法的可选集SELECT

      • (day04)定义回顾:由于各个具有相同的左部的产生式的SELECT集不存在交集,故图片中表达式的文法是LL(1)文法。
    • 根据表达式文法的可选集构造预测分析表 

附:FIRST和FOLLOW集合的计算从定义来看较为晦涩,可以根据要点中“具体解题思路”再反复刷题和观看视频进行理解!

标签:文法,终结符,加入,day05,编译,如果,集合,原理,左部
From: https://blog.csdn.net/m0_74985290/article/details/141905497

相关文章

  • day07_编译原理学习
    第四章语法分析LR文法的概述LR文法的概念LR文法是最大的,可以构造出相应移入-归约语法分析器的文法类L:对输入进行从左到右的扫描R:反向构造出一个最右推导序列LR(k)分析需要向前查看k个输入符号的LR分析k=0和k=1这两种情况具有实践意义,当省略k时,k=1LR分析法的......
  • C++从小白到大牛:C++智能指针的使用、原理和分类
    C++从小白到大牛:C++智能指针的使用、原理和分类引言在C++编程中,指针是一个强大但危险的工具。它们允许直接操作内存,但也可能导致内存泄漏、悬空指针等问题。为了解决这些问题,C++引入了智能指针(SmartPointers)的概念。智能指针是一种封装了原始指针的对象,它们自动管理内存的生命周期......
  • ARM SMMU原理与IOMMU技术(“VT-d” DMA、I/O虚拟化、内存虚拟化)
    名词缩写ASID:AddressSpaceID地址空间标识符CD:ContextDescriptor;上下文描述符;CTP:Context-tablepointer上下文表指针EPT:ExtendedPageTable扩展页表GPA:GuestPhyicalAddress客人的实际地址GVA:GuestVirtualAddress访客虚拟地址HPA:HostPhyicalAddress......
  • 【AI大模型】ChatGPT模型原理介绍(下)
    目录......
  • 一个简单的交叉编译riscv的makefile脚本
    为了编写一个使用特定交叉编译工具链(在这个例子中是`riscv64-unknown-linux-gnu-`)来编译`hello.c`的Makefile脚本,你需要设置`CROSS_COMPILE`变量,并在编译命令中使用这个变量来指定交叉编译器的路径。下面是一个简单的Makefile示例:```makefile#定义交叉编译工具链的前缀CROSS_COM......
  • Mysql数据库的原理和应用
    第一章数据库概述一学习环境介绍1.Windows10/11非家庭版内存8g2.Vmwareworkstation16.03.LAMP--LinuxAparchemysqlPHPLNMP--LinuxnginxmysqlPHPWAMP--WindowsAparchemysqlPHPWNMP--WindowsnginxmysqlPHP注意:Windows是非客服端操作系统,而是服务器版......
  • cefsharp.H264.x64.109(88、84、79)可播放视频包免费编译版
    一、下载网址:https://www.nuget.org/packages/CefSharp.H264.x64/109.1.110?_src=templateDownloadpackage(82.59MB)如果是直接下载的cefsharp.h264.x64.109.1.110.nupkg1、用解压缩软件,将这个文件解压缩2、在解压缩目录中(cefshap\cefsharp.h264.x64.109.1.110\cef),再次解压......
  • 并发容器(Map、List、Set)实战及其原理分析
    1.JUC包下的并发容器Java的集合容器框架中,主要有四大类别:List、Set、Queue、Map,大家熟知的这些集合类ArrayList、LinkedList、HashMap这些容器都是非线程安全的。所以,Java先提供了同步容器供用户使用。同步容器可以简单地理解为通过synchronized来实现同步的容器,比如Vector......
  • GCC安全编译选项
    以CMake为例,给出安全编译选项的定义。关闭RPATH特性。set(CMAKE_SKIP_RPATHTRUE)开启栈保护。set(CMAKE_CXX_FLAGS"${CMAKE_CXX_FLAGS}-fstack-protector-strong")或者set(CMAKE_CXX_FLAGS"${CMAKE_CXX_FLAGS}-fstack-protector-all")开启GOT表保护。set(CM......
  • 《 C++ 修炼全景指南:十 》自平衡的艺术:深入了解 AVL 树的核心原理与实现
    摘要本文深入探讨了AVL树(自平衡二叉搜索树)的概念、特点以及实现细节。我们首先介绍了AVL树的基本原理,并详细分析了其四种旋转操作,包括左旋、右旋、左右双旋和右左双旋,阐述了它们在保持树平衡中的重要作用。接着,本文从头到尾详细描述了AVL树的插入、删除和查找操作,配......