BNF Grammar

BNF Grammar
You are encouraged to solve this task according to the task description, using any language you may know.

In computer science, Backus–Naur Form (BNF) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. John Backus and Peter Naur developed a context free grammar to define the syntax of a programming language by using two sets of rules: i.e., lexical rules and syntactic rules.

BNF is widely used as a notation for the grammars of computer programming languages, instruction sets and communication protocols, as well as a notation for representing parts of natural language grammars. Many textbooks for programming language theory and/or semantics document the programming language in BNF.

There are many extensions and variants of BNF, including Extended and Augmented Backus–Naur Forms (EBNF and ABNF).

The task here is establish a BNF grammar for as many languages as possible to facilitate language categorization and translation.

ALGOL 60

! ----------------------------------------------------------------------------
! ALGOL 60
!
! (ALGO)rithmic (L)anguage
!
! ALGOL is, by far, the most influential programming language developed to 
! date. Although is did not achieve mass use, a large number of syntactic 
! and semantic principles and concepts were developed and incorporated into 
! the language. As a result, ALGOL is considered the main reference language 
! in computer science. 
! 
! In the late 1950's, many in the study of computer science believed that a 
! new universal programming language was needed. This new language would be 
! used through the study of computer science and would eventually replace 
! other popular languages such as FORTRAN. 
! 
! The ACM (Association for Computing Machinery) and GAMM (a European 
! organization of mathematics and mechanics) created an international 
! committee to define and document the new language. This committee 
! included computer scientists from both North America and Europe. 
! 
! The process of developing ALGOL included a number of challenges: 
! 
! First, the computers of the era varied greatly in the number of characters 
! that could be represented. This made it difficult to define the exact 
! lexics of the language. For instance, one mainframe could contain an 
! ampersand character (&) while another may not. 
! 
! Another challenge involved an issue that nowadays seems trival - the 
! representation of decimal points. In the 50 United States and Canada, real 
! numbers are represented using a period. For instance, the value 4 1/2 can 
! be written as "4.5". Europe, on the other hand, uses a comma. The same 
! value is represented with "4,5". Both sides were steadfast that their 
! format was superior. Although the "period" format would eventually 
! dominate, this was a major issue at the time. 
! 
! To describe the syntax of the first version of ALGOL, Peter Naur modified 
! Backus Normal Form to create Backus-Naur Form. This format is now used 
! universially to describe the syntax of programming languages. 
! 
! To spite these challenges, ALGOL created a number of language features 
! that would be incorporated into its numerious successors. These include: 
! 
! * Block structure 
! * Free-form structure (elements are not required to be in a specific column) 
! * Pass by Name  (while powerful, it is not used in modern languages) 
! * The For-Loop 
! * The 'Else' clause on if-statements (LISP's 'cond' predates this though) 
! * Reserved words 
! 
! The grammar below was, for the most part, cut and pasted from "Revised 
! Report on the Algorithmic Language: Algol 60" by Peter Naur. The numbered
! sections refer directly to the chapters in the Report. 
!
! The grammar was modified to remove ambigities and define terminals using
! regular expressions.
!
! ----------------------------------------------------------------------------


"Name"      = 'ALGOL 60'
"Version"   = '1960'

"Author"    = 'J.W. Backus, F.L. Bauer, J.Green, C. Katz, J. McCarthy, P. Naur,'
            | 'A.J. Perlis, H. Rutishauser, K. Samuelson, B. Vauquois,'
            | 'J.H. Wegstein, A. van Wijngaarden, M. Woodger'

"About"     = 'ALGOL (ALGOrithmic Language) is the most influential'
            | 'programming language to date. Although it did not achieve'
            | 'mass use, it established multiple syntactic and semantic'
            | 'features used in languages today.'


"Start Symbol" = <program>


! ========================================================== Terminals


{String Ch}    = {Printable} - [`] - ['']

Identifier     = {Letter}{Alphanumeric}*

String         = '`' ( '`' {String Ch}* '' | {String Ch} )* ''

IntegerLiteral = {Digit}+ 
RealLiteral    = {Digit}+ '.' {Digit}+  (e {Digit}+)?


! =========================================================== Rules

<unsigned integer> 
        ::= IntegerLiteral
         
<unsigned number>          
        ::= IntegerLiteral
         |  RealLiteral


! ====================================================================
! 2.2.2 Logical values.
! ====================================================================

<logical value> ::= true | false



! ====================================================================
! 3. Expressions
! ====================================================================

<expression> 
       ::= <Boolean expression> 
          

! ====================================================================
! 3.1. Variables
! ====================================================================

<subscript expression> 
        ::= <arithmetic expression>

<subscript list> 
        ::= <subscript expression> 
         |  <subscript list> ',' <subscript expression>


<variable> 
        ::= Identifier
         |  Identifier '[' <subscript list> ']'      ! subscripted value

! ====================================================================
! 3.2. Function designators
! ====================================================================

<actual parameter> 
        ::= String
         |  <expression>

<parameter delimiter> 
        ::= ',' 
         |  ')' Identifier ':' '('


<actual parameter list> 
        ::= <actual parameter>  
         |  <actual parameter list> <parameter delimiter> <actual parameter>


! ====================================================================
! 3.3. Arithmetic expressions
! ====================================================================

<adding operator> ::= '+' | '-'

<multiplying operator> ::=  '*' | '/' | 'div'       

<primary> 
        ::= <unsigned number>
         |  <variable>
         |  Identifier '(' <actual parameter list> ')'
         |  '(' <arithmetic expression> ')'

<factor> 
       ::= <primary> 
         | <factor> '^' <primary>     !Originally an up-arrow                          
       
<term> 
        ::= <factor> 
         |  <term> <multiplying operator> <factor>


<simple arithmetic expression> 
        ::= <term> 
         |  <adding operator> <term>
         |  <simple arithmetic expression> <adding operator> <term>

<if clause> ::= if <Boolean expression> then

<arithmetic expression> 
        ::= <simple arithmetic expression>
         |  <if clause> <simple arithmetic expression> else <arithmetic expression>



! ====================================================================
! 3.4. Boolean expressions
! ====================================================================

<relational operator> ::= '<' | '<=' | '=' | '>=' | '>' | '~='


<relation> 
        ::= <relation> <relational operator> <simple arithmetic expression>
         |  <simple arithmetic expression>  

<Boolean primary> 
        ::= <logical value>
         |  <relation> 

<Boolean secondary> 
        ::= <Boolean primary> 
         |  not <Boolean primary>


<Boolean factor> 
        ::= <Boolean secondary>
         |  <Boolean factor> and <Boolean secondary>

<Boolean term> 
        ::= <Boolean factor> 
         |  <Boolean term> or <Boolean factor>

<implication> 
        ::= <Boolean term> 
         |  <implication> implies <Boolean term>

<simple Boolean> 
        ::= <implication>
         |  <simple Boolean> eqv <implication>


<Boolean expression> 
        ::= <simple Boolean> 
         |  <if clause> <simple Boolean> else <Boolean expression>


! ====================================================================
! 3.5. Designational expressions
! ====================================================================

<label> 
       ::= Identifier
        |  <Unsigned Integer>

<switch designator>
       ::= Identifier '[' <subscript expression> ']'

<simple designational expression> 
       ::= <label> 
        |  <switch designator> 
        | '(' <designational expression> ')'

<designational expression> 
       ::= <simple designational expression> 
        |  <if clause> <simple designational expression> else <designational expression>


! ====================================================================
! 4.1. Compound statements and blocks
! ====================================================================

<unlabelled basic statement> 
        ::= <assignment statement> 
         |  <go to statement>
         |  !EMPTY                 !dummy statement 
         |  <procedure statement>


<basic statement> 
        ::= <unlabelled basic statement>
         |  <label> ':' <basic statement>

<unconditional statement> 
        ::= <basic statement> 
         |  <compound statement> 
         |  <block>

<statement> 
        ::= <unconditional statement>
         |  <conditional statement>
         |  <for statement>

<compound tail> 
        ::= <statement> end 
         |  <statement> ';' <compound tail>

<block head> 
        ::= begin <declaration> 
         |  <block head> ';' <declaration>

<unlabelled block> 
        ::= <block head> ';' <compound tail>

<unlabelled compound> 
        ::= begin <compound tail>

<compound statement> 
        ::= <unlabelled compound> 
         |  <label> ':' <compound statement>

<block> 
        ::= <unlabelled block>
         |  <label> ':' <block>

<program> 
        ::= <block> 
         |  <compound statement>


! ====================================================================
! 4.2. Assignment statements
! ====================================================================

<left part> 
        ::= <variable> ':=' 


<left part list> 
        ::= <left part> 
         |  <left part list> <left part>

<assignment statement> 
        ::= <left part list> <Boolean expression>


 
! ====================================================================
! 4.3. Go to statements
! ====================================================================

<go to statement> ::= goto <designational expression>


! ====================================================================
! 4.4. Dummy statements
! ====================================================================

!<dummy statement> ::= <empty>


! ====================================================================
! 4.5. Conditional statements
! ====================================================================

<if statement> ::= <if clause> <unconditional statement>

<conditional statement> 
       ::= <if statement> 
        |  <if statement> else <statement> 
        |  <if clause> <for statement> 
        |  <label> ':' <conditional statement>


! ====================================================================
! 4.6. For statements
! ====================================================================

<for list element> 
       ::= <arithmetic expression> 
        |  <arithmetic expression> step <arithmetic expression> until <arithmetic expression>
        |  <arithmetic expression> while <Boolean expression>

<for list> 
       ::= <for list element> 
        |  <for list> ',' <for list element>

<for clause> ::= for <variable> ':=' <for list> do

<for statement> 
       ::= <for clause> <statement> 
        |  <label> ':' <for statement>


! ====================================================================
! 4.7. Procedure statements
! ====================================================================


<procedure statement> 
        ::= Identifier '(' <actual parameter list> ')'
         |  Identifier 


! ====================================================================
! 5. Declarations
! ====================================================================

<declaration> 
       ::= <type declaration>
        |  <array declaration>
        |  <switch declaration>
        |  <procedure declaration>


! ====================================================================
! 5.1. Type declarations
! ====================================================================

<type list> 
       ::= Identifier 
        |  Identifier ',' <type list>

<type> 
       ::= real 
        |  integer 
        |  Boolean

<local or own type> 
       ::= <type> 
        |  own <type>

<type declaration> 
       ::= <local or own type> <type list>


! ====================================================================
! 5.2. Array declarations
! ==================================================================== 
 
<lower bound> ::= <arithmetic expression>
 
<upper bound> ::= <arithmetic expression>
 
<bound pair>  ::= <lower bound> ':' <upper bound>
 
<bound pair list> 
       ::= <bound pair> 
        |  <bound pair list> ',' <bound pair>
 
<array segment> 
       ::= Identifier '[' <bound pair list> ']' 
        |  Identifier ',' <array segment>
 
<array list> 
       ::= <array segment> 
        |  <array list> ',' <array segment>
 
<array declaration> 
       ::= array <array list> 
        |  <local or own type> array <array list>
 

! ====================================================================
! 5.3. Switch declarations
! ====================================================================

<switch list> 
       ::= <designational expression> 
        |  <switch list> ',' <designational expression>

<switch declaration> 
       ::= switch Identifier ':=' <switch list>


! ====================================================================
! 5.4. Procedure declarations
! ====================================================================

<formal parameter> 
        ::= Identifier

<formal parameter list> 
        ::= <formal parameter>
         |  <formal parameter list> <parameter delimiter> <formal parameter>

<formal parameter part> 
        ::= !EMPTY 
         | '(' <formal parameter list> ')'

<identifier list> 
        ::= Identifier
         |  <identifier list> ',' Identifier

<value part> 
        ::= value <identifier list> ';' 
         |  !EMPTY

<specifier> 
        ::= string 
         |  <type>
         |  array
         |  <type> array
         |  label
         |  switch
         |  procedure
         |  <type> procedure

<specification part> 
        ::= !EMPTY
         | <specification>
  
!=== The following rule was added

<specification>
        ::=                 <specifier> <identifier list> ';'
         |  <specification> <specifier> <identifier list> ';'



<procedure heading> 
        ::= Identifier <formal parameter part> ';' <value part> <specification part>

<procedure body> 
        ::= <statement>         
!!!      |  <code>             !<code> refers to any embedded non-Algol code         
         

<procedure declaration> 
        ::=        procedure <procedure heading> <procedure body> 
         |  <type> procedure <procedure heading> <procedure body>

BASIC

! -----------------------------------------------------------------------
! BASIC '64 
!
! Beginner's All-purpose Symbolic Instruction Code 
!
!    "It is practically impossible to teach good programming style to students 
!     that have had prior exposure to BASIC; as potential programmers they are 
!     mentally mutilated beyond hope of regeneration." 
!
!     - Edsger W. Dijkstra 
!
! BASIC is one of the oldest programming language and one of the most popular. 
! It was developed in 1964 by John G. Kemeny and Thomas E. Kurtz to teach 
! students the basics of programming concepts. At the advent of the microcomputer,
! BASIC was implemented on numerous platforms such as the Commodore, Atari, 
! Apple II, Altair, IBM PC computers. Over time, BASIC evolved into GW-BASIC, 
! QBasic, Visual Basic, and recently Visual Basic .NET.
!
! In practically all programming languages, the reserved word/symbol that denotes
! a comment is treated as a form of whitespace - having no effect in the manner in
! which the program runs. Once such type of comment is used to indicate the remainder
! of the line is to be ignored. These can be added to the end of any line without
! changing the meaning of the program. In C++, it is the '//' symbol;
! in BASIC '64 it is 'REM'.
!
! However, in the BASIC programming language, the line comment is treated like a 
! statement. For instance, if 'REM' was a normal line comment:
!
!    10  PRINT "Hello World" REM Common first program
!
! would be a valid statement. However, in BASIC, this is illegal. In the example 
! above, the comment must be added as an additional statement.
!
!    10  PRINT "Hello World" : REM Common first program
!
! As a result, the Line Comment terminal that is used in the GOLD Parser cannot be
! used here. In the grammar below, a 'Remark' terminal was created that accepts all 
! series of printable characters starting with the characters "REM ". In some 
! implementations of BASIC, any string starting with "REM" is a comment statement.
! Examples include "REMARK", "REMARKABLE" and "REMODEL". This grammar requires the space.
!
! This grammar does not include the editor statements such as NEW, SAVE, LOAD, etc...
!
! Note: This is an ad hoc version of the language. If there are any flaws, please 
! e-mail GOLDParser@DevinCook.com and I will update the grammar. Most likely I have
! included features not available in BASIC '64.
! -----------------------------------------------------------------------


"Name"    = 'BASIC (Beginners All-purpose Symbolic Instruction Code)'
"Author"  = 'John G. Kemeny and Thomas E. Kurtz' 
"Version" = '1964 - Original - before Microsoft enhanced the language for the IBM PC.'
"About"   = 'BASIC is one of most common and popular teaching languages ever created. '

"Case Sensitive" = False 
"Start Symbol"   = <Lines>

{String Chars} = {Printable} - ["]
{WS}           = {Whitespace} - {CR} - {LF}

NewLine        = {CR}{LF}|{CR}
Whitespace     = {WS}+

Remark         = REM{Space}{Printable}*
ID             = {Letter}[$%]? 
String         = '"'{String Chars}*'"' 
Integer        = {digit}+ 
Real           = {digit}+.{digit}+ 

<Lines>       ::= Integer <Statements> NewLine <Lines> 
                | Integer <Statements> NewLine

<Statements>  ::= <Statement> ':' <Statements>
                | <Statement>

<Statement>   ::= CLOSE '#' Integer
                | DATA <Constant List> 
                | DIM ID '(' <Integer List> ')'
                | END          
                | FOR ID '=' <Expression> TO <Expression>     
                | FOR ID '=' <Expression> TO <Expression> STEP Integer      
                | GOTO <Expression> 
                | GOSUB <Expression> 
                | IF <Expression> THEN <Statement>         
                | INPUT <ID List>       
                | INPUT '#' Integer ',' <ID List>       
                | LET Id '=' <Expression> 
                | NEXT <ID List>               
                | OPEN <Value> FOR <Access> AS '#' Integer
                | POKE <Value List>
                | PRINT <Print list>
                | PRINT '#' Integer ',' <Print List>
                | READ <ID List>           
                | RETURN
                | RESTORE
                | RUN
                | STOP
                | SYS <Value>
                | WAIT <Value List>
                | Remark

<Access>   ::= INPUT
             | OUPUT
                   
<ID List>  ::= ID ',' <ID List> 
             | ID 

<Value List>      ::= <Value> ',' <Value List> 
                    | <Value> 

<Constant List>   ::= <Constant> ',' <Constant List> 
                    | <Constant> 

<Integer List>    ::= Integer ',' <Integer List>
                    | Integer
                 
<Expression List> ::= <Expression> ',' <Expression List> 
                    | <Expression> 

<Print List>      ::= <Expression> ';' <Print List>
                    | <Expression> 
                    |  

<Expression>  ::= <And Exp> OR <Expression> 
                | <And Exp> 

<And Exp>     ::= <Not Exp> AND <And Exp> 
                | <Not Exp> 
 
<Not Exp>     ::= NOT <Compare Exp> 
                | <Compare Exp> 

<Compare Exp> ::= <Add Exp> '='  <Compare Exp> 
                | <Add Exp> '<>' <Compare Exp> 
                | <Add Exp> '><' <Compare Exp> 
                | <Add Exp> '>'  <Compare Exp> 
                | <Add Exp> '>=' <Compare Exp> 
                | <Add Exp> '<'  <Compare Exp> 
                | <Add Exp> '<=' <Compare Exp> 
                | <Add Exp> 

<Add Exp>     ::= <Mult Exp> '+' <Add Exp> 
                | <Mult Exp> '-' <Add Exp> 
                | <Mult Exp> 

<Mult Exp>    ::= <Negate Exp> '*' <Mult Exp> 
                | <Negate Exp> '/' <Mult Exp> 
                | <Negate Exp> 

<Negate Exp>  ::= '-' <Power Exp> 
                | <Power Exp> 

<Power Exp>   ::= <Power Exp> '^' <Value> 
                | <Value> 

<Value>       ::= '(' <Expression> ')'
                | ID 
                | ID '(' <Expression List> ')'
                | <Constant> 

<Constant> ::= Integer 
             | String 
             | Real 

C

! -----------------------------------------------------------------------
! ANSI C
!
! The C programming language evolved at Bell Labs from a series of 
! programming languages: 'CPL', 'BCPL', and then 'B'. As a result, C's
! development was a combined effort between Dennis Ritchie, Ken Thompson,
! and Martin Richards.  
!
! C was designed for the creation and implementation of low-level systems
! such as operating systems, device drivers, firmware, etc... To realize 
! this goal, the language contains the ability to perform operations 
! directly on memory and has direct access to system pointers. While this 
! gives an enormous amount of control and flexibility, it also makes C a 
! professional programming language - not to be used by an inexperienced
! programmer.
!
! C (and later C++) quickly became the de facto standard for developing
! operating systems, applications and most other large projects. UNIX as 
! well as Windows, Linux, and Mac-OS X were developed using this 
! language (and its successors).
!
! More information is available at Dennis Ritchie's website:
!     http://cm.bell-labs.com/cm/cs/who/dmr/
!
! The C grammar is inherently ambigious and requires a large number of
! LALR(1) states to parse. As a result, the time required by the GOLD 
! Parser Builder to compile this grammar is extensive.
! 
! C is not a line-based grammar with the notable exception of compiler
! directives (which are preceeded by a '#' character). These are usually not
! handled directly by the actual parser, but, rather, the pre-processor. 
! Before the program is analyzed by the parser, C compilers scan the code and
! act on these commands. The final C program is then passed to the parser.
! -----------------------------------------------------------------------

! -----------------------------------------------------------------------
! This grammar does not contain the compiler directives.
!
! Note: This is an ad hoc version of the language. If there are any flaws, 
! please visit the contact page and tell me.
!
! SPECIAL THANKS TO:
!     BOB MEAGHER
!     MIKE WISDOM
!     VLADIMIR MOROZOV
!     TOM VAN DIJCK
!
! Modified 06/14/2002
!   * The correct definition for "return" was added. Thanks to Bob Meagher.
!   * Added the missing rules for labels, storage specifications, etc...
!     which were left out. Thanks to Mike Wisdom for calling this to
!     my attention.
!
! Modified 06/21/2002
!   * I fixed an error in the grammar for declaring functions. 
!
! Modified 06/15/2003
!   * Vladimir Morozov fixed an error for calling functions with no parameters
!
! Modified 01/31/2004
!   * Tom van Dijck found a bug in the grammar concerning variable 
!     initialization.
!
! Modified 04/26/2004
!   * Some errors in the grammar were fixed.
!
! Modified 01/19/2005
!   * The definition for comments was modified. In ANSI C, block comments
!     cannot be nested. As a result, they are defined using the whitespace
!     terminal.
!
! Modified 03/28/2007
!   * The commented-out definition for non-nested comments was updated. The
!     previous version did not work in all cases.
! -----------------------------------------------------------------------


"Name"    = 'ANSI C' 
"Version" = '1973'
"Author"  = 'Dennis Ritchie, Ken Thompson, Martin Richards' 
"About"   = 'C is one of the most common, and complex, programming languages in use today.'

"Case Sensitive" = True
"Start Symbol"   = <Decls>

{Hex Digit}      = {Digit} + [abcdefABCDEF]
{Oct Digit}      = [01234567]

{Id Head}        = {Letter} + [_]
{Id Tail}        = {Id Head} + {Digit}

{String Ch}      = {Printable} - ["]
{Char Ch}        = {Printable} - ['']

DecLiteral       = [123456789]{digit}*
OctLiteral       = 0{Oct Digit}*
HexLiteral       = 0x{Hex Digit}+
FloatLiteral     = {Digit}*'.'{Digit}+

StringLiteral    = '"'( {String Ch} | '\'{Printable} )* '"'
CharLiteral      = '' ( {Char Ch} | '\'{Printable} )''

Id               = {Id Head}{Id Tail}*


! ===================================================================
! Comments
! ===================================================================

Comment Start = '/*'
Comment End   = '*/'
Comment Line  = '//'


! Typically, C comments cannot be nested. As a result, the 
! Comment Start and Comment End terminals cannot be used.
!
! To implement non-nested comments, the whitespace terminal is
! modified to accept them. In the definition below, Whitespace 
! is defined as one or more {Whitespace} characters OR a series
! of characters delimited by /* and */. Note that the characters
! between the two delimiters cannot contain the */ sequence. 
!
! Uncomment the following to prevent block commments. Make sure 
! to comment the Comment Start and Comment End definitions.
!
! {Non Slash}     = {Printable} - [/]  
! {Non Asterisk}  = {Printable} - [*]
! 
! Whitespace     = {Whitespace}+   
!                | '/*' (  {Non Asterisk} | '*' {Non Slash}? )*  '*/'

!=======================================================

<Decls> ::= <Decl> <Decls>
          |

<Decl>  ::= <Func Decl>
          | <Func Proto>
          | <Struct Decl>
          | <Union Decl>
          | <Enum Decl>
          | <Var Decl>    
          | <Typedef Decl>
              
! ===================================================================
! Function  Declaration
! ===================================================================

<Func Proto> ::= <Func ID> '(' <Types>  ')' ';'
               | <Func ID> '(' <Params> ')' ';'
               | <Func ID> '(' ')' ';'

<Func Decl>  ::= <Func ID> '(' <Params>  ')' <Block>
               | <Func ID> '(' <Id List> ')' <Struct Def> <Block>
               | <Func ID> '(' ')' <Block>


<Params>     ::= <Param> ',' <Params>
               | <Param>
               
<Param>      ::= const <Type> ID
               |       <Type> ID
               
<Types>      ::= <Type>  ',' <Types>
               | <Type> 
   
<Id List>    ::= Id ',' <Id List>
               | Id

<Func ID>    ::= <Type> ID
               | ID

! ===================================================================
! Type Declaration
! ===================================================================

<Typedef Decl> ::= typedef <Type> ID ';'

<Struct Decl>  ::= struct Id '{' <Struct Def> '}'  ';' 

<Union Decl>   ::= union Id '{' <Struct Def> '}'  ';' 


<Struct Def>   ::= <Var Decl> <Struct Def>
                 | <Var Decl>

! ===================================================================
! Variable Declaration
! ===================================================================

<Var Decl>     ::= <Mod> <Type> <Var> <Var List>  ';'
                 |       <Type> <Var> <Var List>  ';'
                 | <Mod>        <Var> <Var List>  ';'
             
<Var>      ::= ID <Array>
             | ID <Array> '=' <Op If> 

<Array>    ::= '[' <Expr> ']'
             | '[' ']'
             |
             
<Var List> ::=  ',' <Var Item> <Var List>
             | 

<Var Item> ::= <Pointers> <Var>

             
<Mod>      ::= extern 
             | static
             | register
             | auto
             | volatile
             | const   

! ===================================================================
! Enumerations
! ===================================================================

<Enum Decl>    ::= enum Id '{' <Enum Def> '}'  ';'
 
<Enum Def>     ::= <Enum Val> ',' <Enum Def>
                 | <Enum Val>

<Enum Val>     ::= Id
                 | Id '=' OctLiteral
                 | Id '=' HexLiteral
                 | Id '=' DecLiteral  


! ===================================================================
! Types
! ===================================================================

<Type>     ::= <Base> <Pointers> 

<Base>     ::= <Sign> <Scalar>
             | struct Id 
             | struct '{' <Struct Def> '}' 
             | union Id
             | union '{' <Struct Def> '}' 
             | enum Id  


<Sign>     ::= signed 
             | unsigned
             |

<Scalar>   ::= char
             | int
             | short
             | long
             | short int
             | long int
             | float
             | double
             | void           

<Pointers> ::= '*' <Pointers>
             |

! ===================================================================
! Statements
! ===================================================================

<Stm>        ::= <Var Decl>
               | Id ':'                            !Label
               | if '(' <Expr> ')' <Stm>          
               | if '(' <Expr> ')' <Then Stm> else <Stm>         
               | while '(' <Expr> ')' <Stm> 
               | for '(' <Arg> ';' <Arg> ';' <Arg> ')' <Stm>
               | <Normal Stm>

<Then Stm>   ::= if '(' <Expr> ')' <Then Stm> else <Then Stm> 
               | while '(' <Expr> ')' <Then Stm> 
               | for '(' <Arg> ';' <Arg> ';' <Arg> ')' <Then Stm>
               | <Normal Stm>

<Normal Stm> ::= do <Stm> while '(' <Expr> ')'
               | switch '(' <Expr> ')' '{' <Case Stms> '}'
               | <Block>
               | <Expr> ';'               
               | goto Id ';'
               | break ';'
               | continue ';'
               | return <Expr> ';'
               | ';'              !Null statement


<Arg>       ::= <Expr> 
              | 

<Case Stms> ::= case <Value> ':' <Stm List> <Case Stms>
              | default ':' <Stm List>                  
              |

<Block>     ::= '{' <Stm List> '}' 

<Stm List>  ::=  <Stm> <Stm List> 
              | 


! ===================================================================
! Here begins the C's 15 levels of operator precedence.
! ===================================================================

<Expr>       ::= <Expr> ',' <Op Assign>   
               | <Op Assign>

<Op Assign>  ::= <Op If> '='   <Op Assign>
               | <Op If> '+='  <Op Assign>
               | <Op If> '-='  <Op Assign>
               | <Op If> '*='  <Op Assign>
               | <Op If> '/='  <Op Assign>
               | <Op If> '^='  <Op Assign>
               | <Op If> '&='  <Op Assign>
               | <Op If> '|='  <Op Assign>
               | <Op If> '>>=' <Op Assign>
               | <Op If> '<<=' <Op Assign>
               | <Op If>

<Op If>      ::= <Op Or> '?' <Op If> ':' <Op If>
               | <Op Or>

<Op Or>      ::= <Op Or> '||' <Op And>
               | <Op And>

<Op And>     ::= <Op And> '&&' <Op BinOR>
               | <Op BinOR>

<Op BinOR>   ::= <Op BinOr> '|' <Op BinXOR>
               | <Op BinXOR>

<Op BinXOR>  ::= <Op BinXOR> '^' <Op BinAND>
               | <Op BinAND>

<Op BinAND>  ::= <Op BinAND> '&' <Op Equate>
               | <Op Equate>

<Op Equate>  ::= <Op Equate> '==' <Op Compare>
               | <Op Equate> '!=' <Op Compare>
               | <Op Compare>

<Op Compare> ::= <Op Compare> '<'  <Op Shift>
               | <Op Compare> '>'  <Op Shift>
               | <Op Compare> '<=' <Op Shift>
               | <Op Compare> '>=' <Op Shift>
               | <Op Shift>

<Op Shift>   ::= <Op Shift> '<<' <Op Add>
               | <Op Shift> '>>' <Op Add>
               | <Op Add>

<Op Add>     ::= <Op Add> '+' <Op Mult>
               | <Op Add> '-' <Op Mult>
               | <Op Mult>

<Op Mult>    ::= <Op Mult> '*' <Op Unary>
               | <Op Mult> '/' <Op Unary>
               | <Op Mult> '%' <Op Unary>
               | <Op Unary>

<Op Unary>   ::= '!'    <Op Unary>
               | '~'    <Op Unary>   
               | '-'    <Op Unary>
               | '*'    <Op Unary>
               | '&'    <Op Unary>               
               | '++'   <Op Unary>
               | '--'   <Op Unary>
               | <Op Pointer> '++'
               | <Op Pointer> '--'
               | '(' <Type> ')' <Op Unary>   !CAST
               | sizeof '(' <Type> ')'
               | sizeof '(' ID <Pointers> ')'
               | <Op Pointer>

<Op Pointer> ::= <Op Pointer> '.' <Value>
               | <Op Pointer> '->' <Value>
               | <Op Pointer> '[' <Expr> ']'
               | <Value>

<Value>      ::= OctLiteral
               | HexLiteral
               | DecLiteral  
               | StringLiteral
               | CharLiteral
               | FloatLiteral
               | Id '(' <Expr> ')'
               | Id '(' ')'          

               | Id
               | '(' <Expr> ')'