创建有限制的上下文无关语法

Question

我试图通过使用一个有一些障碍的例子来理解 CFG。

比如我要匹配一个double变量的声明：

双d；在这种情况下，"d" 可以是任何其他有效标识符。

有些情况不应该匹配，例如"double double;"，但我不明白如何避免匹配第二个 "double"

我的做法：

G = (Σ, V, S, P)
Σ = {a-z}
V = {S,T,U,W}
P = { S -> doubleTUW 
T -> _(space)
U -> (a-z)U | (a-z)
W -> ;
}

现在必须有一种方法可以通过使用函数 L(G) 来限制此文法的可能结果。不幸的是，我找不到满足我拒绝第二个 "double".

要求的语法

Answer 1

这里有一个有点繁琐的正则表达式，用于匹配 double 以外的任何标识符。将其转换为 CFG 可以机械地完成，但更繁琐。

([a-ce-z]|d[a-np-z]|do[a-tv-z]|dou[ac-z]|doub[a-km-z]|doubl[a-df-z]|double[a-z])[a-z]*

将其转换为 CFG 可以机械地完成，但更乏味：

ALPHA → a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
NOT_B → a|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
NOT_D → a|b|c|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
NOT_E → a|b|c|d|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
NOT_L → a|b|c|d|e|f|g|h|i|j|k|m|n|o|p|q|r|s|t|u|v|w|x|y|z
NOT_O → a|b|c|d|e|f|g|h|i|j|k|l|m|n|p|q|r|s|t|u|v|w|x|y|z
NOT_U → a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|v|w|x|y|z
WORD  → NOT_D
      | d NOT_O
      | do NOT_U
      | dou NOT_B
      | doub NOT_L
      | doubl NOT_E
      | double ALPHA
      | WORD   ALPHA

这就是为什么我们中的许多人通常使用像 (f)lex 这样的扫描仪生成器来自动处理此类排除。

创建有限制的上下文无关语法

Creating Context-Free-Grammar with restrictions

grammar

context-free-grammar