Sample Grammar Document

Documentation..... (Describe your grammar and the notation you use in there)

The grammar is given in Extended Backus-Naur Form (EBNF). The meaning of the meta-symbols are as follows MetaSymbol Meaning

::= is defined to be
| alternatively
[X] 0 or 1 instance of X
{X} 0 or more instances of X
(X | Y) a grouping: either X or Y
xyz The terminal symbol xyz
MetaIdentifier The non-terminal symbol MetaIdentifier

The grammer below is for a subset of Pascal, taken (and revised) from the Pascal User Manual and Report, 3rd edition, by K. Jensen & N. Wirth (Springer, 1985). Thelanguage has been substantially simplified by not allowing nested procedures.  The terminal symbols id and Int refer to the identifier and integer literal tokens returned by the lexer.

Program::= Program id ; [ TypeDefinitions] [ VariableDeclarations]

[ SubprogramDeclarations] CompoundStatement.

TypeDefinitions::= type TypeDefinition; { TypeDefinition; }

VariableDeclarations::= var VariableDeclaration; { VariableDeclaration; }

SubprogramDeclarations::= {( ProcedureDeclaration| FunctionDeclaration) ; }

TypeDefinition::= id = Type

VariableDeclaration::= IdentifierList: Type

ProcedureDeclaration::= Procedure id ( FormalParameterList) ;
                                                                     ( Block| forward )

FunctionDeclaration::= function id ( FormalParameterList) : ResultType;
                                                                    ( Block| forward )

FormalParameterList::= [ IdentifierList: Type{ ; IdentifierList: Type} ]

Block::= [ VariableDeclarations] CompoundStatement

CompoundStatement::= begin StatementSequenceend

StatementSequence::= Statement{ ; Statement}

Statement::= SimpleStatement| StructuredStatement

SimpleStatement::= [ ( AssignmentStatement| ProcedureStatement) ]

AssignmentStatement::= Variable:= Expression

ProcedureStatement::= id ( ActualParameterList)

StructuredStatement::= CompoundStatement
                                       | if Expressionthen Statement[ else Statement]
                                       | while Expressiondo Statement
                                       | for id := Expressionto Expressiondo Statement

Type::= id | array [ constant.. constant] of Type| record FieldListend

ResultType::= id

Fieldlist::= [ IdentifierList: Type{ ; IdentifierList: Type} ]

Constant::= [ sign] int

Expression::= SimpleExpression[ RelationalOp SimpleExpression]

RelationalOp::= < | <= | > | >= | <> | =

SimpleExpression::= [ sign] Term{ AddOp Term}

AddOp::= + | - | or

Term::= Factor{ MulOp Factor}

MulOp::= * | div | mod | and

Factor::= int | string | Variable| FunctionReference| not Factor| ( Expression)

FunctionReference::= id ( ActualParameterList)

Variable::= id ComponentSelection

ComponentSelection::= [ ( . id ComponentSelection|

[ expression] C omponentSelection) ]

ActualParameterList::= [ Expression{ , Expression} ]

IdentifierList::= id { , id }

Sign::= + | -

In a conditional, an else is associated with the nearest if... then.