Written on Tuesday, May 06, 2008 by Ennah, the comsci student
Assume the following rules of precedence for expressions:
Highest is addition (+)
then subtraction (-)
then multiplication (*)
then division (/)
Evaluate inputs such as:
(a) 1+4*3-2/2 Output: 5*3-2/2 = 5*1/2 = 5/2 = 2.5
(b) 5-2/2+1*2 Output: 5-2/3*2 = 3/3*2 = 3/6 = 0.5
(c) 3-2+4-2+5 Output: 3-6-7 = -3 - 7 = -10
Posted in
computer science,
principles of programming
|
Written on Monday, May 05, 2008 by Ennah, the comsci student
Chapter 5
Part 1. Define the following:
1. Descriptor
2. Ordinal, enumeration, subrange types
3. Static array, fixed static-dynamic array, stack-dynamic array, dynamic array
4. Aggregate constant
5. Row major order, column major order
6. Fully qualified, elliptical references to fields in records
7. Union, free union, discriminated union
Part 2. Answer briefly.
1. Why does a decimal value waste memory space?
2. What are the design issues for character string types?
3. What are the design issues for pointer types?
Chapter 6
Part 1. Define the following:
1. Operator precedence, operator associativity
2. Functional side effect
3. Coercion
4. Conditional expression
5. Overloaded operator
6. Narrowing & widening conversions
Part 2. Answer briefly.
1. What is the purpose of a compound assignment operator?
2. Describe a situation in which the add operator in a programming language would not be associative.
Answers
Chapter 5
Part 1.
Define the following:
1.Descriptor
A descriptor is the collection of the attributes of a variable. In an implementation a descriptor is a collection of memory cells that store variable attributes. If attributes are all static, descriptors are required only at compile time. They are built by the compiler usually as a part of the symbol table, and are used during compilation. For dynamic attributes, however, part or all of the descriptor must be maintained during execution. In this case the descriptor is used by the run-time system.
2. Ordinal, enumeration, subrange types
An ordinal type is one in which the range of possible values can be easily associated with the set of positive integers. In many languages, users can define two kinds of ordinal types: enumeration and subrange.
An enumeration type is one in which all of the possible values, which become symbolic constants, are enumerated in the definition. Enumeration types have advantages to readability and reliability.
Example: In Ada, type DAYS is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
A subrange type is a contiguous subsequence of an ordinal type. Subrange types were introduced by Pascal and are also included in Ada. There are no design issues that are specific to subrange types.
Example: 12 ... 14 is a sub range of integer type.
3. Static array, fixed static-dynamic array, stack-dynamic array, dynamic array
A static array is one in which the subscript ranges are statically bound and storage allocation is static (done before run time). The advantage of static array is efficiency: No dynamic allocation or deallocation is required.
A fixed stack-dynamic array is one in which the subscript ranges are statically bound, but the allocation is done at declaration elaboration time during execution. The advantage of fixed stack-dynamic arrays over static arrays is space efficiency. A large array in one procedure can use the same space as a large array in different procedure, as long as both procedures are not active at the same time.
A stack-dynamic array is one in which the subscript ranges are dynamically bound and the storage allocation is dynamic (done during run time). Once the subscript ranges are bound and the storage is allocated, however, they remain fixed during the lifetime of the variable. The advantage of stack-dynamic array over static and fixed-stack dynamic array is flexibility. The size of an array may need not to be known until the array is bound to be used.
A dynamic array is one in which the binding of subscript ranges and allocation is dynamic and can change any number of times during the array’s lifetime. The advantage here is flexibility: Arrays can grow and shrink during program execution as the need for space changes.
4. Aggregate constant
Aggregate constant are initializing values which are assigned to the array element locations in the order in which they appear or by directly assigning them to an index operator using direct assignment (=> operator). They are usually delimited by parentheses.
5. Row major order, column major order
Row major order is one way of mapping multidimensional array to one dimensional array in which the elements of the array that have as their first subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the first subscript, and so forth.
Column major order is one way of mapping multidimensional array to one dimensional array in which the elements of the array that have as their last subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the last subscript, and so forth.
6. Fully qualified, elliptical references to fields in records
A fully qualified reference to a record field is one in which all intermediate record names, from the largest enclosing record to the specific field, are named in the reference.
An elliptical reference to a record field is one in which the field is named, but any or all of the enclosing record names can be omitted, as long as the resulting reference is unambiguous in the referencing environment.
7. Union, free union, discriminated union
A union is a type whose variables are allowed to store different type values at different times during execution.
A free union is a union for which there is no language support for type checking. Programmers are allowed complete freedom from type checking in their use. FORTRAN, C, and C++ have this kind of union.
A discriminated union has a field that indicates the type of the data in the union. This field is called a discriminant. Pascal and Ada have discriminated unions.
Part 2. Answer briefly.
1. Why does a decimal value waste memory space?
Decimal values are designed to be accurate to a given number of decimal places. Because of this, decimal takes more memory than binary representation because decimal values must be represented by using at least 4-bits per digit in the decimal number, so for instance:
12.69 is represented as: 0001 0010 0110 1001
1 => 0001
2 => 0010
6 => 0110
9 => 1001
Therefore, to store a six-digit decimal number requires 24 bits of memory. However, it takes only 20 bits to store the same number in binary.
2. What are the design issues for character string types?
Design issues for character string types:
a. Is character string a primitive type or just a special kind of array?
b. Is the length of character string objects static or dynamic?
3. What are the design issues for pointer types?
Design issues for pointer types:
a. What is the scope and lifetime of pointer variables?
b. What is the lifetime of heap-dynamic variables?
c. Are pointers restricted to pointing at a particular type?
d. Are pointers used for dynamic storage management, indirect addressing, or both?
e. Should a language support pointer and reference types?
Chapter 6
Part 1. Define the following:
1. Operator precedence, operator associativity
Operator precedence are rules for expression evaluation that define the order in which the operators of different precedence levels are evaluated.
Operator associativity is the rules of the language which determine, when there are two adjacent occurrences of operators of the same level of precedence, which operator is evaluated first.
2. Functional side effect
Functional side effect is the side effect of a function that occurs when the function changes either one of its parameters or a global variable.
Example: A + FUN(A) (This works only if FUN changes A, then there is an effect)
3. Coercion
Coercion is the implicit type conversion that occurs when two operands of an operator are not of the same type (and that’s legal in the language) and the compiler must choose one of them to be coerced and supply the proper code for the coercion.
4. Conditional expression
Conditional expression is an assignment statement of the general form
expression_1 ? expression_2: expression_3 (if-then-else)
where expression_1 is interpreted as Boolean expression. If expression_1 is evaluated as true, the value of the whole expression is the value of expression_2; otherwise, it is the value of expression_3
5. Overloaded operator
Overloaded operator is an operator that has multiple purposes assigned to it, i.e. , in Java, + is used both for numeric additon and for string concatenation
6. Narrowing & widening conversions
A narrowing conversion converts a value to a type that cannot store even approximations of all the values of the original type, for example, converting a double to a float in Java (the range of double is much larger than that of float).
A widening conversion converts a value to a type that can include at least approximations of all the values of the original type, for example, converting an int to a float in Java. Widening conversion are nearly always safe.
Part 2. Answer briefly.
1. What is the purpose of a compound assignment operator?
A compound assignment operator is a shorthand method of specifying a commonly needed form of assignment. The form of assignment that can be abbreviated with this technique has the destination variable also appearing as the first operand on the first side, as in: a = a + b.
2. Describe a situation in which the add operator in a programming language would not be associative.
Consider the equation A + B + C where A and B are large positive numbers C is a negative number with a very large absolute value. If we were to associate the equation as follows: A + (B + C) then the equation will evaluate correctly, as B + C will not cause overflow. However, the situation is not associative as we could associate the equation as follows: (A + B) + C and have an overflow situation which would not yield the same result as the first associations evaluation.
Posted in
computer science,
principles of programming
|
Written on Monday, May 05, 2008 by Ennah, the comsci student
My 2nd Machine Problem. Similar to the 1st Machine Problem. Again in VB.NET
Input: An assignment sentence
(see ambiguous grammar for simple assignment sentence)
assign --> id = expr
id --> A | B | C
expr --> expr + expr | expr *expr |(expr) | id
Output:
"Syntax error" if the grammar is incorrect
or
"Valid" if the grammar is correct.
Example.
A = B + C * B
Valid
B = A * (C + B)
Valid
A = A+C * B+
Syntax error
Screenshots:
Posted in
computer science,
principles of programming
|
Written on Monday, May 05, 2008 by Ennah, the comsci student
My Research 3. I found all of the answer in Sebasta's book. This research helped me in my 2nd machine problem, checking grammars.
1. Define: Language, syntax, semantics, lexemes, tokens.
2. Describe the operations of a general language recognizer and a general language generator.
3. What is the difference between a sentence & a sentence form?
4. What is grammar? Describe CFG, BNF, EBNF.
5. Differentiate between a synthesized and an inherited attribute.
6. What is an attribute grammar? What is its primary purpose?
7. Differentiate between a static and dynamic semantics.
8. Discuss the 3 primary methods of semantic description: operational, axiomatic & denotational.
Answers
1. Define: Language, syntax, semantics, lexemes, tokens.
Language - is set of sentences or strings of characters over some alphabet.
Syntax - is the form or structure of the expressions, statements and program units.
Semantics - is the meaning of expressions, statements and program units.
Lexeme - is the lowest level syntactic unit of a language (e.g. *, sum, begin)
Token - a category of a lexeme (e.g. identifier, equal_sign)
2. Describe the operations of a general language recognizer and a general language generator.
A general language recognizer is a recognition device capable of reading strings of characters from the alphabet. It would analyze the given string and it would either accept or reject the string based from the language given. These recognition devices are like filters separating correct sentences from those that are incorrectly. A recognizer is used in the syntax analysis part of the compiler. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. The syntax analyzer just determines whether the given programs are syntactically correct.
A general language generator is a device that can be used to generate the sentences of the language. It generates unpredictable sentences which makes a generator seems to be a device of limited usefulness as language descriptor. However, people prefer certain forms of generators over recognizer because they can be more easily read and understand them. By contrast, the syntax-checking portion of the compiler which is a language recognizer is not as useful a language descriptor for programmers because it can be used in a trial-and-error mode. For example, to determine the correct syntax of a particular statement using the compiler, the programmer can only submit a guessed-at version and see if the compiler accepts it. On the other hand, it is often possible to determine whether the syntax of a particular statement is correct by comparing it with the structure of the generator.
3. What is the difference between a sentence & a sentence form?
A sentence is a sentential form that has only terminal symbols. A sentence form is every string of symbols in the derivation.
4. What is grammar? Describe CFG, BNF, EBNF.
Grammar is a formal language generation mechanism that is commonly used to describe the syntax of programming languages. A grammar is a 4-tuple (N, T, S, P), whereN is a set of nonterminal symbolsT is a set of terminal symbols S is the start symbolP is a set of productions (also called rewrite rules)
Example of Grammar
Nonterminals = {S, A}
Terminals = {a, b}
Start symbol = SP = { S --> bA, S --> aA, A --> aA, A --> b}
A sentence consists entirely of terminal symbols (in this grammar, a’s and b’s)
The productions can be used to generate sentences, starting with a rule for the start symbol (S).
Context Free Grammars (CFG) is a notation whose productions take the form
A -->a, where A is a single nonterminal symbol and a is any string of terminals and/or nonterminals. Context-free grammars are used to describe the syntax of modern programming languages.
Backus Naur Form (BNF) is a metalanguage, a language used to describe another language. In BNF, rules are used to describe the syntax of a language. There is at least one rule for each language abstraction (nonterminal). BNF is equivalent to CFGs.
Extended Backus Naur Form (EBNF) is an extended version of BNF because of BNF’s few minor inconveniences. The extensions do not enhance the descriptive power of BNF; they only increase its readability and writability. Three versions are commonly included in the various versions of EBNF: Optional parts are placed in brackets([]) ---> ident [ ( )Put alternatives in parentheses and separate them with vertical bars ---> (+|-) constPut repetitions (0 or more) in braces ({}) ---> { , }
5. Differentiate between a synthesized and an inherited attribute.
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.In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.
For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax.
6. What is an attribute grammar? What is its primary purpose?
An attribute grammar is a device used to describe more of the structure of a programming language than is possible with a context-free grammar. An attribute grammar is an extension to a context-free grammar. The primary purpose of an attribute grammar is it allows certain language rules to be described, such as type of compatibility. An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler.
7. Differentiate between a static and dynamic semantics.
Static semantics is more on the legal forms of programs (syntax rather symantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.
Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions
8. Discuss the 3 primary methods of semantic description: operational, axiomatic & denotational.
Operational Semantics is a concept to describe the meaning of the program by executing its statements on the machine, either real or simulated. The changes that occur in the machine’s state when it executes a given statement define the meaning of that statement.
Axiomatic Semantics is a concept that is in conjunction with the development of a method to prove the correctness of a program. Such correctness proofs, when they can be constructed, show that a program performs the computation described by its specifications. In a proof, each statement of a program is both preceded and followed by a logical expression that specifies constraints on program variables. These, rather than the entire state of an abstract machine (as with operational semantics), are used to specify the meaning of the statement. The notation used to describe constraints, indeed the language of axiomatic semantics, is predicate calculus.
Denotational Semantics is a method of describing the meaning of the programs solidly based on recursive function theory. The fundamental concept of the denotational semantics is to define for each language entity both a mathematical object and a function that maps instances of that entity onto instances of mathematical object. Because the objects are rigorously defined, they represent the exact meaning of their corresponding entities. The idea is based on the fact that there are rigorous ways of manipulating mathematical objects but not for programming constructs. The difficulty of this method lies in creating the objects and the mapping functions. The method is named denotational because the mathematical objects denote the meaning of their corresponding syntactic entities.
Posted in
computer science,
principles of programming
|
Written on Monday, May 05, 2008 by Ennah, the comsci student
Machine Problem a.k.a. MP in Principles of Programming. This is the dreadful "Turing Machine". I put here some of my screenshots. Initially made it in VB.net and I have a copy in Java. If ever you want to make one and you need help, you can always email me.
Posted in
computer science,
principles of programming
|
Written on Saturday, May 03, 2008 by Ennah, the comsci student
Imagine some decades ago, the only mathematical machine that people are using is the Turing Machine. Gosh, I imagined their life to be miserable because my life was miserable because of this machine problem. It was really VERY HARD. and complicated.
Post here my research 2 about Turing Machine. In which it really helped me to understand it better and I actually come up with its replica in VB.Net and Java. If you need help in building one, I can help you.
What is a Turing Machine?
A Turing machine is a computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.
What is its Purpose?
A Turing machine is a theoretical computing machine that serves as an idealized model for mathematical calculation. Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do.
There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:
- read (i.e. identify) the symbol currently under the head
- write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
- move the tape left one square
- move the tape right one square
- change state
- halt.
What is the mechanical parts of a Turing Machine?
- an Input/Output Tape,
- the Turing Machine itself,
- and a Rule List
The Input/Output Tape is like the roll of paper you find on some printing calculators, only this roll of paper is infinitely long and is stretched like a scroll between two rollers so it can be wound forwards and backwards. The tape is divided into cells. The cells contain the input and output symbols and change frequently as a program is running. The Turing Machine itself is some kind of mechanical 'black box' that sits above the tape and reads in symbols one at a time from its Read/Write head. The machine is always in a particular internal State indicated by a number on the box. The Rule List is what determines the Machine's move at any particular point. The rule looks at the state of the head, and the color of the cell that the head is on. Then it specifies what the new state of the head should be, what color the head should "write" onto the tape, and whether the head should move left or right.
How it works
A Turing machine has a finite number of states, and, at any point in time, a Turing machine is in one of these states. A Turing machine begins its operation in the start state. A Turing machine halts when it moves into one of the halt states. When a Turing machine begins running, it is in its start state and its tape head is positioned over one of the cells on the tape; the symbol on this cell is the current symbol.
The operation of a Turing machine proceeds as follows: - The Turing machine reads the tape symbol that is under the Turing machine's tape head. This symbol is referred to as the current symbol.
- The Turing machine uses its transition function to map the current state and current symbol to the following: the next state, the next symbol and the movement for the tape head. If the transition function is not defined for the current state and current symbol, then the Turing machine crashes.
- The Turing machine changes its state to the next state, which was returned by the transition function.
- The Turing machine overwrites the current symbol on the tape with the next symbol, which was returned by the transition function.
- The Turing machine moves its tape head one symbol to the left or to the right, or does not move the tape head, depending on the value of the 'movement' that is returned by the transition function.
- If the Turing machine's state is a halt state, then the Turing machine halts. Otherwise, repeat sub-step #1.
The Turing Machine reads a symbol from the Input/Output Tape and consults its Rule List. It then performs two actions. - It modifies its internal state
- It writes a symbol on the tape
Or Moves its R/W head left or right.
Example:
Suppose the machine is in State 10 and the Read/Write head is positioned on the letter 'A'. The Turing Machine would consult its Rule List and possibly find the following rule: 10 A 12 > This rule says: If you are in State 10 and reading an 'A' change to State 12 and advance the tape head to the right. References:
http://www.wolframscience.com/prizes/tm23/turingmachine.html
http://plato.stanford.edu/entries/turing-machine/#Describing
http://en.wikipedia.org/wiki/Turing_machine
http://www.unidex.com/turing/tm_intro.htm
Posted in
computer science,
principles of programming
|
Written on Thursday, May 01, 2008 by Ennah, the comsci student
This is my 1st research in Principles of Programming. I just got 17/20 in this research because it was my 1st research ever. Actually, I thought the research was not graded so I really did not give my best to search. Anyway, still a good start.
Describe briefly the ff:
1. structured programming language
2. procedural programming language
3. functional programming language
4. object-oriented programming language
5. meta-languages
Give at least 2 examples each.
Answers
1. Structured Programming Language
Structured programming (sometimes known as modular programming) is a subset of procedural programming that enforces a logical structure on the program being written to make it more efficient and easier to understand and modify.
Structured programming frequently employs a top-down design model, in which developers map out the overall program structure into separate subsections. A defined function or set of similar functions is coded in a separate module or submodule, which means that code can be loaded into memory more efficiently and that modules can be reused in other programs. After a module has been tested individually, it is then integrated with other modules into the overall program structure.
Program flow follows a simple hierarchical model that employs looping constructs such as "for," "repeat," and "while." Use of the "Go To" statement is discouraged.
Examples: Ada, Pascal and dBASE
2. Procedural Programming Language
Procedural programming is the most natural way to tell a computer what to do, and the computer processor's own language which is the machine code, is procedural, so the translation of the procedural high-level language into machine code is straightforward and efficient. What is more, procedural programming has a built-in way of splitting big lists of instructions into smaller lists: the function.
A procedural program is written as a list of instructions, telling the computer, step-by-step, what to do: Open a file, read a number, multiply by 4, display something. Program units include the main or program block, subroutines, functions, procedures; file scoping; includes/modules; libraries.
Possible benefits:
* The ability to re-use the same code at different places in the program without copying it.
* An easier way to keep track of program flow than a collection of "GOTO" or "JUMP" statements (which can turn a large, complicated program into spaghetti code).
* The ability to be strongly modular or structured.
Examples: C, C++, Fortran, Pascal, Basic and Maple
3. Functional Programming Language
Functional programming languages emphasize rules and pattern-matching. While they appear non-intuitive to those who have only experienced procedural languages, they provide succinct and natural programming structures for those who gain some experience. Functional programming is particularly useful for mathematical work, where the notion of "function" is
already a well established concept.
Examples: Mathematica, APL, Erlang, Haskell, Lisp, ML and F#
4. Object Oriented Programming Language
Object-oriented programming (OOP) is a programming paradigm that uses "objects" and their interactions to design applications and computer programs. It is based on several techniques, including encapsulation, modularity, polymorphism, and inheritance. It was not commonly used in mainstream software application development until the early 1990s. Many modern programming languages now support OOP.
Examples: Java and Visual Basic.Net
5. Meta-languages
In logic and linguistics, a metalanguage is a language used to make statements about other languages (object languages). Formal syntactic models for the description of grammar, e.g. generative grammar, are a type of metalanguage.
More broadly, it can refer to any terminology or language used to discuss language itself—a written grammar, for example, or a discussion about language use.
Example: HTML, XHTML, Backus-Naur form - earliest metalanguages
References:
http://searchcio-midmarket.techtarget.com/sDefinition/0,,sid183_gci866374,00.html
http://amath.colorado.edu/computing/mmm/funcproc.html
http://en.wikipedia.org/wiki/Object-oriented_programming
http://wapedia.mobi/en/Functional_programming
Posted in
computer science,
principles of programming
|
Written on Tuesday, April 29, 2008 by Ennah, the comsci student
Last Semester, I took up this subject - Principles of Programming. This is the most challenging subject I've ever gone through. It kept my creative juices flowing. I was lucky to have a good professor, Ms. Marissa Justan. I learned a lot.
Principles of Programming is a subject about basic concepts and seeing how these concepts are implemented in representative programming languages. I am able to adapt in one programming language patterns learned in other through this subject.
I was really lucky to have a high grade in this subject. I really had fun programming the exercises. I will post some of my exercises and researches if ever I have the time. We also had researches about programming concepts. Our reference book is
"Concepts of Programming Languages" by Robert Sebesta.
I'll post here some useful site that was able to help me throughout this subject:
http://csci.csusb.edu/public/csci/gvaldivi/education/cs320/default.htm>> I got a lot of chapter review answers of Sebasta's book in this site.
http://www.cc.gatech.edu/classes/cs3411b_99_winter/TextNotes.html>> textbook lecture notes of Sebesta's book in powerpoint slides
I forget the other links. These are the links for now. Hope you'll find it useful.
Posted in
computer science,
principles of programming
|
.jpg)
