Kompilatorer och interpretatorer: Lösningar till tentamen 2004-10-18

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta, och det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften.

Uppgift 1: Kontextfri grammatik (6 p)

kommando -> move positionslista
positionslista -> positionslista ; position | position
position -> num , num
Icke-terminaler: kommando positionslista position
Startsymbol: kommando
Terminaler: move num , ;

Uppgift 2: Parse-träd (3 p)

(Träden blir förstås annorlunda om man formulerat grammatiken i uppgift 1 annorlunda.)

Parse-trädet för move 1, 17

Parse-trädet för move 1, 17

Parse-trädet för move 9, 19; 11, 19

Parse-trädet för move 9, 19; 11, 19

Uppgift 3: Top-down-parsning (13 p)

Grammatiken i lösningen på uppgift 1 ovan är vänsterrekursiv.

Den generella regeln för eliminering av vänsterrekursion säger att grammatiken
A -> A x | y
kan skrivas om till
A -> y R
R -> x R | empty

I det här fallet betyder det att produktionen

positionslista -> positionslista ; position | position
skrivs om till
positionslista -> position R
R -> ; position R | empty
där empty markerar en tom tokensträng.

Därefter ser hela grammatiken alltså ut så här:

kommando -> move positionslista
positionslista -> position R
R -> ; position R | empty
position -> num , num
Jag antar att tokentyperna MOVE, HELTAL, KOMMA och SEMIKOLON finns definierade som heltalskonstanter. Spårutskrifterna, som skriver ut namnen på icke-terminaler, behöver inte heller vara med. 
int lookahead;

void error() {
  printf("Ledsen error.\n");
  exit(EXIT_FAILURE);
}

void match(int expected) {
  if (lookahead != expected)
    error();
  else
    lookahead = scan();
}

extern void kommando(), positionslista(), R(), position();

void kommando() {
  printf("[kommando]\n");
  match(MOVE);
  positionslista();
}

void positionslista() {
  printf("[positionslista]\n");
  position();
  R();
}

void R() {
  printf("[R]\n");
  if (lookahead == SEMIKOLON) {
    match(SEMIKOLON);
    position();
    R();
  }
  else {
    /* Match empty */
  }
}

void position() {
  printf("[position]\n");
  match(HELTAL);
  match(KOMMA);
  match(HELTAL);
}

void parse() {
  printf("[parse]\n");
  lookahead = scan();
  kommando();
  printf("[Ok.]\n");
}

Uppgift 4: Lexikalisk analys (3 p)

Ja. Om man struntar i blanktecken:

move [0-9]+ , [0-9]+ ( ; [0-9]+ , [0-9]+ )*

Om man tar hänsyn till var blanktecken får och ska förekomma:

move[ ]+[0-9]+[ ]*,[ ]*[0-9]+([ ]*;[ ]*[0-9]+[ ]*,[ ]*[0-9])*

Uppgift 5: Mellankodsgenerering (10 p)

a) Ett abstrakt syntaxträd:

Ett abstrakt syntaxträd

b) Postfixkod för en stackmaskin: 

          lvalue i
          push 1
          =
          lvalue j
          push 0
          =
label 0:  rvalue i
          rvalue j
          >
          gofalse 1
          rvalue i
          push 10
          <
          gofalse 2
          lvalue i
          rvalue i
          push 1
          +
          =
          goto 3
label 2:  lvalue j
          push 10
          rvalue i
          -
          rvalue j
          -
          =
label 3:  goto 0
label 1:
c) Treadresskod: 
          i = 1;
          j = 0;
label 0:  if (i ≤ j) goto 1;
          if (i ≥ 10) goto 2;
          i = i + 1;
          goto 3;
label 2:  t1 = 10 - i;
          t2 = t1 - j;
          j = t2;
label 3:  goto 0
label 1:

Uppgift 6: Semantik (3 p)

Ingen alls, åtminstone så länge man inte utför optimeringar på syntaxträdet.

Syntaktisk analys, som mynnar ut i ett syntaxträd, är ju en av faserna i kompileringen. Terminering, dvs att programmet avslutas och inte hänger sig i en oändlig loop, är något som händer vi exekveringen.

Uppgift 7: Kontextfri grammatik, igen (6 p)

Ett alternativ:
Switch-sats -> switch ( Expression ) { Branch-list }
Branch-list -> Optional-branches Optional-default-branch
Optional-branches -> Branches | empty
Optional-default-branch -> Default-branch | empty
Branches -> Branches Branch | Branch
Branch -> case Expression : Statement break ;
Default-branch -> default : Statement break ;
Ett annat alternativ, som kräver en default-gren och minst en vanlig gren:
Switch-sats -> switch ( Expression ) { Branches Default-branch }
Branches -> Branches Branch | Branch
Branch -> case Expression : Statement break ;
Default-branch -> default : Statement break ;

Uppgift 8: Syntaxstyrd översättning (10 p)

Koden skulle bli enklare om syntaxträdet konstruerades lite annorlunda. 
void execute_switch(TreeNode* tree) {
  if (tree->type != SWITCH)
    error("Internt fel: Det där var ju ingen switch-sats!");
  int switch_value = execute(tree->args[0]);
  TreeNode* branches = tree->args[1];
  while (branches != NULL) {
    TreeNode* this_branch;
    if (branches->type == SEMICOLON) {
      this_branch = branches->args[0];
      branches = branches->args[1];
    }
    else if (branches->type == CASE) {
      this_branch = branches;
      branches = NULL;
    }
    else if (branches->type == DEFAULT) {
      this_branch = branches;
      branches = NULL;
    }
    else
      error("Internt fel: Omöjligt syntaxträd");

    if (this_branch->type == CASE) {
      if (switch_value == execute(this_branch->args[0])) {
	execute(this_branch->args[1]);
	return;
      }
    }
    else if (this_branch->type == DEFAULT) {
      execute(this_branch->args[0]);
      return;
    }
  } /* while */
} /* execute_switch */

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 27 oktober 2004