AAB*_*AAB 35 compiler-construction parsing lalr context-free-grammar lr-grammar
我理解LR和LALR都是自下而上的解析算法,但两者之间有什么区别？
LR(0),LALR(1)和LR(1)解析之间有什么区别？如何判断语法是LR(0),LALR(1)还是LR(1)？
tem*_*def 58
在较高级别,LR(0),LALR(1)和LR(1)之间的差异如下:
LALR(1)解析器是LR(0)解析器的"升级"版本,其跟踪更精确的信息以消除语法的歧义.LR(1)解析器是一种功能更强大的解析器,可以跟踪比LALR(1)解析器更精确的信息.
LALR(1)解析器是大于LR(0)解析器的常数因子,并且LR(1)解析器通常比LALR(1)解析器指数大.
可以使用LALR(1)解析器解析可以使用LR(0)解析器解析的任何语法,并且可以使用LR(1)解析器解析可以使用LALR(1)解析器解析的任何语法.有一些语法是LALR(1)但不是LR(0)和LR(1)而不是LALR(1).
更正式地说,LR(k)解析器是一种自下而上的解析器,它通过维护一堆终端和非终端来工作.解析器由有限自动机确定,基于所述解析器和输入的下面k个令牌的当前状态控制,是否移动新令牌到堆栈或减少通过施加生产反向的堆栈的顶部的符号.
为了跟踪的足够的信息来确定是否转移或减少,LR(k)的解析器具有每个状态对应于"构式集,"一组用以下信息注释制作的:
首先这些信息被用来确定解析器是否可能需要做的减少 - 如果没有在当前状态下的作品已经完成,没有理由做的减少.在进行减少时使用这些信息中的第二条来确定是否应该执行减少.在决定是否减少时,LR(k)解析器查看输入流的下一个k标记.如果它们与前瞻标记匹配,则解析器将减少,否则解析器不执行任何操作.
当关于解析器在给定状态下应该做什么的冲突时,LR(k)解析器中出现问题.冲突的一个类型,转变/减少冲突,出现在解析器是在生产已完成的状态,但是对于生产冲突先行符号也使用在该州另一未完成生产.这意味着解析器无法判断是否执行缩减.第二种类型的冲突是减少/减少冲突,其中解析器知道它必须进行减少,但是两次或更多次减少是可能的,并且它不能告诉做哪些.
直观地,随着k变得越来越大,解析器具有越来越多的精确信息,以确定何时移位以及何时减少.例如,如果语法不是LR(0),则解析器可能具有一个状态,其中根本没有预测,它无法确定是移位还是减少.然而,该语法可能仍然是LR(1),因为给予额外的前瞻标记,它可能能够识别它应该明确地移动而不是减少或者肯定减少而不是移位.
LR(k)解析器的问题在于随着k变大,状态的数量可以指数增加.先行在LR(k)的解析器由解析器建立越来越多的国家,以对应于生产和向前看符号的不同组合,所以尽可能向前看符号的数目增加也是如此状态的数目来处理.因此,LR(1)解析器通常太大而不实用,并且LR(2)或更大在实践中几乎闻所未闻.
LALR(1)被发明为LR(0)解析器的空间效率和LR(1)解析器的表达能力之间的折衷.有几种方法可以考虑LALR(1)解析器是什么.最初,LALR(1)解析器被指定为将LR(1)自动机转换为较小自动机的转换.虽然LR(1)解析器可能具有比LR(0)自动机更多的状态,但唯一的区别是LR(1)解析器可能具有LR(0)自动机中任何特定状态的多个副本,每个都注释有不同的前瞻信息.LALR(1)解析器可以通过以LR(1)解析器开始,然后将具有相同"核心"(生产集合及其位置)的所有状态组合在一起,然后将所有先行信息聚合在一起来形成.
LALR(1)语法的另一种观点使用"LALR-by-SLR"方法.LALR(1)解析器可以通过从语法的LR(0)解析器开始构造,然后为该语言创建一个新语法,该语法使用有关它们对应的LR(0)解析器中的状态的信息来注释非终结符.然后可以使用关于该语法中的非终结符的FOLLOW集的信息来计算LR(0)解析器中的前瞻.
最终结果是
至于你的第二个问题 - 你如何确定语法是LR(1)还是LALR(1) - 标准方法是尝试为LR(1)解析器和LALR(1)解析器构建解析自动机并检查为了冲突.要构建LR(1)解析器,您需要构建LR(1)配置集,然后检查这些配置集中的任何一个是否具有shift/reduce冲突或减少/减少冲突.要构造LALR(1)解析器,您可以构建LR(1)解析器,然后使用相同的核心压缩配置集,也可以使用基于该语言的LR(0)解析器的LALR-by-SLR方法.大多数编译器教科书都提供了有关如何构建这些配置集的更多详细信息.您还可以查看我在2012年夏季教授的编译器课程中的讲义,它涵盖了所有上述解析方法和其他一些解析方法.
希望这可以帮助!