{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Context-free grammars" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Creating CFGs\n", "\n", "You can create a CFG either by reading from a file (using `Grammar.from_file`) or a list of strings (using `Grammar.from_lines`). The first rule's left-hand side is assumed to be the start symbol." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "nonterminals: {S,T}
\n", "start: S
\n", "S → a T b
\n", "S → b
\n", "T → T a
\n", "T → ε" ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = Grammar.from_lines([\"S -> a T b\",\n", " \"S -> b\",\n", " \"T -> T a\",\n", " \"T -> &\"])\n", "g" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'S', 'T'}" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g.nonterminals" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A `Grammar` can be any unrestricted (type-0) grammar, but currently the grammar-reading functions can only read CFGs." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g.is_contextfree()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Like `RegularExpression` objects, there isn't a lot you can do with `Grammar` objects other than convert them to automata.\n", "\n", "## From CFGs to PDAs\n", "\n", "To convert to a PDA using a top-down construction, use the `from_grammar` function:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "loop\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε → [S] $\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "2->1\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "ε,S → [a] T b\n", "ε,S → b\n", "ε,T → [T] a\n", "ε,T → ε\n", "b,b → ε\n", "a,a → ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m = from_grammar(g)\n", "to_graph(m)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start,ε\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "23\n", "\n", "loop,[S] $\n", "\n", "\n", "\n", "0->23\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "\n", "2\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "a\n", "\n", "\n", "\n", "3\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "b\n", "\n", "\n", "\n", "5\n", "\n", "loop,[a] T b $\n", "\n", "\n", "\n", "7\n", "\n", "loop,[T] b $\n", "\n", "\n", "\n", "5->7\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "8\n", "\n", "loop,[T] a b $\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "7->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "\n", "loop,[a] b $\n", "\n", "\n", "\n", "8->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "\n", "loop,[T] a a b …\n", "\n", "\n", "\n", "8->11\n", "\n", "\n", "\n", "\n", "\n", "12\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "10->12\n", "\n", "\n", "\n", "\n", "\n", "14\n", "\n", "loop,[T] a a a …\n", "\n", "\n", "\n", "11->14\n", "\n", "\n", "\n", "\n", "\n", "15\n", "\n", "loop,[a] a b $\n", "\n", "\n", "\n", "11->15\n", "\n", "\n", "\n", "\n", "\n", "13\n", "\n", "loop,$\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "16\n", "\n", "\n", "accept,ε\n", "\n", "\n", "\n", "13->16\n", "\n", "\n", "\n", "\n", "\n", "14->14\n", "\n", "\n", "\n", "\n", "\n", "18\n", "\n", "loop,[a] a a b …\n", "\n", "\n", "\n", "14->18\n", "\n", "\n", "\n", "\n", "\n", "19\n", "\n", "loop,[a] a a a …\n", "\n", "\n", "\n", "14->19\n", "\n", "\n", "\n", "\n", "\n", "17\n", "\n", "loop,[a] b $\n", "\n", "\n", "\n", "15->17\n", "\n", "\n", "\n", "\n", "\n", "20\n", "\n", "loop,[a] a b $\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "\n", "loop,[a] a a a …\n", "\n", "\n", "\n", "19->21\n", "\n", "\n", "\n", "\n", "\n", "22\n", "\n", "loop,[a] a a b …\n", "\n", "\n", "\n", "19->22\n", "\n", "\n", "\n", "\n", "\n", "23->5\n", "\n", "\n", "\n", "\n", "\n", "23->6\n", "\n", "\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "run(m, \"a a b\", show_stack=4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This diagram is a little hard to read, but one thing to note is the cycle between `loop` and `3.1`. This is caused by the left-recursive rule `T -> T a`, which the automaton applies an unbounded number of times.\n", "\n", "### Shift-reduce parsing\n", "\n", "There's also a bottom-up version:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "loop\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "2->1\n", "\n", "\n", "ε,[S] $ → ε\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "ε,[b] T a → S\n", "ε,b → S\n", "ε,[a] T → T\n", "ε,ε → T\n", "b,ε → b\n", "a,ε → a\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m = from_grammar(g, mode=\"bottomup\")\n", "to_graph(m)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "14\n", "\n", "start,ε\n", "\n", "\n", "\n", "_START->14\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "loop,[T] T S …\n", "\n", "\n", "\n", "19\n", "\n", "loop,[T] T T …\n", "\n", "\n", "\n", "0->19\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "loop,[S] a $\n", "\n", "\n", "\n", "5\n", "\n", "loop,[T] S a …\n", "\n", "\n", "\n", "1->5\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "loop,[S] T T …\n", "\n", "\n", "\n", "3\n", "\n", "loop,[T] S T …\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "3->0\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "loop,[S] T a …\n", "\n", "\n", "\n", "4->3\n", "\n", "\n", "\n", "\n", "\n", "5->0\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "loop,[T] T b …\n", "\n", "\n", "\n", "6->19\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "loop,[T] b T …\n", "\n", "\n", "\n", "7->6\n", "\n", "\n", "\n", "\n", "\n", "8\n", "\n", "loop,[T] T T …\n", "\n", "\n", "\n", "8->8\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "loop,[b] T T …\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "9->2\n", "\n", "\n", "\n", "\n", "\n", "9->7\n", "\n", "\n", "\n", "\n", "\n", "10\n", "\n", "\n", "\n", "13\n", "\n", "\n", "\n", "10->13\n", "\n", "\n", "b\n", "\n", "\n", "\n", "11\n", "\n", "\n", "\n", "11->10\n", "\n", "\n", "a\n", "\n", "\n", "\n", "12\n", "\n", "\n", "\n", "12->11\n", "\n", "\n", "a\n", "\n", "\n", "\n", "15\n", "\n", "loop,$\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "16\n", "\n", "loop,[T] $\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "21\n", "\n", "loop,[a] $\n", "\n", "\n", "\n", "15->21\n", "\n", "\n", "\n", "\n", "\n", "22\n", "\n", "loop,[T] T $\n", "\n", "\n", "\n", "16->22\n", "\n", "\n", "\n", "\n", "\n", "23\n", "\n", "loop,[a] T $\n", "\n", "\n", "\n", "16->23\n", "\n", "\n", "\n", "\n", "\n", "17\n", "\n", "loop,[S] $\n", "\n", "\n", "\n", "18\n", "\n", "\n", "accept,ε\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "20\n", "\n", "loop,[T] S $\n", "\n", "\n", "\n", "17->20\n", "\n", "\n", "\n", "\n", "\n", "19->19\n", "\n", "\n", "\n", "\n", "\n", "20->0\n", "\n", "\n", "\n", "\n", "\n", "24\n", "\n", "loop,[T] a $\n", "\n", "\n", "\n", "21->24\n", "\n", "\n", "\n", "\n", "\n", "25\n", "\n", "loop,[a] a $\n", "\n", "\n", "\n", "21->25\n", "\n", "\n", "\n", "\n", "\n", "27\n", "\n", "loop,[T] T T …\n", "\n", "\n", "\n", "22->27\n", "\n", "\n", "\n", "\n", "\n", "28\n", "\n", "loop,[a] T T …\n", "\n", "\n", "\n", "22->28\n", "\n", "\n", "\n", "\n", "\n", "26\n", "\n", "loop,[T] $\n", "\n", "\n", "\n", "23->26\n", "\n", "\n", "\n", "\n", "\n", "31\n", "\n", "loop,[T] a T …\n", "\n", "\n", "\n", "23->31\n", "\n", "\n", "\n", "\n", "\n", "32\n", "\n", "loop,[a] a T …\n", "\n", "\n", "\n", "23->32\n", "\n", "\n", "\n", "\n", "\n", "33\n", "\n", "loop,[T] T a …\n", "\n", "\n", "\n", "24->33\n", "\n", "\n", "\n", "\n", "\n", "34\n", "\n", "loop,[a] T a …\n", "\n", "\n", "\n", "24->34\n", "\n", "\n", "\n", "\n", "\n", "35\n", "\n", "loop,[T] a a …\n", "\n", "\n", "\n", "25->35\n", "\n", "\n", "\n", "\n", "\n", "36\n", "\n", "loop,[b] a a …\n", "\n", "\n", "\n", "25->36\n", "\n", "\n", "\n", "\n", "\n", "29\n", "\n", "loop,[T] T $\n", "\n", "\n", "\n", "26->29\n", "\n", "\n", "\n", "\n", "\n", "30\n", "\n", "loop,[a] T $\n", "\n", "\n", "\n", "26->30\n", "\n", "\n", "\n", "\n", "\n", "27->27\n", "\n", "\n", "\n", "\n", "\n", "27->28\n", "\n", "\n", "\n", "\n", "\n", "28->29\n", "\n", "\n", "\n", "\n", "\n", "28->31\n", "\n", "\n", "\n", "\n", "\n", "28->32\n", "\n", "\n", "\n", "\n", "\n", "39\n", "\n", "loop,[T] T T …\n", "\n", "\n", "\n", "28->39\n", "\n", "\n", "\n", "\n", "\n", "29->39\n", "\n", "\n", "\n", "\n", "\n", "40\n", "\n", "loop,[a] T T …\n", "\n", "\n", "\n", "29->40\n", "\n", "\n", "\n", "\n", "\n", "37\n", "\n", "loop,[T] $\n", "\n", "\n", "\n", "30->37\n", "\n", "\n", "\n", "\n", "\n", "44\n", "\n", "loop,[T] a T …\n", "\n", "\n", "\n", "30->44\n", "\n", "\n", "\n", "\n", "\n", "45\n", "\n", "loop,[b] a T …\n", "\n", "\n", "\n", "30->45\n", "\n", "\n", "\n", "\n", "\n", "31->33\n", "\n", "\n", "\n", "\n", "\n", "31->34\n", "\n", "\n", "\n", "\n", "\n", "32->35\n", "\n", "\n", "\n", "\n", "\n", "32->36\n", "\n", "\n", "\n", "\n", "\n", "33->39\n", "\n", "\n", "\n", "\n", "\n", "33->40\n", "\n", "\n", "\n", "\n", "\n", "41\n", "\n", "loop,[T] a $\n", "\n", "\n", "\n", "34->41\n", "\n", "\n", "\n", "\n", "\n", "34->44\n", "\n", "\n", "\n", "\n", "\n", "34->45\n", "\n", "\n", "\n", "\n", "\n", "46\n", "\n", "loop,[T] T a …\n", "\n", "\n", "\n", "35->46\n", "\n", "\n", "\n", "\n", "\n", "47\n", "\n", "loop,[b] T a …\n", "\n", "\n", "\n", "35->47\n", "\n", "\n", "\n", "\n", "\n", "38\n", "\n", "loop,[S] a a …\n", "\n", "\n", "\n", "36->38\n", "\n", "\n", "\n", "\n", "\n", "48\n", "\n", "loop,[T] b a …\n", "\n", "\n", "\n", "36->48\n", "\n", "\n", "\n", "\n", "\n", "42\n", "\n", "loop,[T] T $\n", "\n", "\n", "\n", "37->42\n", "\n", "\n", "\n", "\n", "\n", "43\n", "\n", "loop,[b] T $\n", "\n", "\n", "\n", "37->43\n", "\n", "\n", "\n", "\n", "\n", "38->5\n", "\n", "\n", "\n", "\n", "\n", "39->39\n", "\n", "\n", "\n", "\n", "\n", "39->40\n", "\n", "\n", "\n", "\n", "\n", "40->8\n", "\n", "\n", "\n", "\n", "\n", "40->42\n", "\n", "\n", "\n", "\n", "\n", "40->44\n", "\n", "\n", "\n", "\n", "\n", "40->45\n", "\n", "\n", "\n", "\n", "\n", "40->46\n", "\n", "\n", "\n", "\n", "\n", "41->46\n", "\n", "\n", "\n", "\n", "\n", "41->47\n", "\n", "\n", "\n", "\n", "\n", "42->8\n", "\n", "\n", "\n", "\n", "\n", "42->9\n", "\n", "\n", "\n", "\n", "\n", "43->7\n", "\n", "\n", "\n", "\n", "\n", "49\n", "\n", "loop,[S] T $\n", "\n", "\n", "\n", "43->49\n", "\n", "\n", "\n", "\n", "\n", "44->2\n", "\n", "\n", "\n", "\n", "\n", "44->4\n", "\n", "\n", "\n", "\n", "\n", "44->46\n", "\n", "\n", "\n", "\n", "\n", "44->47\n", "\n", "\n", "\n", "\n", "\n", "44->49\n", "\n", "\n", "\n", "\n", "\n", "45->48\n", "\n", "\n", "\n", "\n", "\n", "50\n", "\n", "loop,[S] a T …\n", "\n", "\n", "\n", "45->50\n", "\n", "\n", "\n", "\n", "\n", "46->8\n", "\n", "\n", "\n", "\n", "\n", "46->9\n", "\n", "\n", "\n", "\n", "\n", "47->1\n", "\n", "\n", "\n", "\n", "\n", "47->2\n", "\n", "\n", "\n", "\n", "\n", "47->4\n", "\n", "\n", "\n", "\n", "\n", "47->7\n", "\n", "\n", "\n", "\n", "\n", "47->17\n", "\n", "\n", "\n", "\n", "\n", "47->49\n", "\n", "\n", "\n", "\n", "\n", "47->50\n", "\n", "\n", "\n", "\n", "\n", "48->6\n", "\n", "\n", "\n", "\n", "\n", "49->3\n", "\n", "\n", "\n", "\n", "\n", "50->5\n", "\n", "\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "run(m, \"a a b\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### LL(1) parsing" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "loop\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε → [S] $\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "3\n", "\n", "a\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a,ε → ε\n", "\n", "\n", "\n", "4\n", "\n", "b\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "b,ε → ε\n", "\n", "\n", "\n", "5\n", "\n", "c\n", "\n", "\n", "\n", "2->5\n", "\n", "\n", "c,ε → ε\n", "\n", "\n", "\n", "6\n", "\n", "⊣\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "␣,ε → ε\n", "\n", "\n", "\n", "3->2\n", "\n", "\n", "ε,a → ε\n", "\n", "\n", "\n", "3->3\n", "\n", "\n", "ε,S → [a] S c\n", "\n", "\n", "\n", "4->2\n", "\n", "\n", "ε,b → ε\n", "\n", "\n", "\n", "4->4\n", "\n", "\n", "ε,S → T\n", "ε,T → [b] T\n", "\n", "\n", "\n", "5->2\n", "\n", "\n", "ε,c → ε\n", "\n", "\n", "\n", "5->5\n", "\n", "\n", "ε,S → T\n", "ε,T → ε\n", "\n", "\n", "\n", "6->1\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "6->6\n", "\n", "\n", "ε,S → T\n", "ε,T → ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "g = Grammar.from_lines([\"S -> a S c\",\n", " \"S -> T\",\n", " \"T -> b T\",\n", " \"T -> &\"])\n", "\n", "m = from_grammar(g, mode='ll1')\n", "m" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m.is_deterministic()" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
start[a] a b c cε
loop[a] a b c c[S] $
a[a] b c c[S] $
a[a] b c c[a] S c $
loop[a] b c c[S] c $
a[b] c c[S] c $
a[b] c c[a] S c c $
loop[b] c c[S] c c $
b[c] c[S] c c $
b[c] c[T] c c $
b[c] c[b] T c c $
loop[c] c[T] c c $
cc[T] c c $
cc[c] c $
loopc[c] $
cε[c] $
loopε$
⊣ε$
acceptεε
\n" ], "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "run(m, \"a a b c c\", show_stack=5).only_path()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### LR parsing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Construction of an LR parser involves building the *LR automaton*:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "2\n", "\n", "start'\n", "\n", "\n", "\n", "_START->2\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "3\n", "\n", "loop\n", "\n", "\n", "\n", "0->3\n", "\n", "\n", "ε,2 → [3] $ 2\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "2->0\n", "\n", "\n", "ε,ε → 2\n", "\n", "\n", "\n", "3->1\n", "\n", "\n", "ε,[8] S 3 $ 2 → 2\n", "\n", "\n", "\n", "3->3\n", "\n", "\n", "ε,[6] ⊣ 7 T 3 → [8] S 3\n", "ε,[5] r 4 T 1 l 4 T 1 → [4] T 1\n", "ε,[5] r 4 T 1 l 7 T 3 → [7] T 3\n", "ε,1 → [4] T 1\n", "ε,3 → [7] T 3\n", "r,4 → [5] r 4\n", "l,4 → [1] l 4\n", "l,7 → [1] l 7\n", "⊣,7 → [6] ⊣ 7\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "g = Grammar.from_lines([\n", " 'S -> T -|',\n", " 'T -> T l T r',\n", " 'T -> &'\n", "])\n", "\n", "m = from_grammar(g, mode='lr0')\n", "m" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m.is_deterministic()" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
start'[l] l r l r r ⊣ε
start[l] l r l r r ⊣2
loop[l] l r l r r ⊣[3] $ 2
loop[l] l r l r r ⊣[7] T 3 $ 2
loop[l] r l r r ⊣[1] l 7 T 3 $ 2
loop[l] r l r r ⊣[4] T 1 l 7 T 3 $ 2
loop[r] l r r ⊣[1] l 4 T 1 l 7 T 3 $ 2
loop[r] l r r ⊣[4] T 1 l 4 T 1 l 7 T 3 $ 2
loop[l] r r ⊣[5] r 4 T 1 l 4 T 1 l 7 T 3 $ 2
loop[l] r r ⊣[4] T 1 l 7 T 3 $ 2
loop[r] r ⊣[1] l 4 T 1 l 7 T 3 $ 2
loop[r] r ⊣[4] T 1 l 4 T 1 l 7 T 3 $ 2
loop[r] ⊣[5] r 4 T 1 l 4 T 1 l 7 T 3 $ 2
loop[r] ⊣[4] T 1 l 7 T 3 $ 2
loop⊣[5] r 4 T 1 l 7 T 3 $ 2
loop⊣[7] T 3 $ 2
loopε[6] ⊣ 7 T 3 $ 2
loopε[8] S 3 $ 2
acceptε2
\n" ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "run(m, 'l l r l r r -|', show_stack=15).only_path()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can visualize the LR automaton using `grammars.lr_automaton`, and you can also build an LR(1) parser using `mode='lr1'`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## From PDAs to CFGs\n", "\n", "The conversion in the reverse direction, from PDA to CFG, is actually related to the algorithm that Tock uses internally to simulate PDAs. We use the `remove_useless` method to reduce the size of the converted CFG." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "nonterminals: {(q1,q1),(q1,q4),(q2,q2),(q2,q3),(q3,q3),(q4,q4),(start,accept)}
\n", "start: (start,accept)
\n", "(q2,q3) → 0 (q2,q2) 1
\n", "(q2,q3) → 0 (q2,q3) 1
\n", "(q1,q4) → (q2,q3)
\n", "(start,accept) → (q1,q4)
\n", "(q1,q1) → (q1,q1) (q1,q1)
\n", "(q1,q4) → (q1,q1) (q1,q4)
\n", "(q1,q4) → (q1,q4) (q4,q4)
\n", "(q4,q4) → (q4,q4) (q4,q4)
\n", "(q3,q3) → (q3,q3) (q3,q3)
\n", "(q2,q3) → (q2,q3) (q3,q3)
\n", "(q2,q3) → (q2,q2) (q2,q3)
\n", "(q2,q2) → (q2,q2) (q2,q2)
\n", "(q1,q1) → ε
\n", "(q4,q4) → ε
\n", "(q3,q3) → ε
\n", "(q2,q2) → ε" ], "text/plain": [ "" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = read_csv('examples/sipser-2-14.csv')\n", "g = to_grammar(m).remove_useless()\n", "g" ] } ], "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.8.1" } }, "nbformat": 4, "nbformat_minor": 1 }