Source:
Concepts of Programming Languages, Robert W. Sebesta.
Chapter 4: Lexical and Syntax Analysis, page 199-201
By:
Name : Helena Natanael
NIM : 1801380333
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. The arcs are labeled with the input characters that cause the transitions among the states. An arc may also include actions the lexical analyzer must perform when the transition is taken.
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 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.
8. What are the two distinct goals of syntax analysis?
There are two distinct goals of syntax analysis.
First, the syntax analyzer must check the input program, whether it's syntactically correct or not, and if an error is found, the analyzer must create a diagnostic message. However, the syntax analyzer must create an error list because it's possible to find many errors during a single analysis of the input program. So when it finds an error, it saves the diagnostic message and go on checking. If it is not done well, error recovery may create more errors, or at least more error messages.
Second, it has to produce a complete parse tree, or at least trace the structure of the complete parse tree, for syntactically correct input. The parse tree (or its trace) is used as the basis for translation.
9. Describe the differences between top-down and bottom-up parsers.
The difference is in the making of parsers.
Top-down: the tree is built from the root downward to the leaves
Bottom-up: the tree is built from the leaves upward to the root.
10. Describe the parsing problem for a top-down parser.
I usually use the bottom-up parsers, and I rarely use top-down parser, because it takes more concern and focus to make it correctly, there's bigger chance of bad parsing or skipped leaves in top-down parser. It also would be confusing if it comes to bad grammar/ambiguous grammar.
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
S → AbB → aBBbB → aAcBbB → aAccBbbB → aAcccbbc
b. AbcaBccb
S → AbB → AbcBb → AbcAcb → AbcaBBcb → AbcaBccb
c. baBcBbbc
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.
By:
Name : Helena Natanael
NIM : 1801380333
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. The arcs are labeled with the input characters that cause the transitions among the states. An arc may also include actions the lexical analyzer must perform when the transition is taken.
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 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.
8. What are the two distinct goals of syntax analysis?
There are two distinct goals of syntax analysis.
First, the syntax analyzer must check the input program, whether it's syntactically correct or not, and if an error is found, the analyzer must create a diagnostic message. However, the syntax analyzer must create an error list because it's possible to find many errors during a single analysis of the input program. So when it finds an error, it saves the diagnostic message and go on checking. If it is not done well, error recovery may create more errors, or at least more error messages.
Second, it has to produce a complete parse tree, or at least trace the structure of the complete parse tree, for syntactically correct input. The parse tree (or its trace) is used as the basis for translation.
9. Describe the differences between top-down and bottom-up parsers.
The difference is in the making of parsers.
Top-down: the tree is built from the root downward to the leaves
Bottom-up: the tree is built from the leaves upward to the root.
10. Describe the parsing problem for a top-down parser.
I usually use the bottom-up parsers, and I rarely use top-down parser, because it takes more concern and focus to make it correctly, there's bigger chance of bad parsing or skipped leaves in top-down parser. It also would be confusing if it comes to bad grammar/ambiguous grammar.
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
S → AbB → aBBbB → aAcBbB → aAccBbbB → aAcccbbc
Phrases: aAcccbbc, aAcccb, Ac, ccb, c, c.
Simple Phrases: Ac, c, c
Handle: Ac
b. AbcaBccb
S → AbB → AbcBb → AbcAcb → AbcaBBcb → AbcaBccb
Phrases: AbcaBccb, caBccb, aBcc, aBc,
c
Simple Phrases: c
Handle: c
c. baBcBbbc
S → bAc → baBBc → baBcBbc → baBcBbbc
Phrases: baBcBbbc, aBcBbb, aBcBb, cBb.
Simple Phrases: cBb
Handle: cBb
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> ‘}’
No comments:
Post a Comment