Tuesday, March 26, 2013

Concepts of Programming Languages - Chapter 3


Review Questions

1. Define syntax and semantics.
Syntax is the form or structure of the expressions, statements, and program units.
Semantics is the meaning of the 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.

7. What three extensions are common to most EBNFs?
Three extensions are commonly included in the various versions of EBNF. The first extension denotes an optional part of an RHS, which is delimited by brackets. The second extension is the use of the brackets in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. And the third extension deals with multiple-choice options.

10. What is the difference between a synthesized and an inherited attribute?
The attributes are divided into two groups: synthesized attributes and inherited attributes. 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.

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.

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.
<assign> -> <id> = <expr>

<id> -> A | B | C

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

| <expr> * <expr>

|  (  <expr>  )

| <id>

23. On what branch of mathematics is axiomatic semantic based?
Axiomatic semantics, thus named because it is based on mathematical logic.

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

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.
An example of syntax error, for example in C, is forget to put semicolon
assume that printf("Hello world");
It is a syntax error if we make printf("Hello world")
An example of semantic error is: const int pi = 123;
It is syntactically correct but logically incorrect.

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 is ambiguous, because the grammar generates different parse trees.

9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.
Assume that the operators can precede any operand
<factor> -> <id>
with
<factor> -> + <id>
| - <id>

10. Describe, in English, the language defined by the following grammar:
<S> -> <X><Y>
<X> -> x<X> | x
<Y> -> y<Y> | y
x can be followed by one or more than one x, then followed by one or more than one y.

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
d. abaabb

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:
b. accbcbccc

18.  What is a fully attributed parse tree?
A fully attributed parse tree is a condition when all the attributed values in parse tree have been computed.

23. Compute the weakest precondition for each of the following sequences of assignment statements and their postconditions:
a. a = 2 * (b - 1) - 1 {a > 0}
2 * (b - 1) - 1 > 0
2*b - 2 > 1
2*b > 3
b > 3/2

b. b = (c + 10) / 3 {b > 6}
(c + 10) / 3 > 6
c + 10 > 18
c > 8

c. a = a + 2 * b - 1 {a > 1}
a + 2 * b - 1 > 1
a + 2 * b > 2
2 * b > 2 - a
b > (2 - a) / 2

d. x = 2 * y + x - 1 {x > 11}
2 * y + x - 1 > 11
2 * y + x > 12

24. Compute the weakest precondition for each of the following sequences of assignment statements and postconditions:
a. a = 2 * b + 1;
b = a - 3
{b < 0}

a - 3 < 0
a < 3

2 * b + 1 < 3
2 * b < 2
b < 1

b. a = 3 * (2 * b + a);
b = 2 * a - 1
{b > 5}

2 * a - 1 > 5
2 * a > 6
a > 3

3 * (2 * b + a) > 3
6 * b + 3 * a > 3
2 * b + a > 1
2 * b > 1 - a
b > (1 - a)/2

Monday, March 25, 2013

Concepts of Programming Languages - Chapter 1


Review Questions

3. What programming language has dominated scientific computing over
the past 50 years?
Fortran

4. What programming language has dominated business applications over
the past 50 years?
COBOL

5. What programming language has dominated artificial intelligence over
the past 50 years?
LISP

6. In what language is most of UNIX written?
C

21. What two programming language deficiencies were discovered as a
result of the research in software development in the 1970s?
Incompleteness of type checking and inadequacy of control statements

22. What are the three fundamental features of an object-oriented programming
language?
Encapsulation, inheritance, polymorphism

23. What language was the first to support the three fundamental features of
object-oriented programming?
Smalltalk

25. What are the three general methods of implementing a programming
language?
Compilation, pure interpretation, hybrid implementation system

26. Which produces faster program execution, a compiler or a pure
interpreter?
A compiler

29. Whhat is a hybrid implementation system?
An implementation that translates high-level language programs to an intermediate language designed to allow easy interpretation so that it is faster than pure interpretation because the source language statements are decoded only once.


Problem Set

1. Do you believe our capacity for abstract thought is influenced by our
language skills? Support your opinion.
Yes, because by having programming language skills we know the differences of the languages and we can choose which kind of language that is more suitable to the algorithm we are making so the algorithm will be a simple one.

2. Who is said to be the first programmer in human history? Use the Internet for help.
Ada Lovelace

4. In what way do the languages for scientific applications differ from the languages for business applications? Support your view.
Scientific applications used relatively simple data structures but required large numbers of floating-point arithmetic computations. Business languages are characterized by facilities for producing elaborate reports, precise ways of describing and storing decimal numbers and character data, and the ability to specify decimal arithmetic operations.

7. Java uses a semicolon to mark the end of all statements. What are the advantages for and against this design?
Adv: using semicolon is a simplicity that it closes every statement.
Disadv: sometimes we forget to put semicolon on a statement that it creates compilation error.

10. Make a comparative study of the cost of software and hardware.
The cost of hardware was higher than software in the past, but now they're the opposite.

12. Can we call any programming language complete, in your opinion? Why or why not?
No, because each programming language has its own characteristics and is used for a specific purpose that differs it from other programming languages


Edited on 25/03/2013

Sunday, March 10, 2013

Concepts of Programming Languages - Chapter 2


Review Questions

1. In what year was Plankalkül designed? In what year was that design
published?
1943, 1972

3. What does Plankalkül mean?
Program Calculus

5. What is the number of bits in a single word of the UNIVAC I's memory? How are the bits grouped?
72, they are grouped as 12 six-bit bytes

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

8. Who developed Short Code? Why is Short Code called automatic programming?
John Mauchly. Because it clearly simplified the programming process.

9. Under what environmental consideration was Fortran developed? Which is the first version of Fortran?
- Computers had small memories and were slow and relatively unreliable
- the primary use of computers was for scientific computations
- there were no existing efficient and effective ways to program computers
- because of the high cost of computers compared to the cost of programmers, speed of the generated object code was the primary goal of the first Fortran compilers.
Fortran 0

10. What was the most significant feature added to Fortran I to get Fortran II?
Independent compilation of subroutines

11. What control flow statements were added to Fortran IV to get Fortran 77?
Character string handling, logical loop control statements, and an If with an optional Else clause

12. Which version of Fortran was the first to have any sort of dinamic variables?
Fortran 4

13. Which version of Fortran was the first to have character string handling?
Fortran 77

14. Why were linguists interested in artificial intelligence in the late 1950s?
Linguists were concerned with natural language processing

17. What dialect of LIST is used for introductory programing courses at some universities?
Scheme

22. On what language was COBOL based?
English

23. In what year did the COBOL design process begin?
May 28 and 29, 1959

26. Which data type does the original BASIC language support?
Floating point

28. PL/I was designed to replace what two languages?
Fortran and COBOL

46. What is the primary application for Objective-C?
To write the NeXT computer system software


Problem Set

6. Make an educated guess as to the most common syntax error in C programs.
- Semicolon (;) missing.
- Unmatched parentheses.
- Undeclared variables.
- Prototype function mismatch.

7. LISP began as a pure functional language but gradually acquired more and more imperative features. Why?
To increase its execution efficiency.

8. Describe in detail the two most important reasons, in your opinion, why Speedcoding did not became a very widely used language.
Speedcoding system was an interpreter so that the running time of a program that was written with the help of Speedcoding was usually ten to twenty times that of machine code.
Speedcoding interpreter took much memory to execute the program and it wasn't efficient.

14. What are the arguments both for and against the idea of a typeless language?
Typeless language is highly flexible for the programmer, any storage location can be used to store any type value.
Type checking can't be applied so the programmer has to make sure that the statements are correct.

15. Are there any nonprochedural programming languages other that Prolog?
No

16. What is your opinion of the argument that languages that are too complex are too dangerous to use, and we should therefore keep all languages small and simple?
Languages that are too complex and too dangerous must be avoided because they will be difficult to learn and they may cause so many errors because of the complexity. We should keep all languages small and simple so we can learn them fast and we know hot to use them specifically.

22. Explain two reasons why pure interpretation is an acceptable implementation method for several recent scripting languages.
- Pure interpretation is platform independent
- Interpretation gives the fastest turnaround from script to execution

24. Why, in your opinion, do new scripting languages appear more frequently than new compiled languages?
Because scripting languages usually are simpler and focused on specific applications.


Edited on 25/03/2013