to detect syntax errors in a given program and to proccedure a parse tree, or possibly only the information required to build such a tree, for given program.

Chapter 4 Concepts of Programming Languages, Robert W. Sebesta.  Lexical and Syntax Analysis

Nama : Billy
NIM   : 1801374785

Review Question:
6. What is a state transition diagram?

A state transition diagram, or just state diagram, is a directed graph. The

nodes of a state diagram are labeled with state names.

7. Why are character classes used, rather than individual characters, for the
letter and digit transitions of a state diagram for a lexical analyzer?

A state transition diagram, or just state diagram , is a
directed graph

8. What are the two distinct goals of syntax analysis?

 to detect syntax errors in a given program and to proccedure a parse tree, or possibly only the information required to build such a tree, for given program.

9. Describe 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 is built from the root downward to 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
10. Describe the parsing problem for a top-down parser.

Write an EBNF rule that describes the for statement of Java or C++.
Write the recursive-descent subprogram in Java or C++ for this rule.

Problem Set: 
6. 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 → AbB bAc A → Ab aBB B → Ac cBb c
a. aAcccbbc

b. AbcaBccb

c. baBcBbbc

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])
–ACCEPT–

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

9. Write an EBNF rule that describes the while statement of Java or C++.
Write the recursive-descent subprogram in Java or C++ for this rule.

<while_stmt> -> WHILE ‘(‘ (<arith_expr> | <logic_expr>) ‘)’ <block> <block> -> <stmt> | ‘{‘ <stmt> {<stmt>} ‘}’

10. Write an EBNF rule that describes the for statement of Java or C++.

Write the recursive-descent subprogram in Java or C++ for this rule.

<for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr> {, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’

<assign> → <id> = <expr> <id> → A | B | C <expr> → <expr> + <term> | <term> | - <factor> <term> → <term>*<factor> | <factor> <factor> → (<expr>)

Chapter 3 Concepts of Programming Languages, Robert W. Sebesta. Describing Syntax and Semantics

Nama : Billy
NIM   : 1801374785

Review Question:

6. Define a left-recursive grammar rule.
When a grammar rule has its left hand side (LHS) also appearing at the beginning of its right hand side (RHS), the rule is said to be left recursive. 

7. What three extensions are common to most EBNFs?
Three extensions are common to most EBNFs:
a. The first extension denotes an optional part of a RHS, which is delimited by brackets. For example: <if_stmt> -> if ( <expr> ) stmt [ else <stmt> ]
b. The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. For example: <ident_list> -> ident {, <ident> }
c. The third extension deals with multiple choice options. For example: <term> -> <term> ( *|/|% ) <factor>

8. Distinguish between static and dynamic semantics.
Static semantics is more on the legal forms of programs (syntax rather semantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required checking these specifications can be done at compile time. Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions.

9. What purpose do predicates serve in an attribute grammar?

The use of predicates functions is to state the static semantic rules of the language.

10. What is the difference between a synthesized and an inherited attribute
The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes. In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.
For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax.

Problem Set: 

6. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation 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 and a leftmost derivation 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> → a | b | c

For the grammar of this problem and the expression a=a+b+c there are two different leftmost derivations:

<S>-><A>

-> <A>+<A>

-> <A>+<A>+<A>

-> <id>+<A>+<A>

-> a+<A>+<A>

-> a+<id>+<A>

-> a+b+<A>

-> a+b+<id>

-> a+b+c

Or 

<S>-><A>

-><A>+<A>

-><id>+<A>

->a+<A>

->a+<A>+<A>

->a+<id>+<A>

->a+b+<A>

->a+b+<id>

->a+b+c

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>

                     | - <factor>

<term>    → <term>*<factor>

                     | <factor>

<factor>  → (<expr>)

                     | <id>

10. Describe, in English, the language defined by the following grammar:
<S> → <A> <B> <C>
<A> → a <A> | a
<B> → b <B> | b
<C> → c <C> | c

Chapter 2 Programming Language Concepts R . Sebesta

Review question

6.What hardware capability that first appeared in the IBM 704 computer strongly affected the evolution of programming languages ? Explain why?

A:  The inclusion of floating-point hardware capability that first appeared in the IBM 704 computer strongly affected the evolution of programming languages because at that time ,the lack of floating-point hardware in the available computers. All floating –point operations had to be simulated in software, a very time-consuming process.

7. In what year was the Fortran design project begun ?

A: May 1954

8. What was the primary application area of computers at the time Fortran was designed ?

A: Mathematics applications

9. What was the source of all of the control flow statements of Fortran I ?

A: They were based on 704 instructions

10. What was the most significant feature added to Fortran I to get Fortran II ?

A: Independent-compilation capability

Problem Set

6. Make an educated guess as to the most common syntax error in LISP programs.

A: Undefined escape sequences in literal strings. The backslash character can be used in literal strings and characters :

       - to escape various characters
       - to introduce an escape sequence representing a character

7. LISP began as a pure functional language but gradually acquired more and more imperative features. Why ?

A:Because there is always a new idea for the uses and begin to develop the language.

8. Describe in detail the three most important reasons, in your opinion, why ALGOL 60 did not become a very widely used language. 

A:1.Excessive flexibility hurt ALGOL60 since languages that are difficult to learn were not as well received as languages with a more rigid structure. 2.Sebesta (2002, p. 60) notes that its association with BNF alienated the language as strange and complicated. If programmers are not excited about using a language, they will always find a different one. 3.perhaps the most important reason that ALGOL60 was not very widely used was because of a lack of support from IBM, who was at the time the preeminent company for using computer languages. 

9. Why, in your opinion, did COBOL allow long identifiers when Fortran and ALGOL did not ? 

A:COBOL is more of a reporting language than Fortran. Since Fortran handles calculations much better, there is not a real need for long identifiers. As a reporting language, COBOL uses long identifiers in tagging the source to the reports it is writing. Also, COBOL is the closest language to a fully, self documenting language, that it gets, and long identifiers provides one more case for i

10. Outline the major motivation of IBM in developing PL/I.

A:Like Fortran, PL/I was developed as an IBM product. By the early 1960s, the users of computers in industry had settled into two separate and quite different camps: scientific and business. From the IBM point of view, scientific programmers could use either the large-scale 7090 or the small-scale 1620 IBM computers. This group used floating-point data and arrays extensively

For business applications, people used the large 7080 or the small 1401 IBM computers. They needed the decimal and character string data types, as well as elaborate and efficient input and output facilities. They used COBOL, although in early 1963 when the PL/I story begins