CHAPTER 4 : LEXICAL AND SYNTAX ANALYSIS

Review Question :

16. What is the FIRST set for a given grammar and sentential form?

Answer :
FIRST( ) = {a => * a } (If => * , is in FIRST( ))
in which =>* means 0 or more derivation steps

17. Describe the pairwise disjointness test.

Answer : It is a test of non-left recursive grammar that indicates whether left recursion can be done. It requires the ability to compute a set based on the RHS of a given nonterminal symbol in a grammar.

18. What is left factoring ?

Answer : Left factoring is the action taken when a grammar leads backtracking while marking arsing.syntax tree.

19. What is a phrase of a sentential form ?

Answer : A phrase is a subsequence of a sentential form that is eventually reduced to a single non-termin 

20. What is a simple phrases of a sentential form ?

Answer : Simple phrases is just a phrases that takes a single derivation step from it’s root non-terminal node

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.

Answer :

S → AbB bAc A → Ab aBB B → Ac cBb c a.

a. aAcccbbc
S -> AbB -> aBBbB -> aAcBbB -> aAccBbbB -> aAcccbbc

b. AbcaBccb
S -> AbB -> AbcBb -> AbcAcb -> AbcaBBcb -> AbcaBccb

c. baBcBbbc
S -> bAc -> baBBc -> baBcBbc -> 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.
Answer :

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.
Answer :

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.
Answer :

<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.
Answer :

Assume the following non-terminals are given: <type>, <id>, <literal>, <assign>, <expr>, and <stmt_list>.

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

Assignment From Chapter 3 Programming Language Concepts R.Sebesta

Part: Review Question

16. In denotational semantics, what are the syntactic and semantic domains?

The mapping functions of a denotational semantics programming language specification, like all functions in math, have a domain and a range, the domain is called the syntactic domain, and the range is called the semantic domain.

17. What is stored in the state of a program for denotational semantics?

The state of a program for denotational semantics is the value of all its current variable.

18. Which semantics approach is most widely known?

The Denotational semantics is the most widely known semantics approach.

19. What two things must be defined for each language entity in order toconstruct a denotational description of the language?

objects and functions

20. Which part of an inference rule is the antecedent?

The antecedent is the top part of an inference rule.

Part: Problem Set

14. Draw parse trees for the sentences aabb and aaaabbbb, 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_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>

17. Convert the following EBNF to BNF:

S → A{bA}

A → a[b]A

The BNF form is:

<S> -> <S>b<A> | <A>

<A> -> a<A> | ab<A>

18. What is the difference between an intrinsic attribute and a nonintrinsic synthesized attribute?

1. An intrinsic attribute is an inherent characteristic of a terminal symbol in the grammar. So the value of the attribute is determined solely from the terminal symbol. A nonintrinsic synthesized attribute is an attribute of a non-terminal symbol in the grammar.

2. Intrinsic attributes are synthesized attributes of leaf nodes whose values are determined outside the parse tree. Nonintrinsic means the opposite, the values are not determined.

19. Write an attribute grammar whose BNF basis is that of Example 3.6 in Section 3.4.5 but whose language rules are as follows: Data types cannot be mixed in expressions, but assignment statements need not have the same types on both sides of the assignment operator.

1) Syntax rule: <assign> → <var> = <expr>

2) Syntax rule: <expr> → <var>[2] + <var>[3]

Predicate: <var>[2].actual_type == <var>[3].actual_type

3) Syntax rule: <expr> → <var>

4) Syntax rule: <var> → A | B | C

Semantic rule: <var>.actual_type ← lookup(<var>.string)

OR

Replace the second semantic rule with:
<var>[2].env ← <expr>.env
<var>[3].env ← <expr>.env
<expr>.actual_type ← <var>[2].actual_type
predicate: <var>[2].actual_type = <var>[3].actual_type

20. Write an attribute grammar whose base BNF is that of Example 3.2 and whose type rules are the same as for the assignment statement example of Section 3.4.5.

1) syntax rule: <assign> → <id> = <expr>

semantic rule: <expr>.expected_type ← <id>.actual_type

predicate: <expr>[1].actual_type == <expr>[1].expected_type

2) syntax rule: <expr>[1] → <id> + <expr>[2]

semantic rule: <expr>[1].actual_type ←

if (<id>.actual_type = int and <expr>[2].actual_type = int)

then int

else float

end if

3) syntax rule: <expr>[1] → <id> * <expr>[2]

semantic rule: <expr>[1].actual_type ←

if (<id>.actual_type = int and <expr>[2].actual_type = int)

then int

else float

end if

4) syntax rule: <expr>[1] → ( <expr>[2] )

semantic rule: <expr>[1].actual_type ← <expr>[2].actual_type

5) syntax rule: <expr> → <id>

semantic rule: <expr>.actual_type ← <id>.actual_type

6) syntax rule: <id> → A | B | C

semantic rule: <id>.actual_type ← lookup(<

id>.string)

Assignment From Chapter 2 Programming Language Concepts R.Sebesta

Part: Review Question

16.  In what way are Scheme and Common LISP opposites of each other?

Common LISP allows for static scoping and dynamic scoping Scheme only uses static scoping. Scheme is relatively small while common LISP is large and complex .

17. What dialect of LISP is used for introductory programming courses atsome universities?

Scheme

18. What two professional organizations together designed ALGOL 60?

ACM and GAMM

19. In what version of ALGOL did block structure appear?

ALGOL 60

20. What missing language element of ALGOL 60 damaged its chances for widespread use?

The lack of input and output statements with formatting

Part: Problem Set

14.What are the arguments both for and against the idea of a typeless language?

The main Point is about Typeless language allowing more flexibility but it also can create an ambiguity as to the contents of a variable. Ambigious languages can cause trouble and misunderstanding among people.

Arguments for the idea

Flexibility, Brevity of syntax. It places stricter controls on what objects can receive and send, so making it easier to enforce design strategies throughout the application. When there are errors in types, there can be picked up during precompilation or in the IDE.

Arguments against the idea:

Without type checking, there is no means to verify the integrity of Without type checking, there is no means to verify the integrity of the data without executing the application. The syntax of typed languages can be viewed as overfly long or verbose. Typed languages aren’t as flexible as untyped languages, as data structures need to be cast to the correct type before another object can receive them. it is also said that by using typed languages, the compiler spends less time dynamically typing objects and so executes faster. However, this point is a grey are and that the main area of argument is how these language differences play out when designing applications where more then a few people are working on the code.

15. Are there any logic programming languages other than Prolog?

Yes, there are SQL,Visual Basic, etc .

 16. What is your opinion of the argument that languages that are too complex are too dangerous to use, and we should therefore keep all languages small and simple?

I strongly disagree with that  argument about “Languages that are too complex”, I think Programming languages are not dangerous at all – in case that the programmers who use the language knows exactly what he / she is doing. High complexity means that the program will be more than simple coded programs, as complexity is defined as orthogonality. There is no use in keeping all languages small and simple. Since if there’s a languages which we use are complex, people just don’t have to use it as standard. Instead, they can use simple ones as the standard.

17. Do you think language design by committee is a good idea? Support your opinion.
Language design by committee definitely has its advantages, with varying points of view from different domains, different programming backgrounds, and even different language backgrounds all contributing for the better of the language.

18. Languages continually evolve. What sort of restrictions do you thinkare appropriate for changes in programming languages? Compare youranswers 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.

19. Build a table identifying all of the major language developments, together with when they occurred , in what language they first appeared, and the identities of the developers . 

• Years 50: Creation of high-level languages ​​(closer to humans).
• Years 60: Expansion of specialized languages​​. Forth. Simula I. Lisp, Cobol. Trying unsuccessfully to impose general languages​​: Algol, PL / 1.
• Years 70: Duel between structured programming with Pascal and efficiency of C language. Basic generalized on personal computers from 1977, until the late 80s.
• Years 80: Experimentating other ways including objects. ML. Smalltalk. On computers, we now use C, Pascal, Basic compiled.
• Years 90: Generalization of object-oriented programming with the performance of microcomputers. Java, Perl, Python languages ​​in addition to microphones.
• 2000s: Internet Programming (and future innovations, see end of text).
• Years 2010: Concurrency and asynchronicity. JavaScript and Go languages among others help to create online fluid applications.

 Evolution of programming languages

  ” see the table here “

20. There have been some public interchanges between Microsoft and Sun concerning the design of Microsoft’s J++ and C# and Sun’s Java. Read some of these documents, which are available on their respective Web sites, and write an analysis of the disagreements concerning the delegates.

These are the documents

http://msdn.microsof…v=vs.60%29.aspx
http://benhutchison….gates-for-java/
https://weblogs.java…ngly_types.html
http://java.sys-con.com/node/49097

Delegates are a redundancy polluting object-oriented paradigm. Most of the posts on the subject are missing a big picture.

Assignment From Chapter 1 Programming Language Concepts R.Sebesta

Part: Review Question

16. What is exception handling?

Exception halding is the ability of a program to intercept run-time errors and other unusual conditions detectable by the program and take corrective measures then continue which is an obvious aid to reliability.

17. Why is readability important to writability? 

 Readability is important to writability because programs that are difficult to read will be difficult to be written or modified.

18. How is the cost of compilers for a given language related to the design of that language?

The cost of compilers for a given language is related to the design of it because a languange that requires many run-time type checks will prohibit fast code execution, regardless of the quality of the compiler.

19. What have been the strongest influences on programming language design over the past 50 years?

The shift in major cost of computing from hardware to software. The cost of hardware decreased and programmer cost increased, while th increase of productivity were relatively small. In addition, larger and more complex problems were solved by computers, such as providing airline reservation system.

20. What is the name of the category of programming languages whose structure is dictated by the von Neumann computer architecture? 

A language is called Imperative if it is designed around the prevalent computer architecture. In von Neumann computer, both data and programs are stored in the same memory. While The CPU is separated. Therefore, the instructions and data must be transmitted to the CPU and sent back to the memory after it is processed in the CPU.

Assignment From Chapter 1 Programming Language Concepts R.Sebesta

Part: Problem Set

14. Describe the advantages and disadvantages of some programming environment you have used.

C++ - Best suited for general purpose and low level programming.
Advantages: Extremely fast, works very well for GUI programming on a computer. Good language to write operating systems, drivers, and platform dependent applications with. Good language to learn to program with. Good language for engineers. 
Disadvantages: Although it is platform independent, it is mostly used for platform specific applications. A library set is usually chosen that locks you into a single platform or operating system. Overly complex for very large high level programs. Overly complex and difficult to debug when used for web applications. Marketable skills are low level programming, vendor software, and video games, making it difficult to find jobs unless you have are very advanced in a target area.

C# - new language to take advantage of C++ foundation and add new features.
Advantages: Can be used for web applications on Microsoft computers. Works well with the Microsoft product line. Marketable skill set.
Disadvantages: Almost completely locks you into the Microsoft Platform. New language, so not a great deal of published free code yet.

VB - Used mainly to modify and complement the Microsoft product line.
Advantages: Extremely easy to use, even for people who are not computer programmers. Allows the typical computer user to modify MS Office applications to suite their needs. Works very well on a Microsoft intranet to complement the network shares and permissions. Can be used for low level programming on Microsoft computers. A marketable skill set. Excellent for writing little programs and pieces of programs.
Disadvantages: Completely locks you into using the Microsoft product line. Not a true Object oriented language although it claims to be. VB .Net is an object oriented language. Becomes overly complex and difficult to manage on very large programs. 

15.  How do type declaration statements for simple variables affect the readability of a language, considering that some languages do not require them? 

 The use of type declaration statements for simple scalar variables may have very little effect on the readability of programs. If a language has no type declarations at all, it may be an aid to readability, because regardless of where a variable is seen in the program text, its type can be determined without looking elsewhere. Unfortunately, most languages that allow implicitly declared variables also include explicit declarations. In a program in such a language, the declaration of a variable must be found before the reader can determine the type of that variable when it is used in the program.

16. Write an evaluation of some programming language you know, using the criteria described in this chapter.

Readability :Java has some issues with simplicity with respect to readability. There is feature multiplicity in Java as shown in the textbook, example count=count + 1, count ++, count +=1 and ++count.
Control statements in Java have higher readibility than BASIC and Fortran because they can use more complex conditionals like for loops 

Writability :
Java has a fair bit of orthogonality in that its primitive constructs can be used in various different ways.

Reliability :
Java uses a type checker at compile time which virtually eliminate most of the type errors during run time.

17. Some programming languages—for example, Pascal—have used the semicolon to separate statements, while Java uses it to terminate state-ments. Which of these, in your opinion, is most natural and least likely to result in syntax errors? Support your answer.

I personally feel that Pascal's usage of the semicolon to separate statement is rather counterintuitive but possibly it's because I learned the usage of the semicolon to terminate statement in C before I learned Pascal. Java consistency is more intuitive than the sructure of Pascal, it's easier to remember not to put a semi colon after a right brace than it is to have watch out for not putting it after each statement.

18.  Many contemporary languages allow two kinds of comments: one in which delimiters are used on both ends (multiple line comments), and one in which a delimiter marks only the beginning of the comment (one line comments). Discuss the advantages and disadvantages of each of these with respect to our criteria.

The main disadvantage of using paired delimiters for comments is that it results in diminished reliability. It is easy to inadvertently leave off the final delimiter, which extends the comment to the end of the next comment, effectively removing code from the program. The advantage of paired delimiters is that you can comment out areas of a program. The disadvantage of using only beginning delimiters is that they must be repeated on every line of a block of comments. This can be tedious and therefore errorprone. The advantage is that you cannot make the mistake of forgetting the closing delimiter.