Semantische Analyse¶
Quiz¶
- Ist syntaktisch korrekt, weil ein
if
als condition eine Expression erwartet - Aber semantisch falsch, bool nicht addierbar etc.
- Dies sind kontextsensitive Regeln
Semantic Checker¶
- Input: AST oder konkreter Syntaxtree
- Output: AST + Symboltabelle
- Prüfen, dass das Programm gemäss Sprachregeln "Sinn macht"
- Deklarationen prüfen (eindeutig und nicht mehrfach)
- Typen (Typregeln sind erfüllt)
- Method-Calls (Argumente und Parameter sind kompatibel)
- Und mehr...
- Transformiere Programm, so dass Code Generation einfach wird
- Syntaxbaum umstellen
- z.B. Vereinheitlichen von verschiedenen Loops, z.B. aus for- einen while-loop
- Array Boundary Check
- Implizite Casts
- usw.
Symboltabelle¶
- Datenstruktur zur Verwaltung von Deklarationen
- Zu jedem Namen ist der Scope angegeben
- Scopes können rekursiv sein, z.B. Methode -> Methode etc.
- Scoping auch wichtig bei z.B. loops
Shadowing¶
- Überdecken von Deklarationen in äusserem Scope durch Defintion in innerem Scope
- In Rappi-sharp möglich
- Unterschied zu "Hiding": Beim Hiding verdecken Methoden/Variablen in einer Unterklasse die Deklaration in der Superklasse
- Shadowing in
Global Scope¶
- Es gibt einen global Scope
- Bei uns können dort nur Klassen vorkommen
- Keywords wie
true
,int
,bool
können auch dort definiert werden
Design der Symboltabelle¶
CompilationUnit
ist der "global" Scope- Im ersten Schritt werden die Deklarationen aufgelöst, erste danach werden Typen aufgelöst
- Weil während dem Durchlaufen Typen erst später deklariert werden könnten
- Zu einer lokalen Variable wird dazu gespeichert, in welchen Statements die Variable "lebt"
- Spätestens jetzt muss geprüft werden, dass
int
,bool
etc nicht als Identifier verwendet werden! null
muss speziell behandelt werden- Es gibt ein Dictionary, das Symbole zu Knoten-Referenzen mappt.
Vorgehen¶
- Symboltabelle aufbauen
- Typen auflösen
- AST durchlaufen und mit Symboltabelle verbinden
- Alle Vorkommenden Identifier verlinken mit entsprechendem Symbol
- (Unsere Aufgabe) Typen in AST bestimmen
Namensauflösung¶
- z.B. Typen auflösen
- Zuerst suche im innersten Scope, dann im nächst äusseren Scope, usw. rekursiv
- Suche mit
Find
Method auf Symboltabelle
Type Checking¶
Important
Wichtig für Übung: Folie 32, Folie 36 Punkte 2, 4-7, 9, Folien 38-42
- Für jede Expression den Typ bestimmen
- Insbesondere Binary/Binary Expressions: Typen checken
- Auch z.B. bei
if
: Ist condition ein bool?
Ablauf¶
- Post-Order-Traversierung
- Zuerst child-nodes auflösen
- AST nicht verändern, sondern z.B. Symboltabelle
FixType()
aufrufen - Nach dem Auflösen folgt das Checking
- z.B. Array length read-only, noch selbst implementieren
- Bei Zuweisungen: Prüfen, ob rechte und linke Seite gleichen Typ haben
- Ausser bei Polymorphismus und
null
- Gleiches Prinzip bei Methoden-Aufrufen
- Ausser bei Polymorphismus und
Statische Analyse¶
- Checks wie Array-Bounds sind nicht allgemein entscheidbar
- Kann vom Compiler transformiert werden, z.B. neue Statements einfügen
- Muss bei einer Runtime aber sowieso überprüft werden (Sicherheit), deshalb lohnt es sich hier nicht