现实世界中的LR(k> 1)语法? [英] Real-world LR(k > 1) grammars?

查看:171
本文介绍了现实世界中的LR(k> 1)语法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

对k> 1进行人工LR(k)语法很容易:

Making artificial LR(k) grammars for k > 1 is easy:

Input: A1 B x
Input: A2 B y                   (introduce reduce-reduce conflict for terminal a)
A1   : a
A2   : a
B    : b b b ... b              (terminal b occurs k-1 times)

但是,有没有真实世界非LR(1)计算机是LR(k> 1)可解析的语言?

还是非LR(1)语言也不是LR(k)?

However, are there any real-world non-LR(1) computer languages that are LR(k > 1)-parsable?
Or are non-LR(1) languages also not LR(k) either?

推荐答案

如果语言具有 LR(k)语法,则它具有 LR(1)语法,可以从 LR(k)语法自动生成;此外,原始解析树可以从 LR(1)解析树中重新创建。该定理的证明出现在解析理论第6.7节中。 II,Sippu& Soisalon-Soininen;他们将其归因于MD Mickunas撰写的关于LR(k)语法的完全覆盖问题(1976年),在JACM 23:17-30中。

If a language has an LR(k) grammar, then it has an LR(1) grammar which can be generated mechanically from the LR(k) grammar; furthermore, the original parse tree can be recreated from the LR(1) parse tree. A proof of this theorem appears in Section 6.7 of Parsing Theory Vol. II, Sippu & Soisalon-Soininen; they attribute it to "On the complete covering problem for LR(k) grammars" (1976) by MD Mickunas, in JACM 23:17-30.

因此,没有语言可以解析为 k> 1 LR(k),也不能解析为 LR的语言(1),因此确实没有诸如 LR(k) language 之类的东西 k 的值(0和1除外)。

So there's no language parseable as LR(k) for k>1 which is not also parseable as LR(1), and consequently there really isn't such as thing as an LR(k) language for values of k other than 0 and 1.

但是,有些语言的 LR(2)语法要容易得多。一个经典的例子是 yacc 的Posix语法,它不需要以; 终止生产。这是明确的,因为生产必须以标识符开头,后跟冒号。这样写的语法显然是 LR(2);根据上述定理,虽然存在 LR(1)语法,但还远远不够清晰。

However, there are languages for which an LR(2) grammar is much easier. One classic example is the Posix grammar for yacc, which does not require productions to be terminated with a ;. This is unambiguous, because a production must start with an identifier followed by a colon. Written that way, the grammar is clearly LR(2); by the above theorem, an LR(1) grammar exists but it's nowhere near as clean.

这篇关于现实世界中的LR(k> 1)语法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

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