Chapter 4 : Lexical And Syntax Analysis

From Book : Concept Of Programming  Languages 
By : Robert W. Sebesta


REVIEW QUESTION :

16. What is the FIRST set for a given grammar and sentential form?
Answer :
FIRST( ) = {a => * a } (If => * , is in FIRST( ))
in which =>* means 0 or more derivation steps

17. Describe the pairwise disjointness test.

Answer : 

It is a test of non-left recursive grammar that indicates whether left recursion can be done. It requires the ability to compute a set based on the RHS of a given nonterminal symbol in a grammar.

18. What is left factoring ?

Answer : 

Left factoring is the action taken when a grammar leads backtracking while marking parsing.syntax tree.

Read More


19. What is a phrase of a sentential form ?

Answer :

A phrase is a subsequence of a sentential form that is eventually reduced to a single non-terminal

20. What is a simple phrases of a sentential form ?

Answer : 

Simple phrases is just a phrases that takes a single derivation step from it's root non-terminal node

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

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.
Answer :

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.
Answer :

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.
Answer :

<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.
Answer :

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> ‘}’