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]. |

- 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 - 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 ) - 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`.

- 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?

- 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.

- 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.

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

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

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