Chapter 4, Problem 1E

Explanation of Solution

Context-Free-Grammar and attribute rules for given production:

• The given grammar is not a CFG but one can define an attribute grammar for the given production.
• The following grammar defines the production rules based on Boolean attributes.

  $\begin{array}{l}\text{G }\to \text{ As Bs Cs }\Rightarrow \text{G}\text{.ok := (As}\text{.val = Bs}\text{.val = Cs}\text{.val) }\\ {\text{As}}_1\to {\text{ a As}}_2\Rightarrow {\text{ As}}_1{\text{.val := As}}_2\text{.val + 1}\\ \text{As }\to \in \Rightarrow \text{As}\text{.val := 0}\\ {\text{Bs}}_1\to {\text{ b Bs}}_2\Rightarrow {\text{Bs}}_1{\text{.val := Bs}}_2\text{.val + 1}\\ \text{Bs}\to \in \Rightarrow \text{ Bs}\text{.val := 0}\\ {\text{Cs}}_1\to {\text{ c Cs}}_2\Rightarrow {\text{Cs}}_1{\text{.val := Cs}}_2\text{.val + 1}\\ \text{Cs }\to \in \Rightarrow \text{Cs}\text{.val := 0}\end{array}$

Explanation:

• The first step is to check the Boolean condition of the given production. If the condition becomes true then it will proceed to the next stage.
• In second step, the production for A is validated till it becomes epsilon (an empty production).
• The second step is repeated for both B and C production till they become empty.