Context free grammar for pattern /aaa/{id}

Question

can someone tell me what the CFG for this pattern is: /var/{id}

Over here, var can be repeated many times, but the pattern always ends with {id}

Therefore, these are all valid cases:

/var/var/{id}

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

/var/{id}

I've gotten this grammar till now:

start::= token

token::= token expr token

token::= "/"

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

But I don't think its right. Help would be appreciated. Thanks!

Answer 1

You're almost there! The grammar you have right now will produce strings like /var/var/var/{id}/ but also /{id}/var/var/{id}/var/. So what you need to do is remove {id} from the expr rule. But then you still need to tack on {id} at the end to fit the definition of your language, and this can be done in the start rule. The resulting grammar is then:

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