Given the grammar below provide a leftmost derivation for th

Given the grammar below, provide a leftmost derivation for the given input string: TOKENS: INT for integers, VAR for single letter, +. *, (, ) GRAMMAR: E::= T {+ E} T::= P{* T} P::= INT | VAR|(E) INPUT STRING: a*(a+b)

Solution

Left most derivation means that you start from the start and start making projection. At every point you resolve the left most nonterminal symbol.

E => T => P*T => a*T => a*P => a*(E) => a*(T+E) => a*(P+E) => a*(a+E) => a*(a+T) => a*(a+P) => a*(a+b)