Department of Computer Science and Engineering

Sai Vidya Institute of Technology

(Approved by AICTE, New Delhi, Affiliated to V.T.U, Belagavi, Recognized by Govt. of. Karnataka)
Rajanakunte ,Bengaluru-560064

Questions Bank
Subject Name: System software & Compilers
Subject Code: 18CS61
Sem: VI
Faculty:SUNIL G L

Module -1 Questions.
1. Bring out the differences b/w System software and Application software.( 5)
2. Give the SIC machine architecture with all options? (10)
3. Suppose alpha is an array of 100 words. Write a sequence of instructions for
SIC\XE to set all 100 elements to 0. (6)
4. Write a sequence of instructions for SIC to clear a 20 byte string to all blanks.(6)
5. Give the machine architecture of SIC/XE? (10)
6. With an example, explain simple I/O operation of SIC/XE? (5)

7. What are the fundamental functions of assembler? With an example, give the
list ofassembler directives?(6)
8. Explain the data structures used in Assemblers (8).
9. What is program relocation? Explain the problem associated with it and solutions? (6)
10. Give the format of the following (8)
• Header record
• Text record
• End record
• Modification record
11. Explain the function of each pass of an 2 pass assembler.(5)
12. Explain the following (8)
• SYMTAB
• LOCCTR
• OPTAB
13. Give the algorithm for pass1 of an 2 pass assembler. (8)
14. Give the algorithm for pass2 of an 2 pass assembler (8)
15. Explain the following: Literals, Symbol defining statements, Expressions (8)
1|Page
 16. Explain program blocks with an example. (10)
17. Explain control section and program linking. (8)
18. Explain the following (8)
• Define record
• Refer record
• Modification record(revised)
19. Explain one pass assembler. (6)
20. Explain multipass assembler. (8)
21. Write an algorithm for an absolute loader ( 7)
22. Explain bootstrap loaders. (6)
23. Write an algorithm for Bootstrap loader. (7)
Module-2
1) What is a language processor? What are the various types of language processors?
2) What is a compiler? What are the activities performed by the compiler?
3) What is an interpreter? What are the differences between a compiler and interpreter
4) What is an assembler? What are the activities performed by the compiler?
5) What is hybrid compiler?
6) What are the cousins of the compiler? or Explain language processing system
7) Discuss the analysis of source program with respect to compilation process
8) What are the different phases of the compiler? or “Explain the block diagram of the
compiler construction method
9) Show the output of each phase of the compiler for the assignment statement: sum =
initial + value * 10
10) What is the difference between a phase and pass? What is a multi-pass compiler?
Explain the need for multiple passes in compiler?
11) What are compiler construction tools?
12) What is lexical analysis? What is the role of lexical analyzer?
13) Why analysis portion of the compiler is separated into lexical analysis and syntax
analysis phase?
14) What is the meaning of patterns, lexemes and tokens?
15) Identify lexemes and tokens in the following statement: a
= b * d;
16) Identify lexemes and tokens in the following statement:
printf(“Simple Interest = %f\n”, si);
17) What is the need for returning attributes for tokens along with token name?”

2|Page
 18) Give the token names and attribute values for the following statement: = M * C **2.
where ** in FORTRAN language is used as exponent operator.
19) Give the token names and attribute values for the following statement: si
= p * t * r / 100
20) Why input buffering is required? What is input buffering?
21) What is the disadvantage of input buffering with buffer pairs? Explain the use of
sentinels in recognizing the tokens.
22) Design a lexical analyzer to identify an identifier
23) Design a lexical analyzer to identify the relation operators such as <, <=, >, >=, == and
!=
24) Design a lexical analyzer to identify the keywords begin, else, end. Sketch the program
segment to implement it showing the first two states and one final state
25) Design a lexical analyzer to recognize unsigned number. Sketch the program segment to
implement it showing the first two states and one final state

Module-3

1) What the different sentential forms? What is left sentential form? What is right sentential
form?
2) Define the terms: Language, derivation tree, yield of a tree, ambiguous grammar
3) Show that the following grammar is ambiguous
E → E+E
E → E-E
E → E*E
E → E/E
E → (E) | I
I → id
4) Is the following grammar ambiguous? (if-statement or if-then-else)
S → iCtS | iCtSeS | a
C → b
5) What is dangling else problem? How dangling else problem can be solved
6) Eliminate ambiguity from the following ambiguous grammar:
S → iCtS | iCtSeS | a
C → b
7) Convert the following ambiguous grammar into unambiguous grammar using normal
precedence and associativity of the operators
E → E*E|E-E
E → E^E|E/E
E → E+E
E → (E) | id
3|Page
 8) Convert the following ambiguous grammar into unambiguous grammar
E→E+E
E→E–E
E→E^E
E→E*E
E→E/E
E → (E) | id
by considering * and – operators lowest priority and they are left associative, / and +
operators have the highest priority and are right associative and ^ operator has precedence
in between and it is left associative.
9) What is parsing? What are the different types of parsers?
10) What is a context free grammar? What is derivation? What are the two types of
derivations?
11) Define the terms: leftmost derivation, rightmost derivation, sentence
12) What are error recovery strategies of the parser (or syntax analyzer)?”
13) What is top down parser? Show the top-down parsing process for the string id + id * id
for the grammar
i. E → E + E
ii. E → E * E
iii. E → (E)
iv. E → id
14) What is recursive descent parser? Write the algorithm for recursive descent parser
15) Write the recursive descent parser for the following grammar E
→T
T→F
F → (E) | id
16) What are the different types of recursive descent parsers? What is the need for
backtracking in recursive descent parser
17) Show the steps involved in recursive descent parser with backtracking for the input string
cad for the following grammar
S → cAd A
→ ab | a
18) For what type of grammars recursive descent parser cannot be constructed? What is the
solution?
19) What is left recursion? What problems are encountered if a recursive descent parser is
constructed for a grammar having left recursion?
20) Write the procedure to eliminate left recursion
21) Eliminate left recursion from the following grammar
E → E +T | T
T→T*F|FF
→ (E) | id
22) Write the recursive descent parser for the following grammar:
4|Page
 E → TE1
E1→ +TE1 | ϵ
T → FT1
T1→ *FT1 | ϵ
F → (E) | id
23) Obtain top-down parse for the string id+id*id for the following grammar
E →TE1
E1 → + TE1 | 
T →FT1
T1 → *FT1 | 
F →(E) | id
24) C Eliminate left recursion from the following grammar:
S → Aa | b
A → Ac | Sd | ϵ
Write the algorithm to eliminate left recursion
25) What is left factoring? What is the need for left factoring? How to do left factoring?
Write the algorithm for doing left-factoring

26) Do the left-factoring for the following grammar:

S → iCtS | iCtSeS | a
C→ b
27) Briefly explain the problems associated with top-down parser?
28) What is a predictive parser? Explain the working of predictive parser.
29) What are the various components of predictive parser? How it works?
30) Define FIRST and FOLLOW sets and write the rules to compute FIRST and
FOLLOW sets
31) Consider the following grammar:
E → TE1
E1 → + TE1 | 
T → FT1
T1 → *FT1 | 
F → (E) | id
a) Compute FIRST and FILLOW sets for the following grammar:
b) Obtain the predictive parsing table
c) Show the sequence of moves made by the parser for the string id+id*id
d) Add the synchronizing tokens for the above parsing table and show the sequence of
moves made by parser for the string “ ) id * + id”
32) What is LL (1) grammar? How to check whether a given grammar is LL(1) or not
without constructing the predictive parser
33) Compute FIRST and FOLLOW symbols and predictive parsing table for the following
grammar and check whether the grammar is LL(1) or not.
5|Page
 S → iCtS | iCtSeS | a C
→ b
34) Given the following grammar:
S → a | (L)
L→ L,S|S
a. Is the grammar suitable for predictive parser?
b. Do the necessary changes to make it suitable for LL(1) parser
c. Compute FIRST and FOLLOW sets for each non-terminal
d. Obtain the parsing table and check whether the resulting grammar is LL(1) or not.
e. Show the moves made by the predictive parser on the input “( a , ( a , a ) )”

35) Given the following grammar:

E → 5+T|3–T
T → V | V*V | V+V V
→ a|b
a. Is the grammar suitable for predictive parser?
b. What is the use of left-factoring? Do the left factoring for the above grammar
c. Compute FIRST and FOLLOW sets for each non-terminal
d. Without constructing the parsing table, check whether the grammar is LL(1)
e. By constructing the parsing table, check whether the grammar is LL(1).
36) Given the following grammar:
Z → d | XYZ Y
→ ϵ |c
X→ Y|a
a. Compute FIRST and FOLLOW sets for each non-terminal
b. Without constructing the parsing table, check whether the grammar is LL(1).
c. By constructing the parsing table, check whether the grammar is LL(1).
37) Left factor the following grammar and obtain LL(1) parsing table E
→T+E|T
T → float | float * T | (E)
38) How error recovery is done in predictive parsing

Module-4

1) What are meta characters? Explain some of the meta characters used in a lex program.

2) Write a LEX program to replace the user name with login of the user name.

3) Explain the use of yywrp().

4) Discuss two types of conflicts in YACC with an example.

5) Write a LEX program to return the tokens for identifier and number.

6) How errors are handled by YACC?

7) Explain the meta characters used in regular expression with an example.

6|Page
 8) Write a LEX program to count the number of scanf and printf statements and replacing
them with readf and writef respectively.

9) Write a LEX program to find the length of each word in a text.

10) Explain the working of shift reduce parser

11) What is ambiguous grammar? How it can be overcome?

12) Write a YACC program to check whether the given arithmetic expression is valid or not.

Module-5
1. What is semantic analysis? What is syntax directed definition (SDD)?
2. What is an attribute? Explain with example. What are the different types or
classifications of attributes?
3. What is a semantic rule? Explain with example
4. What is synthesized attribute? Explain with example
5. What is inherited attribute? Explain with example
6. What is annotated parse tree? Explain with example
7. Write the SDD for the following grammar:
S → En where n represent end of file marker
E→E+T|T
T→T*F|F
F → (E) | digit

8. Write the grammar and syntax directed definition for a simple desk calculator andshow
annotated parse tree for the expression (3+4)*(5+6)
9. What is circular dependency when evaluating the attribute value of a node in an
annotated parse tree
10. What is the use of inherited attributes
11. Obtain SDD and annotated parse tree for the following grammar using top-down
approach:
T → T * F | FF →
digit

12. Obtain SDD for the following grammar using top-down approach:
S → En
E→E+T|T
T→T*F|F
F → ( E ) | digit

13. and obtain annotated parse tree for the expression (3 + 4 ) * (5 + 6)n
7|Page
14. What is a dependency graph
15. Obtain the dependency graph for the annotated parse tree obtained in example 5.3
16. What is topological sort of the graph
17. Give the topological sort of the following dependency graph
18. What are different classes of SDD‟s that guarantee evaluation order
19. What is S-attributed definition
20. What is an attribute grammar
21. What is an L-attributed definition
22. What is a side effect in a SDD
23. How to control the side effects in SDD
24. Write the grammar and SDD for a simple desk calculator with side effect
25. Write the SDD for a simple type declaration and write the annotated parse tree andthe
dependency graph for the declaration “float a, b, c”
26. Write the SDD for a simple desk calculator. Write the annotated parse tree for the
expression 3*5+4n
27. What is syntax directed translation
28. What is a syntax tree? What is the difference between syntax tree and parse tree?”
29. For the following grammar show the parse tree and syntax tree for the expression

3 *5 + 4:
E→E+T|E–T|T
T→ T*F | T/F | F
F→ (E) | digit | id

30. How to construct semantic rules that help us to create syntax trees for the
expressions?
31. Obtain the semantic rules to construct a syntax tree for simple arithmetic expressionsusing
bottom up approach
32. Create a syntax tree for the expression “a – 4 + c”
33. Obtain the semantic rules to construct a syntax tree for simple arithmetic expressionsusing
top-down approach with operators + and –

34. Obtain the semantic rules to construct a syntax tree for simple arithmetic expressionswith
operators -, +, * and / using top-down approach
35. Give the syntax directed translation of type int [2][3] and also given the semanticrules
for the respective productions
36. What is syntax directed translation scheme
8|Page
37. What is Postfix Syntax-directed-translation or Postfix SDT
38. Obtain Postfix SDT implementation of the desk calculator to evaluate the given
expression
39. Write the SDD and annotate parse tree for converting an infix to postfix expression
40. Write the SDT for converting an infix to postfix expression. Show the actions for
translating the expression 2*3+4 into its equivalent postfix expression
41. Explain parser-stack implementation of Postfix SDT‟s
42. Write the actions of desk calculator SDT so that they manipulate the parser explicitly
43. When action part specified in the production is executed
44. Write the SDT for converting an infix to prefix expression. Show the actions for
translating the expression 2*3+4 into its equivalent prefix expression

9|Page