是否有可能扭转语法？

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

这可以识别反向的常规语言,但是语法会以不同的方式解析字符串,具体取决于字符串是否以a开始(在反转的情况下结束).在这个简单的例子中,语言是规则的,因此反向语言也是规则的,因此两者都可以通过一些语法从左到右进行解析.但是,情况并非总是如此,并且无论如何您通常会解析字符串以获取解析树,而不仅仅是确定字符串是否有效.b?a*a*b?ab

简而言之,您可以通过反转所有右侧来构造一个无上下文语法来反转语言,但结果语法可能不那么容易解析.(或者它可能更容易.)

笔记

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