Chapter 3

An assignment from Mr. Tri Djoko Wahyono (as always). As what the title said, it is the answer for some question (10 numbers, quite randomly in Review Qustion and 8 or maybe 9 numbers in Problem Set) in Chapter 3 in "Concept of Programming Language" book.

Review Question
1. Define syntax and semantics.
Syntax of a programming language is a form of the language's expressions, statements, and program units and its semantics is the meaning of those expressions, statements, and program units.

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. It can be analogized of a generator as having a button that produces a sentence of the language every time it is pushed.

4. Describe the operation of a general language recognizer?
It's like a mechanism that capable of reading strings of characters the language's characters, and it will either accept or reject the given string.

5. What is the difference between a sentence and a sentential form?
A strings of a language is called a sentence, but a sentential form is each of its strings.

6. Define a left-recursive grammar rule.
It specifies left associativity and disallows the use of some important syntax analysis algorithms.

7. What three extensions are common to most EBNFs?
Brackets, replacement of a recursion by a form of implied iteration,and a feature to deals with multiple-choice options.

8. Distinguish between static and dynamic semantics.
Static semantics defines restrictions on the structure of valid texts that are hard or impossible to express in standard syntactic formalism; and dynamic semantics is a perspective on natural language semantics that emphasizes the growth of information in time.
9. What purpose do predicates serve in an attribute grammar?
Predicates in an attribute grammar state the static semantic rules that a language needs a false value in a predicate function indicates that there is a violation of syntax or static semantics, and thus determines whether an action is allowed or not.

12. What is the primary use of attribute grammars?
It allows certain language rules to be conveniently described, such as type compability.

18. Which semantics approach is most widely known?
Denotational Semantics.

Problem Set
3. Rewrite the BNF of Example 3.4 to represent operator - and operator / instead of operator + and operator *.
<assign> -> <id> = <expr>
         -> A = <expr> - <term>
         -> A = <term> - <term>
         -> A = <factor> - <term> / <factor>
         -> A = <id> - <factor> / <id>
         -> A = B - <id> / D
         -> A = B - C / D

9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher predence than either + or *.
<assign> -> <id> = <expr>
         -> A = <expr> + <term>
         -> A = <term> + <term>
         -> A = <factor> + <term> * <factor>
         -> A = <factor> + <term> - <term> * <factor>
         -> A = <id> + <term> - <term> * <id>
         -> A = B + <factor> - <factor> * D
         -> A = B + <id> - <id> * D
         -> A = B + C - B * D


11. Consider the following grammar:

<S> -> <A>a<B>b
<A> -> <A>b | b
<B> -> a<B> | a

Which of the following sentences are in the language generated by this grammar?

a. bbaabb
b. bbaba
c. bbaaaabb
d. abaabb
None of them, because the <s> will always end with a single 'b' and no a in the end of  the string.

12. Consider the following grammar:

<S> -> a<S>c<B> | <A> | b
<A> -> c<A> | c
<B> -> d | <A>

Which of the following sentences are in the language generated by this grammar?

a. abbccd
b. acccbda
c. accbcbccc
d. acddaccd
e. acccdc
None of them, because, (a) one string cannot have more than one 'b'; (b) the last character of the string cannot  be 'a'; (c) it can have more than 1 'd' but it can satisfied by having 'd' in the end of the line and have a pattern like this "...cdcdcd...cd" ; (d) the second-before-last character in that sting is always 'c'.


13. Write a grammar for the language consisting of strings that have n copies of the letter 'a' followed by double the number of copies of the letter 'b', where n > 0. For example, the string abb, aabbbb, and aaaabbbbbbbb aare in the language but a, aabb, and aaabb are not.
<X> -> <A> <B>
<A> -> a<A> | a
<B> -> bb<B> | bb
.
15. Convert the BNF of Example 3.1 to EBNF.
<program> -> begin <stmt_list> end
<stmt_list> -> <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>}
            | (<expr>)
            | <id>


17. Convert the following EBNF to BNF.

S -> A{bA}
A -> a[b]A

<S> -> <A> | <S>b<A>
<A> -> a


18. What is a fully attributed parse tree?
A parse tree have all the attribute grammar and have been computed.