Analyse the terms pre-processing and assembling.
 

Design Transition Diagrams of regular definitions for the following relational operators:

relop → < | <= | <> | > | >= | =
 

[Two (2) Marks for each operator]

Compiler design impacts several other areas of computer science. Review the three most important interactions and applications of the technology. Give example(s) for these applications.
 

Predictive parsing is a special form of recursive descent parsing where we use one LOOKAHEAD token to unambiguously determine the parse operations. When a nonterminal has multiple productions, each production is implemented in a branch of a selection statement based on input look-ahead information.

Execute the example (Fig. 1) using Predictive Parser.
 

Input: array [ num  dotdot  num] of integer

            ↑

     lookahead

[1 mark for each execution step]
 

Let, two Context-free grammar G1 and G2:

G1=<{list, digit}, {+,-,0,1,2,3,4,5,6,7,8,9}, P, list> with production 
P = list → list + digit 
      list → list-digit 
      list → digit
     digit → 0 |1| ... |9

G2 <{string}, {+,-,0,1,2,3,4,5,6,7,8,9), P, string> with production P = string → string + string | string - string | 0 | 1 | ... |9.

Which grammar (from G1 and G2) is ambiguous to represent the string 9-5+2?
 

Analyse "Panic Mode" in error recovery for Syntex Analyzer.

[1 mark for each points]

Write two methods used in lexical analyzer for buffering in the input. Which technique is used for speeding up the lexical analyzer?

Compute FIRST from the following grammar:

        S-> iEtS/iEtSeS/a

        B -> b
 

Most languages are case sensitive, so keywords can be written only one way, and the regular expressions describing their lexemes are very simple. However, some languages, like SQL, are case insensitive, so a keyword can be written either in lowercase or in uppercase, or in any mixture of cases. Thus, the SQL keyword SELECT can also be written select, Select, or sElEcT, for instance. Show how to write a regular expression for a keyword in a case-insensitive language. Illustrate the idea by writing the expression for "select" in SQL.

Describe the languages denoted by the following regular expressions:        (i) a*                (ii) a | a*b                (iii) ((ε | a) b*)*

What is compiler? Design the analysis and synthesis model of computer.

State the role of the lexical analyzer. Identify the lexemes and their corresponding tokens in the following statement: printf ("Simple Interest=%f\n", si);

Differentiate leftmost derivation and rightmost derivation. Show an example for each.

Write down the NFA of all binary strings in which second last bit is 1. Convert the NFA into DFA.

Define a Parser. What is the role of grammars in Parser construction? Construct the Predictive parsing table for the following grammar G:

E → E+T | T,
T→ T*F | F,
F → (E) | id.

Define an LL(1) grammar. Is the following grammar LL (1)?

S → iEtS | iEtSes | a,
E → b.

Show the following grammar:

S->Aa | bAc | Bc | bBa
A->d
B->d
is LR (l) but not LALR (l).

Design a recursive descent parser for the grammar:

E->E+T | T

T->T*F | F

F->(E) | id

Define type equivalence. Explain the role of intermediate code generator in compilation process.

Define tokens, patterns, and lexemes with examples. What is the function of the lexical analyzer? Demonstrate the Interactions between the lexical analyzer and the parser.

Differentiate the terms (i) Yacc compiler, (ii) Lex compiler, and (iii) C compiler

Distinguish the following terms for error recovery in LR Parsing:
        i) Panic mode,
        ii) Phrase-level recovery

Let, you would like do parsing for syntax analyzer. Write down a table to show FOLLOW(A).

            E →T E_R

            E_R → + T E_R | ε

            T → F T_R

              T_R → * F T_R | ε

            F → (E) | id

In Compiler, syntax-directed checker and translator do the static and dynamic type checking. Distinguish between static and dynamic checking with example(s).

Differentiate the terms (i) Yacc compiler, (ii) Lex compiler, and (iii) C compiler

Analyze the terms: Recursive descent parsing and Predictive parsing

Based on LL(1) predictive parsing table for the following grammar, describe how to do panic mode recovery and phrase level recovery.

In LR(k) Parsers, Shift/Reduce decisions can be ambiguous. We can use a DFA for Shift/Reduce decisions in order to resolve the ambiguous issue. Describe it using Stack.

A good compiler should assist in identifying and locating errors. Describe about (a) Lexical errors, (b) Syntax errors, (c) Static semantic errors, (d) Dynamic semantic errors, (e) Logical errors.

Consider the following grammar and remove left recursion.

A → ABd / Aa / a

B→ Be / b
 

Write the three-address code sequence for the statement x=y*z + y*-z. Also give its triple representation.

Discuss the various phases of compiler and trace the program segment a = b + c * 50 for all phases.

Draw the DFA for the regular expression (a | b)* (abb | a+b).

Write down the sequence of top-down parse trees for the input id+id*id according to the given grammar.

E → T E' 
E' → +T E' | ε 
T → F T' 
T' → * F T' | ε 
F → (E) | id

What is an LALR(1) grammar? Construct LALR parsing table for the following grammar:

S → CC

C → cC

 C → c | d

Check whether the grammar is LALR (1) but not SLR(1)

S-->Aa/bAc/dc/bda
A-->d

Write short note on:

i) Synthesized attributes

ii) Inherited attributes

iii) Dependency graph

iv) Evaluation order

v) Directed Acyclic Graph (DAG)

Find the FIRST and FOLLOW of the non-terminals in the grammar:

S->aABe
A->Abc | b
B->d

Predictive parsing is a special form of recursive descent parsing where we use one LOOKAHEAD token to unambiguously determine the parse operations. When a nonterminal has multiple productions, each production is implemented in a branch of a selection statement based on input look-ahead information.
Execute the example (Fig. 1) using Predictive Parser.

Input: array   [    num     dotdot    num    ]    of    integer

            ↑

     lookahead
 

Construct a quadruple, triples for the following expression:

a + a*(b-c) + (b-c)*d?

What are operations on Language? Let L be the set of letters {A, B, ..., Z, a, b,..., z} and let D be the set of digits {0, 1,...,9}. We may think of L and D in two, essentially equivalent, ways. One way is that L and D are, respectively, the alphabets of uppercase and lowercase letters and of digits. Show some other languages that can be constructed from languages L and D, using the union, concatenation, Kleene closure and Positive closure operators.

How can the following grammar be ambiguous for (id - id / id)?

        E→ E-E | E/E | -E | (E) | id

Based on LR Parsing, for the following grammar, show all steps for the stack, input, and action.

Grammar:

1. E → E+T

2. E → T    

3. T → T* F

4. T → F     

5. F → (E)  

6. F → id    

Construct the predictive parser for the following grammar

S->(L)/a

L->L,S/S

Give specific examples of static checking for the followings:

a) Overloading, Coercion, and Polymorphism, b) Flow-of-Control Checks.

What will be the output of the lexical, syntax and sematic analyzers for the following expression: 
if(y%4=0) {printf("This may be a leap year")}

Compiler design is not only about compilers, and many people use the technology learned by studying compilers in school, yet have never, strictly speaking, written (even part of) a compiler for a major programming language. Compiler technology has other important uses as well. Additionally, compiler design impacts several other areas of computer science. Review the three most important interactions and applications of the technology. Give example for these applications.

When a production for nonterminal A starts with a self-reference then a predictive parser loops forever. For example, A → Aα | β | γ.

We can eliminate left recursive productions by systematically rewriting the grammar using right recursive productions. Analyse this procedure.

The following grammar, which abstracts the dangling-else problem is considered as ambiguous grammar. The grammar is ambiguous and the ambiguity is manifested by a choice in what production to use when an e (else) is seen.

How to make unambiguous ?

The following is a substring of grammar symbols:

a b b c d e

Prove that this substring shows the property of "Handle".

Describe typical tasks of the lexical analyzer.

Discuss the position of a Code Generator in the compiler model using figure.

What is code optimization? Explain machine dependent and independent code optimization.

Using operator precedence relations, parse the string id + (id * id).

Draw the transition diagram for the regular definition, relop◊ < | <= | = | <> | >= | >.

Explain syntax directed definition with simple examples?

What is Recursive Descent parsing? List the problems faced in designing such a parser.

Define peephole optimization. Explain machine dependent and machine independent optimization?

Briefly explain the rules that define regular expressions over some alphabet and the languages that those expressions denote using basis and induction. How do you recognize the reserved words and identifiers? Show the transition diagram of relop.

The following is a substring of grammar symbols: 

a b b c d e                       

Prove that this substring shows the property of "Handle".

Construct the LR parsing table for the following grammar:
E → E + T | T
T → T*F | F
F→(E) | id

What is the advantage of front end and back end model of compiler?

Let, a Context-free grammar for simple expressions: G1 = <{list,digit), (+,-,0,1,2,3,4,5,6,7,8,9), P, list with production

                                      P = list → list + digit

                                            list → list - digit

                                            list → digit

                                            digit → 0 | 1 |... | 9

Suppose we use a single nonterminal string and consider the following context-free grammar: G2 = <{string), {+,-,0,1,2,3,4,5,6,7,8,9), P, string> with production P = string → string + string | string - string | 0 | 1 |...|9.

Which grammar (from G1 and G2) is ambiguous because more than one parse tree represents the string 10-6+3?
 

If the following expression is passed to the lexical analyzer, then what is the output?

y := 31 +28*x

Let, you would like do parsing for syntax analyzer. Write down a table to show FOLLOW(A).

        E →TE_R

        E_R → + TE_R | ε

        T → FT_R

        T_R → * FTR | ε

        F→(E) | id