2023-10-10

Context Free Grammar

[!question]- What is parsing Process of discovering a derivation for a given sentence

[!question]- Formally define CFG $G = <S, N, T, P>$ $P: N \rightarrow (N \cup T)^+$

[!question]- What is a sentential form? A string of terminal and non-terminals that is a valid step in some derivation

[!question]- What makes a grammar context free? The LHS of all the productions have only one non-Terminal

[!question]- Draw the Chomsky Hierarchy of Grammars Type 3: RG Type 2: CFG Type 1: CSG Type 0: Unrestricted Grammar

[!question] Map Grammar and their corresponding abstract model of computing

[!question]- Give an example of things that are not a regular grammar? $a^nb^n$ $wcw^r$

[!question]- RG can count $\underline{\hspace{2cm}}$ and $\underline{\hspace{2cm}}$ bounded sets and bounded differences

[!question]- What is top down parsing Starting with the Start Symbol and working our way down to the sentence

[!question]- What is bottom up parsing Starting with the Sentence and working our way up to the Start Symbol

[!question]- What is a derivation Sequence of rewrites that produce a sentence

[!question]- 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]- How to identify ambiguous grammar?

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

[!question]- 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]- What are the sources of ambiguity?

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

[!question]- 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