无法用LL表示的LR语法示例? [英] Example of an LR grammar that cannot be represented by LL?

查看:171
本文介绍了无法用LL表示的LR语法示例?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

所有的LL语法都是LR语法,但并非相反,但是我仍然很难解决这个区别.我很想知道没有对应的LL表示形式的LR语法的小例子,如果有的话.

解决方案

就语法而言,它很容易-任何简单的左递归语法都是LR(可能是LR(1)),而不是LL.因此,列表语法如下:

list ::= list ',' element | element

是LR(1)(假设element的乘积是),但不是LL.这样的语法可以很容易地通过左分解等方式转换为LL语法,因此这并不是很有趣.

更令人感兴趣的是LR但不是LL的语言-这是一种语言,其中存在LR(1)语法但任何k都不存在LL(k)语法.一个例子是需要可选的尾随匹配的东西.例如,任意数量的a符号的语言,后跟相同数量或更少的b符号,但不多于b s-{a ^ i b ^ j | i> = j}.有一个简单的LR(1)语法:

S ::= a S | P
P ::= a P b | \epsilon

但没有LL(k)语法.原因是LL语法需要在看a时决定是匹配a + b对还是奇数a,而LR语法可以将这个决定推迟到看到b或输入的末尾. /p>

cs.stackechange.com上的这篇帖子有很多与此相关的参考文献

All LL grammars are LR grammars, but not the other way around, but I still struggle to deal with the distinction. I'm curious about small examples, if any exist, of LR grammars which do not have an equivalent LL representation.

解决方案

Well, as far as grammars are concerned, its easy -- any simple left-recursive grammar is LR (probably LR(1)) and not LL. So a list grammar like:

list ::= list ',' element | element

is LR(1) (assuming the production for element is) but not LL. Such grammars can be fairly easily converted into LL grammars by left-factoring and such, so this is not too interesting however.

Of more interest is LANGUAGES that are LR but not LL -- that is a language for which there exists an LR(1) grammar but no LL(k) grammar for any k. An example is things that need optional trailing matches. For example, the language of any number of a symbols followed by the same number or fewer b symbols, but not more bs -- { a^i b^j | i >= j }. There's a trivial LR(1) grammar:

S ::= a S | P
P ::= a P b | \epsilon

but no LL(k) grammar. The reason is that an LL grammar needs to decide whether to match an a+b pair or an odd a when looking at an a, while the LR grammar can defer that decision until after it sees the b or the end of the input.

This post on cs.stackechange.com has lots of references about this

这篇关于无法用LL表示的LR语法示例?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆