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

    2021-05-10 22:55:58
    分析树的底部(叶节点向顶部根节点方向构造分析...可以看成是将输入串归约为文法开始符号S的过程【顶向下的语法分析采用最左推导方式自底向上的语法分析采用最左归约方式(反向构造最右推导)】 每次规约“句柄” ...


    参考哈工大课件

    自底向上的语法分析

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

    自顶向下的语法分析采用最左推导方式;
    自底向上的语法分析采用最左归约方式,实际上是 反向构造最右推导

    自底向上语法分析的通用框架:移入-归约分析

    1)在对输入串的一次从左到右扫描过程中,语法分析器将零个或多个输入符号移入到栈的顶端,直到它可以对栈顶的一个文法符号串β进行归约为止
    2)它将β归约为某个产生式的左部
    3)语法分析器不断地重复这个循环,直到它检测到一个语法错误,或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时,语法分析器停止运行,并宣称成功完成了语法分析)为止
    注意:每步规约都是规范规约,每次规约“句柄”
    移入-归约分析器可采取的4种动作:

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

    移入-归约分析中存在的问题
    造成错误的原因:错误地识别了句柄

    LR分析法概述

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

    L: 对输入进行从左到右的扫描
    R: 反向构造出一个最右推导序列
    LR(k)分析:需要向前查看k个输入符号的LR分析。当省略(k)时,表示k =1

    1. LR 分析法的基本原理
      自底向上分析的关键问题是:如何正确地识别句柄。
      句柄是逐步形成的,用“状态”表示句柄识别的进展程度
      LR分析器基于这样一些状态来 构造自动机进行句柄的识别

    例:S→bBB
    S→·bBB 移进状态
    S→b·BB / S→bB·B 移进、待归约状态
    S→bBB· 归约状态
    注意: 产生式A→ε 只生成一个项目A→ ·

    1. LR 分析器(自动机)的总体结构
      在这里插入图片描述
      LR 分析表的结构:
    • sn:将符号a、状态n 压入栈
    • rn:用第n个产生式进行归约

    例:文法
    ① S→BB
    ② B→aB
    ③ B→b
    在这里插入图片描述

    输入bab#

    状态剩余输入动作
    0#bab#
    04#bab#0和b比较s4,移入b,添加4
    02#Bab#4和a比较r3,归约文法B→b右部长度1,在符号栈和状态栈中分别移出1个符号,在符号栈中进入B。此时栈顶是0,遇到刚规约出的B,到状态2,添加2状态
    023#Bab#2和a比较s3,移入a,添加3
    0234#Bab#3和b比较s4,移入b,添加4
    0236#BaB#4和#r3,归约文法B→b,4和b出栈,B进栈。3和B比较到状态6,6进栈
    025#BB#6和#比较r2,B→aB,36、aB出栈B进栈。2和B到到状态5,5入栈
    0#S#5和#比较r1,S→BB,25、BB出栈,S入栈。
    01#S#0和S比较到状态1,1入栈
    1遇到#成功接收acc
    • 如果ACTION[sm , ai]=acc,那么分析成功
    • 如果ACTION[sm , ai]=err ,那么出现语法错误
    //LR 分析算法
    输入:串w和LR语法分析表,该表描述了文法G的ACTION函数和GOTO函数。
    输出:如果w在 L(G)中,则输出w的自底向上语法分析过程中的归约步骤;否则给出一个错误指示。
    方法:初始时,语法分析器栈中的内容为初始状态s0,输入缓冲区中的内容为w#。
    令a为w$的第一个符号;
    while(1) { /* 永远重复*/ 
      令s是栈顶的状态;
      if ( ACTION [s,a] = st ) {
        将t压入栈中;
        令a为下一个输入符号;
      } else if (ACTION [s,a] =归约A → β ) {
        从栈中弹出│ β │个符号;
        将GOTO [t,A]压入栈中;
        输出产生式 A → β ;
      } else if (ACTION [s,a] =接受) 
          break/* 语法分析完成*/
       else调用错误恢复例程;
    }
    

    LR(0)分析

    增广文法:如果G 是一个以S为开始符号的文法,则G的增广文法 G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法
    引入增广文法的目的:使新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态
    可以把等价的项目组成一个项目集( I ) ,称为项目集闭包(Closure of Item Sets),每个项目集闭包对应着自动机的一个状态
    在这里插入图片描述

    CLOSURE()函数

    计算给定项目集I的闭包:

    CLOSURE(I) = I∪{B→ · γ | A→α·Bβ∈CLOSURE(I) , B→γ∈P}

    //CLOSURE()函数
    SetOfltems CLOSURE ( I ) {
      J = I;
      repeat
        for ( J中的每个项A → α·Bβ ) 
           for ( G的每个产生式B → γ ) 
             if ( 项B → · γ不在J中 ) 
                将B → · γ加入J中;
      until 在某一轮中没有新的项被加入到J中;
      return J;
    }
    

    LR(0) 分析过程中的冲突:移进/归约冲突& 归约归约冲突
    在这里插入图片描述
    表达式文法的LR(0)分析表含有移进/归约冲突
    在这里插入图片描述
    如果LR(0)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(0)文法

    • 不是所有CFG都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法

    SLR分析

    在这里插入图片描述

    在状态2,使用LR0文法,不向后看符号,即不考虑上下文。由followE可以知道如果下一个符号是*,则采取移进,则不会产生冲突。

    SLR分析法的基本思想
    如果集合{a1, a2, …, am}和FOLLOW(B1), FOLLOW(B2),…,FOLLOW(Bn)两两不相交,则项目集I中的冲突可以按以下原则解决:

    • 设a是下一个输入符号
      若a∈{ a1, a2, …, am },则移进a;
      若a∈FOLLOW(Bi),则用产生式Bi→γi 归约
      此外,报错

    由此就可以化解冲突,如果能够化解冲突则成为SLR文法。
    在这里插入图片描述
    在这里插入图片描述
    只对于在follow集中的符号才进行归约

    //SLR 分析表构造算法
    构造G'的规范LR(0)项集族C = { I0, I1,, In}。
    根据Ii构造得到状态i。状态i 的语法分析动作按照下面的方法决定:
      if A→α·aβ∈Ii and GOTO( Ii , a )=Ij then ACTION[ i, a ]=sj
      if A→α.Bβ∈Ii and GOTO( Ii , B )=Ij then GOTO[ i, B ]=j
      if A→α·∈Ii且A ≠ S' then for a∈FOLLOW(A) do
    ACTION[ i, a ]=rj (j是产生式A→α的编号)
      if S'→S·∈Ii then ACTION [ i , $ ]=acc;
    没有定义的所有条目都设置为“error”。
    

    SLR分析存在的问题:
    SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)
    只是归约α的一个必要条件,而非充分条件

    LR(1)分析

    对于产生式 A→α的归约,在不同的使用位置,A会要求不同的后继符号。在特定位置,A的后继符集合是FOLLOW(A)的子集。
    规范LR(1)项目:
    将一般形式为 [A→α·β, a]的项称为 LR(1) 项,其中A→αβ 是一个产生式,a 是一个终结符(这里将$视为一个特殊的终结符)
    它表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符(lookahead)

    • LR(1) 中的1指的是项的第二个分量的长度
    • 在形如[A→α·β, a]且β ≠ ε的项中,展望符a没有任何作用
    • 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约。这样的a的集合总是FOLLOW(A)的子集,而且它通常是一个真子集。
      在这里插入图片描述
      在这里插入图片描述
    展开全文
  • 【学习笔记】编译原理——第五章 自底向上分析法 文章目录系列文章目录概述LR分析法LR0分析增广文法 概述 自底向上分析: 从分析树的底部向顶部方向构造分析树 可以看成是将输入串w规约为文法开始符号S的过程 ...

    系列文章目录

    【学习笔记】编译原理——第一章 编译引论

    【学习笔记】编译原理——第二章 词法分析

    【学习笔记】编译原理——第四章 自上而下分析法

    【学习笔记】编译原理——第五章 自底向上分析法

    【学习笔记】编译原理——第六章 语法制导翻译



    概述

    自底向上分析:

    1. 从分析树的底部向顶部方向构造分析树
    2. 可以看成是将输入串w规约为文法开始符号S的过程
    3. 自顶向下的语法分析采用最左推导方式
      自底向上的语法分析采用最左归约(反向构造最右推导)
    4. 自底向上语法分析的通用框架——移入归约分析

    在这里插入图片描述
    栈的左侧为栈底,右侧为栈顶
    每次归约的符号串称为句柄一旦句柄在栈顶形成我们立即将他归约

    栈内符号串+剩余输入 = “规范句型”

    【移入-归约分析中存在的问题】
    如果错误地识别了句柄,可能会导致规约错误。
    直接短语一定是产生式的右部,而产生式的右部不一定是直接短语

    LR分析法

    LR文法是最大的、可以构造出相应移入-归约语法分析的文法类
    L:对输入进行从到右的扫描
    R:反向构造出一个最推导序列

    LR(k)分析:需要向前查看k个输入符号的LR分析。k=0和k=1的情况具有实践意义,表示k=1。
    在自底向上中,我们遇到的关键问题是如何正确地识别句柄。句柄是逐步形成的,用“状态表示句柄识别的进展程度。
    句柄是逐步形成的,用”状态“表示句柄识别的进展程度。
    在这里插入图片描述
    移进项目:·后面紧跟着终结符
    待约项目:·后面紧跟着非终结符
    规约项目:·后右部的末尾称为规约项目

    可以通过一个例子看一下分析表的结构
    在这里插入图片描述

    LR0分析

    右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目。在这里插入图片描述

    增广文法

    如果G是一个以S为开始的符号的文法,则G的增广文法G‘就是在G中加上新开始符号S’和产生式S‘->S而得到的文法。
    比如说把下图中的左边变成右边,有人可能会问为啥要这样做?
    目的就是使得文法开始符号仅出现一个产生式的左边,从而使分析器只有一个接收状态。
    可以看到左边的开始符号E是1)2)两个产生式的开始符号,而用E’替换之后,文法的开始符号E’就只是一个产生式的开始符号了。
    在这里插入图片描述
    在这里插入图片描述
    不难理解,图中的红色和粉色项目是分别等价的项目。

    构造LR(0)自动机

    在这里插入图片描述
    如图:0号状态遇到S的时候进入1号状态,遇到B的时候进入2号状态,遇到b的时候进入4号状态,遇到a的时候进入3号状态。

    LR(0)分析表的构造

    在这里插入图片描述
    在这里插入图片描述
    我们可以看到,图中状态2存在冲突,自底向上递归的规则是一旦形成句柄我们就将他归约,而图中状态2的第一个项目是一个规约项目,无论输入是什么,把T规约成E,而第二个项目的含义是当输入符号为 * 时,我们要采取移入操作。所以第一个项目要求归约,第二个项目要求移入,产生了冲突,这样的冲突就叫做移进归约冲突。状态9也是类似的问题。

    如果LR(0)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(0)文法
    不是所有的CFG都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法。

    SLR分析

    为了解决移进归约冲突,我们可以采用SLR分析

    基本思想

    SLR分析表构造算法

    在这里插入图片描述
    如果给定文法的SLR分析表中不存在有冲突的动作,那么该文法称为SLR文法

    SLR分析中的冲突

    在这里插入图片描述
    第二个状态中的第一个项目表示当下一个符号是=时,我们采取移入动作,进入状态6。第二个项目表示,当遇到L的FOLLOW集中的符号时,进行规约。所以SLR也是存在冲突的。
    那么如何消解冲突呢?我们就引入了LR(1)分析

    LR(1)分析

    LALR分析

    基本思想

    寻找具有相同核心的LR(1)项集,并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合。
    然后根据合并后的项集族构造语法分析。如果分析表中没有语法分析动作冲突,给定的文法就称为LALR(1)文法,就可以根据该分析表进行语法分析。

    LALR(1)的特点

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

    二义性文法的LR分析

    二义性文法的特点:

    1. 每个二义性文法都不是LR的
    2. 某些类型的二义性文法在语言的描述和实现中很有用,因为非二义性文法需要引进更多的终结符,生成更多的产生式。
      二义性文法的使用:应该保守地使用二义性文法,并且需要在严格控制之下使用,因为稍有不慎就会导致语法分析所识别的语言出现偏差。

    LR去分析中的错误处理

    语法错误的检测

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

    错误恢复策略

    1. 恐慌模式错误恢复
    2. 短语层次错误恢复
      在这里插入图片描述

    在这里插入图片描述
    可以看出我们在原来的LR0分析表的空白处,填入了错误处理例程的指针。

    总结

    这一章节我们主要学习LR分析方法,先讲了LR(0)分析法,其存在移进归约冲突,于是我们又引入了SLR分析,SLR的思想是根据FOLLOW集中的元素进行移进或归约操作,它仍然存在冲突。于是我们引入LR(1)分析法,而LR(1)分析的状态转换图往往过于复杂,于是我们可以将具有相同核心的LR(1)项集合并为一个项集,这就是LALR(1)分析的思想。

    展开全文
  • 顶向下分析法 LL(1)的优缺点 自底向上分析法 基本思想: 引入点记号 写法1 写法2 LR(0)的操作:移进和规约 LR(0) 分析 构造LR(0)分析表

    自底向上分析法:
    LR(0),LR(1),SLR(1),LALR(1)是自下而上的分析法。
    在这里插入图片描述
    LR(1)文法分析最强,而 LR(0)文法分析最弱。
    LR(0) 和 SLR文法分析用的是 LR(0)自动机,LR(1)和 LALR文法分析用的是 LR(1)自动机。而LR(1)自动机构造方法和LR(0)自动机的构造方法相同,只是多增加了向前搜索符号。

    自顶向下分析法 LL(1)的优缺点

    在这里插入图片描述

    自底向上分析法在这里插入图片描述

    基本思想:

    在这里插入图片描述

    引入点记号

    在这里插入图片描述

    写法1

    在这里插入图片描述

    写法2

    在这里插入图片描述

    LR(0)解释:

    L:从左向右扫描输入串
    R:构造最右推导的逆过程
    0:不用前看符号来确定产生式的选择

    LR(0)的操作:移进和规约

    在这里插入图片描述
    给定句型:T * i ↑ (T * F)
    给定文法G[T]:

    T → T * F | F
    F → F ↑ P | P
    P → (T) | i
    

    构造出语法树:
    在这里插入图片描述

    短语(在语法树中,相当于子树的末端结点形成的符号串)

    i
    T * F
    (T * F)
    i ↑ (T * F)
    T * i ↑ (T * F)
    

    直接短语(在语法树中,相当于简单子树(只有一层分支的子树) 的末端结点形成的符号串)

    i
    T * F
    

    句柄(即直接短语中在语法树中位于最左边的为该句型的句柄)

    i
    

    LR(0) 分析在这里插入图片描述

    构造LR(0)分析表

    在这里插入图片描述

    LR(0)实例:

    构建GO函数项目簇

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

    SLR分析算法

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

    展开全文
  • 《编译原理》-用例题理解-底向上的语法分析,FIRSTVT,LASTVT集本笔记是对教材《编译原理》- ...从语法树的角度看自底向上分析的过程是以输入符号串作为端末结点符号串,向着根结点的方向往上构造语法树,是开始...

    《编译原理》-用例题理解-自底向上的语法分析,FIRSTVT,LASTVT集

    本笔记是对教材《编译原理》- 张晶老师版 做学习笔记。

    本篇就是第 5 章的笔记。

    (一)自底向上的语法分析概述

    自底向上语法分析

    自底向上语法分析从待输入的符号串开始,利用文法的产生式步步向上归约,试图归约到文法的开始符号。

    从语法树的角度看

    自底向上分析的过程是以输入符号串作为端末结点符号串,向着根结点的方向往上构造语法树,是开始符号正好是该语法树的根结点。

    自底向上语法分析过程实际上是一个不断进行直接归约的过程

    移进-规约大意:

    用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶符号串形成可归约串时(某个产生式的右部时),即把这个可归约串替换成(归约成)该产生式的左部的非终结符。

    自底向上语法分析法基本思想

    自左向右地扫描输入符号串,一遍把输入符号逐个移进分析栈,一边检查分析栈的栈顶符号串是否已经形成了句柄(句柄就是每个产生式的右部),如果形成句柄就把栈顶符号串替换为相应产生式左部的非终结符号,这种替换就称规约,再根据规约后的新栈顶,继续扫描,移进,规约。

    例题:移进-规约

    题目:

    给定文法 G[S]:

    (1)S -> aABe

    (2)A -> b

    (3)A -> Abc

    (4)B -> d

    解析:

    步骤: 1 2 3 4 5 6 7 8 9 10

    动作: 进 进 归 进 进 归 进 归 进 归

    a b (2) b c (3) d (4) e (1)

    b1f2aa28674d6a2da356535b7975fc81.png

    执行时,首先分析栈中会存放 # 到栈底,图上没有体现出来,应该在 a 的下面加上 #,将余留输入串最左边的字符放在分析栈栈首,此时栈中为 a,分析上面 4 句文法,文法的右部没有完全匹配的,所以没有构成句柄。

    此时,继续移进第二个输入符号 b,此时栈顶的 b 与文法的(4)产生式的右部匹配,用 A -> b 规约,得到栈中为 aA

    然后移进 b,c,用文法的(3)产生式进行规约。

    直到最后 aABe,用产生式(1)规约出 S 开始符号,接受。

    用表格表示:

    6ca5ebada844e760fdf4dfd65aef7ca4.png

    (图片来自教材:《编译原理》张晶老师版)

    用树型表示:

    每一次规约就相当于构造一颗子树,指导输入串结束时,构造成整个语法树。

    56d940dc55a9ec561ddf1f23a05c1415.png

    (图片来自教材:《编译原理》张晶老师版)

    关于规范规约

    首先,自底向上的分析的移进 - 规约过程是自顶向下最右推导的逆过程。

    怎么理解呢?

    最右推导是每次先推导最右边的非终结符,自顶向下的最右推导就是从开始符号开始,每次执行最右推导,推出输入符号串,最右推导是先推出输入串最右端的终结符,最后推出最左端的终结符。

    那逆过程就是从输入符号串开始,每次先从最左端的终结符推导,最后推出开始符号。也就是自底向上的分析的移进 - 规约过程。

    理解这句话之后,因为最右推导被称为规范推导,那么自左向右的规约则称为规范规约。

    关于句柄

    归约过程中,当句柄出现在栈顶符号串时,则用句柄归约。所以关键是在分析过程中如何确定句柄。

    寻找句柄的方法不同,也就形成了不同的自底向上分析法。我们将介绍两种不同的方法,分别是优先分析法和 LR 分析法。

    句柄就是每个产生式的右部。

    句柄具有 “最左” 特征,这一点对于移进-归约过程很重要。

    因为:句柄的 “最左” 性和符号栈的栈顶是相关的。对于规范句型来说,句柄的后面不会出现非终结符号(即,句柄的后面只能是终结符)。

    基于这一点,我们可以用句柄来刻划 “可归约串”。因此,规范归约的实质是,在移进过程中,当发现栈顶呈现句柄时,就用相应产生式的左部符号进行替换。

    优先分析法

    优先分析法是在文法的一些符号之间建立所谓的优先关系,它又可以分为简单优先分析法 和 算符优先分析法

    LR 分析法

    根据分析过程中迄今已经取得的信息,并向前查看若干个输入符号来确定当前应采取的分析动作,及移进,规约,接受或报错。

    可归约串

    每实现异步规约都是把一串符号的用某个产生式的左部符号来代替,我们可以把栈顶上的这串符号成为 “可规约串”。事实上,存在种种不同的方法刻画 “可规约串”。

    对这个概念的不同定义,也就形成了上述不同的自底向上的分析法。

    优先分析法

    简单优先分析法(句柄)

    算符优先分析法(最左素短语)

    即在 算符优先分析 中,我们用 “最左素短语” 来刻画 “可规约串”

    LR分析法(句柄)

    (二)短语,直接短语,句柄

    还有一个概念需要理解,句型,一起看。

    句型的短语,直接短语定义:

    若 S 是文法 G 的开始符号,αβδ 是该文法的一个 句型(能通过这个文法推导出来),即 S =*> αβδ,其中 α,δ ∈ V*,β ∈ V+。

    如果有 S =*> αβδ 且 A=+>β,其中 A ∈ VN,则称 β 是句型 αβδ 相对于非终结符 A 的 短语。

    另外,如果满足 S=*>αβδ,且 A -> β 是文法 G 的一个产生式,则称 β 是句型 αβδ 相对于非终结符 A 的 直接短语。

    句型的句柄定义:

    在一个句型中可以有多个直接短语,位于句型 最左边的直接短语 就称为 句柄。

    例题:找短语,直接短语,句柄

    题目:

    给定文法:

    (1)T -> T*F

    (2)F -> F↑P|P

    (3)P -> (T)|a

    对于句型 T*P↑(T*F)

    解析:

    (1)根据 T =*> T*P↑(T) 和 T =*> T*F(即产生式1),可知 T*F 是该句型的 相对于 T 的 直接短语。

    (2)根据 T =*> T*P↑P(由产生式1和2推出) 和 P =*> (T*F)(由产生式1和3推出),可知 (T*F) 是该句型的 相对于 F 的短语。

    (3)根据 T =*> T*F↑(T*F) 和 F => P,可知 P 是该句型的 相对于 F 的 直接短语。

    (4)根据 T =*> T*F 和 F =*> P↑(T*F),可知 P↑(T*F) 是该句型的 相对于 F 的短语。

    (5)根据 T =*> T 和 T =*> T*P↑(T*F),可知 T*P↑(T*F) 是该句型的 相对于 T 的 短语。

    综上,T*P↑(T*F) 共有 5 个短语,其中两个是直接短语,由于直接短语 P 是句型的最左直接短语,所以 P 是句型的 句柄。

    通俗的说一下,上面 5 个短语的两个条件能推出该句型,可以看出来。那么条件又是怎么来的呢?怎么知道怎么划分短语呢?这个就是通过句型和文法中个各个产生式来推,但这样很不直观,也容易漏。

    怎么更快的找出所有短语,直接短语和句柄呢?

    找出所有短语,直接短语和句柄,一种方法是根据定义寻找,显然,这种方法不直观,而且很难知道是否已穷尽所有情况;

    另一种方法是利用语法树,首先为给定句型构造一颗语法树然后利用这棵语法树就可以找出该句型全部的短语,直接短语和句柄。

    还对上题分析,使用语法树分析:

    0cc74b9bc668214613ad5829910689f7.png

    (图片来自教材:《编译原理》张晶老师版)

    从底向上看,找子树

    (1)T -> T*F

    (2)P -> (T*F)

    (3)F -> P

    (4)F -> P↑(T*F)

    (5)T -> T*P↑(T*F)

    再根据文法中的产生式判断:

    直接短语(文法中包含产生式),有子树(1),子树(3),就是说他俩为直接短语

    句柄(最左直接短语),比较(1)和(3)谁在左边

    对语法树的剪枝方法

    (1)每个句型都有一个语法树

    (2)每个语法树(整棵树)的端末结点自左向右排列就组成一个 句型

    (3)每棵 子树的端末结点 自左向右排列就组成一个 短语

    (4)每棵 简单子树的端末结点 自左向右排列就组成一个 直接短语

    (5)最左简单子树的端末结点自左向右排列就组成一个 句柄

    (三)简单优先分析法

    优先分析法分为:

    简单优先分析法(句柄)

    算符优先分析法(最左素短语)

    简单优先分析法是一种典型的 自底向上 的分析法,它符号串进行语法分析的过程是一个 规范规约 的过程。

    它首先对文法 按一定规则 求出 所有符号(即终结符和非终结符) 之间的 优先关系,然后在分析过程中根据文法符号之间的 简单优先关系 来寻找符号串中可以进行规约的子串(即句柄)来进行规约。

    简单优先文法

    由于简单优先分析法是按照文法符号之间的 优先关系 来确定句柄的,所以首先要介绍两个文法符号之间存在的优先关系,然后介绍优先关系是 怎样确定的 和 如何构造关系表。

    三种简单优先关系:

    在简答优先文法中,两个文法符号之间可以是下述三种优先关系之一:

    0a51cdc32cc57884518c518223717af3.png

    注意:

    上面所引入的是三种优先关系都是对文法中的符号序偶来定义的,这三种关系和数学中的 =, 不同,它们是有序的,就是不满足交换律,即

    Si

    详细:

    (1)第一种关系 - Si 和 Sj 优先级相同

    (2)第二种关系 - Si 的优先级低于 Sj

    (3)第三种关系 - Si 的优先级高于 Sj

    (4)第四种关系 - 不存在优先关系。这个上面没有体现。

    例题:已知文法,求优先关系

    题目:

    给定文法:

    (1)S -> (R)|A|∧

    (2)R -> T

    (3)T -> S,T|S

    注意:(3)中的逗号是终结符

    求文法符号之间的优先关系:

    解析:

    为了更好理解,直接上截图,注意逗号的理解,并列逗号和终结符中的逗号。

    ffb5e9682344f5f3dbbc6430ee102e1e.png

    简单优先文法定义:

    简单文法是满足以下条件的文法:

    (1)在文法字汇表中,任意两个符号之间至多存在一种简单优先关系

    (2)文法中的任意两个产生式没有相同的右部(唯一性)

    简单优先关系矩阵

    对上面例题,做出简单优先关系矩阵

    a45a8de781bab17ed3fb0fa67f40805e.png

    (图片来自教材:《编译原理》张晶老师版)

    简单优先分析法定义:

    对简单优先文法的分析方法就是简单优先分析法。

    简单优先分析法的局限性:

    简单优先分析法只适应于简单优先文法。实际上,一般的程序设计语言的文法都不是简单优先文法。

    所以,虽然简单优先分析法准确、规范,但分析效率较低,而且实际使用价值不大,更多可以看书,此处不再描述

    (四)算符优先分析法

    算符优先分析法是一种古典又实用的方法。

    算符优先文法(OPG文法)定义

    简单优先分析法 规定了文法符号间 (非终结符 VN 和终结符 VT) 的优先顺序和结合性质,然后借助这种优先关系和结合顺序来寻找可归约串(句柄)进行归约。

    算符优先分析法 规定了算符间 (终结符 VT) 的优先顺序和结合性质,然后借助这种优先关系和结合顺序来寻找可归约串(最左素短语)进行归约。

    通俗的说,算符优先分析法借助于终结符之间的优先关系确定可归约串。由于它不考虑非终结符之间的优先级关系,而且在规约过程中只要找到句柄就规约,并不考虑规约到哪个非终结符,因而算符优先规约并不是规范规约,确切的说,可规约串是最左素短语,而不是句柄。

    特别有利于表达式分析,宜于手工实现。

    但是它能力不强,仅能对算符优先文法进行分析。

    算符优先分析法的分析过程是一种自下而上的归约过程,但这种归约未必是严格的最左归约。即 算符优先分析法不是一种规范归约法。

    使用工具: 优先表、总控程序、栈

    定义算符优先分析法前,先定义算法文法。

    算符文法定义

    若在上下文无关文法 G 中,不含 ε-产生式,且不含形如 U → …AB…的产生式,则称 G 为算符文法,也称 OG 文法 (Operater Grammar)

    算符文法要满足:

    不含ε-产生式;

    产生式右部不包含两个相邻非终结符

    算符优先分析法中,要利用 终结符 之间的 优先关系 来找出句柄,所以要先给出终结符之间存在的三种优先关系。

    180493cba501e047570e8a32cc8f5a91.png

    (图片来自教材:《编译原理》张晶老师版)

    用语法树表示:

    54bc68d5a689ad544ff016f99b28e54b.png

    5e4d09bd674dca6953550af63704da98.png

    a93821fcb63e587beea26f4dabfd7e6a.png

    例题:判断 G 是否是 OPG 文法

    题目:

    对于文法 G(E):

    (1)E -> E+T|T

    (2)T -> T*F|F

    (3)F -> (E)|i

    (1)判断 G 是否是 OG 文法(算符文法);

    (2)再找出 G 中所有终结符对的优先关系;

    (3)最后判断 G 是否是 OPG 文法(算符优先文法)

    解析:

    (1)判断 G 是否是 OG 文法(算符文法),根据算符文法要满足:

    不含ε-产生式;

    产生式右部不包含两个相邻非终结符

    (2)再找出 G 中所有终结符对的优先关系,得出优先关系表

    具体怎么构造关系表,在下面有提

    fd44e1bef91287bf7c1aa911b338e685.png

    (图片来自教材:《编译原理》张晶老师版)

    (3)最后判断 G 是否是 OPG 文法(算符优先文法)

    由于对于 G(E) 的任何终结符对(a,b)至多只有一种优先关系成立,即优先关系表中不存在多重入口,所以,文法 G(E) 是一个算符优先文法

    8e22e3266ca568406f5aa9db5f4920a0.png

    优先关系表的构造

    由定义构造缺乏可操作性。所以选择由算法构造。

    为了找出所有优先关系,使得优先关系表没有疏漏,要对 G 的每个非终结符 T 构造两个集合:FIRSTVT集(最左终结符集),LASTVT集(最右终结符集)

    FIRSTVT 集,LASTVT 集定义:

    1209d78b1116f17f097d301bb7509d4d.png

    FIRSTVT(T) 的构造规则(必背)

    (1)若有 T→a… 或 T→Ra…,则 a∈FIRSTVT(T);

    (2)若 a∈FIRSTVT(R),且有产生式 T→R…,则 a∈FIRSTVT(T)

    LASTVT(T) 的构造规则(必背)

    (1)若有 T→…a 或 T→…aR,则 a∈LASTVT(T);

    (2)若 a∈LASTVT(R),且有产生式 T→…R,则 a∈LASTVT(T)

    例题:求 FIRSTVT,LASTVT 集

    题目:

    对于文法 G(E):

    (1)E -> E+T|T

    (2)T -> T*F|F

    (3)F -> (E)|i

    结果:

    4b58e7210ec4a44125459a389dcb0bc1.png

    具体说一下怎么来的,

    第一个 FIRSTVT(E) 集

    由文法(1)和规则(1)得出 + ∈ FIRSTVT(E)

    由文法(2)和规则(1)得出 * ∈ FIRSTVT(T)

    由文法(1)和规则(2)得出 * ∈ FIRSTVT(E)

    由文法(3)和规则(1)得出 ( ∈ FIRSTVT(F)

    由文法(2)和规则(2)得出 ( ∈ FIRSTVT(T)

    由文法(1)和规则(2)得出 ( ∈ FIRSTVT(E)

    由文法(3)和规则(1)得出 i ∈ FIRSTVT(F)

    由文法(2)和规则(2)得出 i ∈ FIRSTVT(T)

    由文法(1)和规则(2)得出 i ∈ FIRSTVT(E)i

    上面为了容易理解,分开写,但不直观,同理也可以根据 LASTVT 集规则计算出 LASTVT 集。

    素短语

    在这里插入图片描述 素短语是满足下面条件的短语:

    至少包含一个终结符。

    该短语不再包含满足第一个条件的更小的短语。

    最左素短语:

    处于句型最左边的那个素短语

    算符优先分析算法就是根据 最左素短语 的定理构造的

    算符优先分析算法的实现

    工作原理: 对当前句型不断寻找最左素短语进行归约的过程。寻找最左素短语时,首先找到最左素短语的末尾终结符,然后再向前搜索最左素短语的首终结符。

    使用的数据结构: 栈,数组。

    有关约定:#作为语句括号,视为终结符,其优先级最低。

    算符优先分析的局限性

    算符优先分析 比规范归约要快得多,因为它跳过了所有单个非终结符的归约。

    忽略非终结符的归约 在归约过程中存在某种 危险性,可能导致把本来不是文法句子的输入串误认为是文法的句子,即会把错误的句子得到正确的归约。

    总结

    算符优先分析算法与简单优先分析算法的比较

    两个算法类似,所不同的是 算符优先分析算法 每一步归约 不一定是规范归约,而是找出最左素短语进行归约,并且在寻找最左素短语的过程中,只比较终结符之间优先关系,不受非终结符的影响

    比较表格:

    -

    简单优先分析法

    算符优先分析法

    语法分析类别

    自上而下分析

    自下而上分析

    可规约串

    句柄

    最左素短语

    确定可规约串的根据

    任意两文法符号之间的简单优先关系

    任意两终结符之间的算符优先关系

    效率比较

    效率较低

    只考虑终结符,效率较高

    展开全文
  • 解题思路:现学现用。注意事项:见代码第114行。参考代码:#include#include#includetypedefstructHTNode{intweight;//权重intparent;//父结点的下标intlchild,rchild;//左右孩子的下标}HTNode,*HuffTree;...
  • 自底向上分析5.1 移进—规约分析5.2 简单优先分析法5.2.1 基本概念5.2.2 优先关系定义5.2.3 简单优先文法定义5.2.4 简单优先分析法的操作步骤5.2.5 实例5.2.3 缺点5.3 算符优先分析5.4 算符优先分析法的进一步讨论...
  • 编译器之语法分析自底向上基本概念算符优先SLR规范LRLALR 自底向上 基本概念 自底向上形成语法树的过程就是及逆行归约,将一堆单词串放在一起,形成某个产生式的样子,然后规约成某个产生式,所以关键就是什么时候...
  • C++实现自底向上的归并排序算法既然有C++实现顶向下的归并排序算法,当然也有C++实现自底向上的归并排序算法啦。下面小编为大家整理了C++实现自底向上的归并排序算法,希望能帮到大家!一. 算法描述自底向上的归并...
  • 在国内的网站上搜索什么叫“自底向上”编程,给人的感受似乎是同一个问题有两种解决思路,一个是“顶向下”,一个是“自底向上”。但你仔细看那些文章的讲解,其实说的都只是“顶向下”。 为了说清楚“自底向上...
  • 语法分析有两个总的思路,一个是顶向下分析,一个是自底向上分析底向上的分析思路是,对一个句子sss,不断进行归约(“合并”),看能否归约成开始符号SSS的状态。 自底向上分析(LR概述) 自底向上分析通常...
  • 编译原理学习笔记——第六讲 语法分析:自底向上分析1. 自底向上分析1.1 语法分析1.2 移进-归约分析示例2. 短语与直接短语3. 算符优先分析方法 1. 自底向上分析 1.1 语法分析 自底向上分析: 1.从输入串开始,逐步...
  • 编译原理作业之一,作为学习记录,若有错误或者需要改进的地方欢迎底下评论。Mind master原文件 百度网盘提取码:i6cr
  • 自底向上分析之算符优先分析法说明:以老师PPT为标准,借鉴部分教材内容,AlvinZH学习笔记。基本过程1. 一般方法:采用左向右地扫描和分析输入串,从输入符号串开始,通过反复查找当前句型的句柄(最左简单短语),...
  • 题意 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右...解法一:顶向下 这道题希望我们判断一棵树是否是平衡二叉树,即所有节点的左右子树高度差不
  • 图 3: 在CrowdPose数据集上自底向上方法的比较 图 4:在CrowdPose数据集上顶向下和自底向上方法的比较 图 5:SAHR和WAHR的混淆实验 5.2 在 CrowdPose 数据集上的实验结果 如表 9 所示,由于 CrowdPose 数据集中...
  • 现在讲数字化转型,大多是顶向下的视角,但企业光提战略、目标是不够的,必须将任务分配到每个团队,落实到每个人每天的工作上,但这些工作会跟员工以前的工作不太一样,也就意味着团队和员工也需要跟...
  • 同样除了处理器的一些内部的机制,比如禁止某些指令重排,缓存一致性,总线锁,缓存锁定等等,同时还向其上层提供了好的方法,比如说内存屏障,CAS等等,这些方法、机制会让上层(通过合理的方式)更好的来保证程序...
  • 本周话题:顶向下还是自底向上? 我所见过学习方式或者设计方式中,普遍都是采用顶向下的思维。即先知其大意,再分析细节与原理。 例如,学习一个技术框架,通常是先知道其如何使用,再去分析原理和解析源码...
  • 本篇主要程序设计方法学,以体育竞技分析为例,介绍顶向下的设计和自底向上的执行。以第三方库自动安装脚本为例,整体理解代码设计思路和os库的使用。 读完本篇,你将了解: 1.方法论 理解并掌握一批Python程序...
  • 数据仓库的实现方法

    2021-09-05 23:41:21
    从整体的角度来看,数据仓库的实现方法主要有顶向下法、自底向上法和联合方法。 1.顶向下法 在该方法中,首先应找出数据仓库解决方案所要满足的商业需求,把商业需求视为实现数据仓库的首要任务。数据仓库是一...
  • 本文转载微软研究院AI头条。编者按:在拥挤的人群的场景下,由于人群过于密集,重合程度太高,所以每个人的位置难以用人体检测框表示,而传统的一些自下而上的人体姿态估计算法也很难检测到人物的关...
  • b站视频:路飞IT学城 ...文章目录#91 钢条切割问题:自底向上实现#92 钢条切割问题:重构解#93 最长公共子序列#94 最长公共子序列:实现#95 欧几里得算法#96 RSA算法介绍#97 RSA算法测试#98 算法课程总结 个人博客 ...
  • 前言在量化分析工具QTYX上,我们新增了双形态的识别功能,不少星球小伙伴结合这个方式选出了上涨初期的个股,同时根据实战应用中的一些经验反馈给我了不少需求,大家一起来优化这个策略体系,不断...
  • 性能测试分析方法

    2020-12-24 20:18:46
    性能测试是通过自动化的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试。负载测试和压力测试都属于性能测试,两者可以...性能测试分析是一个大课题,不同的架构、不同的应用场景、不同...
  • 本文针对产品装配工艺规划的特点及其目前存在的问题,探讨研究了以装配模型和碰撞检测为基础的装配序列规划方法和装配路径规划方法.装配模型设计信息完整准确的记录与传递是装配序列生成和路径求解的先决条件,分析了...
  • 模拟体育竞技分析

    2021-01-03 14:41:22
    掌握自底向上的执行过程 了解计算机生态和模块编程思想 掌握Python第三方库的安装方法 掌握Python源文件的打包方法 一、体育竞技分析实例: 1.设规则如下: 21分制,三局两胜为佳 每球得分制 每回合中取胜的一方的...
  • 今天来记录一下在Activity中或者在(Dialog or Popupwindow )中点击按钮弹出popupwindow 使用判断是向下弹出还是向上弹出。1、Activity中弹出点击按钮弹出popupwindow1.0:比如:QQ图片20170316110343.png这种是要在...
  • 体育竞技分析(完整代码在最下面)比赛规则:-双人比赛,五局三胜-开始时一方先发球,直至判分,接下来胜者发球-球员只能在发球局得分,若发球局对方胜,自己此时不得分也不掉分。15分胜/局分析:-需求:毫厘是多少?...
  • LR语法分析

    2021-05-22 06:27:01
    1LR语法分析器本节介绍一个有效的自底向上分析技术,可以用于一大类上下文无关文法的语法分析。这种技术叫做LR(k)分析法,其中L表示从左到右扫描输入串,R表示构造一个最右推导的逆过程,k指的是在决定语法分析...
  • 本文是一篇关于功能连接分析方法及其相关注意事项的综述,于2016年发表在Frontiers in Systems Neuroscience。 振荡神经元活动可能为动态网络协调提供一种机制。节律性神经元的交互作用可以使用多种指标进行量化,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,317
精华内容 16,526
关键字:

自底向上的分析方法