怎么判断一个文法是LR(0)

Question

如题所述

Answer 1

LR(0)分析就是LR(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。

LR(0)分析器的分析能力最低，但它是构造其余三种LR分析器的基础。SLR是“简单LR”分析的缩写，它是为了解决构造LR(0)分析器所出现的问题而形成的一种方法，其分析能力自然要比LR(0)分析器稍强一些。

扩展资料：

1965年，D.Knuth首先提出了LR(K)文法及LR(K)分析技术。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作。

LR分析是当前最一般的分析方法。这是因为它对文法的限制最少，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析，而且在分析的效率上也不比诸如不带回溯的自顶向下分析、一般的“移进归约”以及算符优先等分析方法逊色。

此外，LR分析器在工作过程中，还能准确及时地发现输入符号串的语法错误。凡此种种，就使LR分析方法在国际上受到了广泛的重视。

参考资料来源：百度百科-LR分析法

Answer 2

设g1、g2是两个文法

若l(g1)=l(g2)

则称g1与g2等价，记作g1≡g2。

即：文法的等价性是所定义的语言是一样的。

文法的化简是指消除如下无用产生式：

1、删除a->a形式的产生式(自定己)；

2、删除不能从其推导出终结符串的产生式(不终结)；

3、删除在推导中永不使用的产生式(不可用)。

扩展资料：

在ARM体系结构中LR的特殊用途有两种：一是用来保存子程序返回地址；二是当异常发生时，LR中保存的值等于异常发生时PC的值减4（或者减2），因此在各种异常模式下可以根据LR的值返回到异常发生前的相应位置继续执行。

当通过BL或BLX指令调用子程序时，硬件自动将子程序返回地址保存在R14寄存器中。在子程序返回时，把LR的值复制到程序计数器PC即可实现子程序返回。如，可以使用MOV PC, LR或者BX LR来完成子程序返回。另外，也可以在在子程序入口处使用下面的指令将LR保存到栈中。

参考资料来源：百度百科-LR

本回答被网友采纳

Answer 3

LL(1)就是向前只搜索1个符号，即与FIRST()匹配，如果FIRST为空则还要考虑FELLOW。　 LR需要构造一张LR分析表，此表用于当面临输入字符时，将它移进，规约（即自下而上分析思想），接受还是出错。 LR(0)找出句柄前缀，构造分析表，然后根据输入符号进行规约。 SLR(1)使用LR(0)时若有冲突，不知道规约，移进，活移进哪一个，所以需要向前搜索，则只把有问题的地方向前搜索一次。 LR(1)1.在每个项目中增加搜索符。2.举个列子如有A->α.Bβ，则还需将B的规则也加入。 LALR(1)就是假如两个产生式集相同则将它们合并为一个，几合并同心集。 我认为LR(1),SLR(1),LALR(1)只是对LR(0)的一种更全面的分析与考虑，关键先把LR(0)搞懂。

Answer 4

1、构造它的LR(0)项目集合的DFA（即识别该文法全部活前缀的DFA）；
2、根据该DFA画出该文法的LR(0)分析表；
3、在分析表中，每格要么只有一个内容，要么没有内容，（即无冲突）则为LR(0)文法。本回答被网友采纳