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$ oreach prefix of the word contains at least as many $b$s as $a$sE.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?
How can this grammar parse such an input?
formal grammars;compilers;parsers;attribute grammars
In attribute grammars, you have variables attached to the symbols inthe parse-tree which can take values. Equations attached to the rulesspecify how these values are propagated through the tree.For that purpose, different occurences of a non-terminal in the samerule are distinguished by subscripts, so as to distinguish thevariables attached to them.For example the rule $S_0 \to S_1 b$ is used in the derivation of thetopmost $S$ in the tree. In this occurrence: $S_0$ stands for thetopmost $S$, while $S_1$ stands for the $S$ just below. So if thesecond $S$ has a $count$ variable equal to $-2$, then by applying theattribute equation $S_0.count=S_1.count+1$, the top $S$ get a countvariable equal to $-1$.Note that the equations are often interpreted as assignments, at leastin attribute systems used in compilers. That is what was just done.But there are uses in which it can be seen as unification of logicalvariables (but you probably have not seen that).Here the attribute rules are used as assignments, that are computedbottom-up (Synthesized attributes), this is why the variable of the topmost symbol (i.e. with the index 0, left-hand side of the grammar rule) are on the left side of the assignment, and get assigned a value depending on the variables of the symbols corresponding to the right-hand side of the grammar rule. But attribute values can alsopropagate top-down sometimes and are then called inherited attributes.Synthesized attributes are more frequent, as they are computationallymore powerful (but it may come at a price).The parse tree for aab is      V      |      S     / \    S   b   / \  S   a / \S  a|We associate three attributes to non-terminals:count: contains the number of $b$ minus the number of $a$ for the terminalstring that non-terminal occurrence derives in.ok: is a boolean variable that is true for an occurrence of a non-terminal $S$ iffthe terminal string this non-terminal occurrence derives in has no prefix withmore $a$ than $b$. It is true for the non-terminal $V$ iff theterminal string $V$ derives in is acceptable.endb: is a boolean variable that is true for an occurrence of a non-terminal $S$ iffthe terminal string this non-terminal occurrence derives in terminates with a $b$.Now you have attribute computation associated to rules as follow:\begin{array}{llll}\text{Grammar}& \text{Attributes computation}\\V \to S& V.ok=S.ok\vee S.endb  \\S_0 \to S_1 a\;\;& S_0.count=S_1.count-1& S_0.ok=S_1.ok\wedge S_1.count>0& S_0.endb=false \\S_0 \to S_1 b& S_0.count=S_1.count+1& S_0.ok=S_1.ok& S_0.endb=true \\S \to \epsilon& S.count=0& S.ok=true  \end{array}