livingmylivetothefullest

It's about life

Chapter 3

This assignment is given by Mr. Tridjoko Wahjono

1. Define syntax and semantics.

Syntax and semantics are terms used in relation to aspects of language.

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.

6. Define a left-recursive grammar rule.

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 recursive specifies left associativity.

7. What three extension are common to most EBNFs?

The first extension denotes an optional part of a 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 extension deals with multiple choice options.

8. Distinguish between static and dynamic semantic.

The static semantics defines restrictions on the structure of valid texts that are hard or impossible to express in standard syntactic formalisms.

The dynamic semantics (also known as execution semantics) of a language defines how and when the various constructs of a language should produce a program behavior. There are many ways of defining execution semantics.

10 What is the difference between a synthesized and an inherited attribute?

A syntax directed definition that uses synthesized attributes exclusively is said to be an S-attributed definition. A parse tree for an S-attributed definition can always be annotated by evaluating the semantic rules for the attributes at each node bottom up, from the leaves to the root.

An inherited attribute is one whose value at a node in a parse tree is defined in terms of attributes at the parent and/or siblings of that node. Inherited attributes are convenient for expressing the dependence of a programming language construct on the context in which it appears.

12. What is the primary use of attribute grammars?

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.

15. Describe the two levels of uses of operational semantics.

At the highest level, the interest is in the final result of the execution of a complete program(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(structural operational semantics).

16. In denotational semantics, what are the syntactic and semantic domains?

In denotational semantics, the domain is called the syntactic domain, because it is syntactic structures that are mapped. The range is called the semantic domain,

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.

27. What is loop invariant? Explain with an example.

The corresponding step in the axiomatic semantics of a “while” loop is finding an assertion, which is crucial to finding the weakest precondition OR a condition that is necessarily true immediately before and immediately after each iteration of a loop.

For example, in Java, a while loop has the following form, where B is a boolean expression (that we shall call the guard of the loop) and S is a sequence of commands/instructions (that we shall call the body of the loop).

Problem Set

1. A syntax error refers to an error in the syntax of a sequence of characters or tokens that is intended to be written in a particular programming language.

Semantic Error: it is a logical error. it is due to wrong logical statements. Semantics is the interpretations of and meanings derived from the sentence transmission and understanding of the message.

example:

syntax error
/* expr
Parses strings in the language generated by the rule:
<expr> -> <term> {(+ | -) <term>}
*/
voidexpr() {
printf(“Enter <expr>\n”);
/* Parse the first term */
term();
/* As long as the next token is + or -, get
the next token and parse the next term */
while(nextToken == ADD_OP || nextToken == SUB_OP) {
lex();
term();
}
printf(“Exit <expr>\n”);
} /* End of function expr */

semantic errror
Me(<expr>, s) ?=case <expr> of
<dec_num>=>Mdec(<dec_num>, s)
<var> =>if VARMAP(<var>, s) == undef
then error
else VARMAP(<var>, s)
<binary_expr> =>
if(M
e(<binary_expr>.<left_expr>,s) == undefOR
Me(<binary_expr>.<right_expr>, s) == undef)
then error
else if (<binary_expr>.<operator> == ‘+’)
then M
e(<binary_expr>.<left_expr>, s) +
Me(<binary_expr>.<right_expr>, s)
else Me(<binary_expr>.<left_expr>, s) *
Me(<binary_expr>.<right_expr>, s

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 grammar in example 3.2, show a parse tree for each of the following statements:
a. A = A *(B*(C+A))
<assign>-><id>=<expr>
<id>->A|B|C
<expr>-><id>+<expr>
|<id>*<expr>
|<id>*<expr>
|(<expr>)
|<id>
b. B=C*(A+C*B)
<assign>-><id>*<id>=<expr>
<id>=A|B|C
<expr>-><id>+<expr>
|<id>*<expr>
|(<expr>)
|<id>
c. A=A+(B*(C))
<assign>-><id>=<expr>
<id>->A|B|C
<expr>-><id>*<expr>
|<id>+<expr>
|(<expr>)
|<id>

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 fully attributed parse tree?

A condition when all the attributed values in parse tree have been computed.

21. Using the virtual machine instructions given in section 3.5.1.1, give an operational semantic definition of the following

a. java

loop: (do body)
if<relational_expression> goto out
goto loop
out: …

b. Ada (for)
for I in first..last loop
I=first
loop: if I<last go out

I=I+1
goto loop
out: …

c. C++ if-then-else

if(condition){
statement1;
statement2;
}
else{
statement3;
statement4;
}

d. C for
for(expr1;expr2;expr3)
evaluate (expr1);
loop=control= evaluate(expr2)
if control == 0 goto out
evaluate (expr3)
goto loop
out: …

e. C switch

switch(condition){
case 1:
statement1;
break;

default:
statement2;
break;

}

23. Compute the weakest precondition for each of the following assignment statement and post condition:

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

c. a=a+2*b-1 {a>1}
a+2*b-1>1
2*b>2-a
b>1-a/2

d. x= 2*y+x-1 {x>11}
2*y+x-1>11
2*y+x>12

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Information

This entry was posted on March 25, 2013 by and tagged .
March 2013
M T W T F S S
« Jan   Apr »
 123
45678910
11121314151617
18192021222324
25262728293031

Blog Stats

  • 6,909 hits
%d bloggers like this: