parsing - 是否可以反转语法？

Question

对于给定的上下文无关语法，是否有可能获得“反向语法”？

我所说的“反向语法”是指一种语法，它接受由原始语法语言的反向单词组成的语言。

例如以下语法

root = r1 [r2] *r3
r1   = "a"
r2   = "b"
r3   = "cd"

反转时看起来像这样:

root = *r3 [r2] r1
r1   = "a"
r2   = "b"
r3   = "dc"

我问这个的原因是我想向后解析字符串(从头到尾)。为此，我需要“反向语法”。

那么有没有系统的方法来获得“逆向语法”呢？

恢复每条规则是否有效？在我看来是这样。但我希望这样的“引理”会在某处陈述，而我什么也没找到。所以也许它只出现在简单的例子中？

Answer 1

上下文无关语言的集合在字符串反转的操作下是封闭的，这是一种数学上的说法，如果您有上下文无关语言，那么向后由相同字符串组成的语言也是上下文无关的。证明很简单，并且正是基于所指出的转换:采用上下文无关文法并反转每个右侧；结果语法显然是上下文无关的，并且接受原始语法所接受的字符串的反转。形式证明可以在形式语言理论的标准教科书中或互联网上轻松找到。 [1]
常规语言也是如此，使用非常相似的结构。
然而，实际上存在一个问题:虽然为语言的逆向构建的语法显然是上下文无关的，但它可能不是 LR(1)。很容易构造一个 LR(1) 文法的例子，它的逆不是:

S -> a A
S -> b B
A -> a
A -> A a
B -> a
B -> B a

识别正则语言 b?a*其反面是 a*b? ，但语法解析了 a 的字符串的不同，取决于字符串是否以 b 开始(在反转的情况下结束) .在这种简单的情况下，语言是正则的，因此反向语言也是正则的，因此可以通过某种语法从左到右解析两者。然而，情况并非总是如此，在任何情况下，您通常会解析字符串以获得解析树，而不仅仅是确定字符串是否有效。
简而言之，您可以通过反转所有右侧来构造用于反转语言的上下文无关文法，但由此产生的文法可能不那么容易解析。 (或者它可能更容易。)

笔记

一个好的搜索开始可能是 context free language closure properties .