../

Syntax Analysis 3

Notes

LL(1) Parsing

Question 1: Write CEG

$G \rightarrow E$ $E \rightarrow E + T$ $E \rightarrow E - T$ $E \rightarrow T$ $T \rightarrow T * F$ $T \rightarrow T / F$ $T \rightarrow F$ $F \rightarrow (E)$ $F \rightarrow \text{number}$ $F \rightarrow \text{identifier}$

Question 2: Give the pseudo code for removing indirect left recursion 

grammar: dict[str, list[str]]
A = list(grammar.keys())
n = len(non_terminals)
for i in range(1, n):
	for s in range(0, i):
		for production in grammar[A[i]]:
			if production.starts_with(A[s]):
				tmp = []
				for production2 in grammar[A[s]]:
					tmp.append(production2 + production[1:])
			production.replace(tmp)
	eliminate_direct_recursion(A[i])

Question 3: What are the two conditions for the above algorithm to work?

  • No cycles $A \Rightarrow^+ A$
  • No $\varepsilon$ productions

Question 4: While drawing the matrix for removing indirect left recursion, what is the meaning of each cell

If the cell [i, j] has the value k then the $NT_i$ derives $NT_j$ in its $k^{th}$ position

Question 5: What is predictive parsing?

Predictive parser is a parser that doesn’t backtrack. It achieves this by using lookahead. Theoretically this lookahead can be unbounded but for most PL grammars this is a bounded

Question 6: Define $FIRST$ set

$x \in FIRST(\alpha)\ iff\ \alpha \Rightarrow^* x\gamma$

Question 7: Define $FOLLOW$ set

$FOLLOW(A)$ is the set of terminal symbols that can appear immediately after A in some sentential form

Question 8: Can the $FOLLOW$ set contain NT?

No

Question 9: Can the $FIRST$ set contain NT?

Yes. $FIRST$ includes all the symbols that appear as the first symbol in some string derived

Question 10: Define $FIRST()^+$

$FIRST(A\rightarrow\alpha) = FIRST(\alpha) \cup FOLLOW(A)$ if $\varepsilon \in FIRST(\alpha)$ else $FIRST(\alpha)$

Question 11: Explain the rationale of $FIRST()^+$

Either the RHS can derive the terminal Or it can vanish and there can be a sentential form where LHS is next to the terminal Basically the two condition where we would pick a rule in the LL table We want these conditions to be unique so that there is no backtracking

Question 12: What is the LL(1) property?

$A \rightarrow \alpha | \beta$ $FIRST(A\rightarrow\alpha)^+ \cap FIRST(A\rightarrow\beta)^+ = \phi$

Question 13: Can all non-LL(1) grammars be transformed into LL(1)?

No

Question 14: Can we guarantee that every language has an LL(1) grammar?

No

Question 15: Give the left factoring algorithm 

def left_factor():
  for production in grammar:
  	if production.hasCommonPrefix():
  		production.replaceCommonPrefix()

Question 16: Give the mathematical form of left-factoring

$A \rightarrow \alpha\beta_1 | \alpha\beta_2 | \alpha\beta_3 | \alpha\beta_4 \alpha\beta_4 | \alpha\beta_5| \gamma$ $A\rightarrow \alpha A’ | \gamma$ $A’ \rightarrow \beta_1 | \beta_2 \ldots | \beta_n$

Question 17: What are predictive grammar?

Grammars that have the LL(1) property