我正在学习无上下文语法,我想知道如何(如果有的话)设计一种避免重复的语言。
我们以SQL中的select语句为例:
possible:
SELECT * FROM table
SELECT * FROM table WHERE x > 5
SELECT * FROM table WHERE x > 5 ORDER desc
SELECT * FROM table WHERE x > 5 ORDER desc LIMIT 5
impossible (multiple conflicting statements):
SELECT * FROM table WHERE X > 5 WHERE X > 5
语法看起来像这样:
S -> SW | SO | SL | "SELECT statement"
W -> "WHERE statement"
O -> "ORDER statement"
L -> "Limit statement"
这种语法将允许像上面提到的那样不可能的陈述。我怎么能设计一个无上下文的语法,避免不可能的陈述,同时仍然灵活?
灵活:
W,O,L的顺序无关紧要。这些子陈述中有多少也无关紧要。我想避免使用只列出所有可能组合的语法,因为如果有很多可能性,这会变得非常混乱。
在无上下文语法中,非终端生成的句子集对于非终端的每次使用都是相同的。这就是无环境意味着什么。特定的非终端,S
,有时不允许匹配,有时不允许匹配。因此,每组可能的匹配必须有自己的非终端,并且在将k
案例列表限制为没有重复案例的句子的情况下,将需要最少的2k
不同的非终端,一个用于k
的每个子集案例。
更糟糕的是,如果您尝试限制的重复具有无限多种可能性(例如,您希望允许多个W
子句但不允许两个相同的W
s),那么无法使用无上下文语法来完成所有。如果你想坚持这样的重复也是如此,基本上你需要做的是让无上下文语法坚持在使用之前声明变量。
但是,很容易在语义操作中进行检查,例如通过保留您遇到的子句的位向量(或者如果不容易枚举可能的子句则使用哈希集)。然后,为语句添加子句的语义操作只需要检查是否已添加该特定子句,如果有,则标记错误。这也将允许更好的错误消息,因为您可以在检测到问题时轻松描述问题,而不是仅报告“语法”错误并让用户猜出问题所在。
我不确定我是否基于语法理解你的问题。也许你的意思是statement
和S
是同一个符号。如果是这种情况,我认为你的语法根本不适合你想要描述的语言。如果我们忽略ORDER
和LIMIT
那么你的语法是
S -> SW | "SELECT S" | foo
W -> "WHERE S"
然后是的,你可以得到像废话一样的废话
S -> SW -> SWW -> SWWW -> "SELECT foo WHERE foo WHERE foo WHERE foo"
但这只是你第一次尝试语法,这并不能证明没有语法可行。考虑一下:
<S> -> <A><B>
<A> -> SELECT <C>
<B> -> epsilon | WHERE <D>
<C> -> (rules for select lists)
<D> -> (rules for WHERE condition)
<C>
和<D>
的规则可以参考S
和A
以及B
,正确地,可能使用括号,根据需要生成适合您的字符串。你再也不能得到糟糕的琴弦了。
这不是CFG自身无法克服的问题。做一些事情,比如强制只能使用声明的变量,是的,上下文敏感的或更好的机制,但我们只是在谈论重复的关键词和短语。这完全在CFG可以做的范围内。现在,如果您想支持别名并在查询中强制执行正确的别名引用,那么在无上下文的语言中这是不可能的。但这不是我们在这里讨论的内容。这是不可能的原因是语言L = {ww | w in E*}
不是一种无上下文的语言,而且这实际上是执行变量名或表别名所涉及的内容。