不是 LALR 的 LL(1) 语法示例? [英] 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.

推荐答案

一些谷歌搜索提出了这个非 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 之间存在归约-归约冲突.在 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.

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