lr分析法 - CSDN
精华内容
参与话题
  • 第五章 LR分析法

    万次阅读 多人点赞 2017-12-03 22:22:23
    LR分析法也是一种“移进—归约”的自底向上语法分析方法,其本质是规范归约,具有以下特点: (1)应用面广:能够用LR分析程序识别绝大多数的程序设计语言的语法结构; (2)实现效率高:虽构造方法复杂,但是实现...

           LR分析法也是一种“移进归约”的自底向上语法分析方法,其本质是规范归约,具有以下特点:

    (1)应用面广:能够用LR分析程序识别绝大多数的程序设计语言的语法结构;

    (2)实现效率高:虽构造方法复杂,但是实现(执行)效率高。

    (3)查错准确:LR分析器能够及时发现语法错误并准确指出错误位置。

    LR(k)分析方法中L是指自左(Left)向右扫描输入单词串,R指分析过程是最右(Right)推导的逆过程(规范归约)k是指在决定当前分析动作时需向前察看的输入符号个数

    LR(0):   构造简单,适用文法少。是SLR(1)LR(K)

                   的基础。

    SLR(1): 是针对LR(0)的一些问题进行改进,简单的

                    LR(1)方法。

    LR(K): 分析能力强,构造复杂。

    一、LR分析器的逻辑结构:

    1.整体结构:



    (1)总控程序的控制下,从左到右扫描输入串,根据分析栈和输入符号的情况,查分析表确定分析动作;

    (2) 分析表LR分析器的核心,根据文法构造,它包括动作表(Action)状态转换表(Goto)两部分,总控程序根据分析表确定分析动作;

    (3) 分析栈包括文法符号栈X[i]和相应的状态栈S[i]两部分,LR分析器通过判断栈顶元素和当前输入符号查分析表确定下步分析动作。

    规范归约的关键是寻找句柄LR法是根据已“移进”、“归约”的符号串及即将读入的符号串进行分析,以确定是否有句柄可归约。

    状态:是对迄今为止的整个分析过程的记录以及对

                  即将扫描的输入串的展望(预测)。

    例:S0状态(开始态)表示当前栈中仅有“#”,且即

                         将输入的符号为句首符号。

            SN状态(接受态)表示当前栈中已归约为开始

                         符号,且即将输入的符号应为“#”

    状态是根据分析表得到的,分析表是由文法构造的。

    2.分析表的组成:



    二、LR分析过程:

    1. 将初始状态S0和输入串的左边界(#)分别进栈;

    2. 根据栈顶状态Si当前输入符号a动作表进行如下工作:

    移进Action[Si,a]为“移进”,则a符号栈;并查Goto[Si,a]得到新的状态Sj进状态栈; 继续扫描,即下一个输入符号变成当前输入符号;
    归约:Action [Si,a]为“归约”,则按相应产生式

    A    β进行归约,若| β |=n,说明符号栈栈顶的n个符号为句柄,所以符号栈栈顶n个符号出栈A进符号栈同时,状态栈顶的n个元素也出栈此时状态栈顶为Sk则查Goto [Sk,A]得到新的状态Sl进状态栈





    三.LR(0)分析表的构造


           事实上:LR分析过程中,任意时刻均应保证栈中符号串是规范句型的活前缀,即:栈中绝无句柄之后的任何符号。若输入串为一合法的“句子”,则栈中符号剩余输入串就构成一个规范句型

           因此识别、产生规范句型的活前缀就是LR分析器的工作过程。为此,我们需要构造可识别文法所有活前缀的有限自动机。

          为构造识别文法所有活前缀的有限自动机,现定义构成有限自动机中状态的“项目

    () 项目

    1.定义:对于文法G,其产生式右部添加一个特殊的符号“.,就构成文法的一个LR(0)项目,简称项目


    ()构造识别活前缀的NFA

           根据项目的定义,我们可给出文法中所有产生式的项目,而每个项目都为识别活前缀的NFA的一个状态。即文法有多少个项目,它所对应识别活前缀的NFA就有多少个状态。

    1.NFA的构造方法

    (1)状态集:由每个项目所对应的状态组成的集合;

    (2)输入字符集合:由文法符号组成,包括:

                  终结符非终结符e

    (3)初态:对于文法G[S]的拓广文法G[S’],有项目S’® . S ,由于S’ 仅在第一个产生式的左部出现,所以规定它为初态

    (4)终态:每个状态均为NFA终态(活前缀的识别态)。


















    展开全文
  • LR(1) 分析例子

    万次阅读 2014-04-24 09:49:16
    第六单元~LR分析法     6.4 LR(1) 分析     本节介绍比SLR(1)功能更强的LR(1)分析法。  例如下列文法G′为:  (0) S′→S  (1) S→aAd  ...

    来自http://jpkc.gdut.edu.cn/comp/cmpl6/6-4-1.htm#top

     

      

    6.4 LR(1) 分析 

     

      本节介绍比SLR(1)功能更强的LR(1)分析法。
      例如下列文法G′为:
      (0) S′→S
      (1) S→aAd
      (2) S→bAc
      (3) S→aec
      (4) S→bed 
      (5)A →e
      我们首先用S′→·S作为初态集的项目,然后用闭包函数和转换函数构造识别文法G′的识别活前缀的有限自动机DFA见P143如图7.11所示,可以发现在项目集I5和I7中存在移进和归约冲突。
      I5:S→ae·c    I7:S→be·d
      A→e·       A→e·
      而归约项目左部非终结符的FOLLOW(A)={c,d}
      在I5中,FOLLOW(A)∩{c}={c,d}∩{c}≠∅     
      在I7中,FOLLOW(A) ∩{d}={c,d}∩{d}≠      
      因此I5,I7中冲突不能用SLR(1)方法解决。只能考虑用下面将要介绍的LR(1)方法解决。  
      由于用SLR(1)方法解决动作冲突时,对于归约项目A→α·,只要当前面临输入符为a∈FOLLOW(A)时,就确定采用产生式A→α进行归约,但是如果栈中的符号串为βα,归约后变为βA,再移进当前符a,则栈里变为βAa,而实际上βAa未必为文法规范句型的活前缀。 
        例如:在识别表达式文法的活前缀DFA中,(见图7.10)在项目集I2存在移进-归约冲突,即{E→T· T→T·*F}若栈顶状态为2,栈中符号为#T,当前输入符为‘)’,而‘)’属FOLLOW(E)中,这时按SLR(1)方法应用产生式E→T进行归约,归约后栈顶符号为#E,而再加当前符‘)’后,栈中为#E)不是表达式文法规范句型的活前缀。 因此这个归约是多余的。因此可以看出SLR(1)方法虽然相对LR(0)有所改进,但仍然存在着多余归约,也说明SLR(1)方法向前查看一个符号的方法仍不够确切,LR(1)方法恰好是要解决SLR(1)方法在某些情况下存在的无效归约问题。
        若[A→α·Bβ]∈项目集I,则[B→·γ](B→γ为一产生式)也包含在I中,不妨考虑,把FIRST(β)作为用产生式B→γ归约的搜索符,称为向前搜索符,作为归约时查看的符号集合,用以代替SLR(1)分析中的FOLLOW集,把此搜索符号的集合也放在相应项目的后面,这种处理方法即为LR(1)方法。(SLR(1)和LR(1)的区别在于LR(1)多使用了一个预判信息,即项目后面的符号如A →·e,c中的c,这个预判信息是用first集而非follow集得出的

    1. LR(1)项目集族的构造

      构造LR(1)项目集的闭包函数CLOSURE(I)按如下方式构造:
      a) I 的任何项目都属于CLOSURE(I)
      b) 若有项目[A→α·Bβ,a ]属于CLOSURE(I), B→γ 
                是文法中的产生式,β∈V*,b∈FIRST(βa), 则 
                 [B→·γ,b]也属于CLOSURE(I)中。
      c) 重复b)直到CLOSURE(I)不再增大为止。
      例:已知拓展文法为:
      (0) S′→S
      (1) S→aAd 
      (2) S→bAc
      (3) S→aec
      (4) S→bed 
      (5) A →e
      LR(1)项目集和转换函数如下:

     

    2.构造LR(1)分析表:


      如果一个文法的LR(1)分析表中不含多重入口时(或任何一个LR(1)项目集中无移进—归约或归约—归约的冲突,则称该文法为LR(1)文法.
      例:G(S):S → BB     B→aB      B →b

      I0:S'→.S   S →.BB    B →.aB      B →.b
      I1:S' →S.
      I2:S →B.B    B→.aB    B→.b
      I3:B→a.B     B→.aB     B→.b 
      I4:B→aB.  
      I5: B→b.
      I6: S→BB.

      例:G(S):S → BB     B→aB      B →b 
      拓展文法 : (0)S' → S   (1) S → BB   (2) B→aB     (3) B →b 

      对于该例题,只要仔细分析该文法的LR(1)每个项目集的项目,不难发现,即使不考察搜索符,它的任何项目都没有冲突,因此它实际上是一LR(0)文法,可以构造一个LR(0)项目集.可以得知它的LR(0)分析器只含7个状态,而现在LR(1)分析器却含有10个状态,其中I3和I6,I4和I7,I8和I9分别为同心集。


     

      

    展开全文
  • 最近学习了编译原理中的LR分析法,就自己用VS写了一个加深了解。 其中算术表达式的文法如下: 〈无符号整数〉∷= 〈数字〉{〈数字〉} 〈标志符〉∷= 〈字母〉{〈字母〉|〈数字〉} 〈表达式〉∷=[+|-]〈项...
        

    最近学习了编译原理中的LR分析法,就自己用VS写了一个加深了解。

    其中算术表达式的文法如下:

    〈无符号整数〉∷= 〈数字〉{〈数字〉} 〈标志符〉∷= 〈字母〉{〈字母〉|〈数字〉} 〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉}

    〈项〉∷= 〈因子〉{〈乘法运算符〉〈因子〉}

    〈因子〉∷= 〈标志符〉|〈无符号整数〉|‘(’〈表达式〉‘)’

    〈加法运算符〉∷= +|-

    〈乘法运算符〉∷= * |/

    效果截图:

    6607861-8df9d7d556aa4525.png

    参考博文和源码下载地址:

    https://write-bug.com/article/1351.html

    展开全文
  • LR(1)分析法

    千次阅读 2019-05-26 21:15:49
    SLR(1)分析法只是简单地考察下一个输入符号b是否属于与归约项目A→αA\rightarrowαA→α相关联的FOLLOW(A),但b∈FOLLOW(A)b\in FOLLOW(A)b∈FOLLOW(A) 只是归约的一个必要条件,而非充分条件。 假设栈内的符号串为...

    SLR(1)分析法只是简单地考察下一个输入符号b是否属于与归约项目AαA\rightarrowα相关联的FOLLOW(A),但bFOLLOW(A)b\in FOLLOW(A) 只是归约的一个必要条件,而非充分条件。

    假设栈内的符号串为 $ $ \delta\alpha $ ,规约之后变为 $ $\delta A$ ,当前读到的输入为a,若文法中不存在以 $ $\delta a $ 为前缀的规范举行,那么这种规约就无效了。并不是FOLLOW(A)中的每个元素在A的所有举行中都会出现在A的后面。

    LR(1)分析法的思想

    当师徒用某一规则AαA \rightarrow{\alpha}规约栈顶的符号α\alpha时,不仅应该查看栈中符号串δα\delta \alpha,还应向前扫视一个输入符号a,只有当δAa\delta Aa确实构成文法某一规范句型的前缀时,才能用此规则进行规约。

    因此,可以考虑在原来LR(0)项目集中增加更多的展望信息,这些信息有助于克服动作冲突和排除无效规约,也就是需要重新定义称之为**LR(1)**的项目。

    LR(1)项目

    一个LR(1)项目是一个二元组[AαβaA \rightarrow{\alpha·\beta,a}],其中AαβA \rightarrow{\alpha·\beta}是一个LR(0)项目,每个a是终结符,称它为展望符或搜索符

    当$\beta \not= \epsilon $时,搜索是无意义的。

    β=ϵ\beta = \epsilon时,搜索符a明确指出当[AαβaA \rightarrow{\alpha·\beta,a}]是栈顶状态的一个LR(1)项目时,仅在输入符号是a时才能用AαA \rightarrow{\alpha} 规约,而不是对FOLLOW(A) 中的所有符号都用AαA\rightarrow{\alpha}规约。

    LR(1)项目集族构造方法

    构造LR(1)项目集I的闭包函数

    1. I的任何项目都属于CLOSURE(I)
    2. 若项目[AαBβaa][A \rightarrow{\alpha·B\beta}a,a]属于CLOSURE(I)BrB \rightarrow{r}是文法中的一条规则,bFIRST(βa)b\in FIRST(\beta a),则[Brb][B \rightarrow{·r},b]也属于CLOSURE(I)
    3. 重复第二步直到CLOSURE(I)不再增大为止

    转换函数构造

    I是一个LR(1)项目集,X是一个文法符号,函数
    GO(I,X)=CLOSURE(J)J={[AαXβa][AαXβa]I} GO(I,X) = CLOSURE(J) \\ J = \{[A \rightarrow{\alpha X·\beta},a] | [A \rightarrow{\alpha ·X\beta},a] \in I\}

    总结

    多数情况下同一个文法的LR(1)项目集的个数比LR(0)项目集的个数要多,这是因为对同一个LR(0)项目集由于搜索符的不同而对应着多个LR(1)项目集

    当一个文法是LR(0)文法,则一定是一个SLR(1)文法,也是LR(1)文法。反之却不一定成立。

    展开全文
  • LR分析方法总结

    千次阅读 2019-06-20 20:32:28
    文章目录LR 类分析方法相关定义LR分析法的工作过程LR 分析表LR 驱动程序LR(0) 分析法LR(0) 分析法基本概念LR(0) 项目项目集的闭包项目集的投影项目集的转换函数(GO 函数)构造 LR(0) 可归前缀状态机 LRSMLR(0) ...
  • 一个简单实例的LR分析过程

    千次阅读 2016-05-24 18:59:35
    一个简单实例的LR分析过程  经过前面两篇文章。已经讲清楚了LR语法分析中最重要的分析表的构造过程。先补充一个小问题,就是LR(0)项目的分类    根据圆点所在的位置和圆点后是终结符还是非终结符或为...
  • 根据LR分析法的原理,对指定文法构造识别活前缀的DFA,做出相应的LR分析表,并编程实现相应的语法分析程序。或根据预测分析法的原理,对指定文法构造预测分析表,并编程实现相应的语法分析程序。 二、实验原理 1.所谓...
  • 实现了LR分析法; 完整vs2012工程; 代码精简,注释得当; 文法、Action、Goto表采用文件读入,操作灵活; 请尊重原创,如有问题,欢迎大家与我探讨。
  • LR分析法

    2018-06-12 16:24:10
    LR分析法就是会给出一种能根据当前分析栈中的符号串和向右顺序查看输入串中的k(k>=0)个符号就可以唯一地确定分析器的动作是移入还是归约和用哪个产生式进行归约 LR分析法的归约过程是规范推导的逆...
  • 本次课程设计需要使用 LR 分析法完成简单计算器的设计,其中算术表达式的文法如下: 〈无符号整数〉∷= 〈数字〉{〈数字〉} 〈标志符〉∷= 〈字母〉{〈字母〉|〈数字〉} 〈表达式〉∷=[+...
  • 【转】LR分析法

    2019-07-10 08:14:32
     LR分析法的归约过程是规范推导的逆过程,所以LR分析过程是一种规范归约过程。  LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的...
  • 本次课程设计需要使用 LR 分析法完成简单计算器的设计,其中算术表达式的文法如下: 〈无符号整数〉∷= 〈数字〉{〈数字〉} 〈标志符〉∷= 〈字母〉{〈字母〉|〈数字〉} 〈表达式〉∷=[+|-]〈项〉{...
  • 自底向上分析之LR分析法 说明:以老师PPT为标准,借鉴部分教材内容,AlvinZH学习笔记。 基本概念 1. LR分析:从左到右扫描(L)自底向上进行规约(R),是规范规约,也即最右推导(规范推导),是自底向上分析方法的高度...
  • 《编译原理》LR 分析法与构造 LR(1) 分析表的步骤 - 例题解析 笔记 直接做题是有一些特定步骤,有技巧。但也必须先了解一些基本概念,本篇会通过例题形式解释概念,会容易理解和记忆,以及解决类似问题。 如果只想做...
  • JAVAC源码 LR分析法 以及一个JAVA的词法分析 ,肯定不会后悔的
1 2 3 4 5 ... 20
收藏数 10,148
精华内容 4,059
热门标签
关键字:

lr分析法