Concepts of Programming Languages ---- Chapter 3 Describing Syntax and Semantics

Concepts of Programming Languages ---- Chapter 3 Describing Syntax and Semantics

Name : Fandy Limardi
NIM : 1601210713
Lecture : Tri Djoko Wahjono, Ir., M.Sc. (D0206)
Assignment : Concept of programming languages ---- Chapter 3 Describing Syntax and Semantics

Chapter 3

REVIEW QUESTIONS

1.      Define syntax and semantics

The syntax of a programming language is the form of its expressions, statements, and program units. Semantics is the meaning of those expressions, statements, and program units.

2.      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 . In this term, people prefer certain forms of generators over recognizers because they can more easily read and understand them. By contrast, the syntax- checking portion of a compiler is not as useful a language description for a programmer because it can be used only in trial and error mode.

3.      Describe the operation of a general language recognizer

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 of reject the given string. Because most useful languages are, for all practical purposes, infinite, this might seem like a lengthy and ineffective process.

4.      What is the difference between a sentence and a sentential form?

Sentence form is a program consists of the special word begin, followed by a list of statements separated by semicolons, followed by the special word end. Sentential form is each of the strings in the derivation, including <program>

5.      Distinguish between static and dynamic semantics

Static semantics of a language is only indirectly related to the meaning of programs during execution; rather, it has to do with the legal forms of programs.

Dynamic semantics is the expressions , statements, and program units of a programming language. Because of the power and naturalness of the available notation, describing syntax is a simple matter.

6.      What is the difference between a synthesized and inherited attribute?

Synthesized attributes are used to pass semantic information up a parse tree, inherited attributes are used to pass semantic information down and across a tree.

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

-          The basic process

The first step in creating an operational semantics description of a language is to design an appropriate intermediate language, where the primary characteristic of the language is clarity. Every construct of the intermediate language must have an obvious and unambiguous meaning

-          Evaluation

The first and most significant use of formal operational semantics was to describe the semantics of PL/I. Operational semantics provides an effective means of describing semantics for language users and language implementers with simple and informal description.

8.      Give an example of an ambiguous grammar.

<assign> -> <id> = <expr>

<id>-> A|B|C

<expr> -> <expr> + <expr>

            | <expr> * <expr>

            | (<expr>)

            | <id>

The grammar is ambiguous because the sentence A = B + C *A

9.      What is the use of the wp function? Why it is called a predicate transformer?

The wp function is helpful 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.

10.  Give the difference between total correctness and partial correctness.

Total correctness is the axiomatic description of the loop when the loop termination is shown

Partial correctness is the other condition can be met but termination is not guaranteed.

PROBLEM SET

1.      Syntax error and semantic error are two types of compilation error. Explain the difference between the two in a program with examples.

Syntax Error: error due to missing colon, semicolon, parenthesis, etc. Syntax is the way in which we construct sentences by following principles and rules. 
Example: In C++, it would be a syntax error to say 
int a = "ten";
This will not compile because it does not follow the syntax of the language and does not make any sense to the compiler. 

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. Semantics errors are Logical, while Syntax errors are code errors. 
Example: A semantic error would compile, but be incorrect logically:
const int a = 12345;

2.      Prove that the following grammar is ambiguous:

<S>  -> <A>

<A> -> <A> * <A> | <id>

<id> -> x|y|z

                                        

3.      Describe, in English, the language defined by the following grammar in BNF

<S> -> <X> <Y>

<X> -> x <X> | x

<Y> -> y <Y> | y

<X> will generate one or more consecutive x’s.

<Y> will generate one or more consecutive y’s.

So <X> <Y> will generate

One or more x’s followed by one or more y’s.

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

b.     bbbab

c.      bbaaaaa

d.     bbaab

      <A> will generate one or more consecutive b's 
      <B> will generate one or more consecutive a's 
      So <A> a <B> b  will generate 

a.       baab : ok

<S>=><A>a<B>b => b a <B> b => b a a b

b.      bbaab : ok

<S> => <A>a<B>b => b b a <B>b => b b a a b

5.      Consider the following grammar in BNF:

<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? Explain your answers.

a)      abcd  : ok

Derivation:

      <S> => a <S> c <B> => a b c <B> => a b c d 

e)      accc : ok

Derivation:

      <S> => a <S> c <B> => a <A> c <B> => a c c <B> => a c c <A> => a c c c

6.      Convert the BNF of Example 3.3 to EBNF

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <id> + <expr>

                 | <id> * <expr>

                 |  ( <expr> )

                 | <id>

            <assign> -> <id> = <expr>

            <id> -> A|B|C

            <expr> -> <id> {(+ | *) <term>}

            <term> -> ‘(‘ <expr> ‘)’

7.      Convert the following EBNF to BNF:

S A {bA}

Aa [b]A

<S> <S>b<A> | <A>

<A> a<A> | ab<A>

8.      What is a fully attributed parse tree?

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

9.      Compute the weakest precondition for each of the following assignment statements and postconditions :

a.       a = 2 * ( b – 1 ) – 1 {a > 0}

b.      b = ( c + 10 ) / 3 {b>6}

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

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

A.    2 * ( b – 1 ) – 1 > 0

2b – 2 – 1  > 0

2b – 3 > 0

2b > 3

B > 3/2

B.     ( c + 10 ) / 3 > 6

c + 10 > 18

c > 8

C.     a + 2 * b – 1 > 1

a + 2 * b > 2

2 * b > 2 – a 

D.    2 * y + x – 1 > 11

2 * y + x > 12

2 * y > 12 – x

10.  Computer the weakest precondition for each of the following sequences of assignment statements and their postconditions :

a.        a = 2 * b + 1;

b = a – 3

{b < 0}

b.      a = 3 * (2 * b + a);

b = 2 * a – 1 

{b > 5}

A.    a – 3 < 0

a < 3

2 * b + 1 < 3

2 * b < 2

b < 1

B.     2 * a – 1 > 5

2 * a > 6

a > 3

3 * ( 2 * b + a ) > 3

2 * b + a > 1

2 * b > 1 - a