精华内容
下载资源
问答
  • 2018-05-18 21:42:51

    语法分析——自下而上分析

    一、规约

            自下而上分析法是一种“移进-归约”法。这种方法的大意是,用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的一个候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

           对于自下而上的分析法,边输入单词符号(移进符号栈),边归约。也就是在从左到右移进输入串的过程中,一旦发现栈顶呈现可归约串就立即进行归约。

    二、规范规约

           在形式语言中,最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。如果文法G是无二义的,那么,规范推导(最右推导)的逆过程必是规范归约(最左归约)。  

    三、符号栈的使用与语法树的表示

           栈是语法分析的一种基本数据结构。在解释“移进-归约”的自下而上分析过程时我们就已经提到了符号栈。一个“移进-归约”分析器使用了这样的一个符号栈和一个输入缓冲区。今后我们将用一个不属于文法符号的特殊符号‘#’作为栈底符,即在分析开始时预先把它推进栈;同时,也用这个符号作为输入串的“结束符”,即无条件地将它置在输入串之后,以示输入串的结束。

            “移进” 指把输入串的一个符号移进栈。

           “归约”指发现栈顶呈可归约串,并用适当的相应符号去替换这个串(这两个问题都还没有解决)。

           “接受”指宣布最终分析成功,这个操作可看作是“归约”的一种特殊形式。

           “出错处理”指发现栈顶的内容与输入串相悖,分析工作无法正常进行,此时需调用出错处理程序进行诊察和校正,并对栈顶的内容和输入符号进行调整。

    四、LR分析法

            规范归约(最左归约—最右推导的逆过程)的关键问题是寻找句柄。在一般的“移进-归约”过程中,当一串貌似句柄的符号串呈现于栈顶时,我们有什么方法可以确定它是否为相对于某一产生式的句柄呢?LR方法的基本思想是,在规范归约过程中,一方面记住已移进和归约出的整个符号串,即记住“历史”,另一方面根据所用的产生式推测未来可能碰到的输入符号,即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时,我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料,来确定栈顶的符号串是否构成相对某一产生式的句柄。

            LR分析法的这种基本思想是很符合哲理的。因而可以想象,这种分析法也必定是非常通用的。正因如此,实现起来也就非常困难。作为归约过程的“历史”材料的积累虽不困难(实际上,这些材料都保存在分析栈中),但是,“展望”材料的汇集却是一件很不容易的事情。这种困难不是理论上的,而是实际实现上的。因为,根据历史推测未来,即使是推测未来的一个符号,也常常存在着非常多的不同可能性。因此,当把“历史”和“展望”材料综合在一起时,复杂性就大大增加。如果简化对“展望”资料的要求,我们就可能获得实际可行的分析算法。

            后面所讨论的LR方法都是带有一定限制的。

           一个LR分析器实质上是一个带先进后出存储器(栈)的确定有限状态自动机。我们将把“历史”和“展望”材料综合地抽象成某些“状态”。分析栈(先进后出存储器)用来存放状态。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候,栈顶的状态都代表了整个的历史和已推测出的展望。因此,在任何时候都可从栈顶状态得知你所想了解的一切,而绝对没有必要从底而上翻阅整个栈。LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。为了有助于明确归约手续,我们把已归约出的文法符号串也同时放在栈里(显然它们是多余的,因为它们已被概括在“状态”里了)。于是,我们可以把栈的结构看成是:

            栈的每一项内容包括状态s和文法符号X两部分。(s0,#)为分析开始前预先放到栈里的初始状态和句子括号。栈顶状态为sm,符号串X1X2…Xm是至今已移进归约出的部分。

    五、LR分析中的出错处理

    在LR分析过程中,当我们处在这样一种状态下,即输入符号既不能移入栈顶,栈内元素又不能归约时,就意味着发现语法错误。发现错误后,便进入相应的出错处理子程序。处理的方法分为两类:第一类多半使用插入、删除或修改的办法。如在语句a[1,2:=3.14;中插入一个]。如果不可能使用这种办法,则采用第二类办法。第二类处理办法包括在检查到某一不合适的短语时,它不能与任一非终结符可能推导出的符号串相匹配。




    更多相关内容
  • 编译原理 - 语法分析(自下而上分析)

    千次阅读 2020-06-15 17:01:14
    预测分析递归的预测分析法非递归的预测分析法 递归的预测分析法 TYPE : 类型 STLIST :语句序列 DECLIST:标志服序列 PROGRAM:程序 非递归的预测分析法

    两种语法分析对比

    在这里插入图片描述

    自下而上语法分析(Bottom-up)

    核心思想 - (移进-规约)

    移进 : 移进到栈里,当形成产生式时就弹出(规约)

    在这里插入图片描述

    规约 : 右部符号替换为左部符

    规约:右部符号替换为左部符号
    原式:i*i+i 规约后 : E
    从下往上合并的过程
    右部符号i 替换为 左部符号E
    在这里插入图片描述

    移进-规约 例题

    在这里插入图片描述当规约过程中,有多重选项,这个时候我到底哪个规约哪个不规约 - 核心问题 :识别可规约串

    核心问题 - 识别可规约串 (短语)

    β可以由非终结符A多步推出
    αβ△是一个句型,当β由A替换后,αA△仍然是一个句型 
     此时称呼β是αβ△相对于A的短语
    

    子串能够向上规约成一个非终结符号A
    这个非终结符A 和上下文一起 仍然是一个句型
    在这里插入图片描述

    直接短语

    β由A一步推出,那么β是αβ△的直接短语
    在这里插入图片描述

    句柄 : 一个句型的最左直接短语

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

    短语和直接短语的例题

    已知文法和句型,写出对应的短语和直接短语

    先按照句型格式展开对应文法 ,套定义进行判断

    在这里插入图片描述以某结点为根的树,末端从左往右 就是短语
    子树只有两代,该短语就是直接短语
    在这里插入图片描述

    分析过程描述

    在这里插入图片描述

    分析方法

    算符优先分析法

    算符优先分析法 - 表达式分析

    算符优先分析法: 按照 算符的优先关系 和结合性质进行语法分析

    存在问题 : 归约顺序不同,构造出的语法树不同,计算顺序不同,结果不一样

    解决: 设定算符的优先顺序,使得归约过程唯一

    在这里插入图片描述左侧的文法 : 需要时刻记住先乘除后加减的优先级
    右侧的文法: 蕴含了算符的优先级,直接无脑展开即可
    自下而上 : 右边的 凑对后 = 文法左边的式子
    在这里插入图片描述

    优先关系

    +<·+ 左边加号的优先级比右边加号的优先级要低
    在这里插入图片描述

    算符文法 - 不会出现连续的非终结符的文法

    算符文法 : E+
    不是算符文法:EF
    在这里插入图片描述

    算符优先文法

    a优先级与b相同: ab,或者aQb是一起归约到P上去

    • P-> …ab…
    • P-> …aQb…
      eg : (E) 推导出 左括号和右括号的优先级相等,符合 aQb型
      在这里插入图片描述
      a的优先级低于b :
    • P-> …aR… R=>b…
    • P-> …aR… R=>Qb…
      eg: E->E+E E=>E*E ∴ + <· * 加号优先级低于乘号优先级
      先归约a后面的 ,然后再用这个整体来和a归约在这里插入图片描述

    a的优先级高于b:

    • P->…Rb… R=>…a
    • P->…Rb… R=>…aQ
      优先级高的先归约
      eg: E->E × E E=>E+E ∴ + ·> × 推理出加号的优先级高,这与第二个例子推出的相矛盾
      在这里插入图片描述
      算符优先文法 : 推理的关系不存在矛盾的情况
      文法G中任何终结符对(a,b) 只满足优先级相等, a优先级高,a优先级低着三个关系之一 - 称G位算符优先文法

    在这里插入图片描述…ab… 相等关系
    …aR… + R->b… =>…ab…或者aQb… a<·R(b)
    …Rb… + R->…a => …ab… 或者…aQb… R(a)·>b

    算符优先文法例题

    在这里插入图片描述

    构造优先关系表

    优先级相等

    检查 优先级相等 无需检查推导式,只需检查所有候选式是否满足ab 或者aQb
    在这里插入图片描述

    优先级低和优先级高 - FIRSTVT集合和LASVT集合

    VT :非终结符
    P能推理出a…或者Qa… 那么a可以进入这个FIRSTVT§ : a在首位12位置
    P能推理出…a或者…aQ,那么a可以进入这个LASVT§ : a在末尾12位置
    在这里插入图片描述在这里插入图片描述

    构造FIRSTVT§的算法

    具体实现 : 栈 + 数组
    在这里插入图片描述

    构造LASTVT§的算法

    在这里插入图片描述

    FIRSTVT的计算

    划首位两个元素
    在这里插入图片描述

    LASTVT的计算

    划末尾两个元素 不断循环 直到没有新的元素进入集合
    在这里插入图片描述

    构造优先关系表

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

    算符优先分析算法

    自下而上的核心 : 识别可归约串 - 素短语

    最左素短语

    在这里插入图片描述短语 : 任何子树两层或两层以上的末端 连接起来
    直接短语 : 两层子树末端
    素短语: 包含终结符的短语 , 且 内部没有比他更小的素短语
    最左素短语 : 最左边的素短语
    在这里插入图片描述可以通过语法树知道最左素短语,但是语法树也是需要推导的最终结果,所以不能依赖语法树

    最左素短语定理

    最左子串 : 最左的终结符 优先级 比 外面的aj-1要高, 内部的终结符优先级都相等, 最右的终结符 优先级 比 ai+1 要高
    这个红色的子串 就是 最左素短语
    Njaj…NiaiNi+1 这一串 就是 最左素短语
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    算符优先分析结果 != 语法树

    在这里插入图片描述

    LR分析法 - 规范归约的过程

    规范归约:句柄作为可归约串
    L : 从左到右扫描输入串
    R : 自下而上进行归约
    在这里插入图片描述

    句柄和规范归约

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

    用句柄归约

    在这里插入图片描述

    规范归约 - 结果是语法树

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

    规范句型

    在这里插入图片描述

    展开全文
  • 自上而下分析法 自上而下分析是一种移进-规约的分析法,其基本思想是:用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式...

    一、自上而下分析法
          1. 自上而下分析是一种移进-规约的分析法,其基本思想是:用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。简单来说就是当把输入符号一个个放进去的过程中,观察栈顶元素与它下边任何i个元素能否规约成某个产生式的左部非终结符,若能,则将这i+1个字符出栈,并用该非终结符来替换这i+1个符号然后入栈,一直进行该过程,直至无法规约成非终结符的形式,规约失败,若规约出最左端的非终结符,便规约成功。
          例如将文法G:S--> aAcBe ; A-->b ; A-->Ab; B-->d; 将abbcde规约到S过程为:
      1)将a 放入栈中,无法规约,然后b进栈
      2)由文法可知b可以规约成A,于是将b出栈,将A压栈,此时栈中剩余为aA,无法规约,将b入栈;
      3)由A-->Ab,可将Ab出栈,规约成A,此时栈中剩余为aA,无法规约,将c入栈;此时栈中剩余为aAc,无
    法规约,将d入栈;
      4)由B-->d,将d出栈,规约成B,此时栈中剩余为aAcB,无法规约,将e入栈;
      5)由S--> aAcBe,将aAcBe出栈,规约成S。规约成功。
    可以看到 自下而上分析的关键是:识别可规约串。那么问题来了,怎么判断栈顶的符号串的可规约性,以及如何规约。
    2.规范规约 
      1) 短语:
        令G是一个文法,S是文法的开始符号,假定αβδ 是文法G的一个句型, 其中α,β,∈(VN∪VT)*,A∈VN ,如果有

     则β称是句型  αβε相对于非终结符A的短语。
      2)直接短语
     特别是,如果有A==》β,则称β是句型  αβε相对于规则A-》β的直接短语。
      3)句柄一个句型的最左直接短语称为该句型的句柄。
      4)规范规约
      假定α是文法G的一个句子,我们称序列
           αn, αn-1,.... ,α0
       是α的一个规范归约,如果此序列满足:
      (1)  αn= α
      (2)  α0为文法的开始符号,即α0=S
      (3)  对任何i,0 < i <=n, αi-1是从αi经把句柄替换成为相应产生式左部符号而得到的。
    规范归约是关于是一个最右推导的逆过程
    3、用符号栈进行语法分析
    分析过程
     自左向右对输入串ω不断向栈中进行移进——归约,直到形成如下格局

     表示分析成功,否则意味着输入串ω有错
     注意:在分析开始时,将’#’预先进栈,作为栈底符号,结束输入时,将’#’作为输入串的结束符
    4、算符优先法
    ·1.意义:定义算符之间优先关系,借助这种关系来寻找“可归约串”和进行归约
    2.定义两个终结符‘a’与‘b’的优先关系
     a =.b   表示a的优先性等于b
     a >.b   表示a的优先性大于b
     a <.b   表示a的优先性小于b
    5.算符文法
     一个文法,如果它的任一产生式的右部都不含两个相继(并列)的非终结符,.

    6.构造算符优先关系表
    (1)通过检查产生式的每一个候选式可以找出满足a=.b
      (即P→…ab…或P→…aQb…的产生式)
    (2)为了满足<.和>.,需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):

    7.构造集合FIRSTVT(P)的算法
     按其定义,可用下面两条规则来构造集合FIRSTVT(P):
     ① 若有产生式P→a…或P→Qa…,
      则aFIRSTVT(P);
     ② 若aFIRSTVT(Q),且有产生式P→Q…,
      则aFIRSTVT(P)。
    8.构造构造集合LASTVT(P)的算法
     按其定义,可用下面两条规则来构造集合LASTVT(P):
     ① 若有产生式P→… a或P→… aQ ,
      则a 属于 LASTVT(P);
     ② 若a属于  LASTVT(Q),且有产生式P→… Q ,
      则a属于  LASTVT(P)。
    9、算符优先分析算法的设计
    1.素短语
     指一个句型的短语,它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语
    2.最左素短语
     处在句型最左端那个素短语成为最左素短语
    10、LR分析法

    LR分析方法是一种自下而上的分析方法,LR分析法的归约过程是规范推导的逆过程,所以LR分析过程是一种规范归约过程。
    LR分析方法是一种适用于一大类上下文无关文法的分析方法,比较复杂,不适于用手工实现,可借助于YACC/bison实现

    LR分析法的构造结构包括Action(移进、规约结合艘、接收、出错)和goto函数(状态转换函数):

                                                                                                   

    动作表:
      ACTION[s,a]:
      当状态s面临输入符号a时,应采取什么动作(<1>. 移进<2>. 归约<3>. 接受<4>. 报错)
     状态转换表:
      GOTO[s,X]:
      状态s面对文法符号X时,下一状态是什么
    11、 LR(0)项目集族和分析表的构造:
    1)活前缀:文法G的活前缀是他的规范句型的前缀,该前缀不超过句柄的右端。
    2)LR(0)项目
    3)项目集规范族
    4)项目集的闭包
    5)LR(0)分析表的构造
    12、构造识别活前缀的NFA步骤:
    1)构造文法的所有产生式的项目,每个项目都为NFA的一个状态。
    2)确定初态、句柄识别态、句子识别态。
     由于S′(起始符)仅在第一产生式的左部出现 ,因此规定起始符相关的项目1为初态
     其余每个状态都为活前缀的识别态(终态)
     圆点在最后的项目为句柄识别态
     第一个产生式的句柄识别态为句子识别态
    3)状态之间的转换关系确定方法如下:
    若项目i为X→X1X2...Xi-1 • Xi…Xn。
      项目j为X→X1X2...Xi-1Xi • Xi+1…Xn。
     则从状态i到状态j连一条标记为Xi的箭弧。

    若i为X→•A,k为A→•,
    则从状态i画标记为的箭弧到状态k。


    13.LR(0)项目集规范族不存在移进-归约,或归约-归约冲突,称为LR(0)文法。

    总结:其实这一章的内容还挺好理解的,但是LR文法这一节就不太明白了,还有分析表的构造,有点懵,不知道如何去构造,看来以后还是要专心听课的,不能跑神。
    展开全文
  • LR分析法及分析程序自动构造 概述 上下文无关文法的LR分析法 LR:自左至右扫描,最右推导的逆过程(也就是最左归约) LR方法: 在归约的过程中,一方面记住移入和归约的整个符号串,另一方面通过产生式推测未来...

    自下而上的语法分析(LR分析法)

    概述

    • 上下文无关文法的LR分析法
    • LR:自左至右扫描,最右推导的逆过程(也就是最左归约)
    LR方法:
    • 在归约的过程中,一方面记住移入和归约的整个符号串,另一方面通过产生式推测未来可能碰到的输入符号

    • 优缺点:

      • 优点:文法范围广,识别能力强,可以识别出错位置
      • 缺点:工作量大,需要构造这种分析程序的产生器
    • 产生器作用:

      • 应用产生器产生一大类上下文无关文法的LR分析程序
      • 对二义性文法或难分析的特殊方法,施加一些限制使之能用LR分析法
    • LR分析器:
      在这里插入图片描述
      包括两部分:总控程序,分析表
      总控程序:控制程序的运行,查分析表的内存做简单动作
      产生器的任务就是产生分析表

    • 分析表:

      • 一个文法的LR分析器对应四种不同分析表,所以分析表都恰好识别产生的所有语句
      • LR(0),SLR,LR(1),LALR四种分析表

    LR分析法

    • LR分析法的基本思想
      • 规范归约时,当一串貌似句柄的符号串呈现于栈顶,LR分析法根据三方面来寻找句柄:历史,展望,现实
    • 下推栈:
      在这里插入图片描述
    • 分析表:
      在这里插入图片描述在这里插入图片描述
    • 总控程序的动作:
      在这里插入图片描述
      解释:移进动作就是将在两个栈的栈顶(si,a)si表示状态,a表示栈顶的字符,因为a是终结符,所以去该状态列对应的终结符行,相交成的动作,需要先将下一个字符移入,然后将某一个状态加入状态栈中栈顶变为(sj,b)

    LR分析器

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

    分析过程:

    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    0状态遇到i,跳到5状态
    在这里插入图片描述5状态遇到*,按照6产生式归约
    在这里插入图片描述F入栈,0状态遇到F非终结符,入栈状态3

    在这里插入图片描述

    LR文法:

    • 定义:如果可以根据某一文法可以构造一张分析表,使得该表中每一个元素至多只有一种明确的动作,这个文法就是LR文法

    LR(0)项目集族和LR(0)分析表的构造:

    • 基本思想:

      • 只根据历史来识别呈现于栈顶的句柄
    • LR(0)是其他分析法的基础

    • 构造表的策略:

      • 构造文法G的优先自动机,他能识别文法中的所有活前缀
    • 活前缀:

      • 字的前缀是指字的任意首部
        • 例如:字ABC的前缀有空,A,AB,ABC
      • 活前缀概念:
        • 指规范句型的前缀,这种前缀不含句柄之后的任何符号
        • 规范句型:通过规范推导和归约得到的句型
      • 例子:
        在这里插入图片描述在这里插入图片描述例如:ab[2]b[3]cd[4]e[1]
        先去识别ab得到[2],通过2号产生式得到对b归约,aAb[3]cd[4]e[1],通过[3],aAcd[4]e[1],通过[4],aAcBe[1],通过[1],的得到S
    • 活前缀的两种类型:

      • 归态活前缀:活前缀的尾部正好为句柄尾部,可以进行归约 前文中的ab[2]就是
      • 非归态活前缀:句柄未形成,需要继续移进若干符号之后才能形成句柄
    • 构造自动机识别活前缀:

      • 对于一个文法,我们可以构造一个自动机来识别它的所有活前缀
      • 由于产生式的右部符号串就是句柄,若这些符号串以进栈,则表示它已处于归态活前缀,若只有部分进栈则属于非归态活前缀。要想要知道活前缀有没有大部分入栈,可以为每一个产生式构造一个自动机,由它的状态来记住当前情况,这个状态称为项目,这些自动机的全体是能识别所有活前缀的优先自动机
    • 项目:
      在这里插入图片描述在这里插入图片描述

    • 由项目构造NFA的方法:
      在这里插入图片描述文法拓展的必要性:通过对文法的扩展,不会出现单单只识别了一个开始符号就确定是这个句子的情况。例如S->bS’A | asd,这时候,当我们,读入了b,进入bS‘A状态,然后需要读入S’,这时我们返回去,通过读入asd进入了终态,这时候,我们结束,但是也可以继续,这时候机器就不知道怎么选择了

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

    • 例子:
      在这里插入图片描述列出所有项目
      在这里插入图片描述
      对于识别空串就是,小圆点到达了一个非终结符前面,可以通过读入这个非终结符的首符集来进入这个非终结符。

      在这里插入图片描述

    • LR(0)项目集族的机器构造法:
      在这里插入图片描述
      在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
      在这里插入图片描述

    • 例子:
      在这里插入图片描述
      在这里插入图片描述
      解释:(这里使用了*表示点)
      首先找到开始符号S‘的e闭包状态集S’->E,E->*aA,E->bB,为状态集0
      找状态集族里的状态集0,发现可以通过E到达状态S‘->E ,可以通过a到达状态E->aA,可以通过b到达状态E->b
      B,
      对三个终态集求闭包
      以此类推

    • 构造LR(0)分析表:
      在这里插入图片描述解释:
      这里的go函数表示的就是当栈顶符号为Ik,读头下符号为a,那么就将a入栈,并入栈一个识别了a的状态
      当小点出现在一个产生式的最后位置,那就表示对于读头下任何符号,都可以使用归约,将符号栈中已有的部分符号按照某个产生式进行归约,
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    SLR语法分析方法:

    • 当使用LR(0)分析法,出现归约和归约之间的冲突,移进和归约之间的冲突,可以尝试使用SLR分析法,可以解决LR(0)分析法的部分问题。

    • 例如在一个项目中A->a* ;B->b*;这时候,到这个状态按照LR(0)有两种归约方法,因此发生了冲突。

    • 在归约时除了考虑历史情况之外,还考虑一些现实

    • 消除冲突
      在这里插入图片描述
      在这里插入图片描述

    • 构造SLR分析表:构造LR(0)项目集族,使用SLR分析法填表。
      在这里插入图片描述
      2):对于读头下面是follow集中的字符,才使用归约操作

      在这里插入图片描述
      为什么不能解决移进-归约:信息不足,因为当follow(A)存在a字符,可以对A进行归约也可以对X进行移进操作。

    • 例子:
      在这里插入图片描述
      在这里插入图片描述在这里插入图片描述在这里插入图片描述上图为产生移进-归约冲突,提示:为什么LR(0)不能避免归约-移进操作,LR(0)分析法,对于可以进行归约操作的字符串,将所有字符都作为归约操作,这样对于可以移进操作的字符,就会出现重定义。为什么不能避免归约-归约冲突:因为如果一个字符串有两个选择进行归约,同样因为将所有的读入字符都可以进行归约,这样会导致可以对所有的字符都可以进行两个选择进行归约。
      为什么SLR文法可能不会产生移进-归约冲突:因为当归约项的follow集中不包含移进项的字符,就可以明确下一个动作就是归约
      例如I1状态,其中按照SLR分析法,有归约动作我们需要求FOLLOW(S’)={#}可以归约操作,对于+可以进行移进操作,当时这时候+不属于FOLLOW(S’)所以没有发生冲突。
      在这里插入图片描述可以看到这张表中,有些带有归约动作的行,不是如LR(0)文法,一行都是归约动作,可以看3状态T->F*;按照SLR规则我们需要找到T的follow()集合{*,+,),#},当读头下出现这四个符号时,表示可以对T->F归约。

    • 一个非SLR的例子:
      在这里插入图片描述
      在这里插入图片描述对于状态2:follow®中存在=,这就造成了移进和归约的冲突
      在这里插入图片描述为什么会出现这种情况:当follow集中有某个字符,当读头下是这个符号时;但是不能将栈中符号串进行归约,也就是上图中的项目2,R的follow集中有{=}但是,不能将L归约成R,原因是,follow集中的符号是忽略了前提的,它只是告诉我们后面可能会出现的符号,但是当某些前提达不到时,其实后面跟随的符号是永远不会出现的;就像题中的R的follow集,存在"=“但是只有S‘->S;S->L=R;L->*R时,R后面才可能出现”=",所以当R前面是" * “时,后面读入的符号才可能是”=";否则,如果将这题中的L归约成R,就可能造成,两条路,向一条走的可以走通,但是我们走向了另外一条,导致了错误,程序认为该句子不能识别。

    在这里插入图片描述
    如上图对于一个字符串i=进行归约,按照上图步骤推出错误,所以当我们推导i=R(这里的R只是一个R只是代指一个R可以推出的字符串)也是会推出错误,但是这样的字符串可以通过S->L=R归约得到,就是因为将i归约成了L又错误的归约成了R,导致了错误。

    在这里插入图片描述

    规范LR分析表构造:

    SLR的缺陷:

    在这里插入图片描述
    在这里插入图片描述
    对于项目集2,产生了移进归约冲突,因为当读头下为=,可以进行移进,当时follow®中也存在=,这是为什么,因为follow()集指的是,这个符号后面可能出现的符号,这时忽略了前提条件的。例如对于这个文法,在2项目的情况下,读头下是=,但是如果我们将L归约成了R,那也就是说我们认为R后面可以跟着=,但是我们根据文法推导得到,要出现R=的情况,只有在R前面是*的时候才成立,也就是R‘->R->L=R->*R=R,但是我们显然知道项目2是通过S‘->S->R->L得到的,也就是栈中没有 * ,所以在项目2中没有L归约成R的可能性。我们应该关系的是这样的规范推导后面跟着的符号是什么,在S‘->S->R->L也就是first(#),因为S‘后面跟着的就是#好,也就是说,当读头后面跟着的是#的时候,才可以将L归约成R,这样一路归约下去,到R’。

    规范LR:

    在这里插入图片描述
    这个也就是表示栈里面放的是α,读头下面是β,预计当我们读入β后,
    在这里插入图片描述
    这个也就是表示栈里面
    在这里插入图片描述在这里插入图片描述

    在这里插入图片描述
    在这种情况下,我们在x项目下,我们可以知道的是我们栈中有ae,遇到了c可以进行移进操作也就是S->aec,也可以使用归约操作A->e,因为A的follow集中有=,产生冲突了,那就是因为,follow集只考虑了会出现了,但是没有考虑在规范推导中会出现的,我们进行规范推导,发现当ae在栈中,只有读头下面是first(d)时,才可以通过将e归约成A,然后读入d,将栈归约成S,再归约成S‘,而此时的读头下面是c,所以当我们将e归约成了A,栈中变成了aA,读头下面是c,则出现了错误,因为当栈中是aA时,之后读头下面是d,才能读入。

    follow(A)={c,d},当A后面出现c,那正确的条件是栈中有a;当A后面跟d,那正确的条件是栈中有b,这两种中,只有aAd是规范推导在这里插入图片描述

    规范LR项目集族的构造过程:

    在这里插入图片描述
    (表示点号)对于{(A->α * Bβ,a)}项目集,(A->α * Bβ,a)表示栈中有了α,我们需要读入B,再读入β,这时候进行归约,只有当读入下面是a的时候才能归约;我们先使用LR(0),将空串产生式加入项目集{(A->α * Bβ,a),(B-> γ,first(βa))},这里的first(βa)是因为,我们需要找到规范推导后,可以进行γ归约成B的条件,也就是读头下面是first(βa)。

    在这里插入图片描述
    在这里插入图片描述因为还是针对同一个需要被归约的式子,搜索符只是作为一个归约是读头的判断条件而已。在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述解释:从(S’-> * S,#)产生(S-> * L=R,#),当读头下面是#对L=R进行归约,再产生(L-> (点) *R,first(=R#))……
    此处的图在《编译原理及编译程序构造第三版》的p121页

    LR(1)分析表:

    在这里插入图片描述只有对后文中的first()才进行归约。
    1),对于一个项目k,如果k读入一个终结符到j项目,将action[k,a]置为读入并转到状态j
    2),对于一个归约状态k,只有读头下是a的时候,才会归约,也就是将action[k,a]置为归约产生式的编号
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    LALR分析法:

    基本思想:

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

    合并同心:

    在这里插入图片描述假设有同心项目m和n,则,m和n通过识别X到达了m’和n’状态,我们就可以将两个项目合并,假设去除n项目那一栏,然后将原来指向n项目的指向m项目,原来指向n’项目的指向m’项目
    在这里插入图片描述
    !移进和移进合并,因为当前项目是同心的,所以当这个项目读一个非终结符之后,得到的项目也是同心的,则我们去掉一个项目,让其他本来指向去除项目的关系,指向对应的同心项目

    归约和出错合并,因为规定做归约的原因,所以放松了报错条件,因为可能遇到了报错的那种情况,但是我们去做了归约处理,但是报错能力没有减弱,时间推后了
    在这里插入图片描述在这里插入图片描述在这种情况下,第一个项目,当读头下是d归约为A,是e归约成B,当两个项目合并后,因为两个搜索符都一样,当出现这种情况,就不知道怎么进行归约了,出现了归约归约冲突。所以LALR文法是LR(1)的子集

    构造算法:

    在这里插入图片描述比LR(1)多个一个合并同心的操作,action表的构造一致
    在这里插入图片描述构造goto表,需要将删去的那些项目,读入一个X填写的值,置为还存在的那个项目集读入一个X填写的值一致

    在这里插入图片描述

    定义

    在这里插入图片描述

    展开全文
  • 第五章 语法分析——自下而上分析

    千次阅读 2018-06-17 10:48:53
     自下而上分析法是一种“移进-规约”法,这种方法的基本思想是,用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部...
  • 编译中存在着多种自下而上分析法,但不管哪种自下而上分析法都是按照“移进 - 归约”法的原理建立起来的一种语法分析方法。这种分析法的基本思想是用一个寄存文法符号的先进后出栈,将输入符号一个一个地按从左到...
  • 自下而上语法分析1.基本概念 1.基本概念 1)从分析树的底部(叶节点)向顶部(根节点)方向构造分析树 2)可以看成是将输入串w归约为文法开始符号S的过程 3)自上而下的语法分析采用最左推导方式,自底向上的语法...
  • 根据对自下而上语法分析的理论知识的学习,可以知道自下而上语法分析的两种实现方法:算符优先分析法和LR分析法,本实验采用后者LR分析法 本实验对PL0文法的表达式文法进行设计自下而上语法分析,表达式巴斯克范式...
  • 语法分析:自下而上分析

    万次阅读 2016-11-30 18:35:29
    自下而上分析法就是从输入串开始,逐步进行“归约”,直至归约到文法的开始符号;或者说,从语法树的末端开始,步步向上“归约”,直到根结。
  • 知识总结自下而上分析移进-归约法:句柄为可归纳串算符优先分析法:最左素短语为可归纳串从输入串开始,逐步进行“归约”,直至归约到文法的开始符号。从语法树末端开始,步步向上“归约”,直至根结。基本思想:用...
  • 一、知识总结 自下而上分析是从输入串开始,逐步进行规约,直至规约到文法的开始符号,就是一种“移进-规约”。自上而下分析的中心问题是怎样判断栈订单符号串的可归约性以及如何规约。解决方案是规范规约。所谓...
  • 文章目录1 实验目的和内容1.1 实验目的1.2 实验内容1.3 实验要求2 设计思想2.1 根据BNF描述该文法2.2 根据文法写出LR(0)项目集规范族2.3 根据项目集规范族画出识别活前缀的DFA2.4 判断该文法是否是LR(0)文法2.5 ...
  • 自下而上语法分析

    千次阅读 2018-05-20 20:38:51
    本章学习自下而上的语法分析,其分析过程为边输入单词符号,边归约,直至归约到文法的开始符号。(归约是指根据文法的产生式规则,把产生式的右部替换成左部符号)自下而上分析方法的关键就是找到可归约串。 对于...
  • 自下而上分析自下而上分析基本问题归约规范归约算符优先分析LR分析法出错判断:基本思想LR文法构造LR分析表LR(0)分析表的构造思想:前缀:活前缀:LR(0)项目构造NFA的方法(识别活前缀)LR(0)项目集规范族和LR(0)...
  • 语法分析:自上而下分析 目录语法分析:自上而下分析知识背景计算海明校验码步骤一:计算校验码位数步骤二:确定校验组步骤三:计算校验码的值得出海明校验码利用海明校验码校验数据其他总结 知识背景 百度百科: ...
  • 之前学过的自上而下的分析是递归,这周学习的是自下而上分析是一种归约的算法,感觉比上一章的难度有所加大,理解起来也比较的困难,在学习的过程中我也遇到过一些困难,在老师和同学的帮助下得到了解决,下面,我...
  • 本章主要学习以自下而上的方法进行语法分析,自下而上的分析是一种归约的算法,感觉比上一章的难度有所加大,理解起来也比较的困难。...自下而上分析过程:边输入单词符号,边归约。其核心问题是识别可归约串。...
  • 自下而上的文法分析,基本要满足这么几个需求,每个阶段的下一步操作是唯一的(编译原理中文法分析核心需求)、过程规范高效(很多属于都是基于这个需求的,比如句柄,活前缀,素短语等) 自下而上文法的核心工作...
  • 编译原理实验三 自下而上语法分析

    千次阅读 2021-06-13 18:35:13
    (3)选择最有代表性的语法分析方法,算符优先分析法、LR分析法;或者调研语法分析器的自动生成工具YACC的功能与工作原理,使用YACC生成一个自底向上的语法分析器。 二、实验内容 (1)已给 PL/0 语言文法,构造...
  • 第五章:语法分析---自下而上分析

    千次阅读 2018-05-16 21:51:36
    自下而上语法分析基本问题1.移进归约1.1基本思想 用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。1.2归约 是...
  • 三、自下而上分析的PDA 自左至右把输入串的符号一个一个移进栈,在移 进过程中不断查看栈顶符号串,一旦形成某个句型的 句柄时,就将此句柄用相应的产生式左部替换(归 约),若再形成句柄,就继续替换,直到栈顶...
  • (3) 选择最有代表性的语法分析方法,如算符优先分析法、LR 分析法; 或者调研语法分析器的自动生成工具 YACC 的功能与工作原理,使用 YACC 生成一个自底向上的语法分析器。 2. 实验准备 微机安装好 C 语言,或 C++,...
  • 一:知识点总结自下而上分析法是从输入串开始,逐步进行”规约“,直至规约到文法的开始符号;或者说,从语法树的末端开始,步步向上”规约“,直至根结。Ⅰ、归约1、短语:令G是一个文法,S是文法的开始符号,假定...
  • LR分析法是一种相当有效的自下而上分析技术,它可以用于很大一类上下文无关文法的语法分析。L表示从左向右扫描输入串;R表示构造一个规范推导(最右推导)的逆过程,也就是规范归约(最左规约)。LR分析法比我们前面介绍...
  • 一、 实验目的通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练学生掌握开发应用程序的基本方法。有利于提高...
  • 编译课程设计报告通过编程实现语法分析(自上而下,自下而上)的可视化过程,加深对两法分析原理思想的理解。
  • 基本思想用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。2.规约是指根据文法的产生式规则,把产生式的右部...
  • 方式:自上而下的语法分析(推导)和自下而上的语法分析(规约) 下推自动机: 下推自动机模型: pda和fa的模型相比,多了一个下推栈 决定pda的动作因素:当前状态,读头指向的符号,下推栈栈顶符号 当输入串读...
  • PL/0语言 自下而上语法分析 SLR分析

    千次阅读 2020-04-23 23:38:40
    一、简介 PL0 语言功能简单、结构清晰、可读性强,而又...分析对象〈算术表达式〉的 BNF 定义如下: <表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,133
精华内容 1,253
关键字:

自下而上分析法的思想

友情链接: ACMProblemAnswer.pdf.rar