Chapter 3 Answers

Review Questions

1.       Define syntax and semantics.

Syntax is the form of programming language, expressions, statements, and program units.

Semantics is the meaning of those expressions, statements, and program units.

2.       Who are language descriptions for ?

The language descriptions is important for the programming language implementers to determine how the expressions, statements, and program units of a language are formed, and also their intended effect when executed.

3.       Describe the operation of a general language generator.

A language generator is a device that can be used to generate the sentences of a language. We can think of the generator as having a button that produces a sentence of the language every time it is pushed. Because the particular sentence that is produced by a generator when its button is pushed is unpredictable, a generator seems to be a device of limited usefulness as a language descriptor.

4.       Describe the operation of a language recognizer.

Suppose we have a language L that uses an alphabet _ of characters. To define L formally using the recognition method, we would need to construct a mechanism R, called a recognition device, capable of reading strings of characters from the alphabet _. R would indicate whether a given input string was or was not in L. In effect, R would either accept or reject the given string. Such devices are like filters, separating legal sentences from those that are incorrectly formed. If R, when fed any string of characters over _, accepts it only if it is in L, then R is a description of L. Because most useful languages are, for all practical purposes, infinite, this might seem like a lengthy and ineffective process. Recognition devices, however, are not used to enumerate all of the sentences of a language—they have a different purpose. The syntax analysis part of a compiler is a recognizer for the language the compiler translates. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. Rather, it need only determine whether given programs are in the language. In effect then, the syntax analyzer determines whether the given programs are syntactically correct.

12.   What is the primary use of attribute grammars?

An attribute grammar is a device used to describe more of the structure of a programming language than can be described with a context-free grammar. An attribute grammar is an extension to a context-free grammar. The extension allows certain language rules to be conveniently described, such as type compatibility. Before we formally define the form of attribute grammars, we must clarify the concept of static semantics.

15.   Describe the two levels of uses of operational semantics.

There are different levels of uses of operational semantics. At the highest level, the interest is in the final result of the execution of a complete program. This is sometimes called natural operational semantics. At the lowest level, operational semantics can be used to determine the precise meaning of a program through an examination of the complete sequence of state changes that occur when the program is executed. This use is sometimes called structural operational semantics.

21.   When is a grammar rule said to be left recursive?

When a grammar rule has its LHS also appearing at the beginning of its RHS, the rule is said to be left recursive. This left recursion specifies left associativity.

22.   Give an example of an ambiguous grammar.

<stmt> -><matched> | <unmatched>

<matched> -> if <logic_expr> then <matched> else <matched>

|any non-if statement

<unmatched> -> if <logic_expr> then <stmt>

|if <logic_expr> then <matched> else <unmatched>

23.   On what branch of mathematics is axiomatic semantics based?

Axiomatic semantics, thus named because it is based on mathematical logic, is the most abstract approach to semantics specification discussed in this chapter. Rather than directly specifying the meaning of a program, axiomatic semantics specifies what can be proven about the program. Recall that one of the possible uses of semantic specifications is to prove the correctness of programs.

24.   Give an unambiguous grammar for if-then-else.

<if_stmt> -> if <logic_expr> then <stmt>

if <logic_expr> then <stmt> else <stmt>

Problem Set

 3.       Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.

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

<id> -> A | B | C

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

| <term>

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

| <factor>

<factor> -> ( <expr> )

| <id>

6.       Using the grammar in Example 3.2, show a parse tree for each of the following statements:

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

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

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

7.       Using the grammar in Example 3.4, show a parse tree 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))

8.       Prove that the following grammar is ambiguous:

<S>  -> <A>

<A> -> <A>*<A>|<id>

<id> ->  x|y|z

It is ambiguous because it can has two distinct parse tree

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

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

<id>  ->  A | B | C

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

| <term>

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

| <factor>

<factor> -> ( <expr> )

| +<id> | -<id>

13.   Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For example, the strings abb, aabbbb, and aaaabbbbbbbb are in the language but a, aabb, ba, and aaabb are not.

S -> ab

b ->bb

14.   Draw parse trees for the sentences abb and aabbbb, as derived from the grammar of Problem 13.

15.   Convert the BNF of Example 3.1 to EBNF.

<program>  ->  begin <stmt_list> end

<stmt_list> -> <stmt>

| <stmt> ; <stmt_list>

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> {(+|-) <var>}

16.   Convert the BNF of Example 3.3 to EBNF.

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

<id> -> A | B | C

<expr> -> <expr> {(+|*) <expr>}

| <id>

• Posted in: Concept of Programming Language Assignments