CSC 533: Organization of Programming Languages
Spring 2007

HW2: Syntex and EBNF Grammars

The following is the entire EBNF for the programming language Oberon-2, a descendant of ALGOL and Pascal. These rules are taken from The Oberon-2 Programming Language by Niklaus Wirth and Hanspeter Mössenböck. 

Module        = MODULE ident ";" [ImportList] DeclSeq [BEGIN StatementSeq] END ident ".".
ImportList    = IMPORT [ident ":="] ident {"," [ident ":="] ident} ";".
DeclSeq       = { CONST {ConstDecl ";" } 
                | TYPE {TypeDecl ";"} 
                | VAR {VarDecl ";"}} {ProcDecl ";" 
                | ForwardDecl ";"}.
ConstDecl     = IdentDef "=" ConstExpr.
TypeDecl      = IdentDef "=" Type.
VarDecl       = IdentList ":" Type.
ProcDecl      = PROCEDURE [Receiver] IdentDef [FormalPars] ";" DeclSeq 
                [BEGIN StatementSeq] END ident.
ForwardDecl   = PROCEDURE "^" [Receiver] IdentDef [FormalPars].
FormalPars    = "(" [FPSection {";" FPSection}] ")" [":" Qualident].
FPSection     = [VAR] ident {"," ident} ":" Type.
Receiver      = "(" [VAR] ident ":" ident ")".
Type          = Qualident
                | ARRAY [ConstExpr {"," ConstExpr}] OF Type
                | RECORD ["("Qualident")"] FieldList {";" FieldList} END
                | POINTER TO Type
                | PROCEDURE [FormalPars].
FieldList     = [IdentList ":" Type].
StatementSeq  = Statement {";" Statement}.
Statement     = [ Designator ":=" Expr
                | Designator ["(" [ExprList] ")"]
                | IF Expr THEN StatementSeq {ELSIF Expr THEN StatementSeq} [ELSE StatementSeq] END
                | CASE Expr OF Case {"|" Case} [ELSE StatementSeq] END
                | WHILE Expr DO StatementSeq END
                | REPEAT StatementSeq UNTIL Expr
                | FOR ident ":=" Expr TO Expr [BY ConstExpr] DO StatementSeq END
                | LOOP StatementSeq END
                | WITH Guard DO StatementSeq {"|" Guard DO StatementSeq} [ELSE StatementSeq] END
                | EXIT
                | RETURN [Expr]
                ].        
Case          = [CaseLabels {"," CaseLabels} ":" StatementSeq].
CaseLabels    = ConstExpr [".." ConstExpr].
Guard         = Qualident ":" Qualident.
ConstExpr     = Expr.
Expr          = SimpleExpr [Relation SimpleExpr].
SimpleExpr    = ["+" | "-"] Term {AddOp Term}.
Term          = Factor {MulOp Factor}.
Factor        = Designator ["(" [ExprList] ")"] | number | character | string | 
                NIL | Set | "(" Expr ")" | " ~ " Factor.
Set           = "{" [Element {"," Element}] "}".
Element       = Expr [".." Expr].
Relation      = "=" | "#" | "<" | "<=" | ">" | ">=" | IN | IS.
AddOp         = "+" | "-" | OR.
MulOp         = " * " | "/" | DIV | MOD | "&".
Designator    = Qualident {"." ident | "[" ExprList "]" | " ^ " | "(" Qualident ")"}.
ExprList      = Expr {"," Expr}.
IdentList     = IdentDef {"," IdentDef}.
Qualident     = [ident "."] ident.
IdentDef      = ident [" * " | "-"].

ident         = letter {letter | digit}.
number        = integer | real.
integer       = digit {digit} | digit {hexDigit} "H".
real          = digit {digit} "." {digit} [ScaleFactor]. 
ScaleFactor   = ("E" | "D") ["+" | "-"] digit {digit}.
hexDigit      = digit | "A" | "B" | "C" | "D" | "E" | "F".
digit         = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".
string        = ' " ' {char} ' " ' | " ' " {char} " ' ".

  1. Which of the following are legal numbers in Oberon-2? For each legal number, provide a parse tree (with the number abstraction at the root). 00 -2.9 0XA2 5. 2E-4 0.01E12 5.5E+5.5 3.0H
  2. Describe, in concise English, the format for identifiers (ident) in Oberon-2. That is, what characters may be used? What restrictions (if any) are there on order?

  3. What is the shortest possible procedure declaration (ProcDecl) in Oberon-2? Justify your answer.

  4. What is the order of precedence for the operators + and * in Oberon-2? Justify your answer by providing the parse tree for the Expr:   1+2*3.

  5. In C++ and Java, the test for an if statement or while loop must be surrounded by parentheses. Are parentheses required for tests in Oberon-2? If not, are they optional? Justify your answer.

  6. In C++ and Java, an assignment returns a value, allowing the programmer to chain assignments together, e.g., x = y = 0;. Can assignments similary be chained in Oberon-2? Justify your answer.

  7. Does the dangling-else problem apply to Oberon-2? Justify your answer.