Programming Language Concept (3)

Book : Concept of Programming Language

Page 162
Review Questions
1. Define syntax and semantics?
Syntax is concerned with the structure of language. Syntax is a matter of the logical or grammatical form of sentences, rather than what they refer to or mean. Semantics is concerned with the meaning of words and sentences. Semantics is a matter of the content or meaning of sentences, often in relation to their truth and falsehood.

4. Describe the operation of a general language recognizer?
A general language recognizer is a recognition device capable of reading strings of characters from the alphabet. It would analyze the given string and it would either accept or reject the string based from the language given. These recognition devices are like filters separating correct sentences from those that are incorrectly. A recognizer is used in the syntax analysis part of the compiler. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. The syntax analyzer just determines whether the given programs are syntactically correct.

6. Define a left-recursive grammar rule.
A grammar rule has its LHS also appearing at the beginning of its RHS.

8. Distinguish between static and dynamic semantics
Static semantic of a language is only indirectly related to the meaning of program 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 is required to check these specification can be done at compile time.
Dynamic semantics is the meaning of the expression, statements, and program units of a programming language.

14. Why can machine languages not be used to define statements in operational semantics?
Because the individual steps in the execution of machine language and the resulting changes to the state of machine are too small and too numerous.

15. Describe the two levels of uses of operational semantics.
Natural Operational Semantics : At the highest level, the interest is in the final result of the execution of a complete program.
Structural 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.

18. Which semantics approach is most widely known?
Denotational semantics

20. Which part of an inference rule is the antecedent?
if the truth of S in the top part of an inference rule

28. What is the use of the wp function? why it is called a predicate transformer?
the use of the wp function is to treat the process of producing a weakest precondition as a function. it is called a predicate transformer because it takes a predicate, or assertion, as a parameter and returns another predicate.

29. Give the difference between total corectness and partial correctness.
Total correctness : loop termination can be shown
Partial correctness : loop conditions that can be met but termination is not guaranteed

Page 163
Problem Set
3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *
<assign> -> <id> = <expr>
<expr> -> <expr> * <term> | <term>
<term> = <factor> + <term> | <factor>
<factor> -> (<expr>) | <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?
if all the attributed values in a parse tree have been computed. a parse tree of an attributed grammar is the parse tree based on its underlying BNF grammar, with a possibly empty set of attribute values attached to each node.

23.  Compute the weakest precondition for each of the followeing 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

24. Compute the weakest precondition for each of the following sequences of assignment statements and their postcondition
a. a= 2*b+1
b=a-3 {b<0}
a-3<0
a<3
we have:
a=2*b+1 {a<3}
2*b+1<3
2*b<2
b<1
b. a= 3*(2*b+a)
b= 2*a-1 {b>5}
2*a-1>5
2*a>6
we have:
a= 3*(2*b+a) {a>3}
3*(2*b+a)>3
6*b+3*a>3
2*b+a>1
b>(1-a)/2