| Übungsaufgabe Parser |
Was ist ein Parser?Der Parser übernimmt die Syntaxanalyse des Eingabetextes. Hierzu wird die erstellte Tokenliste des Scanners verwendet, um festzustellen ob der Eingabetext zur Sprache gehört oder nicht. Diese Feststellung basiert auf einer Grammatik. Reguläre Grammatiken sind fast immer unzureichend, da damit typische Programmiersprachen wie C oder Java nicht realisierbar sind. In der Praxis werden kontextfreie Grammatiken, im speziellen LR(k) Sprachen (k steht für die Anzahl der Vorrauschauzeichen), verwendet. Eine umfassende Definition zu LR(k) Sprachen finden Sie hier: LR(k).pdfDer Parsergenerator YACC (darauf basierend auch VCC) ist in der Lage so genannte LALR(1) Sprachen zu verarbeiten. AufgabeLaden Sie die Datei "calc_c#.xml" in VCC. Generieren Sie den Compiler und legen Sie eine Eingabedatei "input.txt" an. Schreiben Sie in diese Textdatei einen mathematische Ausdruck (z.B.: 23+12+(2+3)*2) und kompilieren diese mit dem Compiler ("compiler.exe input.txt").Betrachten Sie dazu die verwendete Grammatik und vergleichen Sie diese mit der Darstellung in VCC:
Input: | Epsilon | Input Expression
Expression: Expression '+' Expression
| Expression '-' Expression
| Expression '*' Expression
| Expression '/' Expression
| '(' Expression ')'
| Number
Dieser einfache Rechner enthält noch keine Regeln für die Priorität der Operatoren. Der Ausdruck "1+2*2+2*2" liefert 13 statt 9. Entwickeln Sie auf dem Papier eine neue Grammatik, welche die Regel Punktrechnung vor Strichrechnung verwirklicht (Beachten Sie, dass VCC später einen LALR(1) Parser generiert und somit jede Regel von Rechts aufgelöst wird!). Tipp: Sie benötigen zusätzliche Nichtterminale für diese Grammatik.[Lösung: Grammatik] Implementieren Sie Ihre Grammatik anschließend mit VCC. Öffnen Sie dazu am besten einen zweiten VCC Editor um den C# Quellcode für die einzelnen Regeln (der im Fenster unten rechts angezeigt wird) zu kopieren. Kompilieren und testen Sie erneut den Compiler auf verschiede arithmetische Ausdrücke. [Lösung: VCC Datei] |