How can this grammar parse such an input?

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 $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?

Answer 1

In attribute grammars, you have variables attached to the symbols in the parse-tree which can take values. Equations attached to the rules specify how these values are propagated through the tree.

For that purpose, different occurences of a non-terminal in the same rule are distinguished by subscripts, so as to distinguish the variables attached to them.

For example the rule $S_0 \to S_1 b$ is used in the derivation of the topmost $S$ in the tree. In this occurrence: $S_0$ stands for the topmost $S$, while $S_1$ stands for the $S$ just below. So if the second $S$ has a $count$ variable equal to $-2$, then by applying the attribute equation $S_0.count=S_1.count+1$, the top $S$ get a count variable equal to $-1$.

Note that the equations are often interpreted as assignments, at least in attribute systems used in compilers. That is what was just done. But there are uses in which it can be seen as unification of logical variables (but you probably have not seen that).

Here the attribute rules are used as assignments, that are computed bottom-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 also propagate top-down sometimes and are then called inherited attributes. Synthesized attributes are more frequent, as they are computationally more 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 terminal string that non-terminal occurrence derives in.

• ok: is a boolean variable that is true for an occurrence of a non-terminal $S$ iff the terminal string this non-terminal occurrence derives in has no prefix with more $a$ than $b$. It is true for the non-terminal $V$ iff the terminal string $V$ derives in is acceptable.

• endb: is a boolean variable that is true for an occurrence of a non-terminal $S$ iff the 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}

Answer 2

In an attribute grammar one assigns values to the nonterminals of the grammar. This is to help evaluating parts of a grammar that are not context-free. One of the simple types is inherited attributes, these are assigned bottom-up in the derivation tree.

The indexes $S_0$ and $S_1$ are used here to distingish different occurrences of the nonterminal $S$ in the grammar. A good choice for an attribute here would be the difference of the number of occurrences $b$ and $a$. This number should never be negative according to your specification. I do not know how you are supposed to denote this, but assume the attribute is called $N$. For the rule $S_0 \to S_1 a$, the value of $N$ for $S_1$ determines the value of $N$ for $S_0$: $S_0.N = S_1.N - 1$ (since $S_0$ has one more $a$ than $S_1$.

Similarly for the other rule that introduces a $b$.

Now we have to introduce another attribute. In the end we should test whether the last symbol derived is a $b$. So the attribute should remember that letter and test it in the last step $V\to S$ (this is the last step in a bottom-upevaluation).

Again: check your class notes on how to specify alle these details.

Your examples are not clear: $aa$ does not end in a $b$ and neither has it at least as many $b$'s (?!)