Coursify

Semantic Actions in Context-Free Grammars: Deriving Output for Input aadbd

Semantic Actions in Context-Free Grammars: Deriving Output for Input aadbd

Verified Sources
Nov 3, 2026

We interpret the braces {print(k)} as semantic actions attached to grammar productions, typically executed when that production is reduced (i.e., during bottom-up parsing) or at the corresponding production application time (in a general attributed-grammar view). In both interpretations, the observable “output” is the ordered list of print(k) values triggered by the derivation for the given input string.

For the grammar:

  • S→AS {print(1)}S \rightarrow AS\ \{print(1)\}
  • S→AB {print(2)}S \rightarrow AB\ \{print(2)\}
  • A→a {print(3)}A \rightarrow a\ \{print(3)\}
  • B→bC {print(4)}B \rightarrow bC\ \{print(4)\}
  • B→dB {print(5)}B \rightarrow dB\ \{print(5)\}
  • C→e {print(6)}C \rightarrow e\ \{print(6)\}

and the input aadbd, we must find a parse/derivation that generates exactly a a d b d and then list the semantic action prints in the order they occur during that parse.

Key notions: semantic action and reduction and attributed grammar and derivation.

Important constraint from the grammar: the only way to produce a d is via B→dB {print(5)}B \rightarrow dB\ \{print(5)\}, so every d in the input must correspond to a print(5)-reduction. Also, the only way to produce an e is via C→e {print(6)}C \rightarrow e\ \{print(6)\}, so input must contain e to ever execute print(6).

From the above, to match the middle substring b inside aadbd, we would need B⇒bCB \Rightarrow bC, which forces C⇒eC \Rightarrow e. But the input contains no e. Therefore, there is no valid parse of aadbd under these productions as written.

Grammar validity check

Input aadbd contains no e. Since the only production that introduces e is C→eC → e, any derivation that uses B→bCB → bC would be forced to produce an e. If no other production can introduce b (and here only B→bCB→bC introduces b), then aadbd is not generatable by this grammar.

Attempt to derive `aadbd` and detect the semantic-action sequence

  1. 1
    Step 1

    Choose between S→ASS→AS and S→ABS→AB. Since the string begins with two a symbols, the consistent attempt is to use S→ASS→AS so that A→aA→a provides the first a, and the remaining part must be generated by the inner SS.

  2. 2
    Step 2

    Use A→aA→a (this production carries {print(3)}) for each a that appears in the string.

  3. 3
    Step 3

    After producing the two a symbols, the remaining substring is d b d, which must be generated by BB-productions inside either S→ABS→AB (or after S→ASS→AS resolves). The only way to produce any b is B→bCB→bC (carrying {print(4)}), which forces C→eC→e (carrying {print(6)}), but the input has no e.

  4. 4
    Step 4

    Because the grammar forces an e whenever a b is produced (via B→bCB→bC), and the input aadbd has a b but no e, the grammar cannot generate aadbd. Therefore no sequence of reductions exists, hence no semantic actions can be executed.

Final result (observable output)

Because the input string aadbd is not derivable from the given grammar, the semantic actions {print(1)}…{print(6)} cannot be triggered by any valid parse.

Output: (no output — parse error / no valid derivation)

If the input were aad b e d (i.e., containing an e where required by C→eC→e), then a parse could use B→bCB→bC and thus eventually execute {print(4)} and {print(6)}.

Reduction-driven execution of semantic actions (if derivation existed)

Execute print(3)

1. Reduce A→a

Each time an a is derived via A→aA→a, action {print(3)} would execute."

Execute print(5)

2. Reduce B→dB

Each time a d is consumed through B→dBB→dB, action {print(5)} would execute."

Execute print(4)

3. Reduce B→bC

When a b is produced via B→bCB→bC, action {print(4)} would execute."

Execute print(6)

4. Reduce C→e

To complete B→bCB→bC, C→eC→e must reduce, forcing {print(6)}—but it cannot happen for inputs lacking e."

Common interpretations and edge cases

Knowledge Check

Question 1 of 4
Q1Single choice

Which production is the only one that can generate terminal b?

Explore Related Topics

1

Ambiguity in Grammar and a Proof of Ambiguity for a Given CFG

2

FIRST and FOLLOW Sets for a Given CFG

3

Constructing an LALR(1) Parsing Table for a Given Grammar (and Proving It Is Not SLR(1))

Browse all research articles