Concepts of Programming Languages Chapter 3

Concepts of Programming Languages Chapter 3

Name            : Erland
NIM              : 1601218035
Lecturer       : Tri Djoko Wahjono, Ir., M.Sc. (D0206)
Assignment  : Concept of programming languages Chapter 3

Review Questions

       1.  Define syntax and semantics.

             Answer : Syntax is the form of its expressions, statements, and program units.
                             Semantics is the meaning of those expressions, statements, and 
                             program units.

       2. Who are language descriptions for?

            Answer : I think, language description is made for those who want to use it, 
                            i.e programmers.

       3. Describe the operation of a general language generator.

             Answer : Language generator is a device that can be used to generate the 
                             sentences if a language.The produced sentences is unpredictable, 
                             and a generator seems to be a device of a limited usefulness as 
                             a language descriptor.

       4. Describe the operation of a general language recognizer.

             Answer : Language Recognizers accept a Language.Recognizers are Machines. 
                             The Machines take a string as input. The Machines will accept 
                             the input if when run, the Machine stops at an accept state. 
                             Otherwise the input is rejected. If a Machine M recognizes all 
                              strings in Language L, and accepts input provided by a given
                              string S, M is said to accept S. Otherwise M is said to reject S. S 
                              is in L if and only if M accepts S. 

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

             Answer : A sentence is a sentential form that has only terminal symbols. 
                             A sentence form is every string of symbols in the derivation.

        6. Define a left-recursive grammar rule.

             Answer: 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

        8.  Distinguish between static and dynamic semantics.

               Answer :

• Static semantic of a language is only indirectly related to the meaning of program during execution; rather it has to do with the legal forms of programs (syntax rather than semantics). Many static semantic rules of a language state its type constraints. Static semantics is so named because the analysis is required to check these specification can be done at compile time.

• Dynamic semantics is the meaning of the expression, statements, and program units of a programming language.

        10. What is the difference between aa synthetized and an inherited attribute?

             Answer : Synthesized attributes are used to pass semantic information 
                             up a parse tree. Inherited attributes pass semantic information 
                             down and across a tree.

        27. What is loop invariant?

             Answer : loop invariant is an invariant used to prove properties of loops 
                             and, by extension, algorithms employing loops (usually correctness). 
                             Informally, a loop invariant is a statement of the conditions that 
                             should be true on entry into a loop and that are guaranteed to 
                             remain true on every iteration of the loop. This means that on
                             exit from the loop both the loop invariant and the loop 
                             termination condition can be guaranteed.

Problem Sets

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

     Answer:  -Syntax error is an error that caused due to missing or misspelling 
                        when writing a function.
                        i.e.  printf("Error")
                              the example above is missing a semicolon which caused  
                              syntax error.
                      -  Semantic error is a logical error due to wrong logical statement.
                          i.e. pi = 1.52
                                it's wrong because pi is constant value of 3.14
                            

3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of 

     operator + and operator *.

     Answer:

<assign> → <id> = <expr> 

 <id> → A | B | C 

<expr> → <expr> – <term>׀ <term>

<term> → <term> / <factor>׀ <factor>

 <factor> → ( <expr> )׀ <id> 

4. Rewrite the BNF of example 3.4 to add the += and *= operator of java.

      Answer : 

<assign> → <id> = <expr> 

 <id> → A | B | C 

<expr> → <expr> += <term>׀ <term>

<term> → <term> *= <factor>׀ <factor>

 <factor> → ( <expr> )׀ <id> 

6. Use the grammar in example 3.2,show a parse tree for each of the following statements.

     Answer: 

• A=A *(B*(C+A))

• B=C *(A+C *B)

• A = A+(B*(C))

7. Using the grammar in example 3.4 , show a parse tree for each of
       the following statement

       Answer :

•      A=(A*B)+C

• A = B*C +A

• A=A+(B*C)

• A=B*(C+(A*B))

8.Prove that the following grammar is ambiguous :

   <S> -> <A>

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

   <id>->x|y|z

   Answer : 
   The grammar above is ambiguous because it can has 2 distinct parse.

10. Describe, in english, the language defined by the following grammar:

   <S> -> <X><Y>

   <X>->x<X>|x

   <Y>->y<Y>|y

Answer : <S> is the start symbol ,in the start symbol exist 2 string of <X> and <Y>.
                 The string <X> can be replaced with x<X> or with x.The same can be done 
                 with string <Y>.The output may be like this xxxyyy or xy , but the output 
                 cannot be xyxy.