From Surf Wiki (app.surf) — the open knowledge base

Translational Backus–Naur form

Translational Backus–Naur Form (TBNF or Translational BNF) refers to Backus–Naur form, which is a formal grammar notation used to define the syntax of computer languages, such as Algol, Ada, C++, COBOL, Fortran, Java, Perl, Python, and many others. TBNF goes beyond BNF and extended BNF (EBNF) grammar notation because it not only defines the syntax of a language, but also defines the structure of the abstract syntax tree (AST) to be created in memory and the output intermediate code to be generated. Thus TBNF defines the complete translation process from input source code to intermediate code. Specification of the output intermediate code is optional, in which case you will still get automatic AST creation and have the ability to define its structure in the grammar.

Overview

The TBNF concept was first published in April 2006 in a paper at SIGPLAN Notices, a special interest group of the ACM.

Here is a sample grammar specified in 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. */

Given this input:

TEXT

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
}

Running the translator generated from the above grammar would produce this output:

ASM

      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

References

(2006). "A Translational BNF Grammar Notation (TBNF)". SIGPLAN Notices.

Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

compiling-tools parser-generators compiler-construction

Want to explore this topic further?

Ask Mako anything about Translational Backus–Naur form — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report