LL(1)语法示例不是LALR?

问题描述

我现在正在编译理论"课程中学习有关解析器的知识.我需要找到一个在LL(1)中但不在LALR中的语法示例.我知道它应该存在.请帮助我想到这个问题的最简单示例.

I am learning now about parsers on my Theory Of Compilation course.I need to find an example for grammar which is in LL(1) but not in LALR.I know it should be exist. please help me think of the most simple example to this problem.

推荐答案

给出了非LALR(1)语法(即LL(1))的示例:

Some googling brings up this example for a non-LALR(1) grammar, which is LL(1):

S ::= '(' X
    | E ']'
    | F ')'
X ::= E ')'
    | F ']'
E ::= A
F ::= A
A ::= ε

LALR(1)构造失败，因为E和F之间存在reduce-reduce冲突.在LR(0)状态集中，存在一个由...组成的状态

The LALR(1) construction fails, because there is a reduce-reduce conflict between E and F. In the set of LR(0) states, there is a state made up of

E ::= A . ;
F ::= A . ;

S和X上下文都需要

.因此，这些项目的LALR(1)前瞻集将来自S和X产生的令牌混合在一起.对于LR(1)，情况有所不同.

which is needed for both S and X contexts. The LALR(1) lookahead sets for these items thus mix up tokens originating from the S and X productions. This is different for LR(1), where there are different states for these cases.

使用LL(1)，可以通过查看第一组备选方案来做出决策，其中')'和']'总是出现在不同的备选方案中.

With LL(1), decisions are made by looking at FIRST sets of the alternatives, where ')' and ']' always occur in different alternatives.

这篇关于LL(1)语法示例不是LALR?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！