PJP - Cvičení 9

Překlad aritmetického výrazu do jazyka zásobníkového procesoru (počítače)

Zásobníkový počítač je zjednodušený a zidealizovaný počítač, který je vybaven pamětí typu RWM, zasobníkově orientovaným procesorem a (potenciálně) nekonečným zásobníkem (explicitně mimo paměť). Procesor neobsahuje registry tak jak je známe z "obvyklých" procesorů, místo toho všechny aritmetické operace provádí pouze na zásobníku.

Pro naše potřeby si definujeme následující instrukční sadu zásobníkového počítače. Předpokládejme, že procesor umí pracovat s celými čísly, desetinnými čísly a adresami. Dále pro jednoduchost předpokládáme, že všechny výše zmíněné datové typy mají stejnou velikost v bajtech a zabírají právě 1 položku v zásobníku.

               ; zásobnik, vrchol vlevo
               ; empty
 LITF   1.5    ; 1.5 
 LIT     15    ; 15 | 1.5 
 FLT           ; 15.0 | 1.5
 BOPF     -    ; -13.5
 TA       x    ; x | -13.5
 STF           ; empty
               ; na adresu x ulozeno -13.5

Pro zásobníkový procesor se snadno generuje program, proto jej použijeme pro naše příklady. Instrukce zásobníkového procesoru lze homomorfním překladem nahradit instrukcemi procesoru "obyčejného", vygenerovaný kód bude správný, i když neefektivní. Nevyužijeme totiž optimalizace v registrech. Následující příklad ukazuje, jak se některé instrukce zásobníkového procesoru dají přepsat instrukcemi x86:

Příklad: realizujte program, který vypočte k zadanému aritmetickému výrazu kód pro jeho vyhodnocení v jazyce výše popsaného zásobníkového procesoru. Předpokládejte, že výraz obsahuje operátory +, -, *, /, (, ), čísla (konstanty) a proměnné (identifikátory). Konstanty a proměnné mohou být jak celočíselné, tak i "reálné". Vygenerovaný kód musí umět zajistit správné konverze datových typů pokud se maji sčítat (odčítat,...) operandy různých typů, tj. výsledkem binárního operátoru je datový typ celé číslo pokud jsou oba operandy typu celé číslo, jinak je výsledkem datový typ float.

Předpokládáme, že existuje lexikální analyzátor, který má obvyklé rozhraní, tj. globálni proměnnou Token, funkci NextToken() a globální proměnné Lex_AInt, Lex_AFloat a Lex_AStr, ve kterých jsou předávány atributy právě čteného lexikálního elementu. Lexikální elementy shrnuje následující seznam:

 LEX_INT         cele cislo (Lex_AInt)
 LEX_FLOAT       desetinne cislo (Lex_AFloat)
 LEX_IDENT       identifikator (Lex_AStr)
 
 LEX_ADD         +
 LEX_SUB         -
 LEX_MUL         *
 LEX_DIV         /
 
 LEX_LPA         zavorky
 LEX_RPA
 
 LEX_NULL        konec souboru

Při překladu pro zásobníkový procesor generujeme kód podobný postfixovemu zápisu aritmetického výrazu, tedy stejně jako v příkladu z hodiny 6. Jediný rozdíl je v tom, že musíme rozlišovat datové typy. Pro každý podvýraz musíme být schopni určit, jakého datového typu je, abychom potom byli schopni určit zda potřebujeme celočíselný nebo "reálny" operand. Tuto informaci si budeme předávat ve formě ---- správně, atributu. Pro unární operátory tím problém nevzniká, u k-arních operátorů obecně ano. Např. pro binárni operátory mohou nastat celkem čtyři kombinace datových typů, které jsou znázorněny v následující tabulce. Tabulka dále uvádí, jaké datové konverze se provedou, máme-li za dané situace provést binární operaci BINOP op.

Vyjdeme z nám dobře známé levě asociativní LL gramatiky z minulých příkladů, přidáme výstupy podobně jako v příkladu z hodiny 6 a zajistíme informování o typu mezivýsledku pomocí atributů. Pozor, atributy zde již neznamenají hodnotu výsledku, ale pouze jeho datový typ ! (Vlastní hodnota mezivýsledku existuje až při běhu generovaného programu a je uložena na vrcholu zásobníku.) Pro zdůraznění tohoto rozdílu jsem atributy přejmenoval na styp (syntetizovany typ) a optyp (typ operandu). Předpokládejme, že typ celé číslo je reprezentován hodnotou 0 a typ reálné číslo hodnotou 1.

Poznámka: 'UNOP op' znamená instrukci UOP op nebo UOPF op podle typu operandu. Analogicky 'BINOP op' znamená "makro", které se rozvine podle typu operandu na jednu ze 4 variant podle tabulky uvedené výse.

#include "lexan.h" /* LEX_xxxx, Token, NextToken (), Lex_AFloat, Lex_AStr */

static int E  ( void ); 
static int EC ( int op ); 
static int T  ( void ); 
static int TC ( int op );
static int F  ( void ); 

void Error ( void )
 {
   /* nejake zpracovani chyby (nastaveni glob. promenne .... ) */
 }
/*-----------------------------------*/ 
static void Convert ( int Left, int Right )  
 {
   // vygeneruje kod pro datove konverze potrebne pro binarni operatory 
   
   switch ( Left | ( Right << 1 ) )
    {
      case 0: // oba int
       break;
      case 1: // Left int, right float
       printf ( "TA Tmp\n" );
       printf ( "STF\n" );
       printf ( "FLT\n" );
       printf ( "TA Tmp\n" );
       printf ( "DRF\n" );
       break;
      case 2: // left float, right int
       printf ( "FLT\n" );
       break;
      case 3: // oba float
       break;
    }
 }
/*-----------------------------------*/ 
static int E  ( void )
 {
   int Type;
   if ( Token == LEX_SUB )
    {          /* E -> - T E' */
      Token = NextToken ();
      Type  = T ();
      if ( Type )
        printf ( "UOPF -\n" )
       else
        printf ( "UOP  -\n" ) 
      return ( EC ( Type ) ); 
    } else
     {
       return ( EC (T  ()) );  /* E -> T E' */
     }  
 }
/*-----------------------------------*/ 
static int EC ( int lop )
 {
   int rop, styp;       // typy operandu
   
   switch ( Token ) 
    {
      /* HINT: pozor, zde se jiz musi rozlisit + a - */
      case LEX_ADD:          /* E' -> +TE' */
       Token = NextToken (); 
       rop   = T ();
       Convert ( lop, rop );
       styp  = lop | rop;          /* typ vysledku */
       if ( styp ) 
         printf ( "BOPF +\n" );
        else
         printf ( "BOP  +\n" );
       return ( EC ( styp ) );
      case LEX_SUB:          /* E' -> -TE' */
       Token = NextToken (); 
       rop = T ();
       Convert ( lop, rop );
       styp  = lop | rop;          /* typ vysledku */
       if ( styp )          
         printf ( "BOPF -\n" );
        else
         printf ( "BOP  -\n" );
       return ( EC ( styp ) );
      default:               /* epsilon pravidlo i pro ostatni dopredu */
       return ( lop );       /* prohlizene retezce - optimalizace */
    }
 }
/*-----------------------------------*/   
static int T ( void )
 {
   return ( TC ( F  ()) );
 }
/*-----------------------------------*/ 
static int TC ( int lop )
 {
   int rop, styp; // operand types
   
   switch ( Token )
    {
      case LEX_MUL:  
       Token = NextToken (); 
       rop   = F ();
       Convert ( lop, rop );
       styp  = lop | rop;          /* typ vysledku */
       if ( styp ) 
         printf ( "BOPF *\n" );
        else
         printf ( "BOP  *\n" );
       return ( TC ( styp ) );
      case LEX_DIV:       
       Token = NextToken (); 
       rop   = F ();
       Convert ( lop, rop );
       styp  = lop | rop;          /* typ vysledku */
       if ( styp ) 
         printf ( "BOPF /\n" );
        else
         printf ( "BOP  /\n" );
       return ( TC ( styp ) );
      default:
       return ( lop );
    }
 }
/*-----------------------------------*/   
static int F ( void )
 {
   int Ret;
   
   switch ( Token )
    {
      case LEX_INT:
       printf ( "LIT %d\n", Lex_AInt ); 
        /* 
          HINT: precist hodnotu atributu z globalni 
           promenne musime jeste pred srovnanim, volani 
           NextToken () totiz globalni promennou Lex_AFloat
           muze prepsat !
         */   
       Token = NextToken (); 
       return ( 0 );   // integer
       
      case LEX_FLOAT:
       printf ( "LITF %f\n", Lex_AFloat ); 
       Token = NextToken (); 
       return ( 1 );   // float
       
      case LEX_LPA:
       Token = NextToken (); 
       Ret = E ();
       if ( Token != LEX_RPA )  Error (); 
       Token = NextToken ();
       return ( Ret );
      case LEX_IDENT:
       switch ( SymbolTableGetType ( Lex_AStr ) )   // typ symbolu !!
        {
          case SYM_CONST:
           // rozhodnout DATOVY typ konstanty
           
           // nacist jeji hodnotu, 
           
           // vystup = LIT / LITF
           break;
          case SYM_VARIABLE:
           Adr = SymbolTableVariableAddr ( Lex_AStr ); // adresa v pameti ...
           printf ( "TA %d\n", Adr );
           Res = SymbolTableVariableType ( Lex_AStr ); // datovy typ promenne
           if ( Res ) 
             printf ( "DRF\n" ); // float 
            else
             printf ( "DR\n" ); // integer
           
           Token = NextToken (); // srovnani !
           return ( Res );   
          case SYM_FUNCTION:
           ....
           break; 
          default:
           Error (); // label, dat. typ, .... 
        }
       Token = NextToken (); 
       return ( Ret );
      default:    /* HINT: zde se jiz optimalizace neuplatni !!! */
       Error ();  /* protoze existuje vice pravidel pro F a nelze F -> e */
       break;
    }
 }
/*-----------------------------------*/ 
/* HINT: zde zacina vlastni analyza  */
/*-----------------------------------*/
int Translate ( char * String )
 {
   int Result;
    /* zde nastavit indikaci chyby na 0 ... */
   LexanInit ( String );
    /* inicializace lexanu, ... */
   Token = NextToken (); 
    /* HINT: musime inicializovat dopredu prohlizeny symbol */
   Result = E ();
    /* vlastni analyza */
   if ( Token != LEX_NULL ) Error (); 
    /* HINT: kontrola, ze jsme precetli cely vstup */

   if ( /* nedoslo k chybe */ )
     return ( Result ); /* uspech */
    
   /* doslo k chybe */
   delete Result;
   return ( NULL );
 } 

import java . io . Reader;
import java . io . FileReader;
import java . io . IOException;


class ParserException extends Exception
 {
   public ParserException ( String message ) { super ( message ); }
 };



class Translator
 {
   protected CLexan      lex;
   protected int         token;
   
   protected static final int TYPE_INT   = 0;
   protected static final int TYPE_FLOAT = 1;
   
   
   
   //-------------------------------------------------------------------------------------------------
   protected static int    formatConversion2 ( int typeL, int typeR ) throws DebugException
    {
      switch ( typeL| ( typeR << 8 ) )
       {
         case TYPE_INT | ( TYPE_INT << 8 ): // oba int
          return ( TYPE_INT ); // int result
          
         case TYPE_INT | ( TYPE_FLOAT << 8 ): // Left int, right float
          System . out . println ( "TA Tmp" );
          System . out . println ( "STF" );
          System . out . println ( "FLT" );
          System . out . println ( "TA Tmp" );
          System . out . println ( "DRF" );
          return ( TYPE_FLOAT ); // float result

         case TYPE_FLOAT | ( TYPE_INT << 8 ): // left float, right int
          System . out . println ( "FLT" );
          return ( TYPE_FLOAT ); // float result
          
         case TYPE_FLOAT | ( TYPE_FLOAT << 8 ): // oba float
          return ( TYPE_FLOAT ); // float result
         
         default: 
          throw new DebugException ( "Unknown datatype combination" );
       }
    }
   //-------------------------------------------------------------------------------------------------
   protected static void outputMacro ( int type, String instruction )
    {
      switch ( type )
       {
         case TYPE_INT: 
          System . out . println ( instruction );
          break;
         case TYPE_FLOAT: 
          System . out . println ( instruction + "F" );
          break;
       }
    } 
   //-------------------------------------------------------------------------------------------------
   protected static void outputMacro ( int type, String instruction, String op )
    {
      switch ( type )
       {
         case TYPE_INT: 
          System . out . println ( instruction + " " + op );
          break;
         case TYPE_FLOAT: 
          System . out . println ( instruction + "F" + " " + op );
          break;
       }
    } 
   //-------------------------------------------------------------------------------------------------
   public                Translator ( Reader in ) throws IOException, DebugException
    {
      lex = new CLexan ( in );
      token = lex . nextToken ();
    }
   //-------------------------------------------------------------------------------------------------
   protected int         nontermE  ( ) throws ParserException, IOException, DebugException
    {
      int type;
      if ( token == CLexan . LEX_SUB )
        {
          token = lex . nextToken ();
          type = nontermT  ();  /* E -> -T E' */
          outputMacro      ( type, "UOP", "-" );
          return nontermEC ( type );
        }
       else
        {
          /* E -> T E' */
          return nontermEC ( nontermT  () );
        } 
    } 
   //-------------------------------------------------------------------------------------------------
   protected int         nontermEC ( int op ) throws ParserException, IOException, DebugException
    {     
      int type, outtype;
      
      switch ( token )
       {
         case CLexan . LEX_ADD:          /* E' -> +TE' */
          token =  lex . nextToken (); /* HINT: takto vypada srovnani */
          type  = nontermT  ();                /* HINT: takto vypada expanze */ 
          outtype           = formatConversion2 ( op, type );
          outputMacro       ( outtype, "BOP", "+" );
          return nontermEC  ( outtype );
          

         case CLexan . LEX_SUB:          /* E' -> -TE' */
          token =  lex . nextToken (); /* HINT: takto vypada srovnani */
          type  = nontermT  ();                /* HINT: takto vypada expanze */
          outtype           =formatConversion2 ( op, type );
          outputMacro       ( outtype, "BOP", "-" );
          return nontermEC  ( outtype );

         default: /* epsilon pravidlo i pro ostatni dopredu prohlizene retezce */
          return op;
       }
    }
   //-------------------------------------------------------------------------------------------------
   protected int         nontermT ( ) throws ParserException, IOException, DebugException
    {
      return nontermTC ( nontermF  () );
    }
   //-------------------------------------------------------------------------------------------------
   protected int         nontermTC ( int op ) throws ParserException, IOException, DebugException
    {
      int type, outtype;
      
      switch ( token )
       {
         case CLexan . LEX_MUL:
          token = lex . nextToken ();
          type  = nontermF  ();
          outtype           = formatConversion2 ( op, type );
          outputMacro       ( outtype, "BOP", "*" );
          return nontermTC  ( outtype );

         case CLexan . LEX_DIV:       
          token = lex . nextToken ();
          type  = nontermF  ();
          outtype           = formatConversion2 ( op, type );
          outputMacro       ( outtype, "BOP", "/" );
          return nontermTC  ( outtype );
         default:
          return ( op );
       }
    }
   //-------------------------------------------------------------------------------------------------
   protected int         nontermF ( ) throws ParserException, IOException, DebugException
    {            
      int type;

      switch ( token )
       {
         case CLexan . LEX_INT:
          System . out . println ( "LIT "+ lex . getInt () );
          token = lex . nextToken (); /* HINT: pouze srovnani, F -> a */
          return ( TYPE_INT );

         case CLexan . LEX_FLOAT:
          System . out . println ( "LITF "+ lex . getFloat () );
          token = lex . nextToken (); /* HINT: pouze srovnani, F -> a */
          return ( TYPE_FLOAT );
          
         case CLexan . LEX_IDENT:   
          System . out . println ( "TA "+ lex . getStr () ); // symbolicka adresa 
          // v realne situaci by bylo: type = tabsym . queryVarType ( lex . getStr () ); // zjisteni typu podle tab. symbolu
          // zde neresime tabulku symbolu, pouzijeme tedy "typ":
          type = Math . random () > 0.5 ? TYPE_FLOAT : TYPE_INT;
          outputMacro ( type, "DR" );
          token = lex . nextToken (); 
          return ( type );
          
         case CLexan . LEX_LPA:
          token = lex . nextToken (); /* F -> ( E ) */
          type = nontermE ();
          if ( token != CLexan . LEX_RPA ) throw new ParserException ( "Expecting ')'" );
          token = lex . nextToken ();
          return ( type );
          
         default:
          throw new ParserException ( "Expecting one of '(', <int>" );
       }
    }
   //-------------------------------------------------------------------------------------------------
   public boolean translate ( )
    {
      try 
       {
         nontermE (); /* vlastni preklad */
    
         if ( token != lex . LEX_NULL ) throw new ParserException ( "Extra characters at the EOF" );
          /* HINT: kontrola, ze jsme precetli cely vstup */
         System . out . print ( "\nOK\n" ); 
         return ( true ); // accept 
       }
      catch ( Exception e ) 
       {
         e . printStackTrace ();
         return ( false );
       } 
       
    }
   //-------------------------------------------------------------------------------------------------
   public static void main ( String argv[] )
    {    
      Translator X;
      
      if ( argv . length != 1 )
       {
         System . out . println ( "Usage: java Translator <input_file>" );
         return;
       }
      
      try 
       {
         X = new Translator ( new FileReader ( argv[0] ) );
       }  
      catch ( Exception e ) 
       {  
         System . out . println ( "File open/read error" );
         return;
       }
      X . translate ();
    }

 };

Kontakt: xvagner (at) fel (dot) cvut (dot) cz (C) 2000, L.Vagner