CSC 533: Organization of Programming Languages
Spring 2015

HW1: Syntax and EBNF Grammars

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

Notation: Square brackets [ ] delimit optional constructs; braces { } indicate zero or more repetitions of the enclosed construct; parantheses ( ) indicate simple grouping of constructs; a vertical bar | indicates choice of one from many; literal text in definitions is denoted using double quotation marks " ". 

letter               = "A" | "B" | ... | "Z" | "a" | "b" | ... | "z".
digit                = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".
hexDigit             = digit | "A" | "B" | "C" | "D" | "E" | "F".

ident                = letter {letter | digit}.
qualident            = [ident "."] ident.
identdef             = ident ["*"]. 

integer              = digit {digit} | digit {hexDigit} "H".
real                 = digit {digit} "." {digit} [ScaleFactor].
ScaleFactor          = ("E" | "D") ["+" | "-"] digit {digit}.
number               = integer | real.
string               = """ {character} """ | digit {hexDigit} "X". 

ConstDeclaration     = identdef "=" ConstExpression.
ConstExpression      = expression. 

TypeDeclaration      = identdef "=" StrucType.
StrucType            = ArrayType | RecordType | PointerType | ProcedureType.
type                 = qualident | StrucType.
ArrayType            = ARRAY length {"," length} OF type.
length               = ConstExpression.
RecordType           = RECORD ["(" BaseType ")"] [FieldListSequence] END.
BaseType             = qualident.
FieldListSequence    = FieldList {";" FieldList}.
FieldList            = IdentList ":" type.
IdentList            = identdef {"," identdef}.
PointerType          = POINTER TO type.
ProcedureType        = PROCEDURE [FormalParameters].

VariableDeclaration  = IdentList ":" type.

expression           = SimpleExpression [relation SimpleExpression].
relation             = "=" | "#" | "<" | "<=" | ">" | ">=" | IN | IS.
SimpleExpression     = ["+" | "- "] term {AddOperator term}.
AddOperator          = "+" | "-" | OR.
term                 = factor {MulOperator factor}.
MulOperator          = "*" | "/" | DIV | MOD | "&".
factor               = number | string | NIL | TRUE | FALSE | set | 
                       designator [ActualParameters] | "(" expression ")" | "~" factor.
designator           = qualident {selector}.
selector             = "." ident | "[" ExpList "]" | "^" | "(" qualident ")".
set                  = "{" [element {"," element}] "}".
element              = expression [".." expression].
ExpList              = expression {"," expression}.
ActualParameters     = "(" [ExpList] ")".

statement            = [assignment | ProcedureCall | IfStatement | CaseStatement |
                       WhileStatement | RepeatStatement | ForStatement].
assignment           = designator ":=" expression.
ProcedureCall        = designator [ActualParameters].
StatementSequence    = statement {";" statement}.
IfStatement          = IF expression THEN StatementSequence
                       {ELSIF expression THEN StatementSequence}
                       [ELSE StatementSequence] END.
CaseStatement        = CASE expression OF case {"|" case} END.
case                 = [CaseLabelList ":" StatementSequence].
CaseLabelList        = LabelRange {"," LabelRange}.
LabelRange           = label [".." label].
label                = integer | string | ident.
WhileStatement       = WHILE expression DO StatementSequence
                       {ELSIF expression DO StatementSequence} END.
RepeatStatement      = REPEAT StatementSequence UNTIL expression.
ForStatement         = FOR ident ":=" expression TO expression [BY ConstExpression]
                       DO StatementSequence END.
ProcedureDeclaration = ProcedureHeading ";" ProcedureBody ident.
ProcedureHeading     = PROCEDURE identdef [FormalParameters].
ProcedureBody        = DeclarationSequence [BEGIN StatementSequence] 
                       [RETURN expression] END.
DeclarationSequence  = [CONST {ConstDeclaration ";"}] [TYPE {TypeDeclaration ";"}]
                       [VAR {VariableDeclaration ";"}] {ProcedureDeclaration ";"}.
FormalParameters     = "(" [FPSection {";" FPSection}] ")" [":" qualident].
FPSection            = [VAR] ident {"," ident} ":" FormalType.
FormalType           = {ARRAY OF} qualident.

module               = MODULE ident ";" [ImportList] DeclarationSequence
                       [BEGIN StatementSequence] END ident "." .
ImportList           = IMPORT import {"," import} ";".
import               = ident [":=" ident].

  1. Which of the following are legal numbers in Oberon-07? For each legal number, provide a parse tree (with the number abstraction at the root). 00 -2.9 0AH2 5. 2E-4 0.01E12 5.5E+5.5 3.0H
  2. Which of the following are legal expressions in Oberon-07? For each legal expression, provide a parse tree (with the expression abstraction at the root). 4 = 3 2 + - 2 - 2 + 2 a < b < c ( ( 4 ) ) Go ( 4 + 2 )
  3. What is the order of precedence for the operators + and * in Oberon-07? Justify your answer by providing the parse tree for the expression:   4 + 5 * 6.

  4. Describe, in concise English, the format for identifiers (ident) in Oberon-07. That is, what characters may be used? What restrictions (if any) are there on order?

  5. Are semicolons statement terminators or statement separators in Oberon-07? That is, does every statement in a block end with a semicolon (including the last one), or are there just semicolons between statements (but not after the last one)? Justify your answer.

  6. 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-07? If not, are they optional? Justify your answer.

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

  8. Give an example of an Oberon-07 ProcedureDeclaration that is as short as possible (in terms of number of tokens).

  9. Give an example of an Oberon-07 module that is as short as possible (in terms of number of tokens).