Příklady pro cvičení z předmětu "Úvod do překladačů"

Atributové a překladové gramatiky

1. Následující gramatiky popisují binární číslo. Doplňte sémantická pravidla tak, aby startovací nonterminál S měl syntetizovaný atribut S.val typu integer reprezentující hodnotu tohoto čísla
    
   
   1. S -> B S | B
      B -> 0 | 1
       
      
   2. S -> S B | B
      B -> 0 | 1
       
2. Následující gramatika popisuje binární číslo s případnou zlomkovou částí. Doplňte sémantická pravidla tak, aby startovací nonterminál S měl syntetizovaný atribut S.val typu real reprezentující hodnotu tohoto čísla.

   S -> D . D | D
   D -> D B | B
   B -> 0 | 1

3. K následující gramatice, popisující deklarace proměnných, doplňte sémantická pravidla tak, aby syntetizovaným atributem startovacího nonterminálu S byl seznam trojic (jméno,typ,adresa) reprezentujících jméno proměnné, její typ a relativní adresu. Předpokládejte, že hodnoty typu int se ukládají v délce 4 a hodnoty typu double v délce 8 a že terminální symbol id má atribut id.name obsahující jméno.

   S -> S D | D
   D -> T L ;
   T -> int | double
   L -> id L'
   L' -> , id L' | e

4. Jednoduchý jazyk smíšených aritmetických výrazů s operací sčítání a celými a reálnými čísly jako operandy je popsán následující gramatikou:

   E -> E + T | T
   T -> inum | rnum

   1. Doplňte do gramatiky sémantické akce tak, aby startovací nonterminál S měl syntetizovaný atribut S.type s hodnotou Int nebo Real reprezentující typ výrazu. Předpokládejte, že součet hodnot typu Int a Real je typu Real.
       

   2. Předpokládejte existenci následujících instrukcí:

      • ipush val - uložení hodnoty val typu Int na vrchol zásobníku
      • rpush val - uložení hodnoty val typu Real na vrchol zásobníku
      • iadd - součet dvou hodnot typu Int na vrcholu zásobníku
      • radd - součet dvou hodnot typu Real na vrcholu zásobníku
      • itor - převod hodnoty typu Int z vrcholu zásobníku na typ Real
      a operace gen(instrukce[, operand]) pro generování jedné instrukce. Doplňte do gramatiky sémantická pravidla tak, aby se generoval kód pro výpočet hodnoty výrazu s vhodně provedenými převody typu operandů ve smíšených podvýrazech. Předpokládejte, že terminální symboly inum a rnum mají atribut val obsahující hodnotu operandu typu Int nebo Real.

      Příklad: Pro vstupní řetězec 1+2.5+7 se vygeneruje tato posloupnost instrukcí:
      ipush 1; itor; rpush 2.5; radd; ipush 7; itor; radd
       

5. Předpokládejme, že generujeme kód pro zásobníkový počítač s těmito instrukcemi:
   • jmp n - nepodmíněný skok na návěští s číslem n
   • fjp n - skok na návěští s číslem n, pokud je na vrcholu zásobníku hodnota false (hodnota se z vrcholu zásobníku odstraní)
   • lbl n - definice návěští s číslem n
   Rozšiřte následující gramatiku na atributovou překladovou gramatiku doplněním výstupních symbolů, reprezentujících jednotlivé instrukce, a příslušných sémantických pravidel tak, aby překladem vznikla posloupnost instrukcí cílového programu. Předpokládejte, že překladem nonterminálu E je kód ponechávající hodnotu booleovského výrazu na vrcholu zásobníku.

   S	->	if E then S
   	|	if E then S else S
   	|	while E do S
   	|	repeat S until E
   	|	S ; S
   	|	...

   Pro přidělování čísel návěští použijte následující metody:
   1. předávejte číslo prvního volného návěští pomocí atributů,
   2. použijte globální funkci getlbl(), která při každém zavolání vrátí nové, ještě nepoužité číslo návěští.
       
6. V předchozím příkladu rozšiřte gramatiku o další dvě pravidla:

   S	->	break
   	|	continue

   a modifikujte odpovídajícím způsobem sémantické akce.
    
7. Rozšiřte následující gramatiku na atributovou překladovou gramatiku pro překlad booleovských výrazů. Předpokládejte existenci instrukce load name, která uloží na vrchol zásobníku obsah booleovské proměnné se jménem name - toto jméno se získá jako hodnota atributu id.name symbolu id.

   B	->	B and B
   	|	B or B
   	|	not B
   	|	id

   1. Generujte kód pro úplné vyhodnocení s použitím instrukcí zásobníkového kódu band, bor a bnot
   
   Příklad: Pro vstupní řetězec "a and b or not c" se vygeneruje kód
   load a; load b; band; load c; bnot; bor
    
   2. Generujte kód pro zkrácené vyhodnocení s použitím skokových instrukcí z předcházejících příkladů.
      Příklad: Pro tentýž řetězec se může vygenerovat kód (Ltrue a Lfalse představují čísla návěští, kam se skočí, je-li hodnota výrazu true, resp. false)
      load a; fjp 1; load b; fjp 1; jmp Ltrue; lbl 1; load c; fjp Ltrue; jmp Lfalse