..

Syntax Analysis 3

Notes

LL(1) Parsing

[!question]- 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]- 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]- What are the two conditions for the above algorithm to work?

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

[!question]- 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]- 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]- Define $FIRST$ set $x \in FIRST(\alpha)\ iff\ \alpha \Rightarrow^* x\gamma$

[!question]- Define $FOLLOW$ set $FOLLOW(A)$ is the set of terminal symbols that can appear immediately after A in some sentential form

[!question]- Can the $FOLLOW$ set contain NT? No

[!question]- Can the $FIRST$ set contain NT? Yes. $FIRST$ includes all the symbols that appear as the first symbol in some string derived

[!question]- Define $FIRST()^+$ $FIRST(A\rightarrow\alpha) = FIRST(\alpha) \cup FOLLOW(A)$ if $\varepsilon \in FIRST(\alpha)$ else $FIRST(\alpha)$

[!question]- 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]- What is the LL(1) property? $A \rightarrow \alpha | \beta$ $FIRST(A\rightarrow\alpha)^+ \cap FIRST(A\rightarrow\beta)^+ = \phi$

[!question]- Can all non-LL(1) grammars be transformed into LL(1)? No

[!question]- Can we guarantee that every language has an LL(1) grammar? No

[!question]- Give the left factoring algorithm

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

[!question]- 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]- What are predictive grammar? Grammars that have the LL(1) property