BuK-KA-WHILE-COMPILER

Aus ProgrammingWiki
< BuK < IIm12

Inhaltsverzeichnis

Aufgabenstellung

Entwickeln Sie einen Compiler, der als Eingabesprache L_{WHILE}\cup L_{GOTO}\cup L_{LOOP} verwendet und ein zur Eingabe äquivalentes Programm aus L_{WHILE} (Zielsprache) erzeugt. Die Interpretation des jeweils entstandenen WHILE-Programms ist nicht gefordert.

Verwenden Sie AtoCC

Zielsetzung

Die Zielsetzung dieses Compiler ist es ein Programm das aus WHILE- LOOP- und GOTO-Befehelen besteht in ein WHILE-Prgramm umzuwandeln. Dabei können die Sprachen beliebig verschachtelt werden.

Ausgangsgrammatik

Definition

G = (N, T, P, s)
N = {S, P, PNM, Loop_P, While_P, Goto_P, Konstante, Zahl, Ziffer, Variable, Zuweisung, Operationssymbol, Marke, Vergleich}
T = {:, ;, LOOP, DO, END, WHILE, IF, THEN, GOTO, HALT, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, x, :=, +, -, M, ==}
P = {
  S                -> P 
  P                -> Marke : PNM | P ; P | PNM 
  PNM              -> While_P | Goto_P | Zuweisung | Loop_P 
  Loop_P           -> LOOP Variable DO P END 
  While_P          -> WHILE Variable DO P END 
  Goto_P           -> IF Vergleich THEN GOTO Marke 
                    | GOTO Marke 
                    | HALT 
  Konstante        -> Zahl 
  Zahl             -> Konstante Ziffer | Ziffer 
  Ziffer           -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
  Variable         -> x Konstante 
  Zuweisung        -> Variable := Konstante 
                    | Variable := Variable Operationssymbol Konstante 
  Operationssymbol -> + | - 
  Marke            -> M Konstante 
  Vergleich        -> Variable == Konstante 
}
s = S

Beispiel Ableitung

Fana_Ausgang_ableitung.png

Compiler

Scanner-Definition

Fana_Token.png

Parser-Definition

Fana_Parser.png

VCC-File download

Vorgehen

Zu jedem Programm in LOOP-Sprache kann ein äquivalentes Programm in der WHILE-Sprache angegeben werden, das gleiche gilt für die GOTO-Sprache.

LOOP zu WHILE

Ein LOOP-Programm wird so oft ausgeführt wie es die zugehörige Zählervariable angibt. Um diesen Ablauf mit einem WHILE-Programm zu erzeugen muss die zugehörige Zählervariable zyklisch dekrementiert und ansonsten nicht verändert werden.

GOTO zu WHILE

Um GOTO-Programme mittels WHILE-Sprache zu realisieren, wird das Programm mit einer WHILE-Schleife umschlossen. Allen Anweisungen wird ein IF vorrangestellt und nach deren Abarbeitung die Zählervariable inkrementiert. Bei einem Sprung zu einer Marke wird die Zählervariable auf den zur jeweiligen Anweisung gehörenden Wert gesetzt.

Beispiel

Compilerwiki

Download

Zielgrammatik

Definition

G = (N, T, P, s)
N = {S, P, PNM, While_P, IFVergleich, Konstante, Zahl, Ziffer, Variable, Zuweisung, Operationssymbol, Vergleich}
T = {;, WHILE, DO, END, IF, THEN, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, x, :=, +, -, ==}
P = {
  S                -> P 
  P                -> P ; P | PNM 
  PNM              -> IFVergleich | While_P | Zuweisung 
  While_P          -> WHILE Variable DO P END 
  IFVergleich      -> IF Vergleich THEN P 
  Konstante        -> Zahl 
  Zahl             -> Konstante Ziffer | Ziffer 
  Ziffer           -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
  Variable         -> x Konstante 
  Zuweisung        -> Variable := Konstante 
                    | Variable := Variable Operationssymbol Konstante 
  Operationssymbol -> + | - 
  Vergleich        -> Variable == Konstante 
}
s = S

Beispiel Ableitung

Fana_Ableitung.png