当前位置：文江博客话题详情

语法是LALR吗？

发布于 2024-08-29 12:05:22 字数 115 浏览 2 评论 0原文

假设同一个文法不是 LR(1)，我们能有把握地说该文法也不是 LALR 吗？

如果不是，那么一个文法成为 LALR 的条件是什么？（或者什么条件使语法不是 LALR）

感谢您的帮助！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

请爱~陌生人 2024-09-05 12:05:24

LALR(1) ⊂ LR(1)，所以是的，我们可以假设。这两种文法以类似的方式表达语言，但 LR(1) 比 LALR(1) 跟踪更多的左状态。比照。这些讲义，讨论了两个表示之间的状态。

一般来说，解析器生成器将为您处理创建移位归约步骤的所有细节；不同之处在于，基于较大语法的生成器更有可能找到无冲突的解析策略。

回复收藏 0 原文

情绪少女 2024-09-05 12:05:24

这是一个简单的语法，它是 LR(1) 但不是 LALR(1)：

G -> S 
S -> c X t 
  -> c Y n
  -> r Y t
  -> r X n 
X -> a
Y -> a

LALR(1) 解析器生成器为您提供一个 LR(0) 状态机。
LR(1) 解析器生成器为您提供一个 LR(1) 状态机。
通过这个语法，LR(1) 状态机多了一个状态
比 LR(0) 状态机。

LR(0) 状态机包含此状态：

X -> a . 
Y -> a .

LR(1) 状态机包含这两个状态而不是
如上所示：

X -> a . { t }
Y -> a . { n }

X -> a . { n }
Y -> a . { t }

LALR 的问题是首先创建状态
没有任何关于前瞻性的知识。然后是前瞻
在状态形成后检查或创建。然后是拉尔
有这个状态和look-a-heads，通常是稍后添加的，
看起来像这样：

X -> a . { t, n }
Y -> a . { n, t }

有人能看出这里有问题吗？如果前瞻是“t”，
您选择哪种减免？很暧昧啊！所以
LALR(1) 解析器生成器为您提供归约冲突
报告可能会让没有经验的语法人员感到困惑
作家。

这就是为什么我将 LRSTAR 制作为 LR(1) 解析器生成器。它
可以处理上面的语法。

Here is a simple grammar that is LR(1) but not LALR(1):

G -> S 
S -> c X t 
  -> c Y n
  -> r Y t
  -> r X n 
X -> a
Y -> a

An LALR(1) parser generator gives you an LR(0) state machine.
An LR(1) parser generator gives you an LR(1) state machine.
With this grammar the LR(1) state machine has one more state
than the LR(0) state machine.

The LR(0) state machine contains this state:

X -> a . 
Y -> a .

The LR(1) state machine contains these two state instead of
the one shown above:

X -> a . { t }
Y -> a . { n }

X -> a . { n }
Y -> a . { t }

The problem with LALR is that the states are made first
without any knowledge of the look-a-heads. Then the look-a-heads
are examined or created after the states are made. Then LALR
has this one state and the look-a-heads, which are usually added later,
will look like this:

X -> a . { t, n }
Y -> a . { n, t }

Can anybody see a problem here? If the look-ahead is 't',
which reduction do you choose? It's ambiguous ! So the
LALR(1) parser generator gives you a reduce-reduce conflict
report which can be confusing to the inexperienced grammar
writer.

That is why I made LRSTAR an LR(1) parser generator. It
can handle the above grammar.

回复收藏 0 原文

~没有更多了~