上下文無關文法

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"