Pak Djoko : Chapter V

Review Questions

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

ANSWER:

Kelebihan dari dynamic type binding adalah lebih luwes dan mudah dalam menulis kode generik, sedangkan kekurangannya adalah perlu waktu run-time yang lama untuk mengecek tipe dan interpretasi.


12. Define static, stack-dynamic, explicit heap-dynamic, and implicit heap- dynamic variables. What are their advantages and disadvantages?

ANSWER:

Static adalah alokasi memori sebelum eksekusi dimulai dan tetap terikat pada memori yang sama di seluruh eksekusi.
Kelebihan: Run-time yang efisien.

Kekurangan: Tidak ada rekursi.

Stack-dynamic adalah alokasi memori dari sistem tumpukan ketika deklarasi diuraikan.
Kelebihan: Ada rekursi dan hemat memory.

Kekurangan: Run-time tidak seefisien static.

Explicit heap-dynamic adalah alokasi dan dealokasi dengan petunjuk eksplisit, yang ditentukan oleh programmer, yang berlaku selama eksekusi.
Kelebihan: Manajemen penyimpanan yang fleksibel.

Kekurangan: Rawan kesalahan dalam membuat pernyataan baru/menghapus pernyataan.

Implicit heap-dynamic adalah alokasi dan dealokasi disebabkan oleh suatu pernyataan.
Kelebihan: Fleksibilitas yang sangat tinggi.

Kekurangan: Waktu run-time untuk menjaga semua attrs dinamis dan deteksi kesalahan kompilator berkurang.

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

ANSWER:

Lifetime adalah ketika memori dialokasikan untuk sebuah variabel (ketika itu eksis).
Scope adalah jangkauan pernyataan di mana variabel yang terlihat. Variabel terlihat dalam sebuah pernyataan jika dapat dirujuk dalam pernyataan itu.
Static scope adalah scope yang berdasarkan teks pada program dan menghubungkan referensi nama untuk sebuah variabel.
Dynamic scope adalah scope yang berdasarkan urutan panggilan run-time.
14. How is a reference to a nonlocal variable in a static-scoped program connected to its definition?

ANSWER: Sebuah referensi untuk variabel non-lokal dalam bahasa static-scoped dengan nested subprogram membutuhkan 2 langkah proses akses:

Cari rekor aktivasi yang benar.
Menentukan offset yang benar dalam rekor aktivasi.
15. What is the general problem with static scoping?

ANSWER: Biasanya terlalu banyak akses. Struktur scope hancur sebagai evolusi program.

Problem Set

1. Which of the following identifier forms is most readable? Support your decision.
sumOfSales
sum_of_sales
SUMOFSALES

ANSWER: Saya memilih sum_of_sales, karena lebih mudah untuk melihat ruang antara kata-kata dan lebih mudah dibaca.

2. Some programming languages are typeless. What are the obvious advantages and  disadvantages of having no types in a language.

ANSWER:

Kelebihan: Memungkinkan pengguna untuk menulis program cepat.
Kekurangan: Tidak dapat mengontrol data dan variabel, compiler tidak dapat mendeteksi kesalahan apapun.

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: Bahasa C++

int count;
count = count + 5;

Tipe yang mungkin untuk dihitung: ditetapkan pada saat desain bahasa.
Tipe hitungan: Terikat pada waktu kompilasi.
Set nilai yang mungkin dari count: Terikat saat waktu desain kompiler.
Nilai hitungan: Terikat pada waktu eksekusi dengan pernyataan ini.
Set kemungkinan arti untuk simbol operator “”: *Terikat pada waktu definisi bahasa.
*Maksud dari simbol operator “” di dalam pernyataan ini: Terikat pada waktu kompilasi.
Representasi internal dari literal “5”: Terikat saat waktu desain kompiler.

4. Dynamic type binding is closely related to implicit heap-dynamic variables. Explain this relationship.

ANSWER: Keduanya terkait dengan tugas dan pernyataan.

Keduanya terkait dengan tugas dan pernyataan.

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

ANSWER: Sejarah variabel sensitif mungkin berguna dalam subprogram manipulasi data, di mana beberapa operasi dilakukan pada variabel, dan fungsi keluar, maka fungsi ini dipanggil lagi. Dengan cara ini, fungsi tidak harus mengambil variabel sebagai parameter, tetapi hanya untuk mengembalikannya.

Chapter 4

Review Questions

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

to find the substring of the current sentential form that must be reduced to its associated.

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

Parsing algorithms that work for any unambiguous grammar are complicated and inefficient. In fact, the complexity of such algorithms is O(n3), which means the amount of time they take is on the order of the cube of the length of the string to be parsed. This relatively large amount of time is required because these algorithms frequently must back up and reparse part of the sentence being analyzed. Reparsing is required when the parser has made a mistake in the parsing process. Backing up the parser also requires that part of the parse tree being constructed (or its trace) must be dismantled and rebuilt. 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.

13.Why are named constants used, rather than numbers, for token codes?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 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 nonterminal, 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.

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

A -> aB | b | CBB

first(aB) = a

first(b) = b

first(CBB) = aaA = a

B -> aB | ba | aBb

first(aB) = a

first(ba) = b

first(aBb) = a

They are intersected & thus the rule fails the test.

C -> aaA | b | caB

first(aaA) = a

first(b) = b

first(caB) = c

are not intersected & thus the rule passes

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

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 bBA A → ab aAB B → aB b
a. aaAbb
b. bBab
c. aaAbBb

a) aaAbb

Phrases: aaAbb, aAb, b

Simple phrases: b

Handle: b

b) bBab

Phrases: bBab, ab

Simple phrases: ab

Handle: ab

 c) aaAbBb (tidak ada jawaban)