是否可以反转语法？
Is it possible to reverse a grammar?
对于给定的上下文无关文法，是否有可能获得 "reversed grammar"?
"reversed grammar" 我的意思是一种语法，它可以接受由原始语法语言的反向单词组成的语言。
例如下面的语法
root = r1 [r2] *r3
r1 = "a"
r2 = "b"
r3 = "cd"
反转后会是这样：
root = *r3 [r2] r1
r1 = "a"
r2 = "b"
r3 = "dc"
我问这个的原因是我想向后解析字符串（从头到尾）。为此，我需要 "reversed grammar".
那么有没有系统的方法获取"reversed grammar"？
还原每条规则是否有效？在我看来是这样。但我预计这样的 "lemma" 会在某处声明，而我什么也没找到。所以也许它只出现在简单的例子中？
FWIW，Grune 和 Jacobs 的解析技术第 2 版。 2008（第 68 页）在自下而上和自上而下的解析以及 production/reduction 对偶性方面以不同方式定义了语法的反转（如将 lhs 转换为 rhs，开始到终端并添加新的开始）。 =11=]
但是，无法理解为什么不能像您描述的那样使用反转的语法解析反转的字符串。如果您需要的是未反转字符串的解析结果（假设您不能按正常顺序输入字符串并且必须向后解析），您可能还需要反转解析结果，例如AST.
希望对您有所帮助。
P.S。 "language consisting of reversed words" -- 看起来你在暗示一种由反转字符串组成的语言；对于颠倒的词，你不需要颠倒 root 的 rhs.
P.P.S。语法是一棵树，它是一个图，因此您可能会发现 tree/graph 反转方法很有用。
上下文无关语言的集合在字符串反转操作下是封闭的，这是一种数学表达方式，如果你有上下文无关语言，那么由相同字符串反向组成的语言也是上下文无关。证明很简单，并且精确地基于所指示的转换：采用上下文无关文法并反转每个右侧；生成的语法显然是上下文无关的，并且接受与原始语法接受的字符串相反的字符串。形式证明很容易在形式语言理论的标准教科书或互联网上找到。 [1]
常规语言也是如此，使用非常相似的结构。
然而，实际上，存在一个问题：虽然为语言的逆向构造的语法显然是上下文无关的，但它可能不是 LR(1)。很容易构造一个反向不是的 LR(1) 文法的例子：
S -> a A
S -> b B
A -> a
A -> A a
B -> a
B -> B a
识别正则语言b<sup>?</sup>a<sup>*</sup>其反义为a<sup>*</sup>b<sup>?</sup>，但是文法解析a的字符串的方式不同，取决于字符串是否以 b 开头（在反转的情况下结束）。在这个简单的例子中，语言是正则的，因此反向语言也是正则的，所以两者都可以通过某种语法从左到右进行解析。然而，情况并非总是如此，在任何情况下，您通常解析字符串是为了获得解析树，而不仅仅是确定字符串是否有效。
简而言之，您可以通过反转所有右侧来构造语言反转的上下文无关语法，但生成的语法可能不那么容易解析。 （或者它可能更容易。）
注释
- 一个好的开始搜索可能是
context free language closure properties。
对于给定的上下文无关文法，是否有可能获得 "reversed grammar"?
"reversed grammar" 我的意思是一种语法，它可以接受由原始语法语言的反向单词组成的语言。
例如下面的语法
root = r1 [r2] *r3
r1 = "a"
r2 = "b"
r3 = "cd"
反转后会是这样：
root = *r3 [r2] r1
r1 = "a"
r2 = "b"
r3 = "dc"
我问这个的原因是我想向后解析字符串（从头到尾）。为此，我需要 "reversed grammar".
那么有没有系统的方法获取"reversed grammar"？
还原每条规则是否有效？在我看来是这样。但我预计这样的 "lemma" 会在某处声明，而我什么也没找到。所以也许它只出现在简单的例子中？
FWIW，Grune 和 Jacobs 的解析技术第 2 版。 2008（第 68 页）在自下而上和自上而下的解析以及 production/reduction 对偶性方面以不同方式定义了语法的反转（如将 lhs 转换为 rhs，开始到终端并添加新的开始）。 =11=]
但是，无法理解为什么不能像您描述的那样使用反转的语法解析反转的字符串。如果您需要的是未反转字符串的解析结果（假设您不能按正常顺序输入字符串并且必须向后解析），您可能还需要反转解析结果，例如AST.
希望对您有所帮助。
P.S。 "language consisting of reversed words" -- 看起来你在暗示一种由反转字符串组成的语言；对于颠倒的词，你不需要颠倒 root 的 rhs.
P.P.S。语法是一棵树，它是一个图，因此您可能会发现 tree/graph 反转方法很有用。
上下文无关语言的集合在字符串反转操作下是封闭的，这是一种数学表达方式，如果你有上下文无关语言，那么由相同字符串反向组成的语言也是上下文无关。证明很简单，并且精确地基于所指示的转换：采用上下文无关文法并反转每个右侧；生成的语法显然是上下文无关的，并且接受与原始语法接受的字符串相反的字符串。形式证明很容易在形式语言理论的标准教科书或互联网上找到。 [1]
常规语言也是如此，使用非常相似的结构。
然而，实际上，存在一个问题：虽然为语言的逆向构造的语法显然是上下文无关的，但它可能不是 LR(1)。很容易构造一个反向不是的 LR(1) 文法的例子：
S -> a A
S -> b B
A -> a
A -> A a
B -> a
B -> B a
识别正则语言b<sup>?</sup>a<sup>*</sup>其反义为a<sup>*</sup>b<sup>?</sup>，但是文法解析a的字符串的方式不同，取决于字符串是否以 b 开头（在反转的情况下结束）。在这个简单的例子中，语言是正则的，因此反向语言也是正则的，所以两者都可以通过某种语法从左到右进行解析。然而，情况并非总是如此，在任何情况下，您通常解析字符串是为了获得解析树，而不仅仅是确定字符串是否有效。
简而言之，您可以通过反转所有右侧来构造语言反转的上下文无关语法，但生成的语法可能不那么容易解析。 （或者它可能更容易。）
注释
- 一个好的开始搜索可能是
context free language closure properties。