March 26, 2013

KBP chapter 3


Rickvian Aldi / 02PCT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

Review questions

1.Define syntax and semantics.
-Syntax is the form of its expresions, statements, and program units.
Semantics is the meaning of those expressions, statements and program units.


2.Who are language descriptions for?
-Language user's



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.



4.Describe the operation of a general language recognizer.
-The syntax analysis part of a compiler is a recognizer for the language the
compiler translates. In this role, the recognizer need not test all possible
strings of characters from some set to determine whether each is in the
language. Rather, it need only determine whether given programs are in the
language. In effect then, the syntax analyzer determines whether the given
programs are syntactically
correct.



5.What is the difference between a sentence and a sentential form?
-sentence is the string of a language
-Sentential form is string in the derivation of a program, including the
<program> itself.



7.What three extensions are common to most EBNFs?
-The first of these denotes an optional part of an RHS, which is delimited by brackets.
-The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. This extension allows lists to be built with a single rule, instead of using recursion and two rules.

-The third common extension deals with multiple-choice options. When a
single element must be chosen from a group, the options are placed in parentheses
and separated by the OR operator, |


10. what is the diffrence between a synthesized and an inherited attribute?
-Synthesized attributes are used to pass semantic information up a parse tree,
while
-Inherited attributes pass semantic information down and across a tree.



12. what is the primary use of attribute grammars?
-Attribute grammars are context-free grammars to which have been added attributes,
attribute computation functions, and predicate functions. Attributes,
which are associated with grammar symbols (the terminal and nonterminal
symbols), are similar to variables in the sense that they can have values assigned
to them.


15.Describe the two levels of a methodology and notation for describing the

semantics of programming languages.
-There are different levels of uses of operational semantics. At the highest
level, the interest is in the final result of the execution of a complete program.
This is sometimes called natural operational semantics.

-At the lowest level,
operational semantics can be used to determine the precise meaning of a program
through an examination of the complete sequence of state changes that
occur when the program is executed. This use is sometimes called structural
operational semantics.



18. which semantics approach is most widely known?
Denotational semantics is the most rigorous and most widely known formal
method for describing the meaning of programs. It is solidly based on recursive
function theory.


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.

if done == true
then if denom == 0
then quotient = 0;
else quotient = num / denom;

it's ambiguous which the "else" is not determined for first if or the second
else.



Problem SET

(1)The two mathematical models of language description are generation
and recognition. Describe how each can define the syntax of a programming
language.
answer :
-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 or reject the given string. Such devices are like filters, separating legal sentences from those that are incorrectly formed. If R, when fed any string of characters over , accepts it only if it is in L, then R is a description of L.

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


(2)3. Rewrite the BNF of Example 3.4 to give + precedence over * and force +
to be right associative.
answer :
<assign> → => A = (B + C) ** A

(3)4. Rewrite the BNF of Example 3.4 to add the ++ and -- unary operators
of Java.
answer : 
<assign> => A = B ++ C * A

(4)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?

answer : NONE of them

a) bbaabb
impossible to have 2 "b"s at the end of <S>

b) bbaba
impossible to have "a" at the end since <S> has always ends with "b"

c) bbaaaabb
impossible to have 2 "b"s at the end of <S>

d) abaabb
impossible to have "a" at the start of <S>



(5)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?

answers :NONE OF THEM

rules from analysis :
1.the end of a statement will always either "b", "c", "d"
2.Since "b" obtained from <S> , impossible if "c" is after the "b".
3.<B> is the last part of <S>, so the "d" will always be the last and

impossible to have others following.
4.since "b" is called by <S>, take a look at the <S> is only one which can only

produce 1 "b" in a statement.

a) abbccd
impossible breaking rule 4

b) acccbda
impossible, breaking rule 1

c) accbcbccc
impossible, breaking rule 2

d) acddaccd
impossible, breaking rule 3

e) acccdc
impossible, breaking rule 3




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

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



(7)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>
| <var> – <var>
| <var>

answer : 

Program -> begin <stmt_list> end
<stmt_list -> <stmt> {; <stmt>)
stmt -> var = expression
var -> A | B | C
<exppression> -> <var> {(+|-) <var>}



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

answer :
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> { (+|*) <expr>}
| (<expr>)
| <id>

(9)18. What is the difference between an intrinsic attribute and a nonintrinsic
synthesized attribute?
answer:
-Intrinsic attributes are synthesized attributes of leaf nodes whose values are determined outside the parse tree.
nonintrinsic means the opposite, the values are not determined.


(10)28. Prove the following program is correct:
{n > 0}
count = n;
sum = 0;
while count <> 0 do
sum = sum + count;
count = count - 1;
end
{sum = 1 + 2 + . . . + n}

answer : 

assume input is 4
{n > 0}
count = n;
sum = 0;
while count <> 0 do

first round (count = 4)
sum = sum + count;
//sum = 4
count = count - 1;
//count = 4-1 = 3

second round (count = 3)
sum = sum + count;
//sum = 4 + 3
count = count - 1;
//count = 3-1 = 2

third round (count = 2)
sum = sum + count;
//sum = 4+3+2
count = count - 1;
//count = 2-1 = 1

first round (count = 1)
sum = sum + count;
//sum = 4+3+2+1 (prove the answer)
count = count - 1;
//count = 1-1 = 0

end
{sum = 1 + 2 + . . . + n}

March 11, 2013

KBP Chapter 2


Rickvian Aldi / 01PBT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

Review Questions

1. In what year was Plankalkul designed? In what year was that design published?
-Designed 1945, published at 1972

2. Mention an interesting feature of Zuse's programs.
-The inclusion of mathematical expressions showing the current relationships between program variables. These expression stated what would be true during execution at the points in the code where they appreared.

3.What does plankakul mean?
-Plankalkul means program calculus.

4.Speedcoding was invented to overcome two significant shortcomings of the computer hardware of early 1950s. What were they?
-The system included prseudoinstructions for the four arithmetic operations on floating-point data, as well as operations such as square root, sine arc tanget exponent. On the other hand, Speedcoding included the novel facility of automatically incrementing address registers.

5.What is the number of bits in a single word of the UNIVAC  I's memory? How are the bits grouped?
-The words of the UNIVAC I's memory had 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.
-Because of its capabilities prompted the development of FORTRAN.
With both indexing and floating-point instructions in hardware, heralded the end of the interpretive era, at least for scientific computation.

7.Who developed the speedcoding system for the IBM 701?
-John Backus 1954

8.Who developed Short Code? Why Short Code called automatic programming?
-Developed by John Mauchly in 1949.
-Short code was not translated to machine code; rather, it was implemented with a pure interpreter.

9.Under what enviromental consideration was Fortran developed? Which is the first version of the Fortran?
-The environment in which Fortran was developed was as follows:
-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.
The first version of FORTRAN is fortran 0.

10.What was the most significant feature added to fortran I to get Fotran II?
-The most important being the independent compilation of subroutines. Without independent compilation, any change in a program required that the entire program be recompled.

11.What control flow statements were added to Fortran IV to get Fortran 77?
-Fortran 77 retained most of the features if Fortran IV and added 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?
-Fortran 90.

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

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

15.What are the different data types and structures in Common LISP?
-records, arrays, complex number, character strings, many more.

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

17.What dialect of LISP is used for introductory programming courses at some universities?
-Scheme is well suited to educational applications, such as courses in functional programming and general introductions to programming.

Problem set

1. What features of Fotran IV do you think would have had the greatest influence on Java if the Java designers had been familiar with Fotran?
-Amon its most important additions were explicit type declaration for variables, a logical if construct and capability of passing subprograms as paramaters to others subprograms.

3.Write a short history of the Fotran 0, Fotran I, Fotran II, and Fotran IV systems.
-Fotran 0:
Even before the 704 sysetem was announced, plans were begun for Fortran. John Backus and his group at IBM had produced the report titled "The IBM Mathematical FORmula TRANsalating System: FORTRAN". This document described the first version of Fortran, the first fortran compiler included little syntax error checking.
Fortran 0 was modified during the implementation periond, which began in january 1955.

-Fortran I :
The implemented language, which we called Fortran I, is described in the first Fortran Programmer's Reference Manual, published October 1956.
the most audacious claim made by the fortran development group during the design of the language was that the machine code produce by the compailer would be about half as efficient as what could be produced by hand.

- Fortran II :
compiler was distributed on 1958. It fixed many bugs in the Fortran I and added some significant features to the language, the most important being the independent compilation of subroutines. Few years after, it also added support for double precision and complex data types

Fortran IV :
- Fortran IV was developed in 1961 and released in 1962. It became the most used programming language of its time. IT contains many improvements from Fortran II, like explicit type declarations for variables, logical if construct and capability of passing subprograms as parameters to other subprograms

4. As a research project, compare the features of C with those of the BASIC.
-BASIC was easy for beginners to learn, especially those who were not science oriented, and its smaller dialects can be implemented on computers with very small memories.
-C has adequate control statements and data-structuring facilities to allow its usee in many applications areas. It also has a rich set of operators that provide a high degree of expressiveness.

5.Which of the three original goals of the Fotran design commitee, in your opinion, was most difficult to achieve at that time?
-Speed of the generated object was the most difficult to achieve because of computers at that time has slow and not reliable performances.

6.Make an educated guess as to the most common syntax error in C programs.
-C has lack of complete type checking, this will cause syntax error difficult to found. For example, in versions before C99, functions could be written for which parameters were not type checked

7.LISP began a a pure functional language but gradually acquired more and more inverative features. Why?
-LISP-The first functional programming language was invented to provide language features for list processing. Interest in AI grew out liguistics were concerned with natural language processing, pyschologist were interested in modeling human information storage and retrieval, mathematiicians were interested in mechanizing certain intelligent processes.
Some method must be developed to allow computers to process symbolic data in linked lists which make LISP gradually developed.

9. Why, in your opinion, did Fortran allow names that began with I,J,K,L,M, and N as implicitly integer type?
-Scientists and engineers, used those alphabets to represent an unknown number as variable so they can process the problem. In my pure opinion, it is because it’s easier to use those alphabets as names since most likely Fortran was not yet used to develop a program that is too complex / has too many parts that using such variable name would confuse the programmer

13. What is the primary reason why C became more widely used than Fortran ?
-Fortran can’t allocate new variables or space during execution time. This made recursive subprograms to run and made it difficult to implement a data structure that change shape dinamically. Kinds of program being built were simpler than recent. Thus Fortran are not able to accomodate the requirements of recent software developments. But, C is able to cover most of Fortran’s weakness on developing software that has advanced requirements. That is why C is more widely used.

March 4, 2013

KBP Chapter 1


Rickvian Aldi / 01PBT / 1601253441
Assignment By Mr. Tri Djoko Wahjono
1. Why is useful for a programmer to have some background in language design,  even though her or she may never actually design a programming language?

-Increased capacity to express ideas
-improved background for choosing appropriate languages
-Increased ability to learn new languages
-better understanding of the significance of implementation
-better use of languages that already known
-overall advancement of computing.

2. How can knowledge of programming language characteristic benefit the whole
computer community?

-If those who choose languages were better informed, perhaps better languages would squeeze out poorer ones.

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 dominate artificial intelligence over the past 50 years?

-LISP

6. In what language is UNIX written?

-C

7. What is the disadvantage of having too many features in a language?

-Programmers who must use a large language often learn a subset of the language and ignore its other features.

8. How can user-defined operator overloading harm the readability of a program?

-In which a single operator symbol has more than one meaning, this simplicity
makes assembly language programs less readable because they lack more complex control statements, program structure is less obvious

9. What is one example of a lack of orthogonality in the design of C?

-C has 2 structured data types, arrays and records (structs), records can be returned from functions but arrays cannot.

10. What language used orthogonality as a primary design choice?

-ALGOL 68

11. What primitive control statement is used to build more complicate control statements in languages that lack them?

-selection statement plus GOTO is used to build more complicated control statements such as FOR loop.

12. What construct of a programming language provides process abstraction?

-Subprograms

13. What does it mean for a program to be reliable?

-A program is said to be reliable if it performs to its specifications under all conditions.

14. Why is type checking the parameter of a subprogram important?

-to avoid bugs and syntax error, the earlier errors in program detected, the less cost it is to make the required repairs.

15. What is aliasing?

-is having two or more distinct names that can be used to access the same memory cell.

16. What is exception handling?

-The ability of a program to intercept run time errors.

17. Why is readability important to writability?

-Both readability and writability influence reliability. Programs that are difficult to read are difficult both to write and to modify.




PROBLEM SET

1. Do you believe that solving a problem in a particular algorithmic step requires programming language skills? Support your opinion.

solving problem don't require programming language skills, algorithmic steps are steps that procedurely done, which usually has different case depending on the condition. For example you have problem to make instant cereal. First step is preparing glass and the cereal sachet. Second, open the cereal sachet. Next pour the cereal into the glass. If you have boiled water / hot water dispenser, pour hot water into the glass, else boil water until boiled then pour it into the glass. This problem doesn't require programming language skills.

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

Augusta Ada Byron and now commonly known as Ada Lovelace, born 10 December 1815 was an English mathematician and writer. Her notes on the engine include what is recognized as the first algorithm intended to be processed by a machine.
Because of this, she is often considered the world's first computer programmer.

3. What are the disadvantages of multiple programming languages?

Programmers will needed to know each programming language they need, diffrent
syntax and diffrent system cause programmers need to study other way to code,
which is take more time to study each of programming language.

4. In what way do the languages for scientific applications differ from the languages for business applications? Support your view.


Languages for scientific applications uses relatively simple data structures, but require large numbers of floating-point arithmetic computations. The most common data structures were arrays and matrices; the most common control , structures were counting loops and  selections.
But in languages for business applications is typically used for producing elaborate reports, precise ways of describing and storing decimal numbers and character data, and the ability to specify decimal arithmetic operations.

5. In what way do the languages for artificial intelligence differ from the languages for web software ? Support your view.

In languages for artificial intelligence is characterized by the use of symbolic computations rather than numeric computations. Symbolic computation means that  symbols, consisting of names rather than numbers, are manipulated. Also, symbolic computation is more conveniently done with linked lists of data rather than arrays. languages for web software supported by an eclectic collection of languages,
Because of the pervasive need for dynamic Web content, some computation capability is often included in the technology of content presentation provided by such as HTML, JavaScript, or PHP. There also some markup-languages that have been extended to include constructs that control document processing.

6. Which characteristics of programming languages do you think are the most important and why?

The most important is Reliability. Reliability consists of Type Checking, Exception Handling, Aliasing and Readability and Writability. A programming language needs to check whether the type of the parameters passed and expected are compatible or not. If it is not compatible and it is not checked, the output will be a nonsense. On the other hand, if a program meets a run-time error, it needs to be able to correct the error and resume its work (exception handling). A Language also need to be simple but at the same time orthogonal on a balanced scale. This is so that a program written in a certain language will be easy to maintain in case if there’s an error and also not confusing to other programmers in manners of education.

7. Java uses a semicolon to mark the end of all statements. What are the advantages for and against this design?

advantage of it is semicolon to mark the end of all statements is one good way to increase program readability, to end each statements and decrease program ambigous. the disadvantage of it is without this semicolon, the compiler will be error. and adding extra semicolon unintentionally will terminate a unfinished statement and doesn't showing syntax error, which in large program cause programmer need to difficultly find out what cause the logical problem.

10. Make a comparative study of the cost of software and hardware!

software and hardware cost are now variative depending on
hardware:
performance
manufacturing cost
Branded
capatibility

software:
the use (for personal, or bussines company use)
development cost
brand of the software

there are a lot of hardware that sold cheap nowdays, large number of manufacturer and brands cause brands to compete each other. But some of hardware are exclusive and expensive for example database server for large worldwide company.
Some personal software sold cheap nowdays, easy access and purchasing lower the
cost, but some expensive software are for spesific purpose and developed by
company.

15. Name some languages which use preprocessor directives and some which don’t.

What are the advantages and disadvantages of preprocessor directives ?
Some languages that use preprocessor directives : C, C++ and C#
Advantages of preprocessor directives :

1. Reduces length of the code and time spent for writing the codes
2. Increases execution speed of the program
3. Increases Readability and Writability of the program
Disadvantages :
1. Increases size of the program
2. Unlike functions, macros can only return the last value processed
3. Causes an error since there’s no variable type check, unlike functions