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.

{{cite journal |last1=Mann |first1=Paul B |date=2006 |title=A Translational BNF Grammar Notation (TBNF) |journal=SIGPLAN Notices |number=4 |volume=41 |pages=16–23 |doi=10.1145/1147214.1147218 }}

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() ;

=> lookup(); // Lookup & store in symbol table.

;

/* Operator precedence. */

{ '==' '!=' } << // Lowest priority.

{ '+' '-' } <<

{ '*' '/' } << // Highest priority.

/* Productions. */

Goal -> Program... *> goal_ (0,,"\t\tSTART\n" ,,"\t\tEOF\n\n")

Program -> 'program' '{' 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 -> *> 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 -> *> intr_ (1,,,,"\t\tLOAD %s\n")

-> *> 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:

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

}

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

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

Category:Compiling tools

Category:Parser generators

Category:Compiler construction