CSC 533: Organization of Programming Languages
Spring 2019

HW1: EBNF Grammar

The following questions all refer to the EBNF of Oberon-2, which is shown below.

  1. Which of the following are legal numbers in Oberon-2? For each legal number, provide a parse tree (with root number). 00 -2.9 C 3AH 2E-4 0.01E12 .88
  2. Which of the following are legal expressions in Oberon-2? For each legal expression, provide a parse tree (with root expr). NIL +5+5 a, b, c a4 IN [1..10] 1 < 2 < 3 a.b x OR y OR z
  3. Describe, in concise English, the format for identifiers in Oberon-2. That is, what characters may be used? What restrictions (if any) are there on order?

  4. What is the order of precedence for the operators +, -, *, and / in Oberon-2? Justify your answers by providing parse trees of the following expressions: a + b * c x / y - z
  5. Are semicolons statement terminators or statement separators in Oberon-2? That is, does every statement in a sequence 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 Java, it is possible to declare multiple variables in a single statement. For example,   int sum1, sum2;   declares sum1 and sum2 to both be of type int. Does Oberon-2 also provide this feature? That is, is it possible to declare more than one variable in a single statement? If so, what would the declaration look like? If not, why not?

  7. In Java, it is possible to chain assignments. For example,   sum1 = sum2 = 0;   assigns sum1 and sum2 to both be 0. Does Oberon-2 also provide this feature? That is, is it possible to chain assignments so that the right-hand side of an assignment is another assignment (e.g., sum1 := sum2 := 0)? Justify your answer.

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

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

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

EBNF for Oberon-2 (based on Mossenbock & Wirth, 1993) ======================================================================================== 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} letter ::= "a" | "b" | ... | "z" | "A" | "B" | ... | "Z" digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 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" string ::= ' " ' {character} ' " ' | " ' " {character} " ' " character ::= *** any printable character other than " or ' *** characterConst ::= digit {hexDigit} "X" Note: | separates alternatives. [] denotes optionality of the enclosed expression. {} denote its repetition (possibly 0 times). Terminal symbols are all uppercase (e.g. BEGIN) or in quotes (e.g. ":=").