Трансляционная форма Бэкуса – Наура - Translational Backus–Naur form

Трансляционная форма Бэкуса – Наура ( TBNF или Translational BNF ) относится к форме Бэкуса – Наура , которая представляет собой формальную грамматическую нотацию, используемую для определения синтаксиса компьютерных языков, таких как Algol , Ada , C ++ , COBOL , Fortran , Java , Perl , Python. , и многие другие. TBNF выходит за рамки BNF и расширенной грамматической нотации BNF (EBNF), потому что он не только определяет синтаксис языка, но также определяет структуру абстрактного синтаксического дерева (AST), которое должно быть создано в памяти, и выходной промежуточный код, который должен быть сгенерирован. Таким образом, TBNF определяет полный процесс трансляции от исходного исходного кода до промежуточного кода. Указание выходного промежуточного кода не является обязательным, и в этом случае вы все равно получите автоматическое создание AST и сможете определять его структуру в грамматике.

Обзор

Концепция TBNF была впервые опубликована в апреле 2006 года в документе SIGPLAN Notices, специальной группы ACM .

Вот пример грамматики, указанной в TBNF: 

/* TBNF Grammar for a simple language.  
   Five node arguments are used in this grammar to avoid having to create node actions.
*/
/* Input Tokens. */

   <error>        => error() ;  
   <identifier>   => lookup();  // Lookup & store in symbol table.
   <integer>      => lookup();  // Lookup & store in symbol table. 
   <eof>          ;

/* Operator precedence. */

   { '==' '!=' }  <<    // Lowest priority.    
   { '+'  '-'  }  <<         
   { '*'  '/'  }  <<    // Highest priority.

/* Productions. */

   Goal     -> Program... <eof>                       *> goal_    (0,,"\t\tSTART\n"     ,,"\t\tEOF\n\n")          
             
   Program  -> 'program' <identifier> '{' Stmt... '}' *> program_ (2,,"\t\tPROGRAM %s\n",,"\t\tEND PROGRAM %s\n")
            
   Stmt     -> Assignment
            -> IfThen
            -> IfElse
            -> IfThenElse
      
   Assignment ~> Target '=' Exp ';'                *> assign_  (0,,         ,,"\t\tSTORE\n")         
   IfThen     -> 'if' RelExp Then 'endif'          *> if_      (0,,"if&0:\n",,"endif&0:\n" )
   IfElse     -> 'if' RelExp Else 'endif'          *> if_      (0,,"if&0:\n",,"endif&0:\n" )
   IfThenElse -> 'if' RelExp Then2 Else2 'endif'   *> if_      (0,,"if&0:\n",,"endif&0:\n" )
              
   Target   -> <identifier>                        *> ident_   (1,,,,"\t\tLADR %s\n")
             
   RelExp   -> Exp '==' Exp                        *> eq_      (0,,,,"\t\tEQ\n" ) 
            -> Exp '!=' Exp                        *> ne_      (0,,,,"\t\tNE\n" ) 
                                                        
   Exp      -> Primary          
            -> Exp '+' Exp                         *> add_     (0,,,,"\t\tADD\n") 
            -> Exp '-' Exp                         *> sub_     (0,,,,"\t\tSUB\n") 
            -> Exp '*' Exp                         *> mul_     (0,,,,"\t\tMUL\n") 
            -> Exp '/' Exp                         *> div_     (0,,,,"\t\tDIV\n") 
             
   Primary  -> <integer>                           *> intr_    (1,,,,"\t\tLOAD %s\n")
            -> <identifier>                        *> ident_   (1,,,,"\t\tLOAD %s\n")
            -> '(' Exp ')'  
             
   Then     -> 'then' Stmt...                      *> then_    (0,,"\t\tBR NZ endif&1\nthen&1:\n",,)
   Else     -> 'else' Stmt...                      *> else_    (0,,"\t\tBR Z endif&1\nelse&1:\n" ,,)
   Then2    -> 'then' Stmt...                      *> then2_   (0,,"\t\tBR NZ else&1\nthen&1:\n" ,,)
   Else2    -> 'else' Stmt...                      *> else2_   (0,,"\t\tBR endif&1\nelse&1:\n"   ,,)

/* End of Grammar. */

Учитывая этот ввод: 

program test
{
      if a == 0 
      then 
         if x == 0 
         then b = 10;     
         else b = 20;     
         endif
      else 
         if x == 1 
         then b = 30;     
         else b = 40;     
         endif
      endif
}

Запуск переводчика, созданного на основе приведенной выше грамматики, даст следующий результат: 

      START
      PROGRAM test
if1:
      LOAD a
      LOAD 0
      EQ
      BR NZ else1
then1:
if2:
      LOAD x
      LOAD 0
      EQ
      BR NZ else2
then2:
      LOAD 10
      LADR b
      STORE
      BR endif2
else2:
      LOAD 20
      LADR b
      STORE
endif2:
      BR endif1
else1:
if3:
      LOAD x
      LOAD 1
      EQ
      BR NZ else3
then3:
      LOAD 30
      LADR b
      STORE
      BR endif3
else3:
      LOAD 40
      LADR b
      STORE
endif3:
endif1:
      END PROGRAM test
      EOF

Ссылки