精华内容
下载资源
问答
  • 自底向上分析方法

    前言

    参考课上PPT内容。 该学习笔记目前仅打算个人使用。
    后续会进一步整理,包括添加笔记内容,标明参考资料。

    更新中。。。


    参考资料

    1. 《编译技术》
    2. 邵老师PPT

    跳过目录

    一、自底向上分析

    1、基本算法思想

    若采用自左向右地扫描和分析输入串,那么自底向上的基本算法是:

    从输入符号串开始,通过反复查找当前句型的句柄(最左简单短语),并利用有关规则进行规约。

    • 若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子;
    • 否则有语法错误。

    分析过程是重复以下步骤 :

    1. 找出当前句型的句柄 x (或句柄的变形);
    2. 找出以 x 为右部的规则 X → x ;
    3. 把 x 规约为X,产生语法树的一枝。

    关键: 找出当前句型的句柄 x(或其变形),难点。

    二、移进-归约分析

    • 自底向上分析的一般过程
    • Shift-reduce parsing

    1、要点

    • 设置符号栈,用来纪录分析的历史和现状 ,并根据所面临的状态,确定下一步动作是移进还是规约。

    在这里插入图片描述

    2、分析过程

    1、把输入符号串按顺序一个一个地移进符号栈(一次移一个);

    2、检查栈中符号,当在栈顶的若干符号形成当前句型的句柄时,就根据规则进行规约——将句柄从符号栈中弹出,并将相应的非终结符号压入栈内(即规则的左部符号),然后再检查栈内符号串是否形成新的句柄,若有就再进行规约,否则移进符号;

    3、分析一直进行到读到输入串的右界符为止。最后,若栈中仅含有左界符号和识别符号,则表示分析成功,否则失败。

    3、优点

    • 简单明了,不断地进行移进规约。

    4、难点

    • 关键是确定当前句型的句柄。

    例:检查输入串 abbcde 是否是文法 G[S] 的合法句子。

    G[S]:

    S → aAcBe
    A → b
    A → Ab
    B → d

    若采用自底向上分析,即能否一步步规约当前句型的句柄,最终规约到识别符号S。先设立一个符号栈,我们仍然统一用符号 “ # ”作为待分析符号串的左右分界符。

    作为初始状态,先将符号串的左分界符推进符号栈作为栈底符号。

    分析过程如下表:

    步骤符号栈输入符号串动作
    1#abbcde#准备。初始化
    2#abbcde#移进
    3#abbcde#移进
    4#aAbcde#归约(A → b)
    5#aAbcde#移进
    6#aAcde#归约(A → Ab)
    7#aAcde#移进
    8#aAcde#移进
    9#aAcBe#归约(B → d)
    10#aAcBe#移进
    11#S#归约(S → aAcBe)
    12#S#成功

    注:

    • 例子的分析过程是一步步地规约当前句型的句柄。

      该句子的唯一语法树为:
      在这里插入图片描述

    • 栈内符号串 + 未处理输入符号串 = 当前句型

    • 句柄都在栈顶

    • 实际上,以上分析过程并未真正解决句柄的识别问题。

    问题:

    上述分析过程中识别句柄的过程,主要看栈顶符号串是否形成规则的右部。

    这种做法形式上是正确的,但在实际上不一定正确。

    举例的分析过程可以说是一种巧合。

    因为不能认为:对句型 xuy 而言,若有U → u,即U ⇒ u 就断定u是简单短语, u 就是句柄,而是要同时满足Z ⇒ ∗ \stackrel{*}{\Rightarrow} xUy

    步骤符号栈输入符号串当前句型
    5#aAbcde#aAbcde

    A → b ∴ A ⇒ b
    A → Ab ∴ A ⇒ Ab

    若用 A → b 归约, 得 aAAcde ×
    若用 A → Ab 归约,得 aAcde √

    展开全文
  • 1、 理解自底向上语法分析方法; 2、 用LR分析技术实现语法分析器; 3、 熟练掌握LR分析程序的构造方法。
  • 一、自底向上分析概述 底向上的语法分析 从分析树的底部(叶节点)向顶部(根节点)方向构造分析树 可以看成是将输入串w归约为文法开始符号S的过程 顶向下的语法分析采用最左推导方式 底向上的语法分析采用最...

    声明:本系列文章,是根据中国大学MOOC网 哈工大的编译原理 这门课学习而成的学习笔记。

    一、自底向上分析概述

    自底向上的语法分析

    • 从分析树的底部(叶节点)顶部(根节点)方向构造分析树
      可以看成是将
      输入串w归约为文法开始符号S
      的过程

    • 自顶向下的语法分析采用最左推导方式
      自底向上的语法分析采用最左归约方式(反向构造最右推导)

    • 自底向上语法分析的通用框架
      移入-归约分析(Shift-Reduce Parsing)
      在这里插入图片描述
      在这里插入图片描述

    移入-归约分析的工作过程

    在这里插入图片描述

    移入-归约分析器可采取的4种动作

    • 移入:将下一个输入符号移到栈的顶端
    • 归约:被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端,并决定用哪个非终结符来替换这个串
    • 接收:宣布语法分析过程成功完成
    • 报错:发现一个语法错误,并调用错误恢复子例程

    移入-归约分析中存在的问题

    在这里插入图片描述
    在这里插入图片描述

    二、LR分析法概述

    LR分析法

    • LR文法(Knuth, 1963)是最大的、可以构造出相应移入-归约语法分析器的文法类

      • L: 对输入进行从左到右的扫描
      • R: 反向构造出一个最右推导序列
    • LR(k)分析
      需要向前查看k个输入符号的LR分析
      k = 0 和 k = 1 这两种情况具有实践意义,当省略(k)时,表示k =1

    LR 分析法的基本原理

    • 自底向上分析的关键问题是什么?
      如何正确地识别句柄

    • 句柄是逐步形成的,用“状态”表示句柄识别的进展程度
      在这里插入图片描述

    LR 分析器(自动机)的总体结构

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    LR 分析器的工作过程

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    LR 分析算法

    在这里插入图片描述

    三、LR(0)分析

    LR(0)项目

    在这里插入图片描述

    增广文法

    在这里插入图片描述

    引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态

    文法中的项目

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    由①②可知,当等待S时,实际也是再等待v,故(0)(2)等价,同理,(3)(7)(11)等价,(5)(13)等价
    在这里插入图片描述
    当后继项目中有非终结符时,需要写出其等价项目

    CLOSURE( )函数

    在这里插入图片描述
    在这里插入图片描述

    GOTO ( )函数

    在这里插入图片描述

    构造LR(0)自动机的状态集

    在这里插入图片描述

    LR(0)分析表构造算法

    在这里插入图片描述

    LR(0) 分析过程中的冲突

    这里是引用
    i2中,E->T· 要求进行归约,而T->T·*F要求进行移进,造成了冲突
    在这里插入图片描述

    四、SLR分析

    SLR分析法的基本思想

    在这里插入图片描述

    • 简单来说,文法,就是看该符号的FOLLOW集来判断此时倒是是规约还是移进,肯定会有人问,什么是FOLLOW集啊,所以
      在这里插入图片描述

    这里是引用
    I2来说,E的follow集中没有*,故此时应该进行移入,不应该规约,I9同理

    SLR 分析表构造算法

    在这里插入图片描述

    SLR 分析中的冲突

    在这里插入图片描述
    I2中,第一条表遇到等号进行移入,第二条,R的FOLLOW中也有R,表明遇到=进行规约,此时造成了规约移入冲突。

    五、LR(1)分析

    LR(1)分析法的提出

    在这里插入图片描述

    LR(1)分析法的提出

    在这里插入图片描述

    规范LR(1)项目

    在这里插入图片描述

    等价LR(1)项目

    在这里插入图片描述

    在这里插入图片描述
    推断时,要在后面加上后继符,自身的和继承的都要加,比如I0中,L的后继符本身有个=,同时也继承了S’的$,故其中L要写两遍,其后继也要写两遍。
    在这里插入图片描述
    如I4和I11是同心的,I7和I13是同心的,I5和I12是同心的,I8和I10是同心的

    LR(1)项目集闭包

    在这里插入图片描述

    GOTO 函数

    在这里插入图片描述

    为文法G’ 构造LR(1)项集族

    在这里插入图片描述

    LR(1)自动机的形式化定义

    在这里插入图片描述

    • LR分析表构造算法
      在这里插入图片描述

    六、LALR分析法

    LALR分析法的提出

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    合并同心项集产生的问题

    在这里插入图片描述
    I6中遇到d,将c规约成A,而在I9中,遇到d,则规约成B,故这两个不能合并,否则会造成归约-归约冲突。

    在这里插入图片描述

    • 上述例子中,r至少包含dcd三个符号,同时I4和I9合并后不会造成冲突,所以可以合并。但例如输入一个d,如果不合并,则在I4就检测出问题,如果合并,则会在I4->I0->I2才会发现错误。
    • LALR合并只合并其展望符相关的,而移位和展望符没有任何关系,故LALR不会作错误的移进操作

    LALR(1)的特点

    1. 形式上与LR(1)相同
    2. 大小上与LR(0)/SLR相当
    3. 分析能力介于SLR和LR(1)二者之间
      SLR<LALR(1)<LR(1)
      合并后的展望符集合仍为FOLLOW集的子集

    七、二义性文法的LR分析

    二义性文法的特点

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    二义性文法的使用

    • 应该保守地使用二义性文法,并且必须在严格控制之下使用,因为稍有不慎就会导致语法分器所识别的语言出现偏差

    八、LR分析中的错误处理

    语法错误的检测

    • 当LR分析器在查询分析表并发现一个报错条目时,就检测到了一个语法错误

    错误恢复策略

    • 恐慌模式错误恢复
    • 短语层次错误恢复

    恐慌模式错误恢复

    在这里插入图片描述

    短语层次错误恢复

    • 检查LR分析表中的每一个报错条目,并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误
    • 然后构造出适当的恢复过程

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 自底向上分析——LR方法

    千次阅读 2017-07-23 16:54:50
    自底向上分析——LR方法LR(k)表示在分析时要求向前看k个符号(即看输入流的前k个符号),以便唯一地确定分析动作。LR(k)一词来自:Left-to-right parse,Rightmost-derivation,k-token lookahead。LR分析主要有LR(0)...

    自底向上分析——LR方法

    LR(k)表示在分析时要求向前看k个符号(即看输入流的前k个符号),以便唯一地确定分析动作。LR(k)一词来自:Left-to-right parse,Rightmost-derivation,k-token lookahead。LR分析主要有LR(0)分析法,SLR(1)分析法,LR(1)分析法以及SALR(1)分析法。

    LR方法的思想:从输入流依次把符号移入到符号栈中,直至栈顶部中出现一个句柄;之后对句柄进行规约,直至栈顶部中不出现句柄为止;再重复上述过程,直至最终规约为一个开始符,且输入流为空。注意:真正的LR分析器并不用符号栈,而是用状态栈。LR分析法的主要动作是移入归约

    增广文法:为处理方便,LR分析法通常要求文法的开始符不出现在任何产生式的右端。若不满足要求,则只需增加一条产生式: ZS ZS #,其中Z是新开始符,S是原开始符。这样扩充后的文法被称为原文法的增广文法。

    基本概念

    归约顺序:一个句型可有多个简单短语,因此,归约顺序可有多种。LR分析法采用用的是从左到右,即每次归约最左简单短语(称为句柄)的办法。也就是说,从左到右地扫描输入串,并且一旦出现一个简单短语,就立即进行归约(否则会出现倒退进行归约的不合理的现象)。

    短语:称句型 αηβ 中的 η 是一个短语,若有: SαAβ A+η ,其中S是文法的开始符。换句话说,称句型αηβ中的η是短语,如果存在一个句型αAβ, A+η

    简单短语:称句型αηβ中的η是一个简单短语,若有 SαAβ Aβ

    句柄:一个句型中可能有多个简单短语,而句柄是其中最左简单短语。是自底向上分析的核心动作归约的单位。

    规范推导:称一个句型推导为规范推导,如果它是最右推导的。

    规范句型:规范推导导出的句型。不一定每个句型都有规范推导。

    规范归约:如果归约的是最左简单短语(句柄),则称其归约为规范归约(从左到右的归约)。规范推导和规范归约存在互逆的关系。

    规范结论:如果给定句型是规范句型,则经规范归约后得到的仍是规范句型。

    活前缀

    规范前缀:称规范句型的前缀为规范前缀,如果其后部分不包含非终极符。显然,每个规范句型的前缀都是规范前缀。

    活前缀:称一个规范前缀 α 为活前缀,如果包含以下任意条件:

    1. α 不含简单短语;

    2. α 含一个简单短语,但其后没有符号。

      活前缀的含义:它表示至今被处理的终极符串部分在语法上是正确的。活前缀在分析格局中的逻辑关系如下图所示。它表示符号栈内容是活前缀 α ,符号栈内容和输入串连起来恰好形成规范句型(如果输入串是正确句子)。

    展开全文
  • 详细的自底向上分析法的解读

    千次阅读 2019-06-20 11:46:16
    详细的自底向上分析法的解读 LR构造分析表 LR分析表的结构如上,其分为两个部分Action Goto Action 两个参数状态i,终结符号a(s(i)代表第i个状态,r(i)代表第i条表达式) 移入j:j是一个状态,把j压入栈(同时移...

    详细的自底向上分析法的解读
    LR构造分析表
    LR分析表的结构如上,其分为两个部分Action Goto
    Action
    两个参数状态i,终结符号a(s(i)代表第i个状态,r(i)代表第i条表达式)
    移入j:j是一个状态,把j压入栈(同时移入a)
    归约A->B:把栈顶的B归约到A(并根据Goto表项压入新状态)
    接受:接受输入,完成分析
    报错:在输入中发现语法错误
    Goto
    Goto[i,A]=j
    什么时候查看Goto表?
    当出现规约时,如当前状态为032,分析动作为r3(E->ACD),将2弹出,查看Goto表[3][E],将新的状态压入栈中,再分析下一个字符是移进还是规约(查看Action表)

    LR(0)中不应出现的现象
    要求每个项目集的诸项目是相容的,即在同一项目集中,不应出现:
    1.移进项目与归约项目并存;
    2.多个归约项目并存.
    若文法G满足上述条件,即不含上述冲突项目,则称G为LR(0)文法.
    显然,只有当一文法是LR(0)文法时,才能构造出无冲突动作的分析表来.

    当出现移入-规约的冲突时知道不是LR(0)文法,如果用Follow集可以解决掉冲突则为LSR(1)文法。

    SLR(1)与LR(0)的关系:
    SLR(1)与LR(0):简单的LR语法分析技术(即SLR(1)分析技术)的中心思想是根据文法构造出LR(0)自动机。
    LR(0):见到First集就移进,见到终态就归约
    SLR(1)见到First集就移进,见到终态先看Follow集,与Follow集对应的项目归约,其它报错。
    对于存在移进-归约冲突的项目集:
    Ii={A1→b.a11,…,Am→·amm,B1→·,…,Bn→·}

    FOLLOW(Bk)( 1≦k≦n)与{a1,a2,…,am}两两互不相交时,则称满足这种条件的文法为SLR(1),可以采用SLR(1)分析
    即规约后的非终结符的Follow集与将要移进的终结符没有交集,根据Follow集判断在当前状态应该用哪条“产生式”

    具体SLR(1)分析表的构造:

    对于项目集:
    Ii={ B→·b, A→·, C→·}

    (1)若GO[Ii, b]=Ij ,置Action[i,b]=“sj”
    (2)若a是Follow(A),置Action[i,a]=“rj”, j为A→
    (3)若a是Follow(C),置Action[i,a]=“rk”, k为C→
    (4)其他均置error
    即仅在 被规约出的非终结符 的 Follow集合元素对应的列 填写对应的规约动作

    LR(1)在LR(0)的基础上增加了向前搜索符号,

    精确地指明哪些符号可以跟在句柄的后面

    展开全文
  • 自底向上分析法与其他分析法

    千次阅读 2017-02-17 12:37:37
    http://www.yingzinanfei.com/2017/02/17/zidixiangshangfenxifayuqitafenxifa/底向上的分析技术:自底向上分析法(bottom-up analysis method )一种语言形式分析算法.是根据形式文法的重写规则,叶开始逐级向上...
  • 编译原理实验-PL0自底向上语法分析

    千次阅读 2019-11-29 19:04:57
    最近顶着考研的压力去做了一下编译原理的实验,实验的要求是写一个PL/0语法的编译器,一开始想从网上找找有没有现成的代码改一改就完事了,结果百度的结果都是递归下降分析,而老师的课程大部分都在讲自底向上分析的...
  • /* 表达式文法: E->E+T|T T->T*F|F F->(E)|$num */ 保证执行
  • LR(0)分析方法的不足 LR(0)方法对文法的要求严格 LR(0)方法容易出现冲突状态 一个文法例: GE: SE $ [1] EE + T [2] ET [3] TT ? P [4] TP [5] Pid [6] P( E ) [7] ? ? ? ? ? ? ? ? ? ? ? ? ? 图 G?E 的LRSM0 + E P ...
  • LR(0)自底向上语法分析 详细介绍自底向上语法分析的处理过程以及相应的问题解决方法
  • 关于编译原理中自底向上分析法的详解,详细讲解了常用的几个分析器方法,以及之间的对比.
  • 5) 模拟分析过程。 如输入一个句子,如果该句子合法则输出与句子 对应的语法树;能够输出分析过程中每一步符号 栈的变化情况以及根据当前最左素短语进行归约 的过程。如果该句子非法则进行相应的报错处理。
  • 编译原理-语法分析自底向上

    千次阅读 2019-11-20 20:35:22
    自底向上分析概述 LR(0) 项目自动机 LR(0) 项 增广 构造自动机--项集,项集闭包,项集投影 内核项 与 非内核项 构造自动机--GOTO函数 移入规约冲突 SLR LR(1) LALR(1) LALR分析器与LR分析器 子问题 构造自动机--完整...
  • 自底向上的语法分析

    千次阅读 2019-05-05 21:57:20
    文章目录概念移入-规约...自底向上的语法分析采用最左规约方式(反向构造最右推导) 移入-规约分析 工作过程 在对输入串的一次从左到右扫描过程中,语法分析器将零个或多个输入符号移入到栈的顶端,直到它可以对...
  • LR语法分析器 自底向上分析的构造 包括文档和代码
  • 自底向上的语法分析相当于从叶子节点开始向上一直到根部构造一棵语法树。我们将使用移入-归约法完成这一过程。 归约 定义:一个与某产生式体相匹配的特定子串被替换成该产生式头部的非终结符号。相当于反向的最右...
  • 自底向上语法分析LR(1)

    千次阅读 2019-10-17 13:42:45
    自底向上分析方法,也称移进-归约分析法,粗略地说它的实现思想是对输入符号串左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,就用该产生式的左部非...
  • 主要介绍了C++实现自底向上的归并排序算法,结合实例形式较为详细的分析总结了自底向上的归并排序算法的原理与具体实现技巧,需要的朋友可以参考下
  • 语法分析之自底向上分析

    千次阅读 2013-12-28 18:02:24
    自底向上分析法不存在要进行消除左递归和左公共因子。一般编译器中大多使用这种语法分析。  首先,要解决的第一个问题是,底向上递归的顺序。  1:每次从最左短语开始归约。 最左短语称为句柄,也就是包含终结...
  • 编译原理自底向上的语法分析(1)
  • 编译原理-自底向上优先分析概述

    千次阅读 2018-05-07 10:25:07
    前言 前面学了顶向下的分析方法,它是使用推导的方式进行语法分析。...自底向上分析所使用的自动机是PDA(下推自动机) 工作方式“移进-规约” 从左至右让输入串进栈,在移动的过程中不断查看栈顶
  •  自底向上分析法,也称移进-归约分析法。 它的实现思想是对输入符号串左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,(该句柄对应某产生式的右部),就...
  • 自底向上分析方法,也称移进-归约分析法。 实现思想: 对输入符号串左向右进行扫描,并将输入符逐个移入一个栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,就用该产生式的左部非终结符代替相应右部的...
  • 一.顶向下 方法 二.自底向上 方法 短语:在一个树中所有的子树的叶子结点 直接短语所有的子树中,高度为1的叶子结点 句柄 在所有的直接短语中最左边那个 例题: 步骤: ...
  • 自底向上语法分析的本质与原理

    千次阅读 2017-08-21 23:26:40
    语法分析的本质就是是否可以生成一颗语法树,它的叶子节点及终结符与我们程序的符号流一致,存在的正确,不存在的错误。  我们可以这样思考,我们将程序的符号表看做是语法树的叶子节点,按照文法进行反向推到,...
  • 底向上句法分析一般采用LR分析法,该刚发要求文法不包含移进--归约或者归约--归约冲突,由于自然语言的歧义性,不可避免的存在各种冲突,因此,自底向上分析法并不适合汉语句法分析
  •  自底向上分析技术-简单优先分析法" TITLE="编译原理笔记13 自底向上分析技术-简单优先分析法" />  自底向上分析技术-简单优先分析法" /> 二、简单优先文法 a) 定义:一个文法G,如果它不含空串产生式,也...
  • 自底向上优先分析.ppt

    2014-01-17 15:00:59
    很不错的自底向上优先分析分析的恨透彻,值得一看的哦,亲
  • 《编译原理》-用例题理解-自底向上的语法分析,FIRSTVT,LASTVT集 转:https://www.cnblogs.com/xpwi/p/10989762.html 主页:https://www.cnblogs.com/xpwi/ 本笔记是对教材《编译原理》- 张晶老师版 做学习...
  • 顶向下和自底向上的实现方法

    千次阅读 2020-11-01 09:07:34
    1将一个大问题分解为小的易处理的子问题,每个子问题可以使用一个方法来实现,这种方法使得问题更加易于编写重用调试,修改和维护 2当一个大问题分解为许多子问题,各个子问题可以分配给不同的编程人员,这更加易于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,970
精华内容 19,188
关键字:

自底向上分析