Chapter 4

Concept of Programming Languages by Robert W. Sebesta Answer

Review Questions

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

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

3. Define lexeme and token.

Lexeme is logical grouping that consists of collection of characters collected by lexical analyzer.   Token is internal code for categories of the lexeme

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

It serves as front end of a syntax analyzer.

6. What is a state transition diagram ?

State diagram is a directed graph whose nodes are labeled with state names.

8. What are the two distinct goals of syntax analysis ?

First, syntax analyzer must check the input program to determine whether it is syntactically correct. The second goal is to produce a complete parse tree, or at least trace the structure of the complete parse tree, for syntactically correct input.

7. Who developed the Speedcoding system for the IBM 701 ?

The language was developed by John Backus in 1953 for the IBM.

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

A top down parser builds from root downward to leaves, while bottom up parser builds from the leaves upward to the root

17. Describe the pairwise disjointness test.

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 RHSs of a given nonterminal symbol in a grammar.

18. What is left factoring ?

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

19. What is a phrase of a sentential form ?

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

Problem Set

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

A->aB|b|cBB
FIRST(aB)=a
FIRST(b)=b
FIRST(cBB)=c
They don’t intersect and pass the test

B-> aB|bA|aBb
FIRST(aB)=a
FIRST(bA)=b
FIRST(aBb)=a
They intersect and fail the test

C->aaA|b|caB
FIRST(aaA)=a
FIRST(b)=b
FIRST(caB)=c
They don’t intersect and pass the test

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

S->aSb|bAA
FIRST(aSb)=a
FIRST(bAA)=b
They don’t intersect and pass the test

A->b{aB} | a
FIRST(b{aB}) = b
FIRST (a) = a
They don’t intersect and pass the test

B->aB | a
FIRST(aB)=a
FIRST(a) = a
They intersect and do not pass the test

4. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a * (b + c)

call lex      // return a
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return *
            exit <factor>
          call lex      // return (
            enter <factor>
          call lex      // return b
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return +
            exit <factor>
            exit <term>
          call lex      // return c
            enter <term>
            enter <factor>
          call lex      // return )
            exit <factor>
            exit <term>
            exit <expr>
          call lex      // return EOF
            exit <factor>
            exit <term>
            exit <expr>