上下文无关文法

Question

有人可以告诉我CFG这种模式是什么：/var/{id}

在这里，VAR可以重复很多次，但模式总是与{id}

结束

因此，这些都是有效的情况下：

/var/var/{id} 

/var/var/var/var/{id} 

/var/{id} 

我已经得到这个语法至今：

start::= token 

token::= token expr token 

token::= "/" 

expr::= "var" | "{id}" 

但我不认为它是正确的。帮助将不胜感激。谢谢！

Answer 1

你快到了！您现在拥有的语法将产生像/var/var/var/{id}/这样的字符串，但也会产生/{id}/var/var/{id}/var/。所以你需要做的是从expr规则中删除{id}。但是，最后还是需要在{id}上添加符合您的语言的定义，这可以在start规则中完成。由此产生的语法为：

start::= token "{id}" 
token::= token expr token 
token::= "/" 
expr::= "var"