LL(1)语法示例不是LALR? [英] Example for LL(1) Grammar which is NOT 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.

推荐答案

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?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！