1. Define syntax and semantics.
Syntax is the form of its expressions, statements, and program units.
Semantics is the meaning of those expressions, statements, and program unit.
2. Who are language descriptions for?
For Language Recognizers and Language Generators.
5. What is the difference between a sentence and a sentential form?
A sentence is the string of a language, while sentential form is each of the strings in derivation.
21. When is a grammar rule 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.
Example :
<assign> -> <id> = <expr>
<id> -> A|B|C
<expr> -> <expr> + <expr>
| <expr * <expr>
| (<expr>)
| <id>
28. What is the use of the wp function? Why it is called a predicate transformer?
Wp fuction is the least restrictive precondition that will guarantee the validity of the associated postcondition.
It's called predicate transformer because it takes a predicate, or assertion, as a parameter and returns another predicate.
29. Give the difference between total correctness and partial correctness.
Total correctness is the loop that can be shown, while partial correctness is the other condition that can be met, but termination is not guaranteed.
_______________________________________________________________________
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.
Syntax error --> struct Abc
{
int value;
char name[100];
}
note : it should be like this :
struct Abc
{
int value;
char name[100];
};
Semantic error --> for(int i=0;i<5;i--)
{
printf("Hey!"); printf("\n");
}
note : it should be like this :
for(int i=0;i<5;i++)
{
printf("Hey!"); printf("\n");
}
3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.
<assign>-> <id> = expr
<id> -> A| B| C
<expr>-> <expr> -<term>
|<term>
<term>-> <term> / <factor>
| <factor>
<factor> -> (<expr>)
|<id>
6. Using the grammar in example 3.2, show a parse tree for each of the following statements:
a). =
/ \
a *
/ \
* a
/ \
b +
/ \
c a
b). =
/ \
b *
/ \
+ c
/ \
a *
/ \
c b
c). =
/ \
a +
/ \
* a
/ \
b c
7. Using the grammar in example 3.4, show a parse tree for each of the following statements:
a). A = (A*B)+C
<assign>-><id>=<expr>
<id>->A|B|C
<expr>-><id>+<expr>
|<term>
<term>-><term>*<factor>
|<factor>
<factor>->(<expr>)
|<id>
b). A=B*C+A
<assign>-><id>=<expr>
<expr>-><expr>+<id>
|<term>
<term>-><term>*<factor>
|<factor>
<factor> -> (<expr>)
|<id>
c). A = A + (B*C)
<assign>-><id>=<expr>
<expr>-><id>+<expr>
|<term>
<term>-><term>*<factor>
|<factor>
<factor>->(<expr>)
|<id>
d). A = B*(C+(A*B))
<assign>-><id>=<expr>
<expr>-><id>*<expr>
|<term>
<term>-><term>+<factor>
|<factor>
<factor>-><id>*<id>
|<id>
13. Write a grammar for the language consisting of strings that have n copies of the letter a followed by double the number of copies of the letter b, where n >0. For example the strings abb, aabbbb, and aaabbbbbb are in the language but, a, aabb, ba, and aaabb are not.
S-> aSb |ab
18. What is a fully attributed parse tree?
The tree is said to be fully attributed if all the attribute in a parse tree have been computed.
24. Compute the weakest precondition for each of the following sequences of assignment statements and their postcondition:
a). b=a-3 --> b<0
a-3<0 --> a<3
a=2*b+1 --> a<3
2*b+1<3 --> 2*b<2 --> b<1
b). b=2*a-1 --> b>5
2*a-1>5 --> 2*a>6 --> a>3
a=3*(2*b+a) --> a>3
3*(2*b+a)>3 --> 6*b+3*a>3 --> divided by 3 --> 2*b+a>1 --> b>(1-a)/2
