问题描述
对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)语法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!