{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# LL parsing (optional)\n",
"\n",
"Deterministic PDAs are appealing because they are much easier to implement. However, the CFG to PDA conversion in the book outputs a deterministic PDA only for the most uninteresting CFGs.\n",
"\n",
"For example, the following grammar generates the language $\\{\\texttt{a}^i \\texttt{b}^j \\texttt{c}^i \\mid i, j \\geq 0\\}$, which you could easily write a deterministic PDA for:\n",
"\n",
"\\begin{align*}\n",
"S &\\rightarrow \\texttt{a} S \\texttt{c} \\\\\n",
"S &\\rightarrow T \\\\\n",
"T &\\rightarrow \\texttt{b} T \\\\\n",
"T &\\rightarrow \\varepsilon\n",
"\\end{align*}"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"from tock import *\n",
"\n",
"g = Grammar.from_lines([\"S -> a S c\",\n",
" \"S -> T\",\n",
" \"T -> b T\",\n",
" \"T -> &\"])\n",
"p1 = from_grammar(g)\n",
"to_graph(p1)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p1.is_deterministic()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There is nondeterminism in state `loop`, when the top stack symbol is either $S$ or $T$. Each of these nonterminals has two rules it can be rewritten with, and the PDA doesn't know which one to use. You can figure it out intuitively:\n",
"\n",
"- If the top stack symbol is $S$:\n",
" - If the next input symbol is $\\texttt{a}$, use the first rule.\n",
" - Else, use the second rule.\n",
"- If the top stack symbol is $T$:\n",
" - If the next symbol is $\\texttt{b}$, use the third rule.\n",
" - Else, use the fourth rule.\n",
" \n",
"Below, we'll show how to modify the CFG to PDA conversion to output a deterministic PDA that is able to _look ahead_ one symbol to capture the above intuition."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The endmarker\n",
"\n",
"When the PDA is at the end of the string, we want it to be able to look ahead and see that there are no more input symbols. So let's append an _endmarker_ $\\dashv$ to end of the input string. We continue to write $\\Sigma$ for the original alphabet that does not contain $\\dashv$.\n",
"\n",
"Accordingly, we modify our grammar by creating a new start nonterminal, $S'$, and adding a rule\n",
"\n",
"$$ S' \\rightarrow S\\dashv $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Basic idea\n",
"\n",
"Given a top stack symbol $A$ and a look-ahead input symbol $c$, we want to automatically figure out which rule $A \\rightarrow \\beta$ to use. The logic will go as follows:\n",
"\n",
"- If $\\beta$ can be rewritten to a string that starts with $c$, then $A \\rightarrow \\beta$ is possible.\n",
"- If $\\beta$ can be rewritten to $\\varepsilon$ and it's possible for $c$ to come after $A$, then $A \\rightarrow \\beta$ is possible.\n",
"\n",
"And we only want one rule to be possible at a time.\n",
"\n",
"We implement this logic by precomputing three tables, defined below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The $\\text{Nullable}$ table\n",
"\n",
"Define a _rhs suffix_ of $G$ to be a suffix of the right-hand side of a rule of $G$. The rhs suffixes of our example grammar are: $\\varepsilon, \\texttt{c}, S\\texttt{c}, \\texttt{a}S\\texttt{c}, T, \\texttt{b}T$.\n",
"\n",
"Define a table $\\text{Nullable}(\\alpha)$, where $\\alpha$ is a terminal or nonterminal symbol or a rhs suffix, that says whether it's possible to rewrite $\\alpha$ to the empty string (that is, $\\alpha \\Rightarrow^\\ast \\varepsilon$).\n",
"\n",
"1. For all $\\alpha$, $\\text{Nullable}(\\alpha) \\leftarrow \\text{False}$.\n",
"2. $\\text{Nullable}(\\epsilon) \\leftarrow \\text{True}$.\n",
"3. Repeat until $\\text{Nullable}$ does not change:\n",
" 1. For each rule $A \\rightarrow \\beta$:\n",
" 1. $n \\leftarrow |\\beta|$\n",
" 2. For $i \\leftarrow n, \\ldots, 1$:\n",
" 1. If $\\text{Nullable}(\\beta_{i+1} \\cdots \\beta_n)$ and $\\text{Nullable}(\\beta_i)$, then $\\text{Nullable}(\\beta_i \\cdots \\beta_n) \\leftarrow \\text{True}$\n",
" 3. If $\\text{Nullable}(\\beta)$, then $\\text{Nullable}(A) \\leftarrow \\text{True}$.\n",
"\n",
"In our example grammar, $S$ and $T$ are both nullable, but $S'$ is not. The nullable rhs suffixes are: $\\varepsilon, T$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The $\\text{First}$ table\n",
"\n",
"Define a table $\\text{First}(\\alpha)$, where $\\alpha$ is a terminal or nonterminal symbol\n",
"or a rhs suffix, that says what terminals $\\alpha$ can start with (after rewriting). That is, \n",
"$$\\text{First}(\\alpha) = \\{b \\mid \\text{$\\alpha \\Rightarrow^\\ast b\\gamma$ for some $\\gamma$}\\}$$\n",
"\n",
"1. For all $\\alpha$, $\\text{First}(\\alpha) = \\emptyset$.\n",
"1. For all terminals $a$, $\\text{First}(a) = \\{ a \\}$.\n",
"2. Repeat until $\\text{First}$ does not change:\n",
" 1. For each rule $A \\rightarrow \\beta$:\n",
" 1. $n \\leftarrow |\\beta|$\n",
" 2. For $i \\leftarrow n, \\ldots, 1$:\n",
" 1. $\\text{First}(\\beta_i \\cdots \\beta_n) \\leftarrow \\text{First}(\\beta_i \\cdots \\beta_n) \\cup \\text{First}(\\beta_{i})$.\n",
" 1. If $\\text{Nullable}(\\beta_i)$, then $\\text{First}(\\beta_i \\cdots \\beta_n) \\leftarrow \\text{First}(\\beta_i \\cdots \\beta_n) \\cup \\text{First}(\\beta_{i+1} \\cdots \\beta_n)$.\n",
" 3. $\\text{First}(A) \\leftarrow \\text{First}(A) \\cup \\text{First}(\\beta)$.\n",
"\n",
"In our example grammar, we have\n",
"\n",
"| $\\alpha$ | $\\text{First}(\\alpha)$ |\n",
"|----------|------------------------|\n",
"| $S$ | $\\{\\texttt{a}, \\texttt{b}\\}$ |\n",
"| $T$ | $\\{\\texttt{b}\\}$ |\n",
"| $\\texttt{a}$ | $\\{\\texttt{a}\\}$ |\n",
"| $\\texttt{b}$ | $\\{\\texttt{b}\\}$ |\n",
"| $\\texttt{c}$ | $\\{\\texttt{c}\\}$ |\n",
"| $\\varepsilon$ | $\\emptyset$ |\n",
"| $S\\texttt{c}$ | $\\{\\texttt{a}, \\texttt{b}, \\texttt{c}\\}$ |\n",
"| $\\texttt{a}S\\texttt{c}$ | $\\{\\texttt{a}\\}$ |\n",
"| $\\texttt{b}T$ | $\\{\\texttt{b}\\}$ |\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The $\\text{Follow}$ function\n",
"\n",
"Define a table $\\text{Follow}(A)$ that says, for each nonterminal $A$, what terminals can come after it. That is, $$\\text{Follow}(A) = \\{ b \\mid \\text{$S \\Rightarrow^\\ast \\gamma A b \\delta$ for some $\\gamma, \\delta$} \\}$$\n",
"\n",
"1. For all $A$, $\\text{Follow}(A) = \\emptyset$.\n",
"2. Repeat until $\\text{Follow}$ does not change:\n",
" 1. For each rule $A \\rightarrow \\beta$:\n",
" 1. $n \\leftarrow |\\beta|$\n",
" 1. For $i \\leftarrow 1, \\ldots, n$ such that $\\beta_i$ is a nonterminal $B$:\n",
" 1. $\\text{Follow}(B) \\leftarrow \\text{Follow}(B) \\cup \\text{First}(\\beta_{i+1}\\cdots \\beta_n)$\n",
" 2. If $\\text{Nullable}(\\beta_{i+1} \\cdots \\beta_n)$, then $\\text{Follow}(B) \\leftarrow \\text{Follow}(B) \\cup \\text{Follow}(A)$.\n",
" \n",
"In our example grammar, we have $\\text{Follow}(S) = \\text{Follow}(T) = \\{\\texttt{c}, \\dashv\\}$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Recursive-descent parsing\n",
"\n",
"We can now use these tables to implement a _recursive-descent_ parser, which has a function for each nonterminal symbol. The function for nonterminal $A$ is called on an input string $w$ and a position $i$ and has to return $j$ such that $A \\Rightarrow^\\ast w_i \\cdots w_{j-1}$. To do this, the function must decide which rule to use, using the Nullable, First, and Follow tables. For our example grammar, the parser would look like:\n",
"\n",
"```\n",
"function parse(w)\n",
" i <- parseS(w, 0)\n",
" if i = |w| then\n",
" return True\n",
" else\n",
" error\n",
" \n",
"function parseS(w, i)\n",
" # S -> aSc\n",
" if i < |w| and w[i] in {\"a\"} # First(aSc)\n",
" i = i + 1\n",
" i = parseS(w, i)\n",
" if w[i] != \"c\" return False\n",
" i = i + 1\n",
" return i\n",
" # S -> T\n",
" else if (w[i] in {\"b\"} # First(T)\n",
" or\n",
" i = |w| or w[i] in {\"c\"}) # Follow(S)\n",
" return parseT(w, i)\n",
" else\n",
" error\n",
" \n",
"function parseT(w, i)\n",
" # T -> bT\n",
" if i < |w| and w[i] in {\"b\"} # First(bT)\n",
" i = i + 1\n",
" return parseT(w, i)\n",
" # T -> ε\n",
" else if i = |w| or w[i] in {\"c\"} # Follow(T)\n",
" return i\n",
" else\n",
" error \n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Conversion to DPDA\n",
"\n",
"We can also use the Nullable, First, and Follow tables to build a DPDA. To do this, we first modify the conversion from a CFG to a PDA to use a one-symbol lookahead. The states of the PDA are the start state $s$, $q$, a state $q_a$ for each $a \\in \\Sigma$, and an accept state $f$.\n",
"\n",
"1. A transition from $s$ to $q$ that pushes $S\\$$.\n",
"2. A transition from $q$ to $q_a$ that reads $a$ for all $a \\in \\Sigma \\cup \\{\\dashv\\}$.\n",
"3. A transition from $q_a$ to $q$ that pops $a$, for all $a \\in \\Sigma$.\n",
"4. For each rule $A \\rightarrow \\beta$ and each $c \\in \\Sigma$, a transition from $q_c$ to itself that pops $A$ and pushes $\\beta$.\n",
"5. A transition from $q$ to $f$ that pops $\\$$.\n",
"\n",
"The PDA looks like this (using the shorthand on page 119):\n",
"\n",
"\n",
"\n",
"where state $q_a$ is replicated for every possible terminal symbol, and the self-loop on state $q_a$ is replicated for all rules. \n",
"\n",
"For our example grammar, this PDA looks like this:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"p2 = read_csv(\"llpda.csv\")\n",
"to_graph(p2)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p2.is_deterministic()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This PDA is similar to the one in the proof of Lemma 2.21, but it has states $q_a$ that can apply rules with the knowledge that the next input symbol is $a$.\n",
"\n",
"So, we can restrict the application of rules only to those that are allowed by Nullable, First, and Follow:\n",
"\n",
"4. For each rule $A \\rightarrow \\beta$ and for each $c \\in \\Sigma$ such that $c \\in \\text{First}(\\beta)$ or ($\\text{Nullable}(\\beta)$ and $c \\in \\text{Follow}(A)$), a transition from $q_c$ to itself that pops $A$ and pushes $\\beta$."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"p3 = read_csv(\"lldpda.csv\")\n",
"to_graph(p3)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p3.is_deterministic()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now the PDA is deterministic, which is what we wanted. Note that it was _not_ guaranteed to be deterministic; we just got lucky. If it is deterministic, we say that the original grammar is $LL(1)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Making grammars $LL(1)$\n",
"\n",
"So, if grammars are not guaranteed to be $LL(1)$, how do we design our grammars so that they are? We show two strategies that can sometimes (but not always) help.\n",
"\n",
"**Merge common prefixes.** Consider this very simple grammar:\n",
"\n",
"\\begin{align*}\n",
"S &\\rightarrow \\texttt{a b} \\\\\n",
"S &\\rightarrow \\texttt{a c}\n",
"\\end{align*}\n",
"\n",
"It's not $LL(1)$ because $\\texttt{a}$ belongs to both $\\text{First}(\\texttt{a b})$ and $\\text{First}(\\texttt{a c})$. The solution is to create a new nonterminal for the non-shared part, like this:\n",
"\n",
"\\begin{align*}\n",
"S &\\rightarrow \\texttt{a} S' \\\\\n",
"S' &\\rightarrow \\texttt{b} \\\\\n",
"S' &\\rightarrow \\texttt{c}\n",
"\\end{align*}\n",
"\n",
"In general, if we have two rules \n",
"\\begin{align*}\n",
"A &\\rightarrow \\beta\\gamma \\\\\n",
"A &\\rightarrow \\beta\\delta\n",
"\\end{align*}\n",
"then $\\text{First}(\\beta\\gamma)$ and $\\text{First}(\\beta\\delta)$ wlil overlap, and the solution is to change this to\n",
"\\begin{align*}\n",
"A &\\rightarrow \\beta A' \\\\\n",
"A' &\\rightarrow \\gamma \\\\\n",
"A' &\\rightarrow \\delta\n",
"\\end{align*}\n",
"\n",
"**Eliminate left recursion.** Consider this grammar:\n",
"\n",
"\\begin{align*}\n",
"S &\\rightarrow S~\\texttt{-}~T \\\\\n",
"S &\\rightarrow T \\\\\n",
"T &\\rightarrow \\texttt{1}\n",
"\\end{align*}\n",
"\n",
"The first rule is called _left-recursive_ because the first symbol on the right-hand side is the same as the left-hand side. In such cases there will always be an overlap between the left-recursive rule's and the \"base case\" rule's right-hand side. The usual fix is:\n",
"\n",
"\\begin{align*}\n",
"S &\\rightarrow T S' \\\\\n",
"S' &\\rightarrow \\texttt{-}~T S' \\\\\n",
"S' &\\rightarrow \\varepsilon \\\\\n",
"T &\\rightarrow \\texttt{1}\n",
"\\end{align*}\n",
"\n",
"But be careful, because it seems we just changed - (minus) from left-associative to right-associative. In a recursive-descent parser, we can get the associativity correct like this:\n",
"\n",
"```\n",
"function parse(w)\n",
" val, i <- parseS(w, 0)\n",
" if i = |w| then\n",
" return val\n",
" else\n",
" error\n",
" \n",
"function parseS(w, i)\n",
" # S -> T S'\n",
" val, i = parseT(w, i)\n",
" val, i = parseS'(w, i, val)\n",
" return val, i\n",
" \n",
"function parseS'(w, i, val)\n",
" # S' -> + T S'\n",
" if i < |w| and w[i] in {\"+\"} # First(+ T S')\n",
" i <- i + 1\n",
" val2, i = parseT(w, i)\n",
" val, i = parseS'(w, i, val-val2)\n",
" return val, i\n",
" else if i = |w| # Follow(S')\n",
" return val, i\n",
" else\n",
" error\n",
" \n",
"function parseT(w, i)\n",
" # T -> a\n",
" if i < |w| and w[i] in {\"1\"} # First(1)\n",
" i <- i + 1\n",
" return 1, i\n",
" else\n",
" error\n",
"```"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}