DA: Analyse von shift/reduce Konflikten
Während der Entwicklung von Parsern mit Hilfe von LR-basierten
Tools wie yacc oder bison [Her92,LMB90] entstehen oft
shift/reduce Konflikte. Diese werden von den Tools in der Regel
durch Bevorzugung der shift Aktion gelöst. Zum Beispiel hat die
folgende yacc Spezifikation einen shift/reduce Konflikt für das
Eingabesymbol + in der LALR(1)-Information für
e'+'e:
%%
e : 'X'
| e '+' e
;
Selbst für einen Compilerbauer mit genauen Kenntnissen der
LR-Strategie ist es schwer zu beurteilen, ob die vom Tool gewählte
shift Aktion der Intention entspricht. Es ist dabei unbedingt nötig
geeignete Beispiele zu finden, in denen 'shift' und
'reduce' zu unterschiedlichen Ableitungen und damit zu verschiedenen
syntaktischen Strukturen führen. In dem Beispiel führt etwa die
Eingabe X+X+X zu unterschiedlichen Ableitungen, die
verschiedenen Assoziativitäten des Symbols + entsprechen:
| shift | | reduce |
|---|
e + e
| |
e + e |
| | |
X X X
| |
e + e
| |
| e + e
| | |
X X X
| Ziel dieser
Diplomarbeit ist die Entwicklung eines Tools zur automatischen
Generierung von solchen Beispielen und den zugehörigen
Ableitungen. Ausgangspunkt ist die Möglichkeit der Tools die
LR-Analysetabelle und LR-Automaten auszugeben. Wesentliche Punkte
dabei sind Endlichkeit/Minimalität und Vollständigkeit: Bereits bei
der obigen Grammatik sind alle Satzformen X+X+...+X
Beispiele für den Konflikt. Es soll nur ein möglichst kleiner
Repräsentant (in diesem Fall X+X+X) generiert
werden. Andererseits soll jeder auftretende Fall durch ein Beispiel
abgedeckt werden.
| Benötigte Vorkenntnisse: |
Vorlesung Compilerbau |
| Einarbeitungsaufwand: |
|
| Zuordnung: |
|
|
![[Mail]](../../../../Images/umschlag.gif)
![[I2 logo]](../../../../Images/i2.gif)
![[RWTH logo]](../../../../Images/rwth-rot90.gif)
Home
