CIS 425 Fall 2019 Assignment 1 September 2019
Submission of assignments is optional. Submitted assignments will not be graded, but will be checked for correctness.
1
Questions to help you understand the reading
What is the difference between a partial and a total function?
What does it mean for a function to be computable?
What is the halting problem?
Give an example of a non computable function not based on the halting problem
What is a grammar? How do you define it i.e understand what is a nonterminal, terminal, productions, root
What is the difference between a regular, context free and context sensitive grammar? What is a parse tree?
What is a derivation?
What is an ambiguous grammar?
How do you solve the ambiguity?
Explain the difference between postfix, prefix and infix notation.
What is the difference between a compiler and an interpreter?
Explain the different phases of a compiler Understandtheadvantagesdisadvantagesoffunctionalversusimperativeprogramming What is the Von Neumann bottleneck?
Understand the task of each of the following:
1. Lexical analyser
2. Syntax analyser
3. Semantic analyser
4. Intermediate code generator 5. Code optimizer
6. Machine code generator
1
CIS 425 Fall 2019 Assignment 1 September 2019
2
1.
Which of the following are advantages of compilers? Which are advantages of inter preters?
1. Generated code can run many times
2. Can afford heavy weight optimizations
3. Can preexamine input program for semantic type errors
4. Have full knowledge of both program input and program implementation 5. Flexible, can easily adapt program behavior dynamically
Language Generated by Grammar
Consider the grammar G :
S:: aST T :: bT U U :: cU
a Which of the following strings is generated by the G grammar?
i. ccc ii. aba iii. bab
iv. ca
b Which of the following is a derivation of the string bbc?
i. S !T !U !bU !bbU !bbU !bbc ii. S !bT !bbT !bbU !bbcU !bbc
iii. S !T !bT !bbT !bbU !bbcU !bbc iv. S !T !bT !bTbT !bbT !bbcU !bbc
c Which of the following regular expressions accepts the same language as the gram mar G?
i. abc ii. abc
iii. abc
iv. aababc
Which of the following grammars describes the same language as 0n1m where m d n? 2
2.
Fall 2019
Assignment 1
CIS 425 September 2019
3.
4.
What language does this grammar generate?
S :: aSa aBa B:: bBb
What language does this grammar generate?
S :: abScB B:: bBb
Designing Grammars
a S::0S1
b S :: 0S1 S1
c S :: 0S1 0S d S :: SS 0 1
3
Follows some hints to generate grammars.
1. Use recursive productions to generate an arbitrary number of symbols.
2. To generate languages with matching, balanced, or related numbers of symbols, write productions which generate strings form the middle.
3. For a language that is the union of other languages, use separate nonterminals for each part of the union and then combine.
1. Design a grammar that generates zero or more a s
2. Design a grammar that generates one or more b s
3. Design a grammar that generates the language ab
4. Design a grammar that generates the language anbnn e 0
5. Design a grammar that generates the language anb2nn e 0
6. Design a grammar that generates the language anbm0 d n d m d 2n
7. Design a grammar that generates words formed from 0,1 that begin and end with the same symbol.
3
CIS 425 Fall 2019 Assignment 1 September 2019
8.
9.
10.
4
Design a grammar that generates the language anbm cm m n e 0 Note that this can be rewritten as anbmm n e 0 ancmm n e 0
Design a grammar for the language L which is over the alphabet a, b, c, which consists of at least three consecutive b s For example, L includes the strings bbb and abcbbba, but not abbab.
For each of the above grammars, state if the grammar is regular or contextfree
Associativity and Priority
Rewrite the ambiguous grammar:
E :: E E E E E a b
1. 2.
5
1.
2.
3.
To reflect the fact that and are left associative and has higher precedence than
To reflect the fact that and are right associative and has higher precedence than
Parse Trees and Ambiguity
Show that the following grammar is ambiguous: S :: SS S
Which of the following grammars is ambiguous? a S::0SS10S1
b S :: A1S1A A :: 0
c S :: S,S,S 1 d None of the above
Consider the following grammar:
4
CIS 425 Fall 2019 Assignment 1 September 2019
4.
5.
6.
6
1.
assignment :: a 1 a 2
stmt :: assignment ifstmt
expr:: xy xz
ifstmt :: if expr stmt if expr stmt else stmt
Note that are used to denote nonterminals
Draw two parse trees for the following program fragment: if x y if x z a 1 else a 2
Consider the following grammar for arithmetic expressions:
E:: ETETT T:: TTTFF F:: 1234E
Draw a parse tree for the following strings:
a 1234 b 123
c 1234
Draw an abstract syntax tree for the following strings:
a 1234 b 123
c 1234
Operational Semantics
This problem asks you about operational semantics for a simple language with assign ment and addition. The expressions of this language are given by the grammar
e :: n x x : e e e
where n can be any number 0,1,2,3,…. We can define the operational semantics
with respect to a function : V ar ! N , where Var is the set of variables that may 5
CIS 425 Fall 2019 Assignment 1 September 2019
appear in expressions and N is the set of numbers that can be values of variables. To have some reasonable terminology, we will call a store and a pair e, a state.
When a program executes, we hope to reach a final state e, where e is a number, which we will call a value.
a Let s look at arithmetic expressions. Two rules for evaluating summands of a sum
are
a1, ! a2 1,2 a1a2, ! a2 1a2,2
a2, ! a2 2,2 na2, ! na2 2,2
We assume that it is a single execution step to add two numbers, so we have the rule
n, m, p are numbers with n m p nm, ! p,
The value of a variable depends on the store, as specified by this evaluation rule x, ! x,
Show how these rules let you evaluate an expression x y to a sum of numbers. Assumeisastorewithx2andy3. Writeyouranswerasan execution sequence of the form below, with an explanation.
xy,! ,! ,! ,
b Put is the function on stores with Put,x,n 2 with 2 x n and 2 y y for all variables y other than x. Using Put, the execution rule for assignment can be written
x : n, ! n,Put,x,n
In this particular language, an assignment changes the store, as usual. In addition, as you can see from the operational semantics of assignment, an assignment is an expression whose value is the value assigned.
If we have an assignment with an expression that has not been evaluated to a number, then we can use this evaluation rule:
e, ! e2 ,2 x:e, ! x:e2 ,2
Combining these rules with the rules from part a, show how to execute x : x 3, when is a store with x 1. Write your answer as an execution sequence of the form below, with an explanation.
x:x3,!x: ,!x: ,! ,
6
CIS 425 Fall 2019 Assignment 1 September 2019
c Show how to execute x : 3 x, in the same level of detail, including an explanation.
d Show how to execute x:x:x3x:x5, when is a store with x 1 in the same level of detail, including an explanation.
7