Chapter 4 : Problem Set

Q6 : 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

A   :

a. S -> AbB -> aBBbB -> aAcBbB -> aAccBbbB -> aAcccbbc

b. S -> AbB -> AbcBb -> AbcAcb -> AbcaBBcb -> AbcaBccb

c. S -> bAc -> baBBc -> baBcBbc -> baBcBbbc

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

A   :

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

A   :

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

A   :

While :

while-statement <= while(expression) statement
do-statement     <= do statement while (expression);

Recursive-descent subprogram :

<initializer> -> "{" <designator> { <designator> } = <expression> "}"

Q10 : Write an EBNF rule that describes the for statement of Java or C++.

A     :  “for-statement <= for(;;) statement”

Chapter 4 : Review Question

Q6 : What is a state transition diagram?

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

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

A   : Suppose we need a lexical analyzer that recognizes only arithmetic expressions, including variable names and integer literals as operands. Assume that the variable names consist of strings of uppercase letters, lowercase letters, and digits but must begin with a letter. Names have no length limitation. The first thing to observe is that there are 52 different characters (any uppercase or lowercase letter) that can begin a name, which would require 52 transitions from the transition diagram’s initial state. However, 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.

Q8 : What are the two distinct goals of syntax analysis?

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

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

A   : Parsers are categorized according to the direction in which they build parse trees. The two broad classes of parsers are top-down, in which the tree is built from the root downward to the leaves, and bottom-up, in which the parse tree is built from the leaves upward to the root.

Q10 : Describe the parsing problem for a top-down parser.

A     :

1. Only judges grammaticality.

2. Stops when it finds a single derivation.

3. No semantic knowledge employed.

4. No way to rank the derivations.

5. Problems with left-recursive rules.

6. Problems with ungrammatical sentences.

Chapter 3 : Problem Set

Q6 : Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements:

a. A = A * (B + (C * A))

b. B = C * (A * C + B)

c. A = A * (B + (C))

A   :

a.                     A = A + (B + (C * A))       

  < assign >    = > <id> = <expr>

  = > A = <expr>

              = > A = <id> + <expr>

  = > A = A + <expr>

              = > A = A + ( <expr> )

  = > A = A + ( <id> + <expr> )

              = > A = A + ( B + <expr> )

              = > A = A + ( B + ( <expr> ) )

              = > A = A + ( B + ( <id> * <expr> ) )

              = > A = A + ( B + ( C * <expr> ) )

              = > A = A + ( B + ( C * <id> ) )

              = > A = A + ( B + ( C * A ) )

 

b.              B = C * (A * C + B)

     < assign >    = > <id> = <expr>

     = > B = <expr>

                 = > B = <id> + <expr>

     = > B = C + <expr>

                 = > B = C + ( <expr> )

     = > B = C + ( <id> + <expr> )

                 = > B = C + ( A * <expr> )

                 = > B = C + ( A * <id> + <expr> )

                 = > B = C + ( A * C + <expr> )

                 = > B = C + ( A * C + <id> )

                 = > B = C + ( A * C + B )

 

c.              A = A * (B + (C))

     < assign >    = > <id> = <expr>

     = > A = <expr>

                 = > A = <id> + <expr>

                 = > A = A * <expr>

                 = > A = A * (<expr> )

                 = > A = A * ( <id> + <expr> )

                 = > A = A * ( B + <expr> )

                 = > A = A * ( B + ( <expr> ) )

                 = > A = A * ( B + ( <id> ) )

                 = > A = A * ( B + ( C ) )

Q7 : Using the grammar in Example 3.4, show a parse tree and a leftmost derivation for each of the following statements:

a. A = ( A + B ) * C

b. A = B + C + A

c. A = A * (B + C)

d. A = B * (C * (A + B))

A   : word “4020hw1”

Q8 : Prove that the following grammar is ambiguous:

<S> → <A>

<A> → <A> + <A> | <id>

<id> → a | b | c

A   : A grammar is ambiguous if the same string has 2 different parse trees. Here are two distinct parse trees for  a + b + c .

              

        S                 S

        |                 |

        A                 A

      / | \             / | \

     A  +  A           A  +   A

     |   / | \       / | \    |

   <id> A  +  A     A  +  A  <id>

     |  |     |     |     |   |

     a <id>  <id>  <id>  <id> c

        |     |     |     |

        b     c     a     b

Q9 : Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.

A   :      <assign> -> <id> = <expr>

<id>  ->  A | B | C

<expr> -> <expr> + <term>

| <term>

<term> -> <term> * <factor>

| <factor>

<factor> -> ( <expr> )

| +<id> | -<id>

Q10 : Describe, in English, the language defined by the following grammar:

<S> → <A> <B> <C>

<A> → a <A> | a

<B> → b <B> | b

<C> → c <C> | c

A    : The LHS non-terminal S is defined as non-terminal A and non-terminal B and non-terminal C, where non-terminal A can be one or more a’s or one a, where non-terminal B can be one or more b’s or one b, and where non-terminal C can be one or more c’s or one c.

Chapter 3 : Review Question

Q6 : Define a left-recursive grammar rule.

A  : In the formal language theory of computer science, left recursion is a special case of recursion. In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.

Q7 : What three extensions are common to most EBNFs?

A   : The first of these denotes an optional part of an RHS, which is delimited by brackets. The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. The third common extension deals with multiple-choice options.

Q8 : Distinguish between static and dynamic semantics.

A   : We can distinguish between the static (external) world, representing the program text, which does not change, and the dynamic (internal) world, representing the hardware at run-time, which is where it all happens.

*Static objects are constructs (identifiers, statements, expressions etc.) in the text of the program, and have no meaningful existence beyond compile-time. 
*Dynamic objects are (instances of) values, locations and the like, which live and move and have their being inside the computer at run-time.

Q9 : What purpose do predicates serve in an attribute grammar?

A   : The use of predicates functions is to state the static semantic rules of the language.

Q10 : What is the difference between a synthesized and an inherited attribute?

A      : The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes. In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.

For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax.

Chapter 2 : Problem Set

Q6 : Make an educated guess as to the most common syntax error in LISP programs.

A    :

1. Semicolon (;) missing.

2. Unmatched parentheses.

3. Function prototype mismatch.

4. Undeclared variables.

Q7 : LISP began as a pure functional language but gradually acquired more and more imperative features. Why?

A    : The main reason why imperative features were put in LISP was to increase its execution efficiency.

Q8 : Describe in detail the three most important reasons, in your opinion, why ALGOL 60 did not become a very widely used language.

A   :

1. Excessive flexibility hurt ALGOL60 since languages that are difficult to learn were not as well received as languages with a more rigid structure.

2. Its association with BNF alienated the language as strange and complicated.

3. Lack of support from IBM, who was at the time the preeminent company for using computer languages.

Q9 : Why, in your opinion, did COBOL allow long identifiers when Fortran and ALGOL did not?

A    : COBOL is more of a reporting language than Fortran. Since Fortran handles calculations much better, there is not a real need for long identifiers. As a reporting language, COBOL uses long identifiers in tagging the source to the reports it is writing. Also, COBOL is the closest language to a fully, self documenting language, that it gets, and long identifiers provides one more case for it.

Q10 : Outline the major motivation of IBM in developing PL/I.

A     : The most important new developments were the following:

• The concept of block structure was introduced. This allowed the programmer to localize parts of programs by introducing new data environments, or scopes.

• Two different means of passing parameters to subprograms were allowed: pass by value and pass by name.

• Procedures were allowed to be recursive. The ALGOL 58 description was unclear on this issue. Note that although this recursion was new for the imperative languages, LISP had already provided recursive functions in 1959.

• Stack-dynamic arrays were allowed. A stack-dynamic array is one for which the subscript range or ranges are specified by variables, so that the size of the array is set at the time storage is allocated to the array, which happens when the declaration is reached during execution.

Chapter 2 : Review Question

Q6 : What hardware capability that first appeared in the IBM 704 computer strongly affected the evolution of programming languages? Explain why.

A   : Its capabilities prompted the development of Fortran because it was able to support floating-point operations hardware.

Q7 : In what year was the Fortran design project begun?

A   : 1954.

Q8 : What was the primary application area of computers at the time Fortran was designed?

A   : Mathematics.

Q9 : What was the source of all of the control flow statements of Fortran I?

A   : 704 instructions.

Q10 : What was the most significant feature added to Fortran I to get Fortran II?

A     : Independent compilation of subroutines.