Assignment 4, Robert W.Sebesta , Chapter 4.

Lecturer: Tri Djoko Wahjono, Ir., M.Sc.

1. What are three reasons why syntax analyzers are based on grammars?

Answer:

 The most commonly used syntax description on syntax analyzers is context-free grammars or BNF. Using BNF, has at least three compelling advantages.

1. BNF descriptions of the syntax of programs are clear and concise, both for humans and for software systems.
2. BNF description can be used as the direct basis for the syntax analyzer.
3. Implementations based on BNF are relatively easy to maintain because of their modularity.



2. Explain the three reasons why lexical analysis is separated from syntax analysis.
Answer:
 1. Simplicity.
Techniques for lexical analysis are less complex than those required for syntax analysis, so the lexical-analysis process can be simpler if it is separate.

2. Efficiency.
Separation facilitates the optimization of lexical analyzer, because lexical analysis requires a significant portion of total compilation time.

3. Portability
Make the syntax analyzer to be platform independent from machine- dependent parts of the software system.



3. Define lexeme and token.

Answer:   

- Lexeme : Lowest level syntactic units.
   -Tokens : Category of lexemes.



4. What are the primary tasks of a lexical analyzer?

Answer:

 Lexical analyzers extract lexemes from a given input string and produce the corresponding tokens and then they detect syntactic errors in tokens.



5. Describe briefly the three approaches to building a lexical analyzer.

Answer:

These are three distinct approaches to construct a lexical analyzer:

1. Using a software tool to generate a table for a table-driven analyzer
2. Building such a table by hand
3. Writing code to implement a state diagram description of the tokens of the language being implemented.

Problem Set

1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
b. B → aB | bA | aBb
c. A → aaA | b | caB

=
a. FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test.

b. FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test.

c. FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test.

2. Perform the pairwise disjointness test for the following grammar rules.

a. S → aSB | bAA
b. A → b[aB] | a
c. B → aB | a

=
a. FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test.

b. FIRST(b{aB}) = {b}, FIRST (a) = {a}, passes the test.

c. FIRST(aB) = {a}, FIRST(a) = {a}, Fails the test.

3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c
=
a + b * c

Call lex /* returns a */

Enter <expr>

Enter <term>

Enter <factor>

Call lex /* returns + */

Exit <factor>

Exit <term>

Call lex /* returns b */

Enter <term>

Enter <factor>

Call lex /* returns * */

Exit <factor>

Call lex /* returns c */

Enter <factor>

Call lex /* returns end-of-input */

Exit <factor>

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)
a * (b + c)

=

Call lex /* returns a */

Enter <expr>

Enter <term>

Enter <factor>

Call lex /* returns * */

Exit <factor>

Call lex /* return (*/

Enter <factor>

Call lex /* returns b */

Enter <expr>

Enter <term>

Enter <factor>

Call lex /* returns + */

Exit <factor>

Exit <term>

Call lex /* returns c */

Enter <factor>

Exit <term>

Call lex / *return )*/

Exit <factor>

Exit <term>

Exit <expr>

Call lex /* returns end-of-input */

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.

parse tree =

S

/ | \

a A b

/|\

a A B

|

b

Handles = b, aAB

Phrases = aaAbb, aaABb, aAb

Simple Phrase = b

b.

parse tree =

S

/ | \

b B A

/ \

a b

Handles = ab

Phrases = bBab, bBA

Simple phrase = ab

c.aaAbBb = aSBb = aSBB = x