The Grammar

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


Some (maybe) useful comments: 

Section 4.3 in the textbook give a partial solution (also see lecture 6). However, this partial solution needs to be incorporated in the grammar. Here are some links that can help.


THE GRAMMAR

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 StatementSequence end

StatementSequence ::= Statement { ; Statement }

Statement ::= SimpleStatement | StructuredStatement

SimpleStatement ::= [ (AssignmentStatement | ProcedureStatement) ]

AssignmentStatement ::= Variable := Expression

ProcedureStatement ::= id ( ActualParameterList )

StructuredStatement ::= CompoundStatement

           | if Expression then Statement [ else Statement ]

           | while Expression do Statement

           | for id := Expression to Expression do Statement

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

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 ] ComponentSelection ) ]

ActualParameterList ::= [ Expression { , Expression } ]

IdentifierList ::= id { , id }

Sign ::= + | -