有可能逆转语法吗？

Question

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

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

例如，遵循语法

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

当倒转的时候是这样的：

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

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

那么，是否有一种系统的方法来获得“反向语法”呢？

恢复每一条规则有效吗？在我看来是这样。但我希望这样的“引理”会在我没有发现任何东西的情况下在某个地方出现。所以也许它只出现在简单的例子中？

Answer 1

第二版FWIW，Grune &Jacobs的解析技术。2008年(第68页)从自下而上和自上而下的解析和生产/还原二元性的角度，将语法的反转定义不同(将lhs转换为rhs，开始到终端，并添加一个新的开始)。

但是，无法理解为什么反向字符串不能与您所描述的相反语法进行解析。如果您需要的是一个未反转字符串的解析结果(假设您不能按正常顺序获得输入字符串，并且必须向后解析)，那么您可能还需要反转解析结果，例如AST。

希望这能有所帮助。

P.S.“由反向词组成的语言”--看起来你是在暗示一种由反向字符串组成的语言；对于相反的词，你不需要逆转root的rhs。

语法是一棵树，它是一个图，所以你可能会发现树/图反转方法很有用。