Assignment 4

Pada post kali ini, saya akan menjawab pertanyaan-pertanyaan Assignment #4 dari Chapter 4, dari buku "Concepts of Programming Languages" karya Robert W. Sebesta.

Review Questions

        1.  What is a state transition diagram ?
A state transition diagram, or just state diagram, is a directed graph. The
nodes of a state diagram are labeled with state names. The arcs are labeled with
the input characters that cause the transitions among the states.

        2. Why are character classes used, rather than individual characters, for the letter and digit transitions of a state diagram for a lexical analyzer ?
Suppose we need a lexical analyzer that recognizes only arithmetic expressions,
including variable names and integer literals as operands. Assume that
the variable names consist of strings of uppercase letters, lowercase letters, and digits but must begin with a letter. Names have no length limitation. The first
thing to observe is that there are 52 different characters (any uppercase or lowercase letter) that can begin a name, which would require 52 transitions from the transition diagram’s initial state. However, a lexical analyzer is interested only in determining that it is a name and is not concerned with which specific name it happens to be. Therefore, we define a character class named LETTER
for all 52 letters and use a single transition on the first letter of any name.

        3. What are two distict goals of syntax analysis ?

To detect syntax errors in a given program and to proccedure a parse tree, or possibly only the information required to build such a tree, for given program.

        4. Describe the differences between top-down and bottom-up parsers ? 

Syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree is built from the root downward to leaves.
bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order which mean the parse tree is built from leaves upward to the root.

        5. Describe the parsing problem for a top-down parser. 

The general form of a left sentential form is xAy, whereby our notational conventions x is a string of terminal symbols, A is a nonterminal, and y is a mixed string. Because x contains only terminals, A is the leftmost nonterminal in the sentential form, so it is the one that must be expanded to get the next sentential form in a left- most derivation. Determining the next sentential form is a matter of choosing the correct grammar rule that has A as its LHS.

Problem Sets

        6. 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→AbB | bAc A→Ab | aBB B→Ac | cBb | c a. 

a. aAcccbbc
b. AbcaBccb
c. baBcBbbc

a. S -> AbB -> aBBbB -> aAcBbB -> aAccBbbB -> aAcccbbc
b. S -> AbB -> AbcBb -> AbcAcb -> AbcaBBcb -> AbcaBccb
c. S -> bAc -> baBBc -> baBcBbc -> baBcBbbc

        7. Show a complete parse, including the parse stack contents, input string, and action for the string id * (id + id) , using the grammar and parse table in Section 4.5.3.

        8. Show a complete parse, including the parse stack contents, input string, and action for the string (id + id) * id, using the grammar and parse table in Section 4.5.3.

        9. Write an EBNF rule that describes the while statement of Java or C++. Write the recursive-descent subprogram in Java or C++ for this rule.

<while_stmt> -> WHILE ‘(‘ (<arith_expr> | <logic_expr>) ‘)’ <block> <block> -> <stmt> | ‘{‘ <stmt> {<stmt>} ‘}’

        10. Write an EBNF rule that describes the for statement of Java or C++. Write the recursive-descent subprogram in Java or C++ for this rule.

Assume the following non-terminals are given: <type>, <id>, <literal>, <assign>, <expr>, and <stmt_list>.

<for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr> {, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’