Compiler-Design - Arten der Analyse

Syntaxanalysatoren folgen Produktionsregeln, die mittels kontextfreier Grammatik definiert wurden. Die Art und Weise, wie die Produktionsregeln implementiert werden (Ableitung), unterteilt das Parsen in zwei Typen: Top-Down-Parsing und Bottom-Up-Parsing.

Top-Down-Analyse

Wenn der Parser beginnt, den Analysebaum aus dem Startsymbol zu erstellen, und dann versucht, das Startsymbol in die Eingabe umzuwandeln, wird dies als Top-Down-Analyse bezeichnet.

• Recursive descent parsing: Es ist eine häufige Form der Top-Down-Analyse. Es wird als rekursiv bezeichnet, da es rekursive Prozeduren verwendet, um die Eingabe zu verarbeiten. Das Parsen rekursiver Abstammung leidet unter Backtracking.

• Backtracking: Wenn eine Ableitung einer Produktion fehlschlägt, startet der Syntaxanalysator den Prozess nach verschiedenen Regeln derselben Produktion neu. Diese Technik kann die Eingabezeichenfolge mehr als einmal verarbeiten, um die richtige Produktion zu bestimmen.

Bottom-up-Analyse

Wie der Name schon sagt, beginnt die Analyse von unten nach oben mit den Eingabesymbolen und versucht, den Analysebaum bis zum Startsymbol zu erstellen.

Example:

Eingabezeichenfolge: a + b * c

Produktionsregeln:

S → E
E → E + T
E → E * T
E → T
T → id

Beginnen wir mit der Analyse von unten nach oben

a + b * c

Lesen Sie die Eingabe und prüfen Sie, ob eine Produktion mit der Eingabe übereinstimmt:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S