Concepts of Programming Languages Assignment - Chapter 3

Review Questions

1. Define syntax and semantics.
Syntax in a programming language is the form of its expressions, statements, and program units. Its 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.
Language generator is a device that can be used to generate the sentences of languages. People prefer certain forms of generators over recognizers because they can more easily read and understand them. Language generator operates by generating a sentence of language, however language generators is unpredictable

5. What is the difference between a sentence and a sentential form?
A sentence is a sentential form that has only terminal symbols. A sentential form is every string of symbols in the derivation

6. Define a left-recursive grammar rule.
A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol

12. What is the primary use of attribute grammar?
Attribute grammar is primary used to provide complete descriptions of the syntax and static semantics of programming languages

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

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

24. On what branch of mathematics is denotational semantics based?
mathematical objects

29. Give the difference between total correctness and partial correctness.
Total correctness requires that the algorithm terminates while partial correctness requires that if an answer is returned it will be correct

Problem Set

1. Syntax error and semantic error are two types of compilation error. Explain the difference between the two in a program with examples.
Syntax error is a code error and semantic error is a logical error. Example of syntax error is forget to put a semicolon, bracket, etc. Example of semantic error is,

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>

8. Prove that the following grammar is ambiguous:
<S> -> <A>
<S> -> <A> * <A> | <id>
<id> -> x | y | z

The grammar generates a different parse tree, so the grammar is ambiguous.

9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.
<factor> → <id>
with
<factor> → + <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

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>

17.  Convert the following EBNF to BNF:
S -> a{bA}
A ->a[b]A

answer :
S -> A | AX
X -> bA | bAX
A -> aA | abA

18. What is a fully attributed parse tree?
If all of the attribute values in a parse tree have been computed, the tree is said to be fully attributed