Java BNF

From

Revision as of 23:15, 4 January 2011 by 199.99.248.147 (Talk)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Java Syntax Specification

BNF and Extended BNF

(Adopted from Th. Estier, CUI - University of Geneva, http://www.cui.unige.ch/db-research/Enseignement/analyseinfo/AboutBNF.html)

BNF is an acronym for "Backus Naur Form". John Backus and Peter Naur introduced for the first time a formal notation to describe the syntax of a given language (This was for the description of the ALGOL 60 programming language, see [Naur 60]). To be precise, most of BNF was introduced by Backus in a report presented at an earlier UNESCO conference on ALGOL 58. Few read the report, but when Peter Naur read it he was surprised at some of the differences he found between his and Backus's interpretation of ALGOL 58. He decided that for the successor to ALGOL, all participants of the first design had come to recognize some weaknesses, should be given in a similar form so that all participants should be aware of what they were agreeing to. He made a few modificiations that are almost universally used and drew up on his own the BNF for ALGOL 60 at the meeting where it was designed. Depending on how you attribute presenting it to the world, it was either by Backus in 59 or Naur in 60. (For more details on this period of programming languages history, see the introduction to Backus's Turing award article in Communications of the ACM, Vol. 21, No. 8, august 1978. This note was suggested by William B. Clodius from Los Alamos Natl. Lab). Since then, almost every author of books on new programming languages used it to specify the syntax rules of the language. See [Jensen 74] and [Wirth 82] for examples.

The following is taken from [Marcotty 86]:

The meta-symbols of BNF are:

 ::= meaning "is defined as"
 | meaning "or"
 < > angle brackets used to surround category names.

The angle brackets distinguish syntax rules names (also called non-terminal symbols) from terminal symbols which are written exactly as they are to be represented. A BNF rule defining a nonterminal has the form:

   nonterminal ::= sequence_of_alternatives consisting of strings of terminals or nonterminals separated by the meta-symbol |

For example, the BNF production for a mini-language is:

   <program> ::=  program
                      <declaration_sequence>
                  begin
                      <statements_sequence>
                  end ;

This shows that a mini-language program consists of the keyword "program" followed by the declaration sequence, then the keyword "begin" and the statements sequence, finally the keyword "end" and a semicolon. (end of quotation)

In fact, many authors have introduced some slight extensions of BNF for the ease of use: optional items are enclosed in meta symbols [ and ], example:

   <if_statement> ::=  if <boolean_expression> then
                            <statement_sequence>
                       [ else
                            <statement_sequence> ]
                       end if ;

repetitive items (zero or more times) are enclosed in meta symbols { and }, example:

   <identifier> ::= <letter> { <letter> | <digit> }

this rule is equivalent to the recursive rule:

   <identifier> ::= <letter> |  <identifier> [ <letter> | <digit> ]

terminals of only one character are surrounded by quotes (") to distinguish them from meta-symbols, example:

   <statement_sequence> ::= <statement> { ";" <statement> }

in recent text books, terminal and non-terminal symbols are distingued by using bold faces for terminals and suppressing < and > around non-terminals. This improves greatly the readability. The example then becomes:

   if_statement ::= if boolean_expression then
                        statement_sequence
                    [ else
                        statement_sequence ]
                    endif ";"

Now as a last example (maybe not the easiest to read !), here is the definition of BNF expressed in BNF:

   syntax     ::=  { rule }
   rule       ::=  identifier  "::="  expression
   expression ::=  term { "|" term }
   term       ::=  factor { factor }
   factor     ::=  identifier |
                   quoted_symbol |
                   "("  expression  ")" |
                   "["  expression  "]" |
                   "{"  expression  "}"
   identifier ::=  letter { letter | digit }
   quoted_symbol ::= """ { any_character } """

BNF is not ony important to describe syntax rules in books, but it is very commonly used (with variants) by syntactic tools. See for example any book on LEX and YACC, the standard UNIX parser generators. If you have access to any Unix machine, you will probably find a chapter of the documentation on these tools.

Some references:

[Naur 60] NAUR, Peter (ed.), "Revised Report on the Algorithmic Language ALGOL 60.", Communications of the ACM, Vol. 3 No.5, pp. 299-314, May 1960.
[Jensen 74] JENSEN, Kathleen, WIRTH, Niklaus, "PASCAL user manual and report", Lecture notes in computer science ; vol. 18., Berlin [etc.] : Springer, 1974., 1974.
[Johnson 75] S.C. Johnson, "Yacc: Yet Another Compiler Compiler", Computer Science Technical Report #32, Bell Laboratories, Murray Hill, NJ, 1975.
[Wirth 82] WIRTH, Niklaus., Programming in Modula-2, Berlin, Heidelberg: Springer, 1982.
[Marcotty 86] M. Marcotty & H. Ledgard, The World of Programming Languages, Springer-Verlag, Berlin 1986., pages 41 and following.
Th. Estier, CUI - University of Geneva

An Extended BNF for Java

Adopted from "http://www.daimi.au.dk/dRegAut/JavaBNF.html"

Java Programs

<compilation unit> ::= <package declaration>? <import declarations>? <type declarations>?

Java Declarations

<package declaration> ::= package <package name> ;

<single type import declaration> ::= import <type name> ;

<type import on demand declaration> ::= import <package name> . * ;

<type declaration> ::= <class declaration> | <interface declaration> | ;

<class declaration> ::= <class modifiers>? class <identifier> <super>? <interfaces>? <class body>

<class modifier> ::= public | abstract | final

<super> ::= extends <class type>

<interfaces> ::= implements <interface type list>

<class body> ::= { <class body declarations>? }

<static initializer> ::= static <block>

<constructor modifier> ::= public | protected | private

<constructor declarator> ::= <simple type name> ( <formal parameter list>? )

<throws> ::= throws <class type list>

<constructor body> ::= { <explicit constructor invocation>? <block statements>? }

<explicit constructor invocation>::= this ( <argument list>? ) | super ( <argument list>? )

<field declaration> ::= <field modifiers>? <type> <variable declarators> ;

<variable declarator id> ::= <identifier> | <variable declarator id> [ ]

<method header> ::= <method modifiers>? <result type> <method declarator> <throws>?

<result type> ::= <type> | void

<method declarator> ::= <identifier> ( <formal parameter list>? )

<method body> ::= <block> | ;

<interface declaration> ::= <interface modifiers>? interface <identifier> <extends interfaces>? <interface body>

<interface modifier> ::= public | abstract

<extends interfaces> ::= extends <interface type> | <extends interfaces> , <interface type>

<interface body> ::= { <interface member declarations>? }

<constant modifiers> ::= public | static | final

<abstract method declaration>::= <abstract method modifiers>? <result type> <method declarator> <throws>? ;

<abstract method modifier> ::= public | abstract

<array initializer> ::= { <variable initializers>? , ? }

Java Types

<primitive type> ::= <numeric type> | boolean

<integral type> ::= byte | short | int | long | char

<floating-point type> ::= float | double

<array type> ::= <type> [ ]

Blocks and Commands

<block> ::= { <block statements>? }

<local variable declaration statement> ::= <local variable declaration> ;

<empty statement> ::= ;

<expression statement> ::= <statement expression> ;

<switch statement> ::= switch ( <expression> ) <switch block>

<switch block> ::= { <switch block statement groups>? <switch labels>? }

<switch label> ::= case <constant expression> : | default :

<while statement> ::= while ( <expression> ) <statement>

<while statement no short if> ::= while ( <expression> ) <statement no short if>

<do statement> ::= do <statement> while ( <expression> ) ;

<break statement> ::= break <identifier>? ;

<continue statement> ::= continue <identifier>? ;

<return statement> ::= return <expression>? ;

<throws statement> ::= throw <expression> ;

<synchronized statement> ::= synchronized ( <expression> ) <block>

<catch clause> ::= catch ( <formal parameter> ) <block>

<finally > ::= finally <block>

Expressions

<assignment operator> ::= = | *= | /= | %= | += | -= | <<= | >>= | >>>= | &= | ^= | |=

<relational expression> ::= <shift expression> | <relational expression> < <shift expression> | <relational expression> > <shift expression> | <relational expression> <= <shift expression> | <relational expression> >= <shift expression> | <relational expression> instanceof <reference type>

<postdecrement expression> ::= <postfix expression> --

<postincrement expression> ::= <postfix expression> ++

<method invocation> ::= <method name> ( <argument list>? ) | <primary> . <identifier> ( <argument list>? ) | super . <identifier> ( <argument list>? )

<field access> ::= <primary> . <identifier> | super . <identifier>

<class instance creation expression> ::= new <class type> ( <argument list>? )

<array creation expression> ::= new <primitive type> <dim exprs> <dims>? | new <class or interface type> <dim exprs> <dims>?

<dim expr> ::= [ <expression> ]

<dims> ::= [ ] | <dims> [ ]

<array access> ::= <expression name> [ <expression> ] | <primary no new array> [ <expression>]

Tokens

<decimal integer literal> ::= <decimal numeral> <integer type suffix>?

<hex integer literal> ::= <hex numeral> <integer type suffix>?

<octal integer literal> ::= <octal numeral> <integer type suffix>?

<integer type suffix> ::= l | L

<decimal numeral> ::= 0 | <non zero digit> <digits>?

<non zero digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<hex digit> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | A | B | C | D | E | F

<octal digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

<floating-point literal> ::= <digits> . <digits>? <exponent part>? <float type suffix>?

<digits> <exponent part>? <float type suffix>?

<exponent indicator> ::= e | E

<sign> ::= + | -

<float type suffix> ::= f | F | d | D

<boolean literal> ::= true | false

<character literal> ::= ' <single character> ' | ' <escape sequence> '

<single character> ::= <input character> except ' and \

<string literal> ::= " <string characters>?"

<string character> ::= <input character> except " and \ | <escape character>

<null literal> ::= null

Explanation of BNF extensions

The character set for Java is Unicode, a 16-bit character set. This is the set denoted by <input character>. Unicode effectively contains the familiar 7-bit ASCII characters as a subset, and includes "escape code" designations of the form \udddd (where each d is from <hex digit>). In the extended BNF for Java the optional appearance of X is written X?, and the iterative appearance of X is written {X}.

The syntax category <identifier> consists of strings that must start with a letter - including underscore (_) and dollar sign ($) - followed by any number of letters and digits. Characters of numerous international languages are recognized as "letters" in Java. A Java letter is a character for which the method Character.isJavaLetter returns true. A Java letter-or-digit is a character for which the method Character.isJaveLetterOrDigit returns true. Also, <identifier> includes none of the keywords given above - these are reserved words in Java.

The only BNF extention used here is the optional construct which is written with '?' added as a suffix to a terminal or non-terminal. Note that '*', '{', and '}' are all terminal symbols. This BNF definition does not address such pragmatic issues as comment conventions and the use of "white space" to delimit tokens. This BNF also does not express numerous "context-sensitive" restrictions on syntax. For instance, type use of identifiers must be consistent with the required declarations, there are size limitations on numerical literals, etc.

Java BNF

From

Contents

BNF and Extended BNF

An Extended BNF for Java

Java Programs

Java Declarations

Java Types

Blocks and Commands

Expressions

Tokens

Explanation of BNF extensions

Views

Personal tools

Navigation

Search

Toolbox