REVIEW QUESTIONS
2. Who are language descriptions for?
Language descriptions are for programmers and Programming language implementors.
5. What is the difference between a sentence and a sentential form?
a. A sentence contains only terminal symbols but a sentential form can contain some non-terminal symbols
b. Sentential forms are a subset of sentences but the converse is not true
c. Sentential forms have no handles but a sentence does.
7. What three extentions are common to most EBNFs?
a. The first of these denotes an optional part of an RHS, which is delimited by brackets.
b. The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether.
c. The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether.
8. Distinguish between static and dynamic semantics.
The static semantics of a language is only indirectly related to the meaning of programs during execution; rather, it has to do with the legal forms of programs
(syntax rather than semantics). Many static semantic rules of a language state its type constraints. Static semantics is so named because the analysis required to
check these specifications can be done at compile time.
Dynamic semantics is the meaning of the expression, statements, and program units of a programming language.
12. What is the primary use of attribute grammars?
An attribute grammar is a device used to describe more of the structure of a programming language than can be described with a context-free grammar. It is also
used to specify how attribute values are computed.
14. Why can machine language not be used to define statements in operational semantics?
Machine language can not be used to define statements in operational semantics because of some problems. First, the individual steps in the execution of machine
language and the resulting changes to the state of the machine are too small and too numerous. Second, the storage of a real computer is too large and complex.
15. Describe the two levels of uses of operational semantics.
At the highest level, the interest is in the final result of the execution of a complete program. This is sometimes called natural operational semantics.
At the lowest level, operational semantics can be used to determine the precise meaning of a program through an examination of the complete sequence of state
changes that occur when the program is executed. This use is sometimes called structural operational semantics.
21. When a grammar rule said to be left recursive?
A grammar rule is said to be left recursive when a grammar rule has its LHS also appearing at the beginning of its RHS.
22. Give an example of an ambiguous grammar.
A = B + C * A
29. Give the difference between total correctness and partial correctness.
If loop termination can be shown, the axiomatic description of the loop is called total correctness. If the other conditions can be met but termination is not
guaranteed, it is called partial correctnes.
PROBLEM SET
1. Syntax error and semantic error are two types of compilation error. Explain the difference between the two in a program with examples.
A syntax error refers to an error in the syntax of a sequence of characters or tokens that is intended to be written in a particular programming language.
Example of syntax error:
In java this is error
System.out.println(Hello World);
The correct syntax is System.out.println(“Hello World”);
Semantic Error is a logical error. It is due to wrong logical statements. Semantics is the interpretations of and meanings derived from the sentence transmission
and understanding of the message. Semantics errors are Logical, while Syntax errors are code errors.
Example of Semantic Error:
int average(int a, int b)
{
return a + b / 2; /* should be (a + b) / 2 */
}
It compiles and runs but does not give the right answer.
3. Rewrite the BNF of example 3.4 to represent operator – and operator / instead of operator + and operator *.
<expr> -> <expr> * <term> | <term>
<term> = <factor> + <term> | <factor>
<factor> -> (<expr>) | <id>
9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.
<assign> -> <id> := <expr>
<id> -> A | B | C
<expr> -> <expr> + <term> | <term>
<term> -> <term> * <negfactor> | <negfactor>
<negfactor> -> – <factor> | <factor>
<factor> -> ( <expr> ) | <id>
12. Consider the following grammar:
<S> -> a <S> c <B> | <A> | b
<A> -> c<A> | c
<B> -> d | <A>
Which of the following sentences are in the language generated by this grammar?
a) abbccd
b) acccbda
c) accbcbccc
d) acddaccd
e) acccdc
No one of the following statements are generated.
18. What is a fully attributed parse tree?
A parse tree of an attribute grammar is the parse tree based on its underlying BNF grammar, with a possibly empty set of attribute values attached to each node. If
all the attribute values in a parse tree have been computed, the tree is said to be fully attributed.
17. Convert the following EBNF to BNF:
S -> A { b A}
A -> a [ b ] A
Answer:
S -> A | A B
B -> b A | b A B
A -> a A | a b A
19. Write an attribute grammar whose BNF basis is that of Example 3.6 in Section 3.4.5 but whose language rules are as follows: Data types cannot be mixed in expressions, but assignment statements need not have the same types on both sides of the assignment operator.
Replace the second semantic rule with:
<var>[2].env <- <expr>.env
<var>[3].env <- <expr>.env
<expr>.actual_type <- <var>[2].actual_type
predicate: <var>[2].actual_type == <var>[3].actual_type
23. Compute the weakest precondition for each of the following assignment statements and postconditions:
(a) a = 2 * (b – 1) – 1 {a > 0}
2 * (b – 1) – 1 > 0
2 * b – 2 – 1 > 0
2 * b > 3
b > 3 / 2
(b) b = (c + 10) / 3 {b > 6}
(c + 10) / 3 > 6
c + 10 > 18
c > 8
(c) a = a + 2 * b – 1 {a > 1}
a + 2 * b – 1 > 1
2 * b > 2 – a
b > 1 – a / 2
(d) x = 2 * y + x – 1 {x > 11}
2 * y + x – 1 > 11
2 * y + x > 12
24. Compute the weakest precondition for each of the following sequences of assignment statements and their postconditions:
(a) a = 2 * b + 1
b = a – 3
{b < 0}
a – 3 < 0 -> a < 3
2 * b + 1 < 3 -> 2 * b < 2 -> b < 1
The weakest precondition is {b < 1}
(b) a = 3 * (2 * b + a);
b = 2 * a – 1
{b > 5}
2 * a – 1 > 5
2 * a > 6
a > 3
3 * (2 * b + a) > 3
3 * (2 * b + a) > 3
(2 * b + a) > 1
(2 * b) > 1 – a
b > (1 – a)/2
The weakest precondition is {b >(1 – a)/2}
25. Compute the weakest precondition for each of the following selection constructs and their postconditions:
(a) if (a = = b)
b = 2 * a + 1
else
b = 2 * a;
{b > 1}
2 * a + 1 > 1 -> 2 * a > 0 -> a > 0
2 * a > 1 -> a > 1/2
The weakest precondition is {a > 1/2}
(b) if (x < y)
x = x + 1
else
x = 3 * x
{x < 0}
x + 1 < 0
x < -1
3 * x < 0
x < 0
The weakest precondition is {x < 0}
(c) if (x > y)
y = 2 * x + 1
else
y = 3 * x – 1;
{y > 3}
2 * x + 1 > 3
2 * x > 2
x > 1
3 * x – 1 > 3
3 * x > 4
x > 4/3
The weakest precondition is {x > 4/3}
Forpakarana 