Chapter 5: Names, Bindings, and Scopes

Review Questions:
1. What are the design issues for names?
   There are 2 primary design issues for names: first we have "are names case sensitive?", and second one is "are the special words of the language  reserved words or keywords?".

2. What is the potential danger of case-sensitive names?
   Writ ability and readability (because sometimes names that look alike are different thing).

3. In what way are reserved words better than keywords?
   Reserved words can be better than keywords because the ability to redefine keywords are confusing.

4. What is an alias?
   When more than one variable can be used to access the same memory location the variables are called alias.

5.  Which category of C++ reference variables is alwas aliases?
   Union types.

 Problem Set:
1. Which of the following identifier forms is most readable? Support your decision.

• SumOfSales
• sum_of_sales
• SUMOFSALES

   The most readable identifier is "sum_of_sales", because there are underscores as separator of the words in that variable.

2. Some programming languages are typeless. What are the obvious advantages and disadvantage of having no types in language?

   Advantages    : - It allows coders to write sloppy programs quickly.

   Disadvantages: - You are not in control of the data and variables, the compiler or interpreter is.

                            -  If you miss assigned variables, there's no way for the compiler to catch any of                                      your mistakes. It just "does what you said" even if it's wrong.

                            - Supporting programs in a typeless language is much more difficult. It often                                            couldn't recognize what the programmer actually want to do.

3. Write a simple assignment statement with one arithmetic operator in some language you know. For each component of the statement, list the various bindings that are required to determine the  semantics when the statement is executed. For each binding, indicate the binding time used for the language.

   int count; count = count + 5;

Possible types for count: set as language design time. 

Type of count: bound at compile time.

Set of possible values of count: bound at compiler design time. 

Value of count: bound at execution time with this statement.

Set of possible meanings for the operator symbol '''' in this statement: bound at compile time.

Internal repesentation of literal "5": bound at compiler design time.

4. Dynamic type binding is closely related to implicit heap-dynamic variables. Explain this relationship.

   Both are related to the assignment and the statement.

5. Describe a situation when a history-sensitive variable in subprogram is useful.

   It is useful when you have a subprogram to be recalled again after the subprogram itself had been exited. Then the function doesn't have the variable to be the parameter, but only to return it. 

Chapter 4: Lexical and Syntax Analysis

This is the post for this week's GSLC assignment. It's about Sebesta's Programming Language Concept, chapter 4 Review Question and Problem Set.

Review Question:
1. What are three reasons why syntax analyzers are based on grammars?

• Grammars are clear and concise. 
• The grammar description can be use as a direct basis for the analyzer.
• Grammar are modular or easy to maintain.

2. Explain the 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: altough 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 loxical analyzer collects characters into, and token is the internal codes for categories of these groupings.

4. What are the primary task of lexical analyzer?

   A lexical analyzer has to perform syntax analysis at the lowest level of program structure.

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.

Problem Set:

1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
   FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, passes the test.
b. B → aB | bA | aBb
   FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, failed the test
c. C→ aaA | b | caB
   FIRST(aaA) = {a}, FIRST (b) = {b}, FIRST (caB) = {c}, passes the test
   
2. Perform the pairwise disjointness test for the following grammar rules.
a. S→ aSb | bAA
   FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test
b. A → b{aB} | a
   FIRST (b{aB}) = {b}, FIRST (a) = {a}, passes the test
c. B → aB | a
   FIRST(aB) = {a}, FIRST(a) = {a}, failed the test

3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string 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>

4. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a * (b + c).
   call lex      // return a
    enter <expr>    enter <term>    enter <factor>   call lex      // return *     exit <factor>   call lex      // return (     enter <factor>   call lex      // return b     enter <expr>     enter <term>     enter <factor>   call lex      // return +     exit <factor>     exit <term>   call lex      // return c     enter <term>     enter <factor>   call lex      // return )     exit <factor>     exit <term>
     exit <expr>   call lex      // return EOF     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

   Parse Tree:

                                   S

                                /   |   \

                             a     A   b

                                 /   |   \

                               a    A   B

                                            |

                                           b

   Phrases: aaAbb, aAb, b

   Simple phrase: b, aAb

   Handle: b

b. bBab

   Parse Tree:

                                    S

                                /    |    \

                             b      B   A

                                         /   \

                                        a    b

   Phrases: bBab, bBA

   Simple phrase: ab

   Handle : ab

c. aaAbBb

   aaAbBb = aSBb = aSBB = x

   The last string cannot be derived from the given grammar. 

Chapter 3: Describing Syntax and Semantics

This time I will post the answer of first 5 numbers of Review Questions and first 5 numbers of Problem Set.

Review Questions:
1. Define syntax and semantics.
   Syntax is more to the structure, form of the programming language; while semantics are more into the meaning of the code.

2. Who are language descriptions for?
   Language descriptions are for initial evaluators, implementors, and users.

3. Describe the operation of a general language generator.
   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. It is often possible to determine whether the syntax of a particular statement is correct by comparing it with the structure of the generator.

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.
   
5. What is the difference between a sentence and a sentential form?
   A sentence is a sentenential form that has only terminal symbols. A sentence form is every strings of the symbols in the derivation.

Problem Set:
1. The two mathematical models of language description are generation and recognition. Describe how each can define the syntax of a programming language.
   Syntax error refers to an error in the program that caused by misused syntax. Semantics error is caused by wrong logical statements.

2. Write EBNF descriptions for the following:
a. A Java class definition header statement
   <class_head> ® {<modifier>} class <id> [extends class_name]
    [implements <interface_name> {, <interface_name>}]
    <modifier> ® public | abstract | final
b. A Java method call statement
   <for> -> for '(' [[<type>] <id> = <expr> {,[<type>] <id> = <expr>}] ; [<expr>] ; [<expr>{, <expr>}] ')' '{' <stmt_list> '}
c. A C switch statement   
   <stmt> -> switch (<int expr>){case <int const> : {<stmt>;} 
    { case<int const> : {<stmt> :}}
    [default : {<stmt>;}]    }
d. A C union definition
   <union_defn> -> union <var_list> <union_identifier>;
    <var_list> -> <list_of_data-type specifier> <var>    <list_of_data-type specifier> -> int | float | long | char | double    <union_identifier> -> <var>
e. C float literals
   <float-literal> -> <real> <suffix>
    | <real> <exponent> <suffix>    | <integer> <exponent> <suffix>

3. Rewrite the BNF of Example 3.4 to give + precedence over * and force + to be right associative.
    <assign>-> <id> = <expr>
    <id> = A|B|C
   <expr>-> <expr>-<term> |<term>
   <term> -> <term>/<factor>|<factor>  
   <factor> ->(<expr>) |<id>
 
4. Rewrite the BNF of Example 3.4 to add the ++ and -- unary operators of Java.
   <assign> -> <id> = <expr>
   <id> = A|B|C
   <expr> -> <expr> + <term> | <term>++ | <term>--
   <term> -> <term> * <factor> | <factor>
   <factor> -> (<expr>) | <id>

5. Write a BNF description of the Boolean expressions of Java, including the three operators &&, ||, and ! and the relational expressions.

   <Boolean_expr> -> <Boolean_expression> || <Boolean_term> | <Boolean_term>   <Boolean_term> -> <Boolean_term> && <Boolean_factor> | <Boolean_factor>   <Boolean_factor> -> id | !<Boolean_factor> | (<Boolean_expr>) | <relation_expr>   <relation_expr> -> id == id | id != id | id < id | id <= id | id >= id | id > id

Chapter 2: Evolution of Major Programming Languages

This post is about chapter 2 of Sebesta's Programming Language Concept book. I will show you about how I think about this chapter by answering 5 numbers of Review Questions, and 5 numbers of Problem Set.

Review Questions:

1. In what year was Plankalkül designed? In what year was that design published?

   Plankalkul was designed in 1945 by a German scientist called Konrad Zuse, but the Plankalkul itself was published in 1972.

2. What two common data structures were included in Plankalkül? 

   The data structures included in Plankalkul were arrays and records. Those two are just addition to the usual scalar type.

3. How were the pseudocodes of the early 1950s implemented?
   In the early 1950s, the computers  weren't as fast as they are nowadays. They were unreliable, expensive, and having extremely small memories. There were no high-level programming languages, so people have to do the programming using the machine code, which means using numeric codes for specifying instructions. Pseudocodes were made to avoid the errors by making new instructions to replace the numeric codes.

4. Speedcoding was invented to overcome two significant shortcomings of the computer hardware of the early 1950s. What were they?
    They were pseudoinstructions for the four arithmetic operations on floating-point data and also novel facility of automatically incrementing address registers.

5. Why was the slowness of interpretation of programs acceptable in the early 1950s? 
    Because in that time the available computers were far less usable than they were today. The computers were slow, unreliable, expensive, and having small memories. There was also lack of supporting software.

Problem Set:
1. What features of Plankalkül do you think would have had the greatest influence on Fortran 0 if the Fortran designers had been familiar with Plankalkül?
   It would be the arrays, loop, and selection features.

2. Determine the capabilities of Backus’s 701 Speedcoding system, and compare them with those of a contemporary programmable hand calculator.
   Backus's speedcoding system converted the 701 to a virtual three-address floating-point calculator which includes four arithmetic operational on floating point such as sqrt, sine, arc tangent, exponent, and logarithm. It was so fast because it only needs 4.2 miliseconds to execute.

3. Write a short history of the A-0, A-1, and A-2 systems designed by Grace Hopper and her associates.
  A-0, A-1, and A-2 was a project developed by a team led by Grace Hopper. They were actually a series of compiling system that expanded pseudocodes into machine code subprograms.

4. As a research project, compare the facilities of Fortran 0 with those of the Laning and Zierler system.
The Laning and Zierler system (Laning and Zierler, 1954) was the first algebraic translation system to be implemented. It translated arithmetic expressions, used separately coded subprograms to computer transcendental functions (e.g., sine and logarithm), and included arrays. Meanwhile, Fortran 0 was mathematical formula translation system implementation

5. Which of the three original goals of the ALGOL design committee, in your opinion, was most difficult to achieve at that time?
   It would be the second goal: "It should be possible to use the language for the description of algorithms in printed publications". In my opinion, it would be hard for someone who hasn't learnt about programming language to know the meaning of syntaxes. Even the syntax was made by human and still being adapted from natural language, sometimes it's hard to find out what does it mean, or when to use the syntax, etc.