Assignment #7
Pengajar : Tri Djoko Wahjono

Review Question :
11. What is an overloaded operator?
=> An overloaded operator if use of an operator for more than one
              purpose.

12. Define narrowing and widening conversions.
=>Narrowing conversion is one that converts an object to a type that
             cannot include all of the values of the original type, example: float
             to int. Widening conversions is one in which an object is converted
             to a type that can include at least approximations to all of the
             values of the original type, example: int to float.

13. In JavaScript, what is the difference between == and ===?
=> “==”  means  equal,
But “===”  means  same type and equal.

14. What is a mixed-mode expression?
=>Mixed-mode expression is one that has operands of different types.

15. What is referential transparency?
=>Referential transparency is a property whereby an expression
            can be replaced by its value without affecting the program.

Problem Set :

11. Write a BNF description of the precedence and associativity rules
      defined for the expressions in Problem 9. Assume the only operands are
      the names a,b,c,d, and e.
=> Assume the only operands are the names a, b, c, d, and e.
<expr> → <expr> or <e1> | <expr> xor <e1> | <e1>
<e1> → <e1> and <e2> | <e2>
<e2> → <e2> = <e3> | <e2> /= <e3> | <e2> < <e3>
| <e2> <= <e3> | <e2> > <e3> | <e2> >= <e3>  | <e3>
<e3> → <e4> <e4> → <e4> + <e5> | <e4> – <e5> | <e4> & <e5>  | <e4> mod <e5> | <e5>
<e5> → <e5> * <e6> | <e5> / <e6> | not <e5>  | <e6>
<e6> → a | b | c | d | e | const | ( <expr> )

12. Using the grammar of Problem 11, draw parse trees for the expressions of Problem 9.
=>

13. Let the function fun be defined as
      int fun(int *k) {
      *k += 4;
      return 3 * (*k) - 1;
      }
      Suppose fun is used in a program as follows:
      void main() {
      int i = 10, j = 10, sum1, sum2;
      sum1 = (i / 2) + fun(&i);
      sum2 = fun(&j) + (j / 2);
      }
     What are the values of sum1 and sum2
     a. if the operands in the expressions are evaluated left to right?
     b. if the operands in the expressions are evaluated right to left?
=> (a) (left -> right) sum1 is 46; sum2 is 48
(b) (right -> left) sum1 is 48; sum2 is 46

14. What is your primary argument against (or for) the operator precedence rules of APL?
=>  I think the operator precedence rules of the common imperative
              languages are nearly all the same, because they are based on those
              of mathematics.

15. Explain why it is difficult to eliminate functional side effects in C.
=>  There’s one reason functional side effects would be difficult to
              remove from C is that all of C’s subprograms are functions,
              providing the ability of returning only a single data value (though
              it could be an array). The problem is that in many cases it is
              necessary (or at least convenient) to return more than one data
              value, which is done through the use of pointer actual parameters,
              which are a means of creating functional side effects

ASSIGNMENT  #6

Pengajar : Tri Djoko Wahjono

Review Question :

11. How does JavaScript support sparse arrays?

       =>Javascript objects are sparse, and arrays are just specialized 

           objects with an auto-maintained length property (which is 

           actually one larger than the largest index, not the number of 

           defined elements) and some additional methods.

12. What languages support negative subscripts?

       => Ruby and Lua support negative subscripts.

13. What languages support array slices with stepsizes?

       =>Ruby, Python, Perl.

14. What array initialization feature is available in Ada that is not 

      available in other common imperative languages?

       =>Ada provides two mechanisms for initializing arrays in the 

           declarations statements : by listing them the order in which 

           they are to be stored, or by directly assigning them to an index 

           position using the => operator, which in Ada is called an arrow.

15. What is an aggregate constant?

       =>A parenthesized lists of values.

Problem Set :

11.  In the Burroughs Extended ALGOL language, matrices are stored 

       as single-dimensioned array of pointers to the rows of the matrix, 

       which are treated as single-dimensioned arrays of values. What 

       are the advantages and disadvantages of such a scheme?

       =>The advantage of this scheme is that accesses that are done in 

           order of the rows can be made very fast; once the pointer to a 

           row is gotten, all of the elements of the row can be fetched very 

           quickly. If, however, the elements of a matrix must be 

           accessed in column order, these accesses will be much slower; 

           every access requires the fetch of a row pointer and an address 

           computation from there. Note that this access technique was 

           devised to allow multidimensional array rows to be segments in 

           a virtual storage management technique. Using this method, 

           multidimensional arrays could be stored  and manipulated that 

           are much larger than the physical memory of the computer.

12.  Analyze and write a comparison of C’s malloc and free functions 

       with C++’s new and delete operators. Use safety as the primary 

       consideration in the comparison.

       =>New and Delete is a safe type. Malloc can return void value
            to pointer access which is  appropriate. New return pointer 
            type with itself. And for malloc, you must tell it how many bite
            to allocate it. New will produce that value its self.

13.  Analyze and write a comparison of using C++ pointers and Java 

       reference variables to refer to fixed heap-dynamic variables. Use 

       safety and convenience as the primary considerations in the 

       comparison.

       => In c and C++ pointer can be use the same way as addresses. 

            This design offer no solutions to the dangling pointer or lost 

            heap-dynamic variable problems. Reference types, such as 

            those in Java and C#, provide heap management without the 

            dangers of pointers. so its clear that Java has more safety for 

            the heap-dynamic variables.

14. Write a short discussion of what was lost and what was gained in 

      Java’s designers’ decision to not include the pointers of C++.

       => With Java, however, there’s a lot of those same programmers 

             felt that the security that was gained was offset by the 

            decreases in speed and the fact that a lot of the earlier JIT 

            compilers were pretty pokey didn't help that. For all their 

            faults, Sun's been pretty adamant about listening to the 

            community so they've made a lot of improvements regarding 

            in-place optimization, HotSpot, conditional compilation, etc. 

15. What are the arguments for and against Java’s implicit 

       heap storage recovery, when compared with the explicit heap 

       storage recovery required in C++? Consider real-time systems.

       => Implicit eliminates the creation of dangling pointers. Disadv: 

            cpu-time to do recovery, sometimes when there’s plenty of 

            heap storage so recovery isn’t necessary.

Assignment #5

Pengajar : Tri Djoko Wahjono

Review Question :

11.   What are the advantages and disadvantages of dynamic type binding?

         =>

         The advantage is flexibility (generic program units).

12. Define static, stack-dynamic, explicit heap-dynamic, and implicit 

      heap-dynamic variables.What are their advantages and disadvantages?

         =>

Static: bound to memory cells before execution begins and remains bound to the same memory cell throughout the execution.

Stack-dynamic: storage bindings are created for variables when their declaration statements are elaborated.

Explicit heap-dynamic: allocated and deallocated by explicit directives, specified by the programmer, which take effect during execution.

Implicit heap-dynamic variables: Allocation and deallocation caused by assignment statements.

13. Define lifetime, scope, static scope, and dynamic scope.

      =>

      Lifetime: A time during which the variable is bound to a specific memory location. The lifetime begins when it is bound to a specific cell and ends when it is unbound from that cell.

      Scope: The range of statements in which the variable is visible. A variable is visible in a statement if it can be referenced in that statement.

      Static scope: is based on program text and to connect a name reference to a variable , you (or the compiler) must find the declaration.

      Dynamic scope: Based on calling sequences of program units, not their textual layout (temporal versus spatial). References to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point.

14. How is a reference to a nonlocal variable in a static-scoped program 

      connected to its definition?

       =>   A reference to a non-locally variable in a static-scoped language with nested subprograms requires a two step access process:

1. Find the correct activation record instance

2. Determine the correct offset within that activation record instance

15. What is the general problem with static scoping?

         => Usually too much access. Scope structure destroyed as program 

               evolves.

Problem  Set :

1. Which of the following identifier forms is most readable? Support your 

    decision.

      sumOfSales

   sum_of_sales

   SUMOFSALES

     => I'm choose sum_of_sales, because it's easier to see the spaces 

          between words and easier to read.

2. Some programming languages are typeless. What are the obvious 

    advantages and  disadvantages of     having no types in a language.

=>

* Advantages : allow users to write sloppy programs faster.

     * Disadvantages : cannot control the data and variables, compiler cannot detect any mistake.

3. Write a simple assignment statement with one arithmetic operator in some language you know. For each component of the statement, list the various bindings that are required to determine the semantics when the statement is executed. For each binding, indicate the binding time used for the language.

=> (C++)

int count;count = count + 5;

Possible types for count: set at language design time. Type of count: bound at compile time.
Set of possible values of count: bound at compiler design time. Value of count: bound at execution time with this statement. Set of possible meanings for the operator symbol ““:*bound at language definition time.*Meaning of the operator symbol “” in this statement: bound at compile time.
Internal representation of the literal “5”: bound at compiler design time.

4. Dynamic type binding is closely related to implicit heap-dynamic 

    variables. Explain this relationship.
    => Both are related to the assignment and the statement.

5. Describe a situation when a history-sensitive variable in a subprogram is
    useful.

    =>History sensitive variables may be useful in data manipulation 

        subprograms, where some operation is performed on a variable, and 

        the function exits, then the function is called again. This way, 

        the function doesn't have to take the variable as a parameter, but only
        to return it.

Assignment #4

Pengajar : Tri Djoko Wahjono

Review Question :

11. Describe the parsing problem for a bottom-up parser.

         =>

         The process of bottom-up parsing produces the reverse of a 
         rightmost derivation. So, in the example derivation, a bottom-up
         parser starts with the last sentential form (the input sentence) and
         produces the sequence of sentential forms from there until all that
         remains is the start symbol, which in this grammar is E. In each step,
         the task of the bottom-up parser is to find the specific RHS, the
         handle, in the sentential form that must be rewritten to get the next
         (previous) sentential form. As mentioned earlier, a right sentential
         form may include more than one RHS. For example, the right
         sentential form.

        

12. Explain why compilers use parsing algorithms that work on only a 
      subset of all grammars.

         =>

         Because  O(n3) algorithms are normally not useful for 
         practical processes, such as syntax    analysis for a compiler, because
         they are far too slow. In situations such as this, computer scientists
         often search for algorithms that are faster, though less general.
         Generality is traded for efficiency. In terms of parsing, faster
         algorithms have been found that work for only a subset of the set of
         all possible grammars. These algorithms are acceptable as long as the
         subset includes grammars that describe programming languages.

13.Why are named constants used, rather than numbers, for token codes?

      =>

      Because it’s for the sake of readability of lexical and syntax analyzers.

14.Describe how a recursive-descent parsing subprogram is written for a 

     rule with a single RHS.

      =>

      A recursive-descent subprogram for a rule with a single RHS is relative
      simple. For each terminal symbol in the RHS, that terminal symbol is
      compared with next Token. If they do not match, it is a syntax error. If
      they match, the lexical analyzer is called to get the next input token.
      For each non terminal, the parsing subprogram for that non terminal
      is called.

15. Explain the two grammar characteristics that prohibit them from being

      used as the basis for a top-down parser.

        =>  Direct or indirect Left Recursion.

Problem Set :

1. Perform the pairwise disjointness test for the following grammar rules.

    a. A → aB | b | cBB
    b. B → aB | bA | aBb
    c. C→ aaA | b | caB

    =>
   (a) FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test
   (b) FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test
   (c) FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test

2. Perform the pairwise disjointness test for the following grammar rules.
     a. S→ aSb | bAA
     b. A → b{aB} | a
     c. B → aB | a

     =>
      S→ aSb | bAA

     first(aSb) = a

     first(bAA) = b

     are not intersected, the rule passes

     A → b{aB} | a

     first(b{aB}) = b

     first(a) = a

     are not intersected, the rule passes

     B → aB | a

     first(aB) = a

     first(a) = a

     They are intersected the rule fails the test.



3. Show a trace of the recursive descent parser given in Section 4.4.1 for
     the string a + b * c.
     Consider the following EBNF description of simple arithmetic 

     expressions:
     <expr> → <term> {(+ | -) <term>}
     <term> → <factor> {(* | /) <factor>}
     <factor> → id | int_constant | ( <expr> )
      =>

     Next token is: 10 Next lexeme is a
     Enter <expr>
     Enter <term>
     Enter <factor>

     Next token is: 21 Next lexeme is +
     Exit <factor>
     Exit <term>

     Next token is: 10 Next lexeme is b
     Enter <term>
     Enter <factor>

     Next token is: 10 Next lexeme is *
     Exit <factor>

     Next token is: 26 Next lexeme is c
     Enter<factor>

     Next token is: -1 Next lexeme is EOF
     Exit <term>
     Exit <expr>


4. Show a trace of the recursive descent parser given in Section 4.4.1 for
     the string a * (b + c).

     => 

     Next token is: 10 Next lexeme is a
     Enter <expr>
     Enter <term>
     Enter <factor>

     Next token is: 21 Next lexeme is *
     Exit <factor>

     Next token is: 25 Next lexeme is (
     Enter <factor>

     Next token is: 10 Next lexeme is b
     Enter <expr>
     Enter <term>
     Enter <factor>

     Next token is: 21 Next lexeme is +
     Exit <factor>

     Next token is: 26 Next lexeme is c
     Enter <factor>

     Next token is: 26 Next lexeme is )
     Exit <term>
     Exit <expr>

     Next token is: -1 Next lexeme is EOF
     Exit <factor>
     Exit <term>
     Exit <expr>

5.  Given the following grammar and the right sentential form, draw a parse
      tree and show the phrases and simple phrases, as well as the handle.
      S → aAb [1] bBA A → ab [1] aAB B → aB [1] b
      a. aaAbb

      b. bBab

      c. aaAbBb

      => 

      

         and for c. it's  doesn't have a answer.

Assignment #3

Pengajar : Tri Djoko Wahjono

Review Question :

11. How is the order of evaluation of attributes determined for the trees of a 

      given attribute grammar?

       =>Now, consider the process of computing the attribute values of 

            a parse tree, which is sometimes called decorating the parse 

            tree. If all attributes were inherited, this could proceed in a 

            completely top-down order, from the root to the leaves. 

            Alternatively, it could proceed in a completely bottomup order, 

            from the leaves to the root, if all the attributes were synthesized. 

            Because our grammar has both synthesized and inherited 

            attributes, the evaluation process cannot be in any single direction. 

           The following is an evaluation of the attributes, in an order in 

           which it is possible to compute them:

                1. <var>.actual_type ← look-up(A) (Rule 4)

                2. <expr>.expected_type ← <var>.actual_type (Rule 1)

                3. <var>[2].actual_type ← look-up(A) (Rule 4)

                    <var>[3].actual_type ← look-up(B) (Rule 4)

                4. <expr>.actual_type ← either int or real (Rule 2)

                5. <expr>.expected_type == <expr>.actual_type is either

                     TRUE or FALSE (Rule 2)

12. What is the primary use of attribute grammars?

       =>to describe both the syntax and the static semantics of programs. 

           Attribute grammars are a formal approach both to describing and 

           checking the correctness of the static semantics rules of a program.

13. Explain the primary uses of a methodology and notation for 

      describing the semantics of programming languages.

      => To describing syntax because it will help programer  to 

            know precisely what the statements of a language do before they 

            can use them effectively in their programs and  If there were a 

            precise semantics specification of a programming language, 

            programs written in the language potentially could be proven 

            correct without testing.

14. Why can machine languages not be used to define statements in 

       operational semantics?

       =>because machine language is too low-level to be easily Understood.

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

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

Problem Set :

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. 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
                One or more b's followed by One a followed by One or more a's 

                followed  by a b which is the same as One or more b's followed 

                by Two a's followed by a b Which matches a and d 

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

       b. acccbd

       c. acccbcc

       d. acd

       e. accc

         => <A> generates one or more c's
              <B> will generate either One d or a string of one or more c's
               So S will generate
               a  <S>  c   {d | c's} | c's | b
               which matches a and e

13. Write a grammar for the language consisting of strings that have n

       copies of the letter a followed by the same number of copies of the

       letter b, where n > 0. For example, the strings ab, aaaabbbb, and

       aaaaaaaabbbbbbbb are in the language but a, abb, ba, and aaabb are 

       not.

=>       S -> ab

                b ->bb

14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from

the grammar of Problem 13.

         =>

            

        

15. Convert the BNF of Example 3.1 to EBNF.

         =>  

         <program> -> begin <stmt_list> end

         .       <stmt_list> -> stmt[stmt_list]

         .       <stmt> -> <var> = <expressions>

         .       <var> -> A| B | C

     .       <expressions> -> <var> {(+|-)< var> }

Assignment #2
pengajar : Tri Djoko Wahjono, Ir, M.Sc

Review Question :

11. What control flow statements were added to Fortran IV to get Fortran 
       77?
     =>Logical loop control statements.

12. Which version of Fortran was the first to have any sort of dynamic 
       variables?
    => Fortran 99

13. Which version of Fortran was the first to have character string handling?
    =>Fortran 77

14. Why were linguists interested in artificial intelligence in the late 1950s?
    => Linguists were concerned with natural language processing.

15. Where was LISP developed? By whom?
    =>LISP was developed at MIT by John McCarthy

Problem Set :

11. Was IBM’s assumption, on which it based its decision to develop PL/I,

      correct, given the history of computers and language developments since

      1964?

      =>The assumption is correct because in that 1970’s, PL/I is widely      
           used for both business and scientific applications although it suffers 
           a lot in previous years and afterwards.

12. Describe, in your own words, the concept of orthogonality in 
      programming language design.

      => It appears that orthogonality means the simplicity of programming 
           constructs, or a minimal number of control and data structures in a 
           language. Each additional construct increases the complexity,
           removing orthogonality.

13. What is the primary reason why PL/I became more widely used than

      ALGOL 68?

=> PL/I included the best of ALGOL 60 (recursion and block structure), FORTRAN IV (separate       compilation with communication through global data), and COBOL (data structure input/output, and report generating facilities), along with a few new constructs.

14. What are the arguments both for and against the idea of a typeless

      language?

      => Arguments for are obvious flexibility and ease of use. Without having to define a data type the    programmer is free to develop code that is generated quickly and without much thought. Learning the language is much simpler because one doesn’t have to determine size or how the compiler will interpret the type later on, only what information must be included. Arguments against include data insecurity, such as the assignment of a character type ‘A’ that could in fact be “defined” as a HEX value by the programmer. The compiler would also have trouble interpreting floating point values compared to integers. The resulting arithmetic would also cause serious problems; like adding 5 + “happy” and how they are interpreted  different than perhaps the programmer intended.

15. Are there any logic programming languages other than Prolog?

      =>-FORTRAN
      -LISP
      -ALGOL 60

Assignment   #1

Due 2  oct  2014

Pengajar : Tri Djoko Wahjono, Ir, M.Sc.

Review Question :

      11. What primitive control statement is used to build more 

          complicated control statements i languages that lack them?

          Answer :

 The selection statement plus GOTO is used to build more complicated  control statements such as FOR loop.

    12. What construct of a programming language provides process 

         abstraction?

         Answer :

         Sub Program

    13. What does it mean for a program to be reliable?

         Answer :

         It’s mean a program can performs to its specifications under 

        all conditions.

    14. Why is type checking the parameters of a subprogram important?

         Answer :

         Because it can lead to lots of hard to debug errors.

    15. What is aliasing?

         Answer :

         aliasing is having two or more distinct names that can be used to 

         access the same  memory cell.

Problem Set :

   11. Describe some design trade-offs between efficiency and safety in 

        some language you know.

        Answer :

        In C language an element will continue in check so even if no 

        exception is made, it will break the C language itself would be safer 

        but the process is much longer because it continue to repeat and it’s 

        make c language take more time to process it.

   

   12. In your opinion, what major features would a perfect programming 

        language include?

        Answer :

        In my opinion Syntax, documentation, and error message are the

        most important features in a perfect programming language. 

    

   13. Was the first high-level programming language you 

       learned implemented with a pure interpreter, a hybrid implementation 

      system, or a compiler? (You may have to research this.)

       Answer :

       My first high-level programming language that  I learned is C++ which 

       is implemented with visual C++ and it is a compiler.

   14. Describe the advantages and disadvantages of some programming 

       environment you have used.

       Answer :

      C Language Advantages :

C Language has list of advantages due to this it is very much popular language around the world and best suitable for the programmer to learn at the fist stage of the programming.

(1). Procedure Oriented Language

C Language is procedure oriented language, Here user creates procedures or functions to execute their task.

(2). Lots of Libraries

C Language provides lots of functions which consist of system generated functions and user defined functions.

(3). Speed of Compilation

C compiler produces machine code very fast compared to other language compiler. C compiler can compile around 1000 lines of code in a seconds or two. One more benefit of the C Compiler is that it also optimize the code for faster execution.

(4). Easy to Learn (Syntax is near to English Language)

C Language syntax is very easy to understand. It uses keyword like if, else, goto, switch, goto, main, etc. This kind of keyword we all are using in our day to day life to convey meaning or to get some decisions. 

5. Portable 

C Language setup is around 3-5 MB. So you can carry this language in your Floppy Drive or Pen Drive. Its very easy to install and operate, Again its output is exe file which can be executed in any computer without any other framework / software.

C Language Disadvantages

Every coin has two sides, as C Language has also some disadvantages. C Language has not any major disadvantages but some features is missing in the C Language, obviously that's why C Language is very much powerful now. 

(1). Object Oriented Programming Features (OOPS)

Object Oriented Programming Features is missing in C Language, You have to develop your program using procedure oriented language only.

(2). Run Time Type Checking is Not Available

In C Language there is no provision for run time type checking, for example i am passing float value while receiving parameter is of integer type then value will be changed, it will not give any kind of error message.

(3). Namespace Feature

C does not provides namespace features, so you can't able to use the same variable name again in one scope. If namespace features is available then you can able to reuse the same variable name.

(4). Constructor and Destructor is not available

C does not provides object oriented features, so it don't have Constructor and Destructor features. Constructor and Destructor is used to construct object and destroy object. 

  15. How do type declaration statements for simple variables affect 

        the readability of a language, considering that some languages do not 

        require them?

        Answer :

       The use of type declaration statements for simple scalar variables may 

      have very little effect on the readability of programs. If a language 

      has no type declarations at all, it may be an aid to readability, because 

      regardless of where a variable is seen in the program text, its type 

      can be determined without looking elsewhere. Unfortunately, most 

      languages that allow implicitly declared variables also include explicit 

      declarations. In a program in such a language, the declaration of a 

      variable must be found before the reader can determine the type of that 

      variable when it is used in the program.