Tuesday, March 26, 2013

Concepts of Programming Languages ---- Chapter 3 Describing Syntax and Semantics



Concepts of Programming Languages ---- Chapter 3 Describing Syntax and Semantics

Name : Fandy Limardi
NIM : 1601210713
Lecture : Tri Djoko Wahjono, Ir., M.Sc. (D0206)
Assignment : Concept of programming languages ---- Chapter 3 Describing Syntax and Semantics

Chapter 3
REVIEW QUESTIONS
1.      Define syntax and semantics
The syntax of a programming language is the form of its expressions, statements, and program units. Semantics is the meaning of those expressions, statements, and program units.

2.      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 . In this term, people prefer certain forms of generators over recognizers because they can more easily read and understand them. By contrast, the syntax- checking portion of a compiler is not as useful a language description for a programmer because it can be used only in trial and error mode.
3.      Describe the operation of a general 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 of reject the given string. Because most useful languages are, for all practical purposes, infinite, this might seem like a lengthy and ineffective process.

4.      What is the difference between a sentence and a sentential form?
Sentence form is a program consists of the special word begin, followed by a list of statements separated by semicolons, followed by the special word end. Sentential form is each of the strings in the derivation, including <program>

5.      Distinguish between static and dynamic semantics
Static semantics of a language is only indirectly related to the meaning of programs during execution; rather, it has to do with the legal forms of programs.

Dynamic semantics is the expressions , statements, and program units of a programming language. Because of the power and naturalness of the available notation, describing syntax is a simple matter.
6.      What is the difference between a synthesized and inherited attribute?
Synthesized attributes are used to pass semantic information up a parse tree, inherited attributes are used to pass semantic information down and across a tree.

7.      Describe the two levels of uses of operational semantics.
-          The basic process
The first step in creating an operational semantics description of a language is to design an appropriate intermediate language, where the primary characteristic of the language is clarity. Every construct of the intermediate language must have an obvious and unambiguous meaning
-          Evaluation
The first and most significant use of formal operational semantics was to describe the semantics of PL/I. Operational semantics provides an effective means of describing semantics for language users and language implementers with simple and informal description.

8.      Give an example of an ambiguous grammar.
<assign> -> <id> = <expr>
<id>-> A|B|C
<expr> -> <expr> + <expr>
            | <expr> * <expr>
            | (<expr>)
            | <id>
The grammar is ambiguous because the sentence A = B + C *A

9.      What is the use of the wp function? Why it is called a predicate transformer?
The wp function is helpful to treat the process of producing a weakest precondition as a function. It is called a predicate transformer because it takes a predicate, or assertion, as a parameter and returns another predicate.

10.  Give the difference between total correctness and partial correctness.
Total correctness is the axiomatic description of the loop when the loop termination is shown
Partial correctness is the other condition can be met but termination is not guaranteed.
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: error due to missing colon, semicolon, parenthesis, etc. Syntax is the way in which we construct sentences by following principles and rules. 
Example: In C++, it would be a syntax error to say 
int a = "ten";
This will not compile because it does not follow the syntax of the language and does not make any sense to the compiler. 

Semantic Error: it is a logical error. it is due to wrong logical statements. Semantics is the interpretations of and meanings derived from the sentence transmission and understanding of the message. Semantics errors are Logical, while Syntax errors are code errors. 
Example: A semantic error would compile, but be incorrect logically:
const int a = 12345;

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



















                                        
3.      Describe, in English, the language defined by the following grammar in BNF
<S> -> <X> <Y>
<X> -> x <X> | x
<Y> -> y <Y> | y

<X> will generate one or more consecutive x’s.
<Y> will generate one or more consecutive y’s.
So <X> <Y> will generate
One or more x’s followed by one or more y’s.


4.      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.      baab
b.     bbbab
c.      bbaaaaa
d.     bbaab

      <A> will generate one or more consecutive b's 
      <B> will generate one or more consecutive a's 
      So <A> a <B> b  will generate 
a.       baab : ok
<S>=><A>a<B>b => b a <B> b => b a a b
b.      bbaab : ok
<S> => <A>a<B>b => b b a <B>b => b b a a b

5.      Consider the following grammar in BNF:
<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? Explain your answers.
a)      abcd  : ok
Derivation:
      <S> => a <S> c <B> => a b c <B> => a b c d 
e)      accc : ok
Derivation:
      <S> => a <S> c <B> => a <A> c <B> => a c c <B> => a c c <A> => a c c c

6.      Convert the BNF of Example 3.3 to EBNF
<assign> -> <id> = <expr>
<id> -> A|B|C
<expr> -> <id> + <expr>
                 | <id> * <expr>
                 |  ( <expr> )
                 | <id>

            <assign> -> <id> = <expr>
            <id> -> A|B|C
            <expr> -> <id> {(+ | *) <term>}
            <term> -> ‘(‘ <expr> ‘)’

7.      Convert the following EBNF to BNF:
S A {bA}
Aa [b]A
<S> <S>b<A> | <A>
<A> a<A> | ab<A>


8.      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.

9.      Compute the weakest precondition for each of the following assignment statements and postconditions :
a.       a = 2 * ( b – 1 ) – 1 {a > 0}
b.      b = ( c + 10 ) / 3 {b>6}
c.       a = a + 2 * b – 1 {a>1}
d.      x = 2 * y + x – 1 {x>11}

A.    2 * ( b – 1 ) – 1 > 0
2b – 2 – 1  > 0
2b – 3 > 0
2b > 3
B > 3/2
B.     ( c + 10 ) / 3 > 6
c + 10 > 18
c > 8
C.     a + 2 * b – 1 > 1
a + 2 * b > 2
2 * b > 2 – a 
D.    2 * y + x – 1 > 11
2 * y + x > 12
2 * y > 12 – x

10.  Computer the weakest precondition for each of the following sequences of assignment statements and their postconditions :
a.        a = 2 * b + 1;
b = a – 3
{b < 0}
b.      a = 3 * (2 * b + a);
b = 2 * a – 1 
{b > 5}

A.    a – 3 < 0
a < 3

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

B.     2 * a – 1 > 5
2 * a > 6
a > 3

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

Monday, March 4, 2013

Concepts of Programming Languages ---- Chapter 2 Evolution of the Major Programming languages


Concepts of Programming Languages ---- Chapter 2 Evolution of the Major Programming languages

Name : Fandy Limardi
NIM : 1601210713
Lecture : Tri Djoko Wahjono, Ir., M.Sc. (D0206)
Assignment : Concept of programming languages ---- chapter 2 Evolution of the Major Programming languages

Chapter 2
Review Questions
1.      In what year was Plankalkul designed? In what year was that design published?
Answer : In 1945, Plankalkul was designed. In 1972, that design published.

2.      Mention an interesting feature of Zuse’s programs.
Answer : An interesting feature of Zuse’s programs is the inclusion of mathematical expressions showing the current relationships between program variables.

3.      What does  Plankalkul mean?
Answer : Plankalkul means high level non-von Neumann programming language or program calculus designed by Konrad Zuse.

4.      Speedcoding was invented to overcome two significant shortcomings of the computer hardware of the early 1950s. What were they?
Answer : Non-connotative names, absolute addressing. (Floating-point arithmetic, automatic incrementing of address register)

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

6.      What hardware capability that first appeared in the IBM 704 computer strongly affected the evolution of programming languages? Explain why.
Answer : The inclusion of floating-point hardware capability that first appeared in the IBM 704 computer strongly affected the evolution of programming languages because at that time ,the lack of floating-point hardware in the available computers. All floating –point operations had to be simulated in software, a very time-consuming process.

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

8.      Who developed Short Code? Why is Short Code called automatic programming?
Answer : John Mauchly developed short code.  Short Code called automatic programming because it was not translated to machine code, it was implemented with a pure interpreter. It clearly simplified the programming process.

9.      Under what environmental consideration was Fortran developed? Which is the first version of Fortran?
Answer :
The environmental consideration in which Fortran was developed was as follows :
1.      Computers had small memories and were slow and relatively unreliable
2.      The primary use of computers was for scientific computations
3.      There were no existing efficient and effective ways to program computers
4.      Because of the high cost of computers compared to the cost of programmers.
the first version of Fortran is Fortran I .

10.  What was the most significant feature added to Fortran I to get Fortran II?
Answer :  the most significant feature added to Fortran I to get Fortran II was being the independent compilation of subroutines.

11.  What control flow statements were added to Fortran IV to get Fortran 77?
Answer :  control flow statements were added to Fortran IV to get Fortran 77 are 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 dynamic variables?
Answer : Fortran 90

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

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

15.  In what way are Scheme and Common LISP opposites of each other?
Answer : Common LISP allows for static scoping and dynamic scoping Scheme only uses static scoping. 

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

17.  What two professional organizations together designed ALGOL 60?
Answer : ACM and GAMM

18.  What were modifications to ALGOL 58 to produce ALGOL 60?
Answer :
1.      The concept of block structure was introduced
2.      Two different means of passing parameters to subprograms were allowed
3.      Procedures were allowed to be recursive
4.      Stack-dynamic arrays were allowed

19.  What language was designed to describe the syntax of ALGOL 60?
Answer : BNF (Backus-Naur form)

20.  On what language was COBOL based?
Answer : Flow-Matic

21.  In what year did the COBOL design process begin?
Answer : 1959

22.  What data structure that appeared in COBOL originated with Plankalkul?
Answer : Hierarchical data structures (records)

23.  What organization was most responsible for the early success of COBOL (in terms of extent of use)?
Answer : Department of Defense (DoD)

24.  Why was BASIC an important language in the early 1980s?
Answer : Its smaller dialects could be implemented on computers with very small memories

25.  PL/I was designed to replace what two languages?
Answer : COBOL and Fortran

26.  For what new line of computers was PL/I designed?
Answer : the IBM system/360 line of computers

27.  What features of SIMULA 67 are now important parts of some object-oriented languages?
Answer : Data abstraction

28.  What innovation of data structuring was introduced in ALGOL 68 but is often credited to Pascal?
Answer : User-defined data types

29.  What design criterion was used extensively in ALGOL 68?
Answer : Orthogonality

30.  What language introduced the case statement?
Answer : ALGOL-W

31.  What operators in C were modeled on similar operators in ALGOL 68?
Answer : for and switch statements, in its assigning operators, and in its treatment of pointers

32.  What are two characteristics of C that make it less safe than Pascal?
Answer : Lack of complete type checking and flexibility

33.  What are the two kinds of statements that populate a Prolog database?
Answer : Facts and rules

34.  What is the primary application area for which Ada was designed?
Answer : Embedded systems

35.  What three concepts are the basis for object-oriented programming
Answer : Classes, objects and methods

Problem Set
1.      What features of Fortran IV do you think would have had the greatest influence on Java if the Java designers had been familiar with Fortran?
Answer : I think features of Fortran IV would have had the greatest influence on Java if the Java designers had been familiar with Fortran are explicit type declarations for variables, a logical If construct, and the capability of passing subprograms as parameters to other subprograms.

2.      Write a short history of the Fortran 0, Fortran I, Fortran II, and Fortran IV systems.
Answer :
Fortran 0 (1955) : It would provide the efficiency of hand coded programs and the ease of programming of the interpretive pseudo code systems.
Fortran I (1956) : It included input/output formatting, variable names of up to six characters. User defined subroutines, the If selection statement , and the Do loop statement.
Fortran II (1958) : It fixed many of the bugs in the Fortran I compilation system and added some significant features to the language , the most important being the independent compilation of subroutines.
Fortran IV (1962) : its most additions were explicit type declarations for variables, a logical If construct, and the capability of passing subprograms as parameters to other subprograms.

3.      As a research project, compare the features of C with those of the BASIC
Answer : Features of C are input/output, looping, selection, pointers, file processing, arrays, struct and so on. Features of BASIC are there was no way for executing program to get input data from the user. Programs were typed in, compiled and run. BASIC had only 14 different statement types and a single data type (floating point).

4.      Which of the three original goals of the Fortran design committee, in my opinion, was most difficult to achieve at that time?
Answer : in my opinion, the primary use of computers for scientific computations (algebraic translation system) was most difficult to achieve at that time

5.      Make an educated guess as to the most common syntax error in C programs
Answer :
1. Semicolon missing.
2  Forget declared variables.
3. Function with not the same data type parameters in main
4..Forget parentheses.


6.      Describe in detail the two most important reasons, in your opinion, why speedcoding did not become a very widely used language?
Answer : because there is a limitations of such systems, consider that the remaining usable memory after loading interpreter was only 700 words and that the add instruction took 4.2 milliseconds to execute. Speedcoding included the novel facility of automatically incrementing address registers. This facility did not appear in hardware until UNIVAC 1107 computers of 1962.

7.      Why, in your opinion, did Fortran allow names that began with I,J,K,L,M, and N as implicitly interger type?
Answer :  Fortran allowed names that began with I,J,K,L,M, and N as implicitly interger type because the choice of the letters for this convention was based on the fact that at that time scientist and engineers used letters as variable subscripts, usually i, j, and k. In a gesture of generosity, Fortran’s designers threw in three additional letters.

8.      Outline the major developments in ALGOL 60.
Answer :
-          The concept of block structure was introduced
-          Two different means of passing parameters to subprograms were allowed
-          Procedures were allowed to be recursive
-          Stack-dynamic arrays were allowed

9.      Was IBM’s assumption, on which it based its decision to develop PL/I, correct, given the history of computers and language developments since 1964
Answer : IBM incorrect in its view of the future of the uses of computers, at least as far as languages are concerned. Commercial applications are nearly all done in languages that are specifically designed for them. On the other hand, the IBM design of the 360 line of computers was a great success. it dominates the area of computers between supercomputers and minicomputers. Furthermore, 360 series computers and their descendants have been widely used for both scientific and commercial applications in large part, in Fortran and COBOL.

10.  What is the primary reason why C became more widely used than Fortran?
Answer : the primary reason why C became more widely used than Fortran is its lack of complete type checking such as functions could be written for which parameters were not type checked. Those who like C appreciate the flexibility. Then, a compiler for it was part of the widely used UNIX operating system. This inclusion in UNIX provided an essentially free and quite good compiler that was available to programmers on many different kinds of computers.

11.  What are the arguments both for and against the idea of a typeless language?
Answer : The argument for typeless languages is their great flexibility for the programmer. Some storage location can be used to store any type value for very low-level languages and  systems programming. The drawback that type checking is impossible, so it is the programmer's responsibility to insure that expressions and assignments are correct.

12.  Languages continually evolve. What sort of restriction do you think are appropriate for the changes in programming languages? Compare your answer with the evolution of Fortran.
Answer : The danger is that the process of revision. It will add new features, so that the language grows more complex. Compounding the problem is the reluctance, because of existing software, to remove obsolete features.

13.  In recent years data structures have evolved within scripting languages to replace traditional arrays. Explain the chronological sequence of these developments.
Answer : As in scheme, Lua’s functions are first-class values. Lua support closures. These capabilities allow it to be used for functional programming. Lua has only  single data structures, although in Lua’s case, it is the table. Lua’s tables extend PHP’s associate arrays. References to table elements can take the form of references to traditional arrays, associative arrays, or records. Luas uses garbage collection for its objects. It uses dynamic typing. Lua is a small and simple language, having only 21 reserved words. Much of its extensibility derives from its table data structure. Lua can conveniently be used as a scripting language extension to other languages. Lua is translated to an intermediate code and interpreted.

14.  Explain two reasons why pure interpretation is an acceptable implementation method for several recent scripting languages
Answer : pure interpretation is an acceptable implementation method for several recent scripting languages is when the amount of computation is small, the processing time will be negligible. The second one is when the amount of computation is small and it is done in interactive environment, where the processor is often idle because of the slow speed of human interactions.

15.  Give a brief general description of the Java servlet
Answer : Java servlet is an instance of a java class that resides on and is executed on a web server system. The execution of a servlet is requested by a markup document being displayed by a web browser. The servlet’s output, which is in the form of an HTML document, is returned to the requesting browser. A program that runs in the web server process, called a servlet container, controls the execution of servlet. Servlet are commonly used for form processing and for database access.