Kompilatorer och interpretatorer: Lösningar till tentamen 2003-06-05

Med vissa rättelser.

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 2: Kontextfri grammatik (10 p)

Expression -> Term
Expression -> Expression union Term
Expression -> Expression minus Term
Term -> Faktor
Term -> Term intersection Faktor
Faktor -> Set
Faktor -> left_parenthesis Expression right_parenthesis
Set -> Literal
Set -> Variable
Literal -> left_bracket Elements right_bracket
Literal -> left_bracket right_bracket
Elements -> Elements comma integer
Elements -> integer
Variable -> identifier
Eller, mer kompakt skrivet:
Expression -> Term | Expression union Term | Expression minus Term
Term -> Faktor | Term intersection Faktor
Faktor -> Set | left_parenthesis Expression right_parenthesis
Set -> Literal | Variable
Literal -> left_bracket Elements right_bracket | left_bracket right_bracket
Elements -> Elements comma integer | integer
Variable -> identifier

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

a)

Parse-trädet för strängen aceeef

b)

(Man kan systematiskt gå igenom alla strängar som går att härleda genom att börja med S och sen tillämpa reglerna i grammatiken.)

Förutom aa och ad matchas (om jag räknat rätt) samma strängar som matchas av det reguljära uttrycket ace*fb*.

Några strängar: aa, ad, acf, acef, aceef, aceeef, aceeeef, aceeeeef, aceeeeeef, aceeeeeeef, aceeeeeeeef, acfb, acefb, aceefb, aceeefb, aceeeefb, aceeeeefb, aceeeeeefb, aceeeeeeefb

c)

Grammatiken innehåller två produktioner för S: 

S -> a X
S -> a Y
där FIRST(a X) och FIRST(a Y) båda är lika med { a }. Därför kan en prediktiv parser inte välja vilken regel som ska användas, i alla fall inte med en enda tokens lookahead.

Produktionen 

X -> X b
innehåller vänsterrekursion. En recursive-descent-parser som parsar en sträng, och ska matcha icke-terminalen X, anropar proceduren X. I den proceduren avgörs att källsträngen matchar högerledet X b. Därefter ska det högerledet matchas, och vi börjar med att matcha X genom att anropa proceduren X. Och nu är vi alltså tillbaka i samma procedur, utan att ha "förbrukat" några tokens i inmatningen, och så håller det på i en oändlig rekursion.

d)

Den generella transformationen vänsterfaktorisering:
A -> x y | x z blir A -> x R och R -> y | z
I vårt fall: S -> a X | a Y blir S -> a R1 och R1 -> X | Y

Den generella transformationen eliminering av vänsterrekursion:
A -> A x | y blir A -> y R och R -> x R | empty
I vårt fall: X -> X b | c Z blir X -> c Z R2 och R2 -> b R2 | empty

Den transformerade grammatiken: 

S -> a R1
R1 -> X | Y
X -> c Z R2
R2 -> b R2 | empty
Y -> a | d
Z -> e Z | f
empty ska egentligen vara symbolen för en tom sträng, men den är svår att skriva i HTML så det blir rätt i alla webbläsare.

e) 

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

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

extern void S(), R1(), X(), R2(), Y(), Z();

void S() {
  printf("S\n");
  match('a');
  R1();
}

void R1() {
  printf("R1\n");
  if (lookahead == 'c')
    X();
  else if (lookahead == 'a' || lookahead == 'd')
    Y();
  else
    error();
}

void X() {
  printf("X\n");
  match('c');
  Z();
  R2();
}

void R2() {
  printf("R2\n");
  if (lookahead == 'b') {
    match('b');
    R2();
  }
  else {
    /* Match empty */
  }
}

void Y() {
  printf("Y\n");
  if (lookahead == 'a') {
    match('a');
  }
  else if (lookahead == 'd')
    match('d');
  else
    error();
}  

void Z() {
  printf("Z\n");
  if (lookahead == 'e') {
    match('e');
    Z();
  }
  else if (lookahead == 'f')
    match('f');
  else
    error();
}  

void parse() {
  printf("parse\n");
  lookahead = scan();
  S();
}

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 8 augusti 2005