如何设计一个避免重复的上下文无关语法?

问题描述 投票:1回答:2

我正在学习无上下文语法,我想知道如何(如果有的话)设计一种避免重复的语言。

我们以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的顺序无关紧要。这些子陈述中有多少也无关紧要。我想避免使用只列出所有可能组合的语法,因为如果有很多可能性,这会变得非常混乱。

grammar context-free-grammar repetition
2个回答
3
投票

在无上下文语法中,非终端生成的句子集对于非终端的每次使用都是相同的。这就是无环境意味着什么。特定的非终端,S,有时不允许匹配,有时不允许匹配。因此,每组可能的匹配必须有自己的非终端,并且在将k案例列表限制为没有重复案例的句子的情况下,将需要最少的2k不同的非终端,一个用于k的每个子集案例。

更糟糕的是,如果您尝试限制的重复具有无限多种可能性(例如,您希望允许多个W子句但不允许两个相同的Ws),那么无法使用无上下文语法来完成所有。如果你想坚持这样的重复也是如此,基本上你需要做的是让无上下文语法坚持在使用之前声明变量。

但是,很容易在语义操作中进行检查,例如通过保留您遇到的子句的位向量(或者如果不容易枚举可能的子句则使用哈希集)。然后,为语句添加子句的语义操作只需要检查是否已添加该特定子句,如果有,则标记错误。这也将允许更好的错误消息,因为您可以在检测到问题时轻松描述问题,而不是仅报告“语法”错误并让用户猜出问题所在。


0
投票

我不确定我是否基于语法理解你的问题。也许你的意思是statementS是同一个符号。如果是这种情况,我认为你的语法根本不适合你想要描述的语言。如果我们忽略ORDERLIMIT那么你的语法是

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>的规则可以参考SA以及B,正确地,可能使用括号,根据需要生成适合您的字符串。你再也不能得到糟糕的琴弦了。

这不是CFG自身无法克服的问题。做一些事情,比如强制只能使用声明的变量,是的,上下文敏感的或更好的机制,但我们只是在谈论重复的关键词和短语。这完全在CFG可以做的范围内。现在,如果您想支持别名并在查询中强制执行正确的别名引用,那么在无上下文的语言中这是不可能的。但这不是我们在这里讨论的内容。这是不可能的原因是语言L = {ww | w in E*}不是一种无上下文的语言,而且这实际上是执行变量名或表别名所涉及的内容。

© www.soinside.com 2019 - 2024. All rights reserved.