Rechts/Links-Ableitungen und Parser

Ein Top-Down-Parser sucht von links eine Links-Ableitung,

ein Bottom-Up-Parser sucht von links eine (umgekehrte) Rechts-Ableitung

Beispiel: G = ({a, b},{S}, S,{S$\to$b, S$\to$aSS})

Rechtsableitung: S$\to$aSS$\to$aSaSS$\to$aSaSb$\to$aSabb$\to$aaSSabb$\to$aaSbabb$\to$aabbabb.

Kellerautomat (shift/reduce), Zustand: (Keller, Eingabe)

($\epsilon$, aabbabb)$\to_{S}^{}$(a, abbabb)$\to_{S}^{}$(aa, bbabb)$\to_{S}^{}$(aab, babb)$\to_{R}^{}$(aaS, babb)$\to_{S}^{}$(aaSb, abb)$\to_{R}^{}$(aaSS, abb)$\to_{R}^{}$(aS, abb)$\to_{S}^{}$(aSa, bb)$\to_{S}^{}$(aSab, b)$\to_{R}^{}$(aSaS, b)$\to_{S}^{}$(aSaSb,$\epsilon$)$\to_{R}^{}$(aSaSS,$\epsilon$)$\to_{R}^{}$(aSS,$\epsilon$)$\to$(S,$\epsilon$)