CS 1104 Introduction to Computer Science

COMPILERS AND TRANSLATORS

 

Backus-Naur Form (BNF)

BNF is a "meta-language" - a language to describe languages, i.e. a SYNTAX

Originally developed to describe ALGOL in 1960

Is the basis for describing programming languages AND defining the syntactic anlyzers thereof.

We have been using it surreptitiously in previous presentations

 

General Form:

 

(NOTE: This requires us to use a "meta-meta-language" to describe a meta-language!)

 

EXAMPLES:

(1) An integer in most programming language is composed of a string of digits with no embedded spaces or other punctuation.
Consider the case of an integer of 4 digits:


<integer> ::= <digit><digit><digit><digit>

Where:

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

Now the case of defining an integer as an unbounded sequence of digits:

<integer> ::= <digit> | <integer><digit>

 

(2) Now define a real number, that is composed of an integer followed by a radix point and a fraction:

<real_number> ::= <integer>.<fraction>

<fraction> ::= <digit> | <fraction><digit>

(3) Describe the original BASIC variable identifier, that was any sequence of alphanumeric characters starting with an alphabetic character:

<variable> ::= <alphabetic_char> | <variable><alphanumeric_char>

where:

<alphabetic_char> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<alphanumeric_char> ::= <alphabetic_char> | <digit>

(4) Define a LISP function:

<LISP_function> ::= (<function_name><space><argument_list>)

where

<argument_list> ::= <argument> | <argument_list><space><argument>

and

<argument> ::= <atom> | <s-exp>

<atom> ::= <variable> | <number>

<s-exp> ::= <LISP_function>

(5) A LISP function definition is then:

<function_defn> ::=
(DEFINE (<function_name><space><parameter_list>) <s-exp>)

where

<parameter_list> ::= <parameter> | <parameter_list><space><parameter>

<parameter> ::= <atom>

 

[TOC]

Last updated 00/03/30
© J.A.N. Lee, 2000.