Chapter 5 Answers
Review Questions
1. What are the 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 , this is a serious detriment to readability, because names that look very similar in fact denote different entities. In that sense, case sensitivity violates the design principle that the language constructs that looks similar should have similar meanings. But in languages whose variable names are case sensitive, although Rose and rose look similar, there is no connection between the.
4. What is an alias?
Alias is when more than one variable name can be used to access the same memory location.
6. What is the l-value of a variable? What is the r-value?
l-value is the address of a variable. r-value is a variable’s value that’s required when the name of the variable appears in the right side of an assignment statement.
15. What is the general problem with static scoping?
In some languages that use static scoping, regardless of whether nested subprograms are allowed, some variable declarations can be hidden from some other code segments.
16. What is the referencing environment of a statement?
The referencing environment of a statement is the collection of all variables that are visible in the statement.
Problem Set
1. Decide which of the following identifier names is valid in C language. Support your decision.
_Student
int
Student
123Student
Student123
The valid identifier names are _Student, Student, and Student123. We cannot use ‘int’ as name because it’s a reserved keyword and we cannot use the 123Student because C doesn’t allow identifier format with a digit at the first letter.
2. What is l-value? Write a statement in C language which gives the compile time error “l-value required”.
An “lvalue” is a value that can be the target of an assignment. The “l” stands for “left”, as in the left hand side of the equals sign. An rvalue is the right hand value and produces a value, and cannot be assigned to directly. If you are getting “lvalue required” you have an expression that produces an rvalue when an lvalue is required.
Example :
1=2;
4. Why is the type declaration of a variable necessary? What is the value range of the int type variable in Java?
The type declaration is important because the type of a variable determines the range of values the variable can store and the set of operations that are defined for values of the type.
The int type in Java have a value range of –2147483648 to 2147483647.
Chapter 3 Answers
Review Questions
1. Define syntax and semantics.
Syntax is the form of programming language, expressions, statements, and program units.
Semantics is the meaning of those expressions, statements, and program units.
2. Who are language descriptions for ?
The language descriptions is important for the programming language implementers to determine how the expressions, statements, and program units of a language are formed, and also their intended effect when executed.
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. Because the particular sentence that is produced by a generator when its button is pushed is unpredictable, a generator seems to be a device of limited usefulness as a language descriptor.
4. Describe the operation of a language recognizer.
Suppose we have a language L that uses an alphabet _ of characters. To define L formally using the recognition method, we would need to construct a mechanism R, called a recognition device, capable of reading strings of characters from the alphabet _. R would indicate whether a given input string was or was not in L. In effect, R would either accept 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. Because most useful languages are, for all practical purposes, infinite, this might seem like a lengthy and ineffective process. Recognition devices, however, are not used to enumerate all of the sentences of a language—they have a different purpose. 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.
12. What is the primary use of attribute grammars?
An attribute grammar is a device used to describe more of the structure of a programming language than can be described with a context-free grammar. An attribute grammar is an extension to a context-free grammar. The extension allows certain language rules to be conveniently described, such as type compatibility. Before we formally define the form of attribute grammars, we must clarify the concept of static semantics.
15. Describe the two levels of uses of operational semantics.
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.
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.
<stmt> -><matched> | <unmatched>
<matched> -> if <logic_expr> then <matched> else <matched>
|any non-if statement
<unmatched> -> if <logic_expr> then <stmt>
|if <logic_expr> then <matched> else <unmatched>
23. On what branch of mathematics is axiomatic semantics based?
Axiomatic semantics, thus named because it is based on mathematical logic, is the most abstract approach to semantics specification discussed in this chapter. Rather than directly specifying the meaning of a program, axiomatic semantics specifies what can be proven about the program. Recall that one of the possible uses of semantic specifications is to prove the correctness of programs.
24. Give an unambiguous grammar for if-then-else.
<if_stmt> -> if <logic_expr> then <stmt>
if <logic_expr> then <stmt> else <stmt>
Problem Set
3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> -<term>
| <term>
<term> -><term> * <factor>
| <factor>
<factor> -> ( <expr> )
| <id>
6. Using the grammar in Example 3.2, show a parse tree for each of the following statements:
a. A = A * (B + (C * A))
b. B = C * (A * C + B)
c. A = A * (B + (C))
7. Using the grammar in Example 3.4, show a parse tree for each of the following statements:
a. A = ( A * B ) + C
b. A = B * C + A
c. A = A + (B * C)
d. A = B * (C + (A * B))
8. Prove that the following grammar is ambiguous:
<S> -> <A>
<A> -> <A>*<A>|<id>
<id> -> x|y|z
It is ambiguous because it can has two distinct parse tree
9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <term>
| <term>
<term> -> <term> * <factor>
| <factor>
<factor> -> ( <expr> )
| +<id> | -<id>
13. Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For example, the strings abb, aabbbb, and aaaabbbbbbbb are in the language but a, aabb, ba, and aaabb are not.
S -> ab
b ->bb
14. Draw parse trees for the sentences abb and aabbbb, as derived from the grammar of Problem 13.
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>}
16. Convert the BNF of Example 3.3 to EBNF.
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> {(+|*) <expr>}
| <id>
Chapter 2 Answers
Chapter 2
Review Questions
1. In what year was Plankalkul designed? In what year was that design published?
Plankalkul design began in 1943 as a proposal for Konrad Zuse’s Ph.D.’s dissertation and published in 1972.
2. Mention an interesting feature of Zuse’s programs.
An interesting feature of Zuse’s program is the inclusion of mathematical expressions showing the current relationships between program variables.
3. What does Plankalkul mean?
Plankalkul means Program Calculus.
8. Who developed Short Code? Why is Short Code called automatic programming?
Short Code was developed by John Maunchly in 1949 for the BINAC computer, which was one of the first success ful stored-program electronic computers. It is called automatic programming because it was not translated to mavhine code; rather it was implemented with a pure interpreter.
9. Under what environmental consideration was Fortran developed? Which is the first version of Fortran?
Because at that time all floating-point operations had to be simulated in software, a very time-consuming process. The first version of FORTRAN is FORTRAN 0 in 1954.
10. What was the most significant feature added to Fortran I to get Fortran II ?
It was the independent-compilation capability. Without the independent compilation, any change in a program required that the entire program be recompiled.
13. Which version of Fortran was the first to have character string handling?
The first to have character string handling is Fortran 77.
14. Why were linguists interested in artificial intelligence in late 1950s?
Because linguists were concerned with natural language processing.
15. What are the different data types and structures in common LISP ?
Common LISP has a large number of data types and structures, including records, arrays, complex numbers, and character strings. It also has a form of packages for modularizing collections of functions and data providing access control.
19. What was the goal for developing C?
To overcome the problem of specifying floating-point rather than integer arithmetic in an expression.
20. What were the significant modifications to ALGOL 58 to produce ALGOL 60?
• The concept of block structure was introduced. This allowed the programmer to localize parts of programs by introducing new data environments, or scopes.
• Two different means of passing parameters to subprograms were allowed: pass by value and pass by name.
• Procedures were allowed to be recursive. The ALGOL 58 description was unclear on this issue. Note that although this recursion was new for the imperative languages, LISP had already provided recursive functions in 1959.
• Stack-dynamic arrays were allowed. A stack-dynamic array is one for which the subscript range or ranges are specified by variables, so that the size of the array is set at the time storage is allocated to the array, which happens when the declaration is reached during execution.
22. On what language was COBOL based?
The specifications were to a great extent inspired by the FLOW-MATIC language invented by Grace Hopper, commonly referred to as “the mother of the COBOL language.”
23. In what year did the COBOL design process begin?
The first formal meeting on the subject of a common language for business applications, which was sponsored by the Department of Defense, was held at the Pentagon on May 28 and 29, 1959 (exactly one year after the Zurich ALGOL meeting).
26. Which data type does the original BASIC language support?
The original BASIC had only 14 different statement types and a single data type—floating-point.
27. Why was BASIC an important language in the early 1980s?
In the mid-1970’s, two college students decided that the new Altair microcomputer needed a BASIC language interpreter. They sold their product on cassette tape for a cost of $350. You may have heard of these entrepreneurs: Bill Gates and Paul Allen!
28. PL/I was designed to replace what two languages?
PL/I is that it included what were then considered the best parts of ALGOL 60 (recursion and block structure), Fortran IV (separate compilation with communication through global data), and COBOL 60 (data structures, input/output, and report-generating facilities), along with an extensive collection of new constructs, all somehow cobbled together.
33. What language introduced the case statement?
ALGOL-W introduced the case statement for multiple selection.
57. What data types does Java support?
There are two data types available in Java:
- Primitive Data Types
- Reference/Object Data Types
Problem Set
6. Make an educated guess as to the most common syntax error in C programs.
(a) Semicolon (;) missing.
(b) Unmatched parentheses.
(c) Function prototype mismatch.
(d) Undeclared variables.
7. LISP began as a pure functional language but gradually acquired more and more imperative features. Why?
The main reason why imperative features were put in LISP was to increase its execution efficiency.
10. Outline the major developments in ALGOL 60.
The most important new developments were the following:
• The concept of block structure was introduced. This allowed the programmer to localize parts of programs by introducing new data environments, or scopes.
• Two different means of passing parameters to subprograms were allowed: pass by value and pass by name.
• Procedures were allowed to be recursive. The ALGOL 58 description was unclear on this issue. Note that although this recursion was new for the imperative languages, LISP had already provided recursive functions in 1959.
• Stack-dynamic arrays were allowed. A stack-dynamic array is one for which the subscript range or ranges are specified by variables, so that the size of the array is set at the time storage is allocated to the array, which happens when the declaration is reached during execution.
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?
IBM was, for the most part, incorrect in its view of the future of the uses of computers, at least as far as languages are concerned. Commercial applications are nearly all done in languages that are specifically designed for them. Likewise for scientific applications. On the other hand, the IBM design of the 360 line of computers was a great success—it still dominates the area of computers between supercomputers and
minicomputers. Furthermore, 360 series computers and their descendants have been widely used for both scientific and commercial applications. These applications have been done, in large part, in Fortran and COBOL.
14. What are the arguments both for and against the idea of typeless language?
The argument for typeless languages is their great flexibility for the programmer. Literally any storage location can be used to store any type value. This is useful for very low-level languages used for systems programming. The drawback is that type checking is impossible, so that it is entirely the programmer’s responsibility to insure that expressions and assignments are correct.
18. Languages continually evolve. What sort of restrictions do you think are appropriate for changes in programming language? Compare your answer with the evolution of Fortran.
A good deal of restraint must be used in revising programming languages. The greatest danger is that the revision process will continually add new features, so that the language grows more and more complex. Compounding the problem is the reluctance, because of existing software, to remove obsolete features.
22. Explain two reasons why pure interpretations is an acceptable implementation method for several recent scripting languages.
One situation in which pure interpretation is acceptable for scripting languages is when the amount of computation is small, for which the processing time will be negligible. Another situation is when the amount of computation is relatively small and it is done in an interactive environment, where the processor is often idle because of the slow speed of human interactions.
24.Why, in your opinion, do new scripting languages appear more frequently than new compiled languages?
New scripting languages may appear more frequently than new compiled languages because they are often smaller and simpler and focused on more narrow applications, which means their libraries need not be nearly as large.
Chapter 1 Answers
Chapter 1
Review Questions
9. What is one example of lack of orthogonality in the design of C?
A member of a structure can be any data type except void or a structure of the same type.
10. What language used orthogonality as a primary design criterion?
LISP(LISt Processing) is one language which computations are made primarily by appliying functions to given parameters.
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.
15. What is aliasing?
Aliasing is having two or more distinct names that can be used to access the same memory cell.
16. What is exception handling?
Exception handling is the ability to intercept run-time errors(as well as other unusual conditional detect by the program), take corrective measures, and then continue is an obvious aid to reliability.
17. Why is readability important to writability?
Because most of the language characteristics that affect readability also effect writability. This follows directly from the fact that the process of writing a program requires the programmer frequently to reread the part of the program that is already written.
25. What are three general methods of implementing a programming language?
Three general methods of implementing a programming language are compilation, pure implementation and hybrid implementation.
26. Which produces faster program execution, a compiler or a pure interpreter?
A compiler, because pure interpreter needs the programs to be interpreted by another program called interpreter and the execution is 10 to 100 times slower than compiled systems.
27. What role does the symbol table play in a compiler?
The symbol table serves as a database for the compilation process. The primary contents of the symbol table are the type and attribute information of each user-defined name in the program. This information is placed in the symbol table by the lexical and syntax analyzers and is used by the semantic analyzer and the code generator.
Problem Set
2. Who said to be the first programmer in human history ?
Ada Lovelace or Augusta Ada King, Countess of Lovelace (10 December 1815 – 27 November 1852), born Augusta Ada Byron was an English mathematician and writer chiefly known for her work on Charles Babbage’s early mechanical general-purpose computer, the Analytical Engine. 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?
Multiple programming languages can cause confusion among the programmers, because they have to learn the different languages, and they need more time to master those languages and implement them.
4. In what way do the languages for scientific applications differ from the languages for business applications? Support your view.
Languages for scientific applications used relatively simple data structures, but required large number of floating point arithmetic computations. Languages for business applications are characterized by facilities 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.
Artificial Intelligence (AI) is a broad area of computer applications characterized by the use of symbolic 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 liked list of data rather than arrays. This kind of programming sometimes requires more flexibility than other programming domains.
The World Wide Web is supported by an electric collection of languages, ranging from markup languages, such as HTML, which is not a programming language, to general-purpose programming languages, such as Java. Because of the pervasive need for dynamic Web content, some computations capability is often included in the technology of content presentation.
6. Which characteristics of programming languages do you think are the most important and why?
The most important thing is the program can be read and understood. Because, readability is an important measure of the quality of programs and programming languages, if the program is not designed for such use, the program may be unnatural and convoluted, making it unusually difficult to read.
7. Java uses semicolon to mark the end of all statements. What are the advantages for and against this design?
The advantage to use semicolon is to make the programmer know where the statement ends. The disadvantage is when sometimes the programmer forget to put the semicolon and it cause an error.
8. Most languages use functions and subroutines. What are the pros and cons of this design decision?
Pros : Functions and subroutines are use to make the program easier to maintain and understand. And make it more simply.
Cons : It requires more skills on the programmer to use functions and subroutines.
9. Explain how orthogonality in programming language is closely related to simplicity.
Orthogonality is an important concept, addressing how a relatively small number of components can be combined in a relatively small number of ways to get the desired results. It is associated with simplicity; the more orthogonal the design, the fewer exceptions.
Cundy's Blog 
Recent Comments