2023-10-10

Context Free Grammar

Question 1: What is parsing

Process of discovering a derivation for a given sentence

Question 2: Formally define CFG

$G = <S, N, T, P>$ $P: N \rightarrow (N \cup T)^+$

Question 3: What is a sentential form?

A string of terminal and non-terminals that is a valid step in some derivation

Question 4: What makes a grammar context free?

The LHS of all the productions have only one non-Terminal

Question 5: Draw the Chomsky Hierarchy of Grammars

Type 3: RG Type 2: CFG Type 1: CSG Type 0: Unrestricted Grammar

Question 6: Map Grammar and their corresponding abstract model of computing

Question 7: Give an example of things that are not a regular grammar?

$a^nb^n$ $wcw^r$

Question 8: RG can count $\underline{\hspace{2cm}}$ and $\underline{\hspace{2cm}}$

bounded sets and bounded differences

Question 9: What is top down parsing

Starting with the Start Symbol and working our way down to the sentence

Question 10: What is bottom up parsing

Starting with the Sentence and working our way up to the Start Symbol

Question 11: What is a derivation

Sequence of rewrites that produce a sentence

Question 12: Are Floating point numbers real numbers?

No. Limited magnitude of $2^{-32} to 2^{31}$ causes overflow and underflow There may also be unexpected loss of precision

Question 13: How to identify ambiguous grammar?

• Multiple left or multiple right derivations or
• Left and right derivation produce different parse trees

Question 14: Consider a grammar $G$. It’s left and right derivations are different. Is it ambiguous?

No. It is ambiguous only if the parse trees are different

Question 15: What are the sources of ambiguity?

• Context-free syntax
• Context-sensitive things such as overloading

Question 16: Give examples of ambiguity that occurs which is not caused by ambiguous grammar

a = f(17) in ALGOL can either be a function call or a subscript into the variable f These sort of ambiguities needs to be resolved outside the CFG as they are not caused by CFG