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