CHAPTER 5

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER5

- REVIEW QUESTION

11. What are the advantages and disadvantages of dynamic type binding?
Answer :
Advantages: flexibility and no definite types declared(PHP, JavaScript).

Disadvantages: adds to the cost of implementation and type error detection by the compiler is difficult.



12. Define static, stack-dynamic, explicit heap-dynamic, and implicit heap- dynamic variables. What are their advantages and disadvantages?
Answer :
- 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.
Answer :
 - 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 con- nected to its definition?
Answer :
 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?
Answer :
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
Answer :
Sum Of Sales is the most readable. It is because it’s doesn’t have any problem with case sensitive, because the following identifier doesn’t use any caps lock.


2. Some programming languages are typeless. What are the obvious advan- tages and disadvantages of having no types in a language?
Answer :
- Advantages : allow users to write sloppy programs faster.
- Disadvantages : cannot control the data and variables, compiler cannot detect any mistakes.


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.
Answer :
(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 vari- ables. Explain this relationship.
Answer :
 Implicit heap-dynamic variables acquire types only when assigned value, which must be at runtime. Therefore, this variable are always dynamically bound to types.


5. Describe a situation when a history-sensitive variable in a subprogram is useful.
Answer :
To describe a situation when a history-sensitive variable in a subprogram is useful, suppose that a FORTRAN subroutine is used to implement a data structure as an abstraction. In this situation, it is essential that the structure persists between different calls to the managing subroutine.

CHAPTER 4

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER 4

- REVIEW QUESTION
11. Describe the parsing problem for a bottom-up parser.
      Answer :


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


13. Why are named constants used, rather than numbers, for token codes?
      Answer :
      - 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.
      Answer :
     -A recursive-descent subprogram for a rule with a single RHS is relatively
      simple. For each terminal symbol in the RHS, that terminal symbol is compared
      with nextToken. 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 nonterminal is called.


15. Explain the two grammar characteristics that prohibit them from being used as the basis for a      top-down parser.
      Answer : Two grammar characteristics that prohibit top-down parsing:
                      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
Answer :
 (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
Answer :
 a. FIRST(aSb)=a
    FIRST(bAA)=b
b. FIRST(b{aB}) = b
    FIRST (a) = a
c. FIRST(aB)=a
    FIRST(a) = a



3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c.
Answer :

a + b * c
Call lex /* returns a */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns + */
Exit <factor>
Exit <term>
Call lex /* returns b */
Enter <term>
Enter <factor>
Call lex /* returns * */
Exit <factor>
Call lex /* returns c */
Enter <factor>
Call lex /* returns end-of-input */
Exit <factor>
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).
Answer :
 call lex      // return a
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return *
            exit <factor>
          call lex      // return (
            enter <factor>
          call lex      // return b
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return +
            exit <factor>
            exit <term>
          call lex      // return c
            enter <term>
            enter <factor>
          call lex      // return )
            exit <factor>
            exit <term>
            exit <expr>
          call lex      // return 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 bBA    A→ab aAB    B→aB b
a. aaAbb
b. bBab
c. aaAbBb
Answer :
 
 

CHAPTER 3

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER 3

- REVIEW QUESTION

11. How is the order of evaluation of attributes determined for the trees of a
      given attribute grammar?
      Answer : Expr → Expr + Term
                     Expr → Term
                     Term → Term * Factor
                     Term → Factor
                     Factor → "(" Expr ")"
                     Factor → integer

12. What is the primary use of attribute grammars?
      Answer : An attribute grammar is an extension to a context-free grammar. The primary purpose                          of an attribute grammar is it allows certain language rules to be described, such as type                        of compatibility. An attribute grammar is a formal way to define attributes for the                                productions of a formal grammar, associating these attributes to values. The evaluation                        occurs in the nodes of the abstract syntax tree, when the language is processed by some                        parser or compiler.


13. Explain the primary uses of a methodology and notation for describing
      the semantics of programming languages.
      Answer : Object modeling techniques and notations presents a methodology using a completely                          different diagrams with other techniques commonly used for data modeling and process                      modeling.


14. Why can machine languages not be used to define statements in operational
      semantics?
      Answer : Machine language can not be used to define statements in operational semantics                                  because of some problems. First, the individual steps in the execution of machine
                     language and the resulting changes to the state of the machine are too small and too                              numerous. Second, the storage of a real computer is too large and complex.


15. Describe the two levels of uses of operational semantics.
      Answer : There are different levels of uses in operational semantics. At the highest level, the                               focus is on the final result of the execution of a program, this is sometime 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.




- 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
     Answer : None of those are the language generated by the grammar, it should be k<A>aj<B>b,(A                     contains b and B contains a) in which the end will be a single b, the list of answer does                         not include an answer that ends with a single b


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
     Answer : No one of the following statements are generated.


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.
      Answer : <S> => a<S>bb  | abb


14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from
      the grammar of Problem 13.
      Answer :  We  first derive a grammar in order to know how to draw the tree.

                     <stmt> -> <A>

                    <A> -> a<A>b | ab

                    tree for aabb

                    tree for aaaabbbb


15. Convert the BNF of Example 3.1 to EBNF.
      Answer : <program> -> begin <stmt_list> end

            .       <stmt_list> -> stmt[stmt_list]

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

            .       <var> -> A| B | C

CHAPTER 2

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER 2

- REVIEW QUESTION

11. What control flow statements were added to Fortran IV to get Fortran
      77?
      Answer : Character string handling, logical loop control statement and an if without an optional                           else clause were added to Fortran IV to get Fortran 77.


12. Which version of Fortran was the first to have any sort of dynamic
      variables?
      Answer : Fortran 90 is the first version of Fortran which support dynamic variables.


13. Which version of Fortran was the first to have character string handling?
      Answer : The first version of Fortran supporting character string handling is Fortran 77.


14. Why are linguists interested in artificial intelligence in the late 1950s?
      Answer : Because they were concerned with natural language processing, when in 1950’s, there                         are only computers with computation based on numeric data in arrays.


15. Where was LISP developed? By whom?
      Answer : It 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?
      Answer : 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.
      Answer : 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?
      Answer :
                    -   PL/I included the best of ALGOL 60 (recursion and block structure), FORTRAN                                  IV (separate compilation with communication through global data), and COBOL                                  (data structures, input/output, and report generating facilities), along with a few                                    new constructs

                    -   PL/I was the first language to have programs allowed to create concurrently executing                         tasks, the possibility to detect and handle 23 different types of exceptions, procedures                           allowed to be use recursively, pointers included as a data type, and reference to the                               cross sections of arrays

14. What are the arguments both for and against the idea of a typeless language?
      Answer : 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?
      Answer : Yes there are some non procedural languages other than Prolog, for example, Visual                             Basic, SQL.
                      -FORTRAN
                      -LISP
                      -ALGOL 60