Book : Concept of Programming Language
Page 342
Review Question
1. Define operator precedence and operator associativity.
operator precedence :expression evaluation partially define
the order in which the operators of different precedence levels are evaluated.
operator associativity:When an expression contains two adjacent
occurrences of operators with the same level of precedence, the question of which operator is evaluated first
3.What is a prefix operator?
the operator precede the operands
5. What operator usually has right associativity?
the indices never need to be stored
6. What associativity rules are used by APL?
all operators have the same level of
precedence. Thus, the order of evaluation of operators in APL expressions is
determined entirely by the associativity rule, which is right to left for all operators.
8. Define functional side effect.
A side effectof a function, naturally called a functional side
effect,occurs when the function changes either one of its parameters or a
global variable. (A global
variable is declared outside the function but is accessible in the function.
44. Define type error.
type erroris the application of an operator to an operand of an inap-propriate type.
45. Define strongly typed.
widely acknowledged as being a highly valuable language characteris-tic
47. What is a nonconverting cast?
extracting the value of a variable of one type and using it as if it were of a different type
48. What languages have no type coercions?
Ada
49. Why are C and C++ not strongly typed?
because both include union types, which are not type checked.
Page 343
Problem Set
1. When might you want the compiler to ignore type differences in an expression?
run time
3.Do you think the elimination of overloaded operators in your favorite language would be beneficial?Why or why not?
no, because operator need to multiply use the operator, so it won’t be hard to use the operator again and again
4. Would it be a good idea to eliminate all operator precedence rules and
require parentheses to show the desired precedence in expressions? Why
or why not?
no, because it partially define the order in which the operators of different precedence levels are evaluated
11. In the Burroughs Extended ALGOL language, matrices are stored as a
single-dimensioned array of pointers to the rows of the matrix, which are
treated as single-dimensioned arrays of values. What are the advantages
and disadvantages of such a scheme?
The advantage of this scheme is that accesses that are done in order of the rows can
be made very fast; once the pointer to a row is gotten, all of the elements of the row can
be fetched very quickly. If, however, the elements of a matrix must be accessed in
column order, these accesses will be much slower; every access requires the fetch of a
row pointer and an address computation from there. Note that this access technique was
devised to allow multidimensional array rows to be segments in a virtual storage
management technique. Using this method, multidimensional arrays could be stored and
manipulated that are much larger than the physical memory of the computer.
15. What are the arguments for and against Head management’s single-size cells and variable-size cells?
Integer values stored in decimal waste storage in binary memory computers, simply as
a result of the fact that it takes four binary bits to store a single decimal digit, but those
four bits are capable of storing 16 different values. Therefore, the ability to store six out
of every 16 possible values is wasted. Numeric values can be stored efficiently on binary
memory computers only in number bases that are multiples of 2. If humans had
developed hands with a number of fingers that was a power of 2, these kinds of problems
would not occur.
21. In what way is dynamic type checking better than static type checking?
run time
2013-06-22
Programming Language Concept (6)
Book : Concept of Programming Language
Page 312
Review Questions
1. What is a descriptor?
A descriptor is the collection of the attributes of a variable.
2. What are the advantages and disadvantages of decimal data types?
The advantages of decimal data types is being able to precisely store decimal values, at least those within a restricted range, which can’t be done with floating-point. And the disadvantages of decimal data types are that the range of values is restricted because no exponents are allowed, and their representation in memory is mildly wasteful.
3. What are the design issues for character sting types?
The two most important design issues that are specific to character string types are the following:
- Should strings be simply a special kind of character array or a primitive type?
- Should strings have static or dynamic length?
4. Describe the three string length options.
- Static length string, the length can be static and set when the string is created.
- Limited dynamic length strings, allow strings to have varying length up to a declared and fixed maximum set by the variable’s definition.
- Dynamic length strings, allow strings to have varying length with no maximum.
8. What are the design issues for arrays?
The primary design issues specific to arrays are the following:
- What types are legal for subscripts?
- Are subscripting expressions in element references range checked?
- When are subscript ranges bound?
- When does array allocation take place?
- Are ragged or rectangular multidimensioned arrays allowed, or both?
- Can arrays be initialized when they have their storage allocated?
- What kinds of slices are allowed,if any?
11.How does JavaScript support sparse arrays?
JavaScript sparse arrays means that the subscript values need not be contiguous.
12. What languages support negative superscripts?
Ruby and Lua
13. What languages support array slices with stepsized?
Phyton, Perl, and Ruby.
14. What array initialization feature is available in Ada that is not available in other common imperative languages?
Ada provides two mechanisms for initializing arrays in the declaration statement: by listing them in the order in which they are to be stored, or by directly assigning them to an index position using the => operator, which in Ada is called an arrow.
23. What is the primary difference between a record and a tuple?
In tuple, the elements are not named.
24. Are the tuples of Phyton mutable?
No, Phyton includes an immutable tuple type.
32. What are the design issues for unions?
The primary design issues that are particular to union types are the following:
- Should type checking be required? Note that any such type checking must be dynamic.
- Should unions be embedded in records?
35. What are the design issues for pointer types?
The primary design issues particular to pointers are the following:
- What are the scope and lifetime of a pointer variable?
- What is the lifetime of a heap-dynamic variable?
- Are pointers restricted as to the type of value to which they can point?
- Are pointers used for dynamic storage management, indirect addressing, or both?
- Should the language support pointer types, reference types, or both?
43. What is a compatible type?
A compatible type is one that either is legal for the operator or is allowed under language rules to be implicitly converted by compiler-generated code to a legal type.
48. What languages have no type coercions?
Ada
Page 314
Problem Set
1. What are the arguments for and against four signed integer sized in Java?
Bytes =1 byte, short = 2 bytes, integer = 4 bytes, long = 8 bytes. As a result, depending on the domain of the variable required, data types are used.
2. How are negative integers stored in memory?
A negative integer could be stored in sign-magnitude notation, in which the sign bit is set to indicate negative and the remainder of the bit string represents the absolute value of the number. Sign-magnitude notation does not lend itself to computer arithmetic. Most computers now use a notation called twos complement to store negative integers, which is convenient for addition and subtraction.
5. What disadvantages are there in implicit dereferencing of pointers, but only in certain contexts? For example, consider the implicit dereference of a pointer to a record in Ada when it is used to reference a record field.
When implicit dereferencing of pointers occurs only in certain contexts, it makes the language slightly less orthogonal. The context of the reference to the pointer determines its meaning. This detracts from the readability of the language and makes it slightly more difficult to learn.
7. Compare the pointer and reference type variable in C++.
A C++ reference type variable is a constant pointer that’s always implicitly dereferenced.
9. C provides two derived data types both for name and structure type equivalence: struct and union. Makes a study on when to use structtype variables and union type variables.
If all data members of the variables are to be used at once then struct type variables are required, otherwise union type variables should be used.
21. In what way is dynamic type checking better than static type checking?
Static checking reduces programmer flexibility.
22. Explain how the dangling-pointer problem can be removed using the locks-and-keys approach.
In the locks-and-keys approach, pointer values are represented as ordered pairs (key, address), where the key is an integer value. Heap-dynamic variables are represented as the storage for the variable plus a header cell that stores an integer lock value. When a heap-dynamic variable is allocated, a lock value is created and placed both in the lock cell of the heap-dynamic variable and in the key cell of the pointer that is specified in the call to new.
Page 312
Review Questions
1. What is a descriptor?
A descriptor is the collection of the attributes of a variable.
2. What are the advantages and disadvantages of decimal data types?
The advantages of decimal data types is being able to precisely store decimal values, at least those within a restricted range, which can’t be done with floating-point. And the disadvantages of decimal data types are that the range of values is restricted because no exponents are allowed, and their representation in memory is mildly wasteful.
3. What are the design issues for character sting types?
The two most important design issues that are specific to character string types are the following:
- Should strings be simply a special kind of character array or a primitive type?
- Should strings have static or dynamic length?
4. Describe the three string length options.
- Static length string, the length can be static and set when the string is created.
- Limited dynamic length strings, allow strings to have varying length up to a declared and fixed maximum set by the variable’s definition.
- Dynamic length strings, allow strings to have varying length with no maximum.
8. What are the design issues for arrays?
The primary design issues specific to arrays are the following:
- What types are legal for subscripts?
- Are subscripting expressions in element references range checked?
- When are subscript ranges bound?
- When does array allocation take place?
- Are ragged or rectangular multidimensioned arrays allowed, or both?
- Can arrays be initialized when they have their storage allocated?
- What kinds of slices are allowed,if any?
11.How does JavaScript support sparse arrays?
JavaScript sparse arrays means that the subscript values need not be contiguous.
12. What languages support negative superscripts?
Ruby and Lua
13. What languages support array slices with stepsized?
Phyton, Perl, and Ruby.
14. What array initialization feature is available in Ada that is not available in other common imperative languages?
Ada provides two mechanisms for initializing arrays in the declaration statement: by listing them in the order in which they are to be stored, or by directly assigning them to an index position using the => operator, which in Ada is called an arrow.
23. What is the primary difference between a record and a tuple?
In tuple, the elements are not named.
24. Are the tuples of Phyton mutable?
No, Phyton includes an immutable tuple type.
32. What are the design issues for unions?
The primary design issues that are particular to union types are the following:
- Should type checking be required? Note that any such type checking must be dynamic.
- Should unions be embedded in records?
35. What are the design issues for pointer types?
The primary design issues particular to pointers are the following:
- What are the scope and lifetime of a pointer variable?
- What is the lifetime of a heap-dynamic variable?
- Are pointers restricted as to the type of value to which they can point?
- Are pointers used for dynamic storage management, indirect addressing, or both?
- Should the language support pointer types, reference types, or both?
43. What is a compatible type?
A compatible type is one that either is legal for the operator or is allowed under language rules to be implicitly converted by compiler-generated code to a legal type.
48. What languages have no type coercions?
Ada
Page 314
Problem Set
1. What are the arguments for and against four signed integer sized in Java?
Bytes =1 byte, short = 2 bytes, integer = 4 bytes, long = 8 bytes. As a result, depending on the domain of the variable required, data types are used.
2. How are negative integers stored in memory?
A negative integer could be stored in sign-magnitude notation, in which the sign bit is set to indicate negative and the remainder of the bit string represents the absolute value of the number. Sign-magnitude notation does not lend itself to computer arithmetic. Most computers now use a notation called twos complement to store negative integers, which is convenient for addition and subtraction.
5. What disadvantages are there in implicit dereferencing of pointers, but only in certain contexts? For example, consider the implicit dereference of a pointer to a record in Ada when it is used to reference a record field.
When implicit dereferencing of pointers occurs only in certain contexts, it makes the language slightly less orthogonal. The context of the reference to the pointer determines its meaning. This detracts from the readability of the language and makes it slightly more difficult to learn.
7. Compare the pointer and reference type variable in C++.
A C++ reference type variable is a constant pointer that’s always implicitly dereferenced.
9. C provides two derived data types both for name and structure type equivalence: struct and union. Makes a study on when to use structtype variables and union type variables.
If all data members of the variables are to be used at once then struct type variables are required, otherwise union type variables should be used.
21. In what way is dynamic type checking better than static type checking?
Static checking reduces programmer flexibility.
22. Explain how the dangling-pointer problem can be removed using the locks-and-keys approach.
In the locks-and-keys approach, pointer values are represented as ordered pairs (key, address), where the key is an integer value. Heap-dynamic variables are represented as the storage for the variable plus a header cell that stores an integer lock value. When a heap-dynamic variable is allocated, a lock value is created and placed both in the lock cell of the heap-dynamic variable and in the key cell of the pointer that is specified in the call to new.
Programming Language Concept (5)
Book : Concept of Programming Language
Page 235
Review Questions
1. What are the design issues for names?
The following are the primary design issues for names:
- Are names case sensitive?
- Are the special words of the language reserved words or keywords?
2. What is the potential danger of case-sensitive names?
To some people, the problems are about writability and readability. For readability, because names that look very similar in fact denote different entities. For writability, many of the predefined names including both uppercase and lowercase letters.
3. In what way are reserved words better than keywords?
As a language design choice, reserved words are better than keywords because the ability to redefine keywords can be confusing.
4. What is an alias?
Aliases are the variables when more than one variable name can be used to access the same memory location.
6. State transition diagram is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause transitions among the states.
8. What are the two distinct goals of syntax analysis?
First, the syntax analyzer must check the input program to determine whether it is syntactically correct.
When an error is found, the analyzer must produce a diagnostic message and
recover. In this case, recovery means it must get back to a normal state and
continue its analysis of the input program. This step is required so that the
compiler finds as many errors as possible during a single analysis of the input
program. If it is not done well, error recovery may create more errors, or at
least more error messages. The second goal of syntax analysis is to produce a
complete parse tree, or at least trace the structure of the complete parse tree,
for syntactically correct input. The parse tree (or its trace) is used as the basis
for translation.
9. The differences between top-down and bottom-up parsers:
- Syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree built from the root downward to the leaves.
- Bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order, which mean the parse tree is built from leaves upward to the root
18. What is left factoring?
This states that a <variable> is either an identifier or an identifier followed by
an expression in brackets (a subscript). These rules clearly do not pass the
pair-wise disjointness test, because both RHSs begin with the same terminal, identi-fier.
20. What is a simple phrases of a sentential form?
simple phrases is just a phrase that takes a single derivation step from its root nonterminal node.
21. What is the handle of a sentential form?
mathematically concise, it provides little help in finding the handle
of a given right sentential for
Page 236
Problem Set
2. What is l-value? Write a statement in C language which gives the compile time error “l-value required”.
The address of a variable is called its l-value.
4. Why is the type declaration of a variable necessary? What is the value range of the int type variable in Java?
because it must include an initial value, byte
5. approaches to building a lexical analyzer:
- Write a formal description of the token patterns of the language using a descriptive language related to regular expressions. These descriptions are used as input to a software tool that automatically generates a lexical analyzer. There are many such tools available for this. The oldest of these, named lex, is commonly included as part of UNIX systems.
- Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
- Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
6. State transition diagram is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause transitions among the states.
8.a.Assuming static scooping, in the following, which declaration of x is the correct one for a reference to x?
b.Repeat part a, but assume dynamic scoping.
(a) i. Sub1
ii. Sub126
iii. Main
(b) i. Sub1
ii. Sub1
iii. Sub1
9. The differences between top-down and bottom-up parsers:
- Syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree built from the root downward to the leaves.
– Bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order, which mean the parse tree is built from leaves upward to the root
Page 235
Review Questions
1. What are the design issues for names?
The following are the primary design issues for names:
- Are names case sensitive?
- Are the special words of the language reserved words or keywords?
2. What is the potential danger of case-sensitive names?
To some people, the problems are about writability and readability. For readability, because names that look very similar in fact denote different entities. For writability, many of the predefined names including both uppercase and lowercase letters.
3. In what way are reserved words better than keywords?
As a language design choice, reserved words are better than keywords because the ability to redefine keywords can be confusing.
4. What is an alias?
Aliases are the variables when more than one variable name can be used to access the same memory location.
6. State transition diagram is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause transitions among the states.
8. What are the two distinct goals of syntax analysis?
First, the syntax analyzer must check the input program to determine whether it is syntactically correct.
When an error is found, the analyzer must produce a diagnostic message and
recover. In this case, recovery means it must get back to a normal state and
continue its analysis of the input program. This step is required so that the
compiler finds as many errors as possible during a single analysis of the input
program. If it is not done well, error recovery may create more errors, or at
least more error messages. The second goal of syntax analysis is to produce a
complete parse tree, or at least trace the structure of the complete parse tree,
for syntactically correct input. The parse tree (or its trace) is used as the basis
for translation.
9. The differences between top-down and bottom-up parsers:
- Syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree built from the root downward to the leaves.
- Bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order, which mean the parse tree is built from leaves upward to the root
18. What is left factoring?
This states that a <variable> is either an identifier or an identifier followed by
an expression in brackets (a subscript). These rules clearly do not pass the
pair-wise disjointness test, because both RHSs begin with the same terminal, identi-fier.
20. What is a simple phrases of a sentential form?
simple phrases is just a phrase that takes a single derivation step from its root nonterminal node.
21. What is the handle of a sentential form?
mathematically concise, it provides little help in finding the handle
of a given right sentential for
Page 236
Problem Set
2. What is l-value? Write a statement in C language which gives the compile time error “l-value required”.
The address of a variable is called its l-value.
4. Why is the type declaration of a variable necessary? What is the value range of the int type variable in Java?
because it must include an initial value, byte
5. approaches to building a lexical analyzer:
- Write a formal description of the token patterns of the language using a descriptive language related to regular expressions. These descriptions are used as input to a software tool that automatically generates a lexical analyzer. There are many such tools available for this. The oldest of these, named lex, is commonly included as part of UNIX systems.
- Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
- Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
6. State transition diagram is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause transitions among the states.
8.a.Assuming static scooping, in the following, which declaration of x is the correct one for a reference to x?
b.Repeat part a, but assume dynamic scoping.
(a) i. Sub1
ii. Sub126
iii. Main
(b) i. Sub1
ii. Sub1
iii. Sub1
9. The differences between top-down and bottom-up parsers:
- Syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree built from the root downward to the leaves.
– Bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order, which mean the parse tree is built from leaves upward to the root
2013-03-27
Programming Language Concept (4)
Book : Concept of Programming Language
Page 199
Review Question
1. What are three reasons why syntax analyzers are based on grammars?
First, using BNF descriptions of the syntax of programs are clear and concise. Second, can be used as the direct basis for the syntax analyzer. Third, implementations based on BNF are relatively easy to maintain because of their modularity.
2. Explain three reasons why lexical analysis is separated from syntax analysis.
- Simplicity (Techniques for lexical analysis are less complex than those required for syntax analysis)
- Efficiency (Although it pays to optimize the lexical analyzer, because lexical analysis requires a significant portion of total compilation time)
- Portability (Because the lexical analyzer reads input program files and often includes buffering of that input, it is somewhat platform dependent)
3. Define lexeme and token.
Lexeme is the logical groupings that the lexical analyzer collects characters into and Token is the internal codes for categories of these groupings.
5. Describe briefly the three approaches to building a lexical analyzer.
- Write a formal description of the token patterns of the language using a descriptive language related to regular expression.
- Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
- Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
6. What is a state transition diagram?
A state transition diagram is a directed graph which the representations of a class of mathematical machine that used for lexical analyzers.
8. What are the two distinct goals of syntax analysis?
Two distinct goals of syntax analysis are to detect syntax errors in a given program and to produce a parse tree or possibly the information required to build such a tree for a given program.
17. Describe the pairwise disjointness test.
The pairwise test try to test whether a parsing subprogram can determine which RHS is being parsed on the basis of the next token of input.
18. What is left factoring?
Left factoring is the action taken when a grammar leads backtracking while marking parsing or syntax tree.
23. Describe three advantages of LR parsers.
Three advantages of LR parsers are:
- They can be built for all programming languages.
- They can detect syntax errors as soon as it possible in a left-to-right scan.
- The LR class of grammars is a proper superset of the class parsable by LL parsers.
Page 200
Problem Set
1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
b. B → aB | bA | aBb
c. A → aaA | b | caB
(a) FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test
(b) FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test
(c) FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test
3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c.
a + b * c
Call lex /* returns a */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns + */
Exit <factor>
Exit <term>
Call lex /* returns b */
Enter <term>
Enter <factor>
Call lex /* returns * */
Exit <factor>
Call lex /* returns c */
Enter <factor>
Call lex /* returns end-of-input */
Exit <factor>
Exit <term>
Exit <expr>
5. Given the following grammar and the right sentential form, draw a parse tree and show the phrases and simple phrases, as well as the handle.
S → aAb | bBa A → ab | aAb B → aB | b
a. aaAbb
b. bBab
c. aaAbBb
7. Show a complete parse, including the parse stack contents, input string, and action for the string id * (id + id) , using the grammar and parse table in Section 4.5.3.
Page 199
Review Question
1. What are three reasons why syntax analyzers are based on grammars?
First, using BNF descriptions of the syntax of programs are clear and concise. Second, can be used as the direct basis for the syntax analyzer. Third, implementations based on BNF are relatively easy to maintain because of their modularity.
2. Explain three reasons why lexical analysis is separated from syntax analysis.
- Simplicity (Techniques for lexical analysis are less complex than those required for syntax analysis)
- Efficiency (Although it pays to optimize the lexical analyzer, because lexical analysis requires a significant portion of total compilation time)
- Portability (Because the lexical analyzer reads input program files and often includes buffering of that input, it is somewhat platform dependent)
3. Define lexeme and token.
Lexeme is the logical groupings that the lexical analyzer collects characters into and Token is the internal codes for categories of these groupings.
5. Describe briefly the three approaches to building a lexical analyzer.
- Write a formal description of the token patterns of the language using a descriptive language related to regular expression.
- Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
- Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
6. What is a state transition diagram?
A state transition diagram is a directed graph which the representations of a class of mathematical machine that used for lexical analyzers.
8. What are the two distinct goals of syntax analysis?
Two distinct goals of syntax analysis are to detect syntax errors in a given program and to produce a parse tree or possibly the information required to build such a tree for a given program.
17. Describe the pairwise disjointness test.
The pairwise test try to test whether a parsing subprogram can determine which RHS is being parsed on the basis of the next token of input.
18. What is left factoring?
Left factoring is the action taken when a grammar leads backtracking while marking parsing or syntax tree.
23. Describe three advantages of LR parsers.
Three advantages of LR parsers are:
- They can be built for all programming languages.
- They can detect syntax errors as soon as it possible in a left-to-right scan.
- The LR class of grammars is a proper superset of the class parsable by LL parsers.
Page 200
Problem Set
1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
b. B → aB | bA | aBb
c. A → aaA | b | caB
(a) FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test
(b) FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test
(c) FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test
3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c.
a + b * c
Call lex /* returns a */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns + */
Exit <factor>
Exit <term>
Call lex /* returns b */
Enter <term>
Enter <factor>
Call lex /* returns * */
Exit <factor>
Call lex /* returns c */
Enter <factor>
Call lex /* returns end-of-input */
Exit <factor>
Exit <term>
Exit <expr>
5. Given the following grammar and the right sentential form, draw a parse tree and show the phrases and simple phrases, as well as the handle.
S → aAb | bBa A → ab | aAb B → aB | b
a. aaAbb
b. bBab
c. aaAbBb
7. Show a complete parse, including the parse stack contents, input string, and action for the string id * (id + id) , using the grammar and parse table in Section 4.5.3.
Stack
|
Input
|
Action
|
0
|
id * (id + id) $
|
Shift 5
|
0id5
|
* (id + id) $
|
Reduce 6 (Use GOTO[0, F])
|
0F3
|
* (id + id) $
|
Reduce 4 (Use GOTO[0, T])
|
0T2
|
* (id + id) $
|
Reduce 2 (Use GOTO[0, E])
|
0T2*7
|
(id + id) $
|
Shift 7
|
0T2*7(4
|
id + id ) $
|
Shift 4
|
0T2*7(4id5
|
+ id ) $
|
Shift 5
|
0T2*7(4F3
|
+ id ) $
|
Reduce 6 (Use GOTO[4, F])
|
0T2*7(4T2
|
+ id ) $
|
Reduce 4 (Use GOTO[4, T])
|
0T2*7(4E8
|
+ id ) $
|
Reduce 2 (Use GOTO[4, E])
|
0T2*7(4E8+6
|
id ) $
|
Shift 6
|
0T2*7(4E8+6id5
|
) $
|
Shift 5
|
0T2*7(4E8+6F3
|
) $
|
Reduce 6 (Use GOTO[6, F])
|
0T2*7(4E8+6T9
|
) $
|
Reduce 4 (Use GOTO[6, T])
|
0T2*7(4E8
|
) $
|
Reduce 1 (Use GOTO[4, E])
|
0T2*7(4E8)11
|
$
|
Shift 11
|
0T2*7F10
|
$
|
Reduce 5 (Use GOTO[7, F])
|
0T2
|
$
|
Reduce 5 (Use GOTO[0, T])
|
0E1
|
$
|
Reduce 2 (Use GOTO[0, E])
|
Programming Language Concept (3)
Book : Concept of Programming Language
Page 162
Review Questions
1. Define syntax and semantics?
Syntax is concerned with the structure of language. Syntax is a matter of the logical or grammatical form of sentences, rather than what they refer to or mean. Semantics is concerned with the meaning of words and sentences. Semantics is a matter of the content or meaning of sentences, often in relation to their truth and falsehood.
4. Describe the operation of a general language recognizer?
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.
6. Define a left-recursive grammar rule.
A grammar rule has its LHS also appearing at the beginning of its RHS.
8. Distinguish between static and dynamic semantics
Static semantic of a language is only indirectly related to the meaning of program during execution; rather it has to do with the legal forms of programs (syntax rather than semantics). Many static semantic rules of a language state its type constraints. Static semantics is so named because the analysis is required to check these specification can be done at compile time.
Dynamic semantics is the meaning of the expression, statements, and program units of a programming language.
14. Why can machine languages not be used to define statements in operational semantics?
Because the individual steps in the execution of machine language and the resulting changes to the state of machine are too small and too numerous.
15. Describe the two levels of uses of operational semantics.
Natural Operational Semantics : At the highest level, the interest is in the final result of the execution of a complete program.
Structural 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.
18. Which semantics approach is most widely known?
Denotational semantics
20. Which part of an inference rule is the antecedent?
if the truth of S in the top part of an inference rule
28. What is the use of the wp function? why it is called a predicate transformer?
the use of the wp function is 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.
29. Give the difference between total corectness and partial correctness.
Total correctness : loop termination can be shown
Partial correctness : loop conditions that can be met but termination is not guaranteed
Page 163
Problem Set
3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *
<assign> -> <id> = <expr>
<expr> -> <expr> * <term> | <term>
<term> = <factor> + <term> | <factor>
<factor> -> (<expr>) | <id>
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 strings abb, aabbbb, and aaabbbbbb are in the language but, a, aabb, ba, and aaabb are not.
S-> aSb |ab
18. what is a fully attributed parse tree?
if all the attributed values in a parse tree have been computed. a parse tree of an attributed grammar is the parse tree based on its underlying BNF grammar, with a possibly empty set of attribute values attached to each node.
23. Compute the weakest precondition for each of the followeing assignment statements and postconditions.
a) a = 2 * (b-1) – 1 {a-0}
2 * (b-1) -1 >0
2 * b-2-1 >0
2 * b > 3
b > 3/2
b) b = (c+10) / 3{b>6}
(c+10) / 3 > 6
c +10 > 18
c > 8
24. Compute the weakest precondition for each of the following sequences of assignment statements and their postcondition
a. a= 2*b+1
b=a-3 {b<0}
a-3<0
a<3
we have:
a=2*b+1 {a<3}
2*b+1<3
2*b<2
b<1
b. a= 3*(2*b+a)
b= 2*a-1 {b>5}
2*a-1>5
2*a>6
we have:
a= 3*(2*b+a) {a>3}
3*(2*b+a)>3
6*b+3*a>3
2*b+a>1
b>(1-a)/2
Page 162
Review Questions
1. Define syntax and semantics?
Syntax is concerned with the structure of language. Syntax is a matter of the logical or grammatical form of sentences, rather than what they refer to or mean. Semantics is concerned with the meaning of words and sentences. Semantics is a matter of the content or meaning of sentences, often in relation to their truth and falsehood.
4. Describe the operation of a general language recognizer?
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.
6. Define a left-recursive grammar rule.
A grammar rule has its LHS also appearing at the beginning of its RHS.
8. Distinguish between static and dynamic semantics
Static semantic of a language is only indirectly related to the meaning of program during execution; rather it has to do with the legal forms of programs (syntax rather than semantics). Many static semantic rules of a language state its type constraints. Static semantics is so named because the analysis is required to check these specification can be done at compile time.
Dynamic semantics is the meaning of the expression, statements, and program units of a programming language.
14. Why can machine languages not be used to define statements in operational semantics?
Because the individual steps in the execution of machine language and the resulting changes to the state of machine are too small and too numerous.
15. Describe the two levels of uses of operational semantics.
Natural Operational Semantics : At the highest level, the interest is in the final result of the execution of a complete program.
Structural 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.
18. Which semantics approach is most widely known?
Denotational semantics
20. Which part of an inference rule is the antecedent?
if the truth of S in the top part of an inference rule
28. What is the use of the wp function? why it is called a predicate transformer?
the use of the wp function is 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.
29. Give the difference between total corectness and partial correctness.
Total correctness : loop termination can be shown
Partial correctness : loop conditions that can be met but termination is not guaranteed
Page 163
Problem Set
3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *
<assign> -> <id> = <expr>
<expr> -> <expr> * <term> | <term>
<term> = <factor> + <term> | <factor>
<factor> -> (<expr>) | <id>
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 strings abb, aabbbb, and aaabbbbbb are in the language but, a, aabb, ba, and aaabb are not.
S-> aSb |ab
18. what is a fully attributed parse tree?
if all the attributed values in a parse tree have been computed. a parse tree of an attributed grammar is the parse tree based on its underlying BNF grammar, with a possibly empty set of attribute values attached to each node.
23. Compute the weakest precondition for each of the followeing assignment statements and postconditions.
a) a = 2 * (b-1) – 1 {a-0}
2 * (b-1) -1 >0
2 * b-2-1 >0
2 * b > 3
b > 3/2
b) b = (c+10) / 3{b>6}
(c+10) / 3 > 6
c +10 > 18
c > 8
24. Compute the weakest precondition for each of the following sequences of assignment statements and their postcondition
a. a= 2*b+1
b=a-3 {b<0}
a-3<0
a<3
we have:
a=2*b+1 {a<3}
2*b+1<3
2*b<2
b<1
b. a= 3*(2*b+a)
b= 2*a-1 {b>5}
2*a-1>5
2*a>6
we have:
a= 3*(2*b+a) {a>3}
3*(2*b+a)>3
6*b+3*a>3
2*b+a>1
b>(1-a)/2
Programming Language Concept (2)
Book : Concept of Programming Language
Page 107
Review Question
1.In what year was Plankalkul designed?In what year was that design published?
Plankalkul was designed in 1945, published in 1972.
2.Mention an interesting feature of Zuse’s programs.
Inclusion of mathematical expressions showing the current relationships between program
variables.
3.What does Plankalkul means?
Program Calculus.
4.Speedcoding was invented to overcome two significant shortcomings of the computer hardware of the early 1950s. What were they?
Two significant shortcomings in 1950’s that was overcome by Speedcoding were lacking of floating-point arithmetic operations and lacking of indexing of some sort to allow the convenient use of arrays.
5.What is the number of bits in a single word of the UNIVAC I’s memory?How are they grouped?
Words of UNIVAC I’s memory had 72 bits, grouped as 12 six-bit bytes.
8.Who developed short code?Why is short code called automatic programming?
Short code was developed by John Mauchly. It was called automatic programming because it simplified the programming process although spent more execution time.
10.What was the most significant feature added to Fortran I to get Fortran II?
The most significant feature added to Fortran I to get Fortran II is the independent compilation of subroutines.
11.What control flow statements were added to Fortran IV to get Fortran 77?
Character string handling, logical loop control statement and an if without an optional else clause were added to Fortran IV to get Fortran 77.
12.Which version of Fortran was the first to have any sort of dynamic variables?
Fortran 90 is the first version of Fortran which support dynamic variables.
13.Which version of Fortran was the first to have character string handling?
The first version of Fortran supporting character string handling is Fortran 77.
14.Why were linguists interested in artificial intelligence in the late 1950s?
Because they were concerned with natural language processing, when in 1950’s, there are only computers with computation based on numeric data in arrays.
16.In what way are Scheme and Common LISP opposites of each other?
Scheme is characterized by its small size and its exclusive use of static scoping, while Common LISP is characterized by its large and complex language, but has pure LISP basis and allowance to both static scoping and dynamic scoping.
17.What dialect of LISP is used for introductory programming courses at
some universities?
Scheme is mostly used for courses in functional programming.
18.What two professional organizations together designed ALGOL 60?
Association for Computing Machinery (ACM) and German acronym for Society for Applied Mathematics and Mechanics (GAMM) are the two companies which started to design ALGOL 60
PS
Page 109
Problem Set
2.Determine the capabilities of Short Code, and compare them with those of contemporary programmable hand calculator.
Short Code is capable of making multiplication without multiplication code needed, just put two operands side-by-side. Besides, it also uses pure interpreter to run itself. Comparing to a contemporary programmable hand calculator, surely Short Code will do the calculations slower than the calculator because Short Code uses interpreter. Short Code offers simpler syntax to do multiplication, however.
9.Why did Fortran allow names that began with I,J,K,L,M,N as implicitly integer type?
Because in that day, scientist often used the variable I,J,K to refer to their integer in their work in science. Moreover, Fortran was built for scientific application, therefore, in order to give more comforts to users (scientists), it allows those variables.
10.The most important new developments of ALGOL 60 are:
a.The concept of block structure was introduced
b.Two different means of passing parameters to subprograms were allowed : pass by value and pass by name
c.Procedures were allowed to be recursive
d.Stack-dynamic arrays were allowed
11.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?
The assumption is correct because in that 1970’s, PL/I is widely used for both business and scientific applications although it suffers a lot in previous years and afterwards.
15.Are there any nonprocedural programming languages other than Prolog?
Yes there are some nonprocedural languages other than Prolog, for example, Visual Basic, SQL.
25.Give a brief general description of the Java Servlet.
Servlet is an instance of a Java class that resides on and is executed on a Web server system for form processing purpose and database access purpose. The execution of servlet is requested by a markup document displayed by Web browser. Then the request is processed by servlet container in the Web server. Lastly, the output of it is returned to the Web browser again.
Page 107
Review Question
1.In what year was Plankalkul designed?In what year was that design published?
Plankalkul was designed in 1945, published in 1972.
2.Mention an interesting feature of Zuse’s programs.
Inclusion of mathematical expressions showing the current relationships between program
variables.
3.What does Plankalkul means?
Program Calculus.
4.Speedcoding was invented to overcome two significant shortcomings of the computer hardware of the early 1950s. What were they?
Two significant shortcomings in 1950’s that was overcome by Speedcoding were lacking of floating-point arithmetic operations and lacking of indexing of some sort to allow the convenient use of arrays.
5.What is the number of bits in a single word of the UNIVAC I’s memory?How are they grouped?
Words of UNIVAC I’s memory had 72 bits, grouped as 12 six-bit bytes.
8.Who developed short code?Why is short code called automatic programming?
Short code was developed by John Mauchly. It was called automatic programming because it simplified the programming process although spent more execution time.
10.What was the most significant feature added to Fortran I to get Fortran II?
The most significant feature added to Fortran I to get Fortran II is the independent compilation of subroutines.
11.What control flow statements were added to Fortran IV to get Fortran 77?
Character string handling, logical loop control statement and an if without an optional else clause were added to Fortran IV to get Fortran 77.
12.Which version of Fortran was the first to have any sort of dynamic variables?
Fortran 90 is the first version of Fortran which support dynamic variables.
13.Which version of Fortran was the first to have character string handling?
The first version of Fortran supporting character string handling is Fortran 77.
14.Why were linguists interested in artificial intelligence in the late 1950s?
Because they were concerned with natural language processing, when in 1950’s, there are only computers with computation based on numeric data in arrays.
16.In what way are Scheme and Common LISP opposites of each other?
Scheme is characterized by its small size and its exclusive use of static scoping, while Common LISP is characterized by its large and complex language, but has pure LISP basis and allowance to both static scoping and dynamic scoping.
17.What dialect of LISP is used for introductory programming courses at
some universities?
Scheme is mostly used for courses in functional programming.
18.What two professional organizations together designed ALGOL 60?
Association for Computing Machinery (ACM) and German acronym for Society for Applied Mathematics and Mechanics (GAMM) are the two companies which started to design ALGOL 60
PS
Page 109
Problem Set
2.Determine the capabilities of Short Code, and compare them with those of contemporary programmable hand calculator.
Short Code is capable of making multiplication without multiplication code needed, just put two operands side-by-side. Besides, it also uses pure interpreter to run itself. Comparing to a contemporary programmable hand calculator, surely Short Code will do the calculations slower than the calculator because Short Code uses interpreter. Short Code offers simpler syntax to do multiplication, however.
9.Why did Fortran allow names that began with I,J,K,L,M,N as implicitly integer type?
Because in that day, scientist often used the variable I,J,K to refer to their integer in their work in science. Moreover, Fortran was built for scientific application, therefore, in order to give more comforts to users (scientists), it allows those variables.
10.The most important new developments of ALGOL 60 are:
a.The concept of block structure was introduced
b.Two different means of passing parameters to subprograms were allowed : pass by value and pass by name
c.Procedures were allowed to be recursive
d.Stack-dynamic arrays were allowed
11.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?
The assumption is correct because in that 1970’s, PL/I is widely used for both business and scientific applications although it suffers a lot in previous years and afterwards.
15.Are there any nonprocedural programming languages other than Prolog?
Yes there are some nonprocedural languages other than Prolog, for example, Visual Basic, SQL.
25.Give a brief general description of the Java Servlet.
Servlet is an instance of a Java class that resides on and is executed on a Web server system for form processing purpose and database access purpose. The execution of servlet is requested by a markup document displayed by Web browser. Then the request is processed by servlet container in the Web server. Lastly, the output of it is returned to the Web browser again.
2013-03-05
Programming Language Concept (1)
Book : Concept of Programming Language
Page 52
Review Questions
1. Why is it useful for a programmer to have some background in language design, even though he or she may never actually design a programming language?
To 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 are already known; and
overall advancement of computing.
2. How can knowledge of programming language characteristic benefits the whole computing community?
Knowledge of programming language benefiting the whole computing community. People can solve their own problems so troubleshooters lose their jobs and it will reduce the number of common sense-lacking questions.
3. What programming language has dominated scientific computing over the last 50 years?
FORTRAN
4. What programming language has dominated scientific business applications over the last 50 years?
COBOL
5. What programming language has dominated artificial intelligence over the last 50 years?
LISP
6. What language is most of UNIX written?
C
Page 53
Problem Set
1. Do you believe that solving problem in a particular algorithmic step require programming language skill? Support your opinion.
Not really.... The definition of "Algorithm" is step by step instruction to do something, and it is something that we learn on daily basis and often used unconciously (like when you want to make tea, take the tea bag, take a glass, put the tea bag into the glass, pour hot water, wait 1 min, take out the tea bag, pour lukewarm water, but most people "just do it")
2. Who is said to be the first programmer in human history? Use the internet for help.
Ada Lovelace.
3. What are the disadvantages of multiple programming languages?
It will be confusing. Each programming language has their own way to write, their own library, and many more "their own". People who learn multiple language would often mistaken one language's command for another.
4. In what way do the languages for scientific application differ from the languages for business application? Support your view.
From the start their goal is different, thus the requirement is different by proxy.
Business applications often need to be able to create reports of different and sometimes elaborate
formats. They need to be able to represent data in a human understandable way, as well as need “precise
ways of describing and storing decimal numbers, and character data.”
Scientific applications typically need simple data structures and arrays, and many floating point operations.
This would be typical of a program that performs matrix manipulation. When performing matrix
manipulation you want both fast floating point calculations, and to be able to load as much data into
memory at once as possible since I/O operations are costly.
6. Which characteristic of programming languages do you think are the most important and why?
Error Checking. Because I do not wish to stare at the computer for hours just for looking at one mistake from hundreds of code line.
7. Java uses a semicolon to mark the end of all statements. What are the advantages for and against this design?
The advantages is that t makes it easy to know where the statement ends, while the disadvantages is that sometimes people forgot to put it in and the whole thing stop working
Langganan:
Postingan (Atom)