Informal Compiler Algorithm Notation (ICAN)


Informal Compiler Algorithm Notation (ICAN)

This notation is used to explicitly express the compiler algorithms. The syntax of ICAN is expressed using the extended Backus-Naur form. Let us first discuss the Extended Backus-Naur form in detail.

We use typewriter font to write terminals in XBNF such as “[“and “type”. The non-terminals are represented using the italic font where the representation starts with capital letters and uppercase letters are properly inter-spread to convey the right meanings and thus help in readability (e.g., ProgUnit instead of Progunit). Some of the operators used in XBNF are:

• | – To separate alternatives
• * – Zero or more repetitions
• { and } – Grouping
• [ and ] – Optional

ICAN – Introduction

Most of the features in ICAN are derived from different programming languages such as Pascal, C and Modula-2. An ending delimiter like “fi” is added to end an “if” statement. Hence there is no need to add separators between the statements.
An ICAN program is lexically a sequence of ASCII characters. The lexical analysis is performed from left to right and each of the characters are analyzed and formed into tokens. An ICAN program comprises of a sequence of type definitions, variable declarations, followed by procedure declaration and at last the main program. A type name followed by an equality sign and a type expression is called as a type definition.
intset = set of integer

Syntax of ICAN program:

Program  -> TypeDef* VarDecl* ProcDecl* [MainProg]
MainProg -> ProcBody

Type Definitions

The type definitions are characterized by one or more type name which is followed by “=” sign and the definition. It can be recursive also. The syntax of type definition outlines the following:
• TypeDef      -> {TypeName =}* TypeExpr
• TypeName -> Identifier
• TypeExpr   ->SimpleTypeExpr | ConstrTypeExpr | ( TypeExpr ) | TypeName | φ
• SimpleTypeExpr -> boolean | integer | real | character
• ConstrTypeExpr  ->EnumTypeExpr | ArrayTypeExpr | SetTypeExpr | SequenceTypeExpr | TupleTypeExpr | RecordTypeExpr | UnionTypeExpr | FuncTypeExpr
• EnumTypeExpr    ->enum { Identifier , }


A variable declaration comprises of the identifier name, an initialization (optional), a colon followed by its type. The syntax can be outlined as:
• VarDecl -> {Variable [:=ConsttExpr]}, : TypeExpr
• Variable -> Identifier
• ProcDecl -> procedure ProcName ParamList [returns TypeExpr] ParamDecls ProcBody
• ProcName -> Identifier
• Parameter ->Identifier
• ParamDecls -> ParamDecl*