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.

Chapter 4 Concepts of Programming Languages, Robert W. Sebesta.  Lexical and Syntax Analysis

Nama : Billy
NIM   : 1801374785

Review Question:
6. 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.

7. Why are character classes used, rather than individual characters, for the
letter and digit transitions of a state diagram for a lexical analyzer?

A state transition diagram, or just state diagram , is a
directed graph

8. What are the two distinct 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.

9. 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
10. Describe the parsing problem for a top-down parser.

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.

Problem Set: 
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. aAcccbbc

b. AbcaBccb

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

Stack Input Action
0 id * (id + id) $ Shift 5
0id5 * (id + id) $ Reduce 6 (Use GOTO[0, F])
0F3 * (id + id) $ Reduce 4 (Use GOTO[0, T])
0T2 * (id + id) $ Reduce 2 (Use GOTO[0, E])
0T2*7 (id + id) $ Shift 7
0T2*7(4 id + id ) $ Shift 4
0T2*7(4id5 + id ) $ Shift 5
0T2*7(4F3 + id ) $ Reduce 6 (Use GOTO[4, F])
0T2*7(4T2 + id ) $ Reduce 4 (Use GOTO[4, T])
0T2*7(4E8 + id ) $ Reduce 2 (Use GOTO[4, E])
0T2*7(4E8+6 id ) $ Shift 6
0T2*7(4E8+6id5 ) $ Shift 5
0T2*7(4E8+6F3 ) $ Reduce 6 (Use GOTO[6, F])
0T2*7(4E8+6T9 ) $ Reduce 4 (Use GOTO[6, T])
0T2*7(4E8 ) $ Reduce 1 (Use GOTO[4, E])
0T2*7(4E8)11 $ Shift 11
0T2*7F10 $ Reduce 5 (Use GOTO[7, F])
0T2 $ Reduce 5 (Use GOTO[0, T])
0E1 $ Reduce 2 (Use GOTO[0, E])
–ACCEPT–

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.

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