Pages

Tuesday 26 March 2013

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.

Thursday 14 March 2013

Chapter 2

An assignment from Mr. Tri Djoko Wahyono (again). As what the title said, it is the answer for some question (17 numbers, quite randomly in Review Qustion and 8 numbers in Problem Set) in Chapter 2 in "Concept of Programming Language" book.


Review Question
1. In what year was Plankalkül designed? In what year was that design published?
The project has begun at 1943 and published at 1972.

3. What does Plankalkül mean?
Plankalkül means program calculus.

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

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

8. Who developed Short Code? Why is Short Code called automatic programming?
John Mauchly; The Short Code is called automatic programming because it simplified the programming process and was implemented with a pure interpreter.

10. What was the most significant feature added to Fortran I to get Fortran II?
The independent compilation feature.

12. Which version of Fortran was the first to have any sort of dynamic variable?
Fortran 90

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

14. Why were linguist interested in artificial intelligence in the late of 1950s?
Linguist were interested with natural language processing in Artificial Intelligence.

16. In what way are Scheme and Common LISP opposites of each other?
Scheme is a small language with simple syntax and semantics, while Common LISP is a relatively large and complex language

17. What dialect of LISP is used for introductory programming courses at some universities?
Scheme.

18. What two professional organization together designed ALGOL 60?
ACM and GAMM.

20. What were the significant modification to ALGOL 58 to produce ALGOL 60?
There're some modification made for ALGOL 58 to become ALGOL 60.
  • The concept of block structure was introduced.
  • Two different means of passing parameters to subprograms were allowed: pass by value and pass by name.
  • Procedures were allowed to be recursive.
  • Stack-dynamic arrays were allowed.
23. In what year did the COBOL design process begin?
1959.

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

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

31. What innovation of data structuring was introduced in ALGOL 68 but is often credited  to Pascal?
User defined data type.


Problem Set
6. Make an educated guess as to the most common syntax error in C programs.
I think, most common syntax error in C is missing close bracket ')' or '}', because it can be stacked like this :

   void ex{
if (x == 0)
{
for (i = 0; i < n; i++)
{
for (k = i+1; k < i; k++)
{
swap (num_1, num_2);
}
}
}

in that example, there's a missing '}', but it might not be seen easily, because of the stacking bracket.

8. Describe in detail the two most important reasons, in your opinion, why Speedcoding did not become a very widely used language.
First, Speedcoding seems to be an exclusive system, made just for IBM 701. Thus, the knowledge about using IBM 701 is required. Then, how about people who don't know about the IBM 701 system?

Secondly, Speedcoding has a novel facility of automatically incrementing address register, but it was out after a long wait in 1962 (around 8 years long from the system was built). Before the facility is available, programmer have to increase the address register manually and it will increase the cost of the program.

9. Why, in your opinion, did Fortran allow names that begins with I, J, K, L, M, and N as  simplicity integer type?
Because it will be more common to people using I, J, K as implicitly of integer type. If Fortran use A, B, C and I, J, K as the substitute, it would be less known and could be forgotten because the usual letters is I, J, and K. So, Fortran use the nearest letters from I, J, and K.

10. Outline the major developments in ALGOL 60.


  • The concept of block structure was introduced.
  • Two different means of passing parameters to subprograms were allowed: pass by value and pass by name.
  • Procedures were allowed to be recursive.
  • Stack-dynamic arrays were allowed.


  • 13. What is the primary reason why C became more widely used than Fortran?
    C's compiler was part of widely used UNIX operating system, which is a free and quite good compiler that was available to programmers on many different kinds of computers. Because of that, Fortran, which is only available in computers manufactured by IBM, was not as used widely as C.

    14. What are the argument both for and against the idea of a typeless language?
    The advantages of the idea of a typeless language is its flexibility. Any variable can be used for any type values. Despite of its advantage, the idea make a poor reliability due to the ease with which type errors can be made and the impossibility to do the type checking because of the advantage.

    15. Are there any nonprocedural programming languages other than Prolog?
    Yes, there are, like SQL and Visual Basic.

    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?
    I think the statement is right that with the complexity of the language increasing, the more dangerous its language to use, because it will make just a few of people who mastering this kind of language. Furthermore, with just a few of people who know that kind of language, other people will then abandon that language. Other opinion about this is about the programs made by the language. How if the few people who master the language, make a virus program with that language which is not known by the other people? It might be hard to figure out, how to eradicate that virus if thhey don't know the language.

    Monday 4 March 2013

    Chapter 1

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

    Review Question
    6. In what language is most of UNIX written?

    UNIX is written almost entirely in C.

    7.What is the disadvantage of having too many features in a language?
    Having too many features in a language will make a disadvantage at many things too, like the cost for the program or else, because every features in a language has its own drawback. For example, many operators in a language improve the writability greatly, but lower the readability.

    9. What is one example of a lack of orthogonality in the design of C?
    C is usually specified with variables and assignment statements.

    14. Why is type checking the parameters of a subprogram important?
    Type Checking is an important because the earlier errors in program are detected, the less expensive it is to make the required repairs.

    15. What is aliasing?
    In this context, Aliasing is having two or more distinct names that can be used to access the same memory cell.

    16. What is exception handling?
    Exception Handling is an ability of a program to intercept run-time errors, take corrective measures, and then continue the program.

    19. What have been the strongest influence on programming language design over the past 50 years?
    Imperative language is, the most popular language and has the strongest influences in programming language, in past 50 years that has been designed around the prevalent computer architecture (von Neumann architecture).

    20. What is the name of the category of programming languages whose structure is dictated by the von Neumann computer architecture?
    Imperative.

    21. What two programming language deficiencies were discovered as a result of the research in software development in the 1970s?
    The incompleteness of type checking and inadequacy of control statements (requiring the extensive use of gotos).

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

    Problem Set
    2. Who is said to be the first programmer in human history? Use the internet for help.
    The person who is said to be the first programmer in human history is Ada Lovelace.

    4. In what way do the languages for scientific application differ from the languages for business application? Support your view.
       >>In scientific application, the languages is used to make data structures that are arrays and matrices, to do calculation with large numbers of floating-point, and such. The primary concern here is the efficiency.
       >> In business application, the languages is used to produce elaborate reports, precise ways of describing and storing decimal numbers and characters data, and such.

    6. Which characteristics of programming languages do you think are the most important and why?
    I think, reliability is the most important characteristic in a programming languages, because it contains readability and writablility of the language itself. So, when the readability and the writablity of a programming language improves, then reliability of it will improve too, but not only that. The other features, related to reliability, is also important, like Type Checking, Aliasing, and Exception Handling. Without it all, the cost of the programming language will greatly increase and will make the language expensive.

    7. Java uses a semicolon to mark the end of all statements. What are the advantages for and against this design?
    The advantages of using semicolon in the end of all statements is, it indicate the closure of the statements and it would help if the use instance initialization is needed. But on the other hand, it might trip up the beginner and misunderstood that with C or C++ program.

    12. Can we call any programming language complete, in your opinion? Why or why not?
    No, because with one characteristic of a language is improving, thus another characteristic might be degrade, like the readability and the writablity of a language. When a language's readability is greatly improves, which means that it can be easily understand by another programmer, then the writability of the language might not be very good. Even when the writability and the readability is improved, the cost for the language might be not as good as that two characteristics.

    17. Some programming languages--for example, SQL--use "=" to check the equality of two expression, while C uses it to assign values to variable. Which of these, in your opinion, is most natural and least likely to result in syntax errors? Support your answer.
    In my opinion, the use of '=' in C would often make some mistake, because beginners might think that it will be use to check the equality too or it might be because some of languages didn't use '==' for equality checking. So, I would say that the use of '=' in SQL is least likely to result in syntax error.