Chapter 3 Concepts of Programming Language
Review Question
1. Define syntax and semantics
Answer:
The syntax of a programming language is the form of its expressions,
statements, and program units. The semantics is the meaning of those
expressions, statements, and program units.
3. Describe the operation of a
general language generator
Answer: A language generator is a device that can be used to generate
the sentences of a language. The particular sentence that is produced by a
generator is unpredictable, a generator seems to be a device of limited
usefulness as a language descriptor.
6. Define a left-recursive
grammar rule
Answer: A left-recursive grammar rule means that a rule is recursive if
its Left-Hand Side appears in its Right-Hand Side. Example: <ident_list> -> identifier
|
Identifier, <ident_list>
7. What are three extensions are
common to most EBNFs?
Answer: The first of these
denotes an optional part of an RHS, which is delimited by brackets.
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.
The third common extension deals with multiple-choice options.
15. Describe the two levels of
uses of operational semantics.
Answer: There are different
levels of uses of operational semantics.
At the highest level, the interest is in the final result of the
execution of a complete program that called as 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.
22. Give an example of an ambiguous grammar
Answer:
Example of an ambiguous grammar
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>
23. On what branch of mathematics
is axiomatic semantics based?
Answer: Axiomatic semantics is
based on mathematic logic branch.
24. Give an unambiguous grammar
for if-then-else.
Answer: an unambiguous grammar
for if-then-else
<stmt> → <matched> | <unmatched>
<matched> → if <logic_expr> then <matched> else
<matched>
|any non-if statement
<unmatched> → if <logic_expr> then <stmt>
|if <logic_expr> then <matched> else <unmatched>
27. What is loop invariant?
Explain with an example.
Answer:
Loop invariant is an assertion of the corresponding step in the
axiomatic semantics of a while loop. Example:
The inference rule for computing the precondition for a while loop is
Where I is the loop invariant.
28. What is the use of the wp
function? Why it is called a predicate transformer?
Answer:
wp function is helpful to treat the process of producing a weakest
precondition as a function, wp.
A wp function is called as a predicate transformer, because it takes a
predicate, or assertion, as a parameter and returns another predicate.
Problem Set
1. Syntax Error and semantic
error are two types of compilation error. Explain the differences between the
two in a program with examples.
Answer:
Syntax error is an error that cause by wrong typing or mistype of one
or more character that represent a syntax or it can be en error because of
breaking the rule of writing the syntax.
The program can’t be compiled because of syntax error
For example in C:
printf (Hello world) //it would be an error because of
mistyping the “ ” and the semicolon
Semantic error is a logical error, it might be compiled but it has a
logic error in the program.
For example : int r = 20;
int pi = 12345;
int
area = pi *(r ^2);
It can be compiled but if assign the value of
pi to calculate the circle area the result would be wrong.
5. Write a BNF of description of
the relational operator of Java, including the two operators == and !=.
Answer:
<equality expression> ::= <relational expression> | <equality expression> == <relational
expression> | <equality
expression> != <relational
expression>
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))
8. Prove that the following grammar is ambiguous:
<S> → <A>
<A> → <A> *<A>
| <id>
<id> → x | y | z
Answer:
It is ambiguous because it has two or more
possibility parse trees to express a statement
Example:
The statement xyz with
parse tree
11. Consider the following grammar:
<S> → <A> a
<B> b
<A> → <A> b
| b
<B> → a <B>
| a
Which of the following sentences are in the language
generated by this grammar?
a. bbaabb
b. bbaba
c. bbaaaabb
d. abaabb
Answer:
a. bbaabb and c.bbaaaabb
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
Answer:
e.acccdc
15. Convert the BNF of Example 3.1 to EBNF.
Answer:
BNF of example 3.1
<program> → begin
<stmt_list> end
<stmt_list> →
<stmt>
| <stmt> ; <stmt_list>
<stmt> →
<var> = <expression>
<var> → A | B | C
<expression> →
<var> + <var>
| <var> – <var>
| <var>
EBNF of example 3.1
<program> → begin
<stmt_list> end
<stmt_list> →
<stmt>
| <stmt> ;
<stmt_list>
<stmt> →
<var> = <expression>
<var> → A | B | C
<expression> →
<var> { (+|-)<var>}
| <var>
16. Convert the BNF of Example 3.3 to EBNF.
Answer:
BNF of example 3.3
<assign> →
<id> = <expr>
<id> → A | B | C
<expr> →
<expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>
EBNF of example 3.3
<assign> →
<id> = <expr>
<id> → A | B | C
<expr> → <expr>
{ (+ | * ) <expr>}
| (
<expr> )
|
<id>
17. Convert the following EBNF to BNF:
S → A{bA}
A → a[b]A
Answer:
The BNF of S → A{bA}
S →A
|bA
The BNF of A → a[b]A
A→ aA
|abA
18. What is a fully attributed parse tree?
Answer:
A fully attributed parse tree is a condition when all
the attributed values in parse tree have been computed.
Special thanks to Mr. Tri Djoko Wahjono, Ir., M.Sc.
