B5: Wortproblem und Syntaxanalyse

• Wir sind auf der Suche danach, ob wir ein Wort oder eine Sprache beweisen / nutzen können
• Wir haben uns mit $L_1$ Grammatik angeschaut, wie wir das mit Linksableitungen modellieren können

$LL(1)$-Grammatiken

• zuerst brauchen wir $FIRST(\alpha )$
  • Das ding beinhaltet, alle ersten Terminalzeichen von Strings, die aus $\alpha$ abgeleitet werden können
• $FOLLOW(X)$
  • Das beinhaltet alle Terminalzeichen, die in der Sprache DIREKT nach $X$ kommen
• Wir wollen zeigen, dass man die Mengen effizient berechnen kann
  • Denn wir wollen schauen, wie wir das idealerweise gut parsen können
• Die grammatiken haben feste Regeln, die wir beachten müssen
  • $FIRST(\alpha )\cap FIRST(\beta )\ne \varnothing$
  • IF $a⟹\ast ϵ$ then $FOLLOW(X)\cap FIRST(\beta )=\varnothing$

Parsing

• Wenn wir parsen wollen, bauen wir uns erstmal eine Tabelle, die uns sagt, wann wir wie welche Regel brauchen
  • Diese Tabelle brauen wir aus der Grammatik zusammen
  • Die bestimmen wir genauer gesagt aus den $FIRST$ und $FOLLOW$-Mengen
• Wenn wir dann also mal was Parsen müssen, schauen wir uns immer erst die Tabelle an
  • Die gibt uns dann, relativ Stupide vor, wie wir den kram ableiten müssen.
  • Sprich, die sagt uns wie wir (schritt für schritt) zu einem $c$ kommen, beispielsweise

Bottom-Up Syntaxanalyse (Ausflug)