March 26, 2013

KBP chapter 3

Rickvian Aldi / 02PCT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

Review questions

1.Define syntax and semantics.
-Syntax is the form of its expresions, statements, and program units.
Semantics is the meaning of those expressions, statements and program units.

2.Who are language descriptions for?
-Language user's

3.Describe the operation of a general language generator.
-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.

4.Describe the operation of a general language recognizer.
-The syntax analysis part of a compiler is a recognizer for the language the
compiler translates. In this role, the recognizer need not test all possible
strings of characters from some set to determine whether each is in the
language. Rather, it need only determine whether given programs are in the
language. In effect then, the syntax analyzer determines whether the given
programs are syntactically

5.What is the difference between a sentence and a sentential form?
-sentence is the string of a language
-Sentential form is string in the derivation of a program, including the
<program> itself.

7.What three extensions are common to most EBNFs?
-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. This extension allows lists to be built with a single rule, instead of using recursion and two rules.

-The third common extension deals with multiple-choice options. When a
single element must be chosen from a group, the options are placed in parentheses
and separated by the OR operator, |

10. what is the diffrence between a synthesized and an inherited attribute?
-Synthesized attributes are used to pass semantic information up a parse tree,
-Inherited attributes pass semantic information down and across a tree.

12. what is the primary use of attribute grammars?
-Attribute grammars are context-free grammars to which have been added attributes,
attribute computation functions, and predicate functions. Attributes,
which are associated with grammar symbols (the terminal and nonterminal
symbols), are similar to variables in the sense that they can have values assigned
to them.

15.Describe the two levels of a methodology and notation for describing the

semantics of programming languages.
-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.
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.

18. which semantics approach is most widely known?
Denotational semantics is the most rigorous and most widely known formal
method for describing the meaning of programs. It is solidly based on recursive
function theory.

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, the rule is said to be left recursive. This left recursion specifies left

22.Give an example of an ambiguous grammar.

if done == true
then if denom == 0
then quotient = 0;
else quotient = num / denom;

it's ambiguous which the "else" is not determined for first if or the second

Problem SET

(1)The two mathematical models of language description are generation
and recognition. Describe how each can define the syntax of a programming
answer :
-Suppose we have a language L that uses an alphabet of characters. To define L formally using the recognition method, we would need to construct a mechanism R, called a recognition device, capable of reading strings of characters from the alphabet . R would indicate whether a given input string was or was not in L. In effect, R would either accept or reject the given string. Such devices are like filters, separating legal sentences from those that are incorrectly formed. If R, when fed any string of characters over , accepts it only if it is in L, then R is a description of L.

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

(2)3. Rewrite the BNF of Example 3.4 to give + precedence over * and force +
to be right associative.
answer :
<assign> → => A = (B + C) ** A

(3)4. Rewrite the BNF of Example 3.4 to add the ++ and -- unary operators
of Java.
answer : 
<assign> => A = B ++ C * A

(4)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

answer : NONE of them

a) bbaabb
impossible to have 2 "b"s at the end of <S>

b) bbaba
impossible to have "a" at the end since <S> has always ends with "b"

c) bbaaaabb
impossible to have 2 "b"s at the end of <S>

d) abaabb
impossible to have "a" at the start of <S>

(5)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

answers :NONE OF THEM

rules from analysis :
1.the end of a statement will always either "b", "c", "d"
2.Since "b" obtained from <S> , impossible if "c" is after the "b".
3.<B> is the last part of <S>, so the "d" will always be the last and

impossible to have others following.
4.since "b" is called by <S>, take a look at the <S> is only one which can only

produce 1 "b" in a statement.

a) abbccd
impossible breaking rule 4

b) acccbda
impossible, breaking rule 1

c) accbcbccc
impossible, breaking rule 2

d) acddaccd
impossible, breaking rule 3

e) acccdc
impossible, breaking rule 3

(6)17. Convert the following EBNF to BNF:
S -> A{bA}
A -> a[b]A

<S> -> <A> | <S> b <A>
<A> -> a

(7)15. Convert the BNF of Example 3.1 to EBNF.

<program> → begin <stmt_list> end

<stmt_list> → <stmt>
| <stmt> ; <stmt_list>
<stmt> → <var> = <expression>
<var> → A | B | C
<expression> → <var> + <var>
| <var> – <var>
| <var>

answer : 

Program -> begin <stmt_list> end
<stmt_list -> <stmt> {; <stmt>)
stmt -> var = expression
var -> A | B | C
<exppression> -> <var> {(+|-) <var>}

(8)16. Convert the BNF of Example 3.3 to EBNF.
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>

answer :
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> { (+|*) <expr>}
| (<expr>)
| <id>

(9)18. What is the difference between an intrinsic attribute and a nonintrinsic
synthesized attribute?
-Intrinsic attributes are synthesized attributes of leaf nodes whose values are determined outside the parse tree.
nonintrinsic means the opposite, the values are not determined.

(10)28. Prove the following program is correct:
{n > 0}
count = n;
sum = 0;
while count <> 0 do
sum = sum + count;
count = count - 1;
{sum = 1 + 2 + . . . + n}

answer : 

assume input is 4
{n > 0}
count = n;
sum = 0;
while count <> 0 do

first round (count = 4)
sum = sum + count;
//sum = 4
count = count - 1;
//count = 4-1 = 3

second round (count = 3)
sum = sum + count;
//sum = 4 + 3
count = count - 1;
//count = 3-1 = 2

third round (count = 2)
sum = sum + count;
//sum = 4+3+2
count = count - 1;
//count = 2-1 = 1

first round (count = 1)
sum = sum + count;
//sum = 4+3+2+1 (prove the answer)
count = count - 1;
//count = 1-1 = 0

{sum = 1 + 2 + . . . + n}