Programming Language Concept – Chapter 3

Review Question:

3. A language generator is a device that can be used to generate the sentences of　a language. We can think of the generator as having a button that produces a　sentence of the language every time it is pushed. Because the particular sentence　that is produced by a generator when its button is pushed is unpredictable, a　generator seems to be a device of limited usefulness as a language descriptor.

4.Suppose we have language L uses an alphabet zigma of character. To define L formally using recognition method, we would need to construct mechanism R called as recognition device, capable of reading strings of characters from alphabet zigma. R would either indicate whether a given input string was or was not in L. In affect R would either accept or reject the given string.

6. 　A “left-recursive” grammar means that the parser can get into a loop in the parsing rules without making any progress consuming the input. A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol.

7. 3 extensions that are common to most EBNFs are

C if-else statement
The use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether
The third common extension deals with multiple-choice options
8. Static semantics is more on the legal forms of programs (syntax rather symantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.

Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions

12. Attribute grammars are a formal approach both to describing and checking the correctness of the static semantics rules of a program. Although they are not always used in a formal way in compiler design, the basic concepts of attribute grammars are at least informally used in every compiler.

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.

27. Loop invariant is some predicate (condition) that holds for every iteration of the loop. Example:

int j = 9;
for(int i=0; i= 0 && i < 10 (because this is the termination condition!) or that j = 0.

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

PS

8. Prove that the following grammar is ambiguous:
→
→ + |
→ a | b | c

The following two distinct parse tree for the same string prove that the grammar is
ambiguous.
a b c a b
+ <A
+ +

10.Describe, in English, the language defined by the following grammar:
→
→ a | a
→ b | b
→ c | c

The LHS non-terminal S is defined as non-terminal A and non-terminal B and non-terminal C, where non-terminal A can be one or more a’s or one a, where non-terminal B can be one or more b’s or one b, and where non-terminal C can be one or more c’s or one c.

12.Consider the following grammar:
→ a c | | b
→ c | c
→ d |
Which of the following sentences are in the language generated by this
grammar?
a. abcd
b. acccbd
c. acccbcc
d. acd
e. accc

The LHS non-terminal S is defined as non-terminal A, terminal a, non-terminal B and terminal b, where non-terminal A can be zero or more b’s or one b, and where non-terminal B can be one or more a’s or one a;

Resulting in one or more b’s or one b, one a, one or more a’s or one a, and one b.

Answers a (baab) and d (bbaab) adhere to this production.

13.Write a grammar for the language consisting of strings that have n
copies of the letter a followed by the same number of copies of the
letter b, where n > 0. For example, the strings ab, aaaabbbb, and
aaaaaaaabbbbbbbb are in the language but a, abb, ba, and aaabb are not

->

-> a b

21.
(a) (Java do-while) We assume that the logic expression is a single relational
expression.
loop: (do body)
if goto out
goto loop
out: …
(b) (Ada for) for I in first .. last loop
I = first
loop: if I end goto out
…

K= K + step
goto loop
out: …
(e) (C for) for (expr1; expr2; expr3) …
evaluate(expr1)
loop: control = evaluate(expr2)
if control == 0 goto out
…
evaluate(expr3)
goto loop
out: …