Grammars

ACompressed recap

🧾

A context-free grammar has terminals, nonterminals, productions and a start symbol. A derivation rewrites one nonterminal per step; leftmost and rightmost derivations of one parse tree have the same number of steps. A parse tree records the structure; its leaves read left to right give the sentence. A grammar is ambiguous if some sentence has two parse trees; precedence is encoded by one nonterminal per level and associativity by which side repeats.

BMerged rule card

2.1.1 Context-free grammar primer: productions, derivations (leftmost/rightmost), parse trees

• CFG = terminals, nonterminals, productions A → α, start symbol.
• Derivation step: replace one nonterminal by a right side. Leftmost (⇒lm) / rightmost (⇒rm = canonical).
• Sentential form: derivable string; sentence: all terminals; L(G) = all sentences.
• Parse tree: root = start symbol, interior = nonterminals, leaves = terminals/ε; yield = leaves left to right.
• Steps in any derivation of a tree = number of interior nodes.
• Grammars ⊃ regular expressions (aⁿbⁿ, balanced brackets).

2.1.2 Ambiguity; encoding operator precedence and associativity in a grammar

• Ambiguous grammar: some sentence has ≥ 2 parse trees (≥ 2 leftmost derivations).
• Fix precedence: one nonterminal per level; lowest precedence nearest the start symbol.
• Fix associativity: E → E op T (left), E → T op E (right).
• Dangling else: else matches the nearest unmatched then (matched/unmatched grammar).
• Trees of an operator chain in E → E op E | id: Catalan numbers 1, 2, 5, 14, 42.

CInterleaved GATE-style questions

Q1NAT1 markDerivations

In E → E + T | T, T → T * F | F, F → ( E ) | id, how many steps does any derivation of ( id ) take?

Numerical answer: ________

Q2MCQ1 markTerms

A string of terminals and nonterminals derived from the start symbol is a:

• (A) sentence
• (B) sentential form
• (C) production
• (D) token

Q3NAT2 marksAmbiguity

How many parse trees does id + id + id + id have in E → E + E | E * E | id?

Numerical answer: ________

Q4MCQ2 marksEvaluation

If E → E − E | n is parsed so that − is right associative, what is 10 − 3 − 2?

• (A) 5
• (B) 9
• (C) −5
• (D) 15

Q5MSQ1 markLanguages

Which strings belong to S → a S b | ε?

• (A) ε
• (B) ab
• (C) abab
• (D) aaabbb

Q6MCQ1 markDangling else

In C, if (a) if (b) x(); else y(); attaches the else to:

• (A) the first if
• (B) the second (inner) if
• (C) both ifs
• (D) neither; it is a syntax error

Q7MCQ1 markPrecedence

To make ^ bind tighter than * and be right associative, add the level:

• (A) T → T ^ F | F
• (B) P → B ^ P | B, placed below T
• (C) E → E ^ T | T, placed above E
• (D) F → F ^ F | id

Q8MSQ2 marksFacts

Which are true?

• (A) Every parse tree has a unique leftmost derivation.
• (B) Ambiguity can always be decided by an algorithm.
• (C) An unambiguous grammar can generate the same language as an ambiguous one.
• (D) If a sentence has two leftmost derivations, the grammar is ambiguous.