Return to Question

I've an example which I simply don't get at all.

Implement an attributed grammar that checks that either

• the word ends in $b$ or
• each prefix of the word contains at least as many $b$s as $a$s

E.g. the word $bbbb\ aab\ aab\ aa$ is allowed but $abbabaabba$ is not. (I know - what an example!)

However, the grammar looks like this:

\begin{align} V &\rightarrow S \\ S_0 &\rightarrow S_1 a \\ S_0 &\rightarrow S_1 b \\ S &\rightarrow \epsilon \end{align}

and I am allowed to extend it to an attributed grammar. But I can't imagine how this can even be parsed from those rules since removing element by element from e.g. $abbab$ will never end up such that a rule can be applied.

What am I missing here?

I've an example which I simply don't get at all.

Implement an attributed grammar that checks that either

• the word ends in $b$ or
• each prefix of the word contains at least as many $b$s as $a$s

E.g. the word $bbbbaabaabaa$ is allowed but $abbabaabba$ is not. (I know - what an example!)

However, the grammar looks like this:

\begin{align} V &\rightarrow S \\ S_0 &\rightarrow S_1 a \\ S_0 &\rightarrow S_1 b \\ S &\rightarrow \epsilon \end{align}

and I am allowed to extend it to an attributed grammar. But I can't imagine how this can even be parsed from those rules since removing element by element from e.g. $abbab$ will never end up such that a rule can be applied.

What am I missing here?