Chapter 2: A Simple One-Pass Compiler

What do you mean by context-free grammar? What are the components of the grammar?

[2021, 17, 10]

Or,

Define CFG. What are the components of CFG?

[2013]
Define CFG, parse tree, and syntax tree.

[2015, 10]

Advantages of CFG Over BNF
- What advantages do context-free grammars offer in describing the syntax of programming language constructs over the Backus-Naur Form (BNF)?[2019, 14]
Defining CFG and Equality
- How will you define a context-free grammar? When will you say that two CFGs are equal?[2011]
Parse Tree
- What do you mean by a parse tree? Describe its properties.[2020, 17, 10]
Lexical Analyzer and Parser
- Discuss the relationship among input, lexical analyzer, and parser.[2020, 18, 14, 09]Or,How does a lexical analyzer interface between input stream and a parser?[2021, 19, 17, 13, 10]
Separation of Analysis Phase
- What are the reasons for separating the analysis phase of compiling into lexical analysis and parsing?[2014, 12, 11, 09]
Transition Diagram
- What do you mean by a transition diagram? Draw the transition diagram for relational operators.[2021, 18, 09]
Associativity of Operators
- Describe the associativity of operators with examples.[2011]

CFG

Consider the following Context-Free Grammar (CFG):
```
stmt → expr;
expr → expr + term | term
term → term * factor | factor
factor → number | (expr)
number → 0 | 1 | 2 | ... | 9
```
(i) Show how the string 1 + 2*(3 + 4) + 5 can be generated by this grammar.

(ii) Construct a parse tree for the string.[2018]
Parsing Table
- What do you mean by CFG? Consider the following grammar: Now, draw the parsing table.[2020, 15, 12]
```
S → C + S | ε
C → b
```
Parse Tree for 9-5+2
- Derive a parse tree for 9-5+2 according to the following rules or productions:[2019, 18]
```
list → list + digit
list → list - digit
list -> digit
digit → 0 | 1 | 2 | ... | 9
```
Predictive Parsing
- What is predictive parsing? Construct the parsing table for the following grammar:[2014, 13]
```
E → T E'
E → + T E' | ε
T → F T'
T' → * F T' | ε
F → (E) | id
```

CFG Example

Consider the context-free grammar:
```
S → S + S | S * S | a
```
**(i) Show how the string aa + a * can be generated by this grammar. (ii) Construct a parse tree for this string.[2021, 17, 10]

Or,
- Consider the context-free grammar:Show how the string xx + x * can be generated by this grammar.[2013]
```
S → SS+ | SS* | x
```
Infix to Postfix Translation
- Translate the following infix expression into its equivalent postfix expression:(i) (A + B + D) / (E - F) + G2012, 11 (A * (B + D)) / (E - F)
Infix to Prefix Translation
- Translate the following infix expression into its equivalent prefix expression:(i) (A + B * D) / (E - F) + G(ii) (A * (B + D)) / E - F * (G + H + K)[2016]
Postfix Evaluation
- Evaluate the postfix expression ab + c *, where a = 1, b = 3, and c = 5.
Predictive Parsing Table
- Construct the predictive parsing table for the following grammar:[2013, 2019]
```
S → C S'
S' → a S | ε
C → b
```

NU CSE 7th Semester Notes