0. Context-Free Grammar (CFG)

• 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]

1. 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]
2. Defining CFG and Equality
   • How will you define a context-free grammar? When will you say that two CFGs are equal?[2011]
3. Parse Tree
   • What do you mean by a parse tree? Describe its properties.[2020, 17, 10]
4. 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]
5. Separation of Analysis Phase
   • What are the reasons for separating the analysis phase of compiling into lexical analysis and parsing?[2014, 12, 11, 09]
6. Transition Diagram
   • What do you mean by a transition diagram? Draw the transition diagram for relational operators.[2021, 18, 09]
7. Associativity of Operators
   • Describe the associativity of operators with examples.[2011]

Simplification

1. 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]

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

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

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

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