Commits

Anonymous committed 25be410

.

  • Participants

Comments (0)

Files changed (3)

+It's a project to make OCaml implementation of Earley parser.
+
+Goal: create a parser using descriptions from doc/ directory.

doc/PracticalEarleyParsing.pdf

Binary file added.

doc/earley_parser_from_wikipedia.html

+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" lang="en" dir="ltr">
+<head>
+<title>Earley parser - Wikipedia, the free encyclopedia</title>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
+<meta http-equiv="Content-Style-Type" content="text/css" />
+<meta name="generator" content="MediaWiki 1.16wmf4" />
+<link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Earley_parser&amp;action=edit" />
+<link rel="edit" title="Edit this page" href="/w/index.php?title=Earley_parser&amp;action=edit" />
+<link rel="apple-touch-icon" href="http://en.wikipedia.org/apple-touch-icon.png" />
+<link rel="shortcut icon" href="/favicon.ico" />
+<link rel="search" type="application/opensearchdescription+xml" href="/w/opensearch_desc.php" title="Wikipedia (en)" />
+<link rel="copyright" href="http://creativecommons.org/licenses/by-sa/3.0/" />
+<link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&amp;feed=atom" />
+<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/vector/main-ltr.css?283-12" type="text/css" media="screen" />
+<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/common/shared.css?283-12" type="text/css" media="screen" />
+<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/common/commonPrint.css?283-12" type="text/css" media="print" />
+<link rel="stylesheet" href="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/css/combined.min.css?117" type="text/css" media="all" />
+<link rel="stylesheet" href="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/css/vector/jquery-ui-1.7.2.css?1.7.2y" type="text/css" media="all" />
+<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Common.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="all" />
+<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Print.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="print" />
+<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Handheld.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="handheld" />
+<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Vector.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="all" />
+<link rel="stylesheet" href="/w/index.php?title=-&amp;action=raw&amp;maxage=2678400&amp;gen=css" type="text/css" media="all" />
+<script type="text/javascript">
+var skin="vector",
+stylepath="http://bits.wikimedia.org/skins-1.5",
+wgUrlProtocols="http\\:\\/\\/|https\\:\\/\\/|ftp\\:\\/\\/|irc\\:\\/\\/|gopher\\:\\/\\/|telnet\\:\\/\\/|nntp\\:\\/\\/|worldwind\\:\\/\\/|mailto\\:|news\\:|svn\\:\\/\\/",
+wgArticlePath="/wiki/$1",
+wgScriptPath="/w",
+wgScriptExtension=".php",
+wgScript="/w/index.php",
+wgVariantArticlePath=false,
+wgActionPaths={},
+wgServer="http://en.wikipedia.org",
+wgCanonicalNamespace="",
+wgCanonicalSpecialPageName=false,
+wgNamespaceNumber=0,
+wgPageName="Earley_parser",
+wgTitle="Earley parser",
+wgAction="view",
+wgArticleId=9685,
+wgIsArticle=true,
+wgUserName=null,
+wgUserGroups=null,
+wgUserLanguage="en",
+wgContentLanguage="en",
+wgBreakFrames=false,
+wgCurRevisionId=396700343,
+wgVersion="1.16wmf4",
+wgEnableAPI=true,
+wgEnableWriteAPI=true,
+wgSeparatorTransformTable=["", ""],
+wgDigitTransformTable=["", ""],
+wgMainPageTitle="Main Page",
+wgFormattedNamespaces={"-2": "Media", "-1": "Special", "0": "", "1": "Talk", "2": "User", "3": "User talk", "4": "Wikipedia", "5": "Wikipedia talk", "6": "File", "7": "File talk", "8": "MediaWiki", "9": "MediaWiki talk", "10": "Template", "11": "Template talk", "12": "Help", "13": "Help talk", "14": "Category", "15": "Category talk", "100": "Portal", "101": "Portal talk", "108": "Book", "109": "Book talk"},
+wgNamespaceIds={"media": -2, "special": -1, "": 0, "talk": 1, "user": 2, "user_talk": 3, "wikipedia": 4, "wikipedia_talk": 5, "file": 6, "file_talk": 7, "mediawiki": 8, "mediawiki_talk": 9, "template": 10, "template_talk": 11, "help": 12, "help_talk": 13, "category": 14, "category_talk": 15, "portal": 100, "portal_talk": 101, "book": 108, "book_talk": 109, "wp": 4, "wt": 5, "image": 6, "image_talk": 7},
+wgSiteName="Wikipedia",
+wgCategories=["Parsing algorithms", "Dynamic programming"],
+wgDBname="enwiki",
+wgMWSuggestTemplate="http://en.wikipedia.org/w/api.php?action=opensearch\x26search={searchTerms}\x26namespace={namespaces}\x26suggest",
+wgSearchNamespaces=[0],
+wgMWSuggestMessages=["with suggestions", "no suggestions"],
+wgRestrictionEdit=[],
+wgRestrictionMove=[],
+wgFlaggedRevsParams={"tags": {"status": {"levels": 1, "quality": 2, "pristine": 3}}},
+wgStableRevisionId=0,
+wgWikimediaMobileUrl="http://en.m.wikipedia.org/wiki",
+wgCollapsibleNavBucketTest=false,
+wgCollapsibleNavForceNewVersion=false,
+wgVectorPreferences={"collapsiblenav": {"enable": 1}, "editwarning": {"enable": 1}, "simplesearch": {"enable": 1, "disablesuggest": 0}},
+wgVectorEnabledModules={"collapsiblenav": true, "collapsibletabs": true, "editwarning": true, "expandablesearch": false, "footercleanup": false, "simplesearch": true},
+wgArticleAssessmentJUIPath="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/js/js2stopgap/jui.combined.min.js",
+Geo={"city": "", "country": ""},
+wgNoticeProject="wikipedia";
+</script><script src="http://bits.wikimedia.org/skins-1.5/common/wikibits.js?283-12" type="text/javascript"></script>
+<script type="text/javascript" src="http://bits.wikimedia.org/skins-1.5/common/jquery.min.js?283-12"></script>
+<script src="http://bits.wikimedia.org/skins-1.5/common/ajax.js?283-12" type="text/javascript"></script>
+<script src="http://bits.wikimedia.org/skins-1.5/common/mwsuggest.js?283-12" type="text/javascript"></script>
+<script src="http://bits.wikimedia.org/w/extensions/WikimediaMobile/MobileRedirect.js?2.2" type="text/javascript"></script>
+<script src="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/js/plugins.combined.min.js?283-12" type="text/javascript"></script>
+<script src="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/Vector/Vector.combined.min.js?283-12" type="text/javascript"></script>
+<script type="text/javascript">mw.usability.addMessages({'vector-collapsiblenav-more':'More languages','vector-editwarning-warning':'Leaving this page may cause you to lose any changes you have made.\nIf you are logged in, you can disable this warning in the \"Editing\" section of your preferences.','vector-simplesearch-search':'Search','vector-simplesearch-containing':'containing...'});</script>
+<script src="/w/index.php?title=Special:BannerController&amp;cache=/cn.js&amp;283-12" type="text/javascript"></script>
+<!--[if lt IE 7]><style type="text/css">body{behavior:url("/w/skins-1.5/vector/csshover.htc")}</style><![endif]-->
+<script src="/w/index.php?title=-&amp;action=raw&amp;gen=js&amp;useskin=vector&amp;283-12" type="text/javascript"></script>
+
+</head>
+<body class="mediawiki ltr ns-0 ns-subject page-Earley_parser skin-vector">
+		<div id="mw-page-base" class="noprint"></div>
+		<div id="mw-head-base" class="noprint"></div>
+		<!-- content -->
+		<div id="content">
+			<a id="top"></a>
+			<div id="mw-js-message" style="display:none;"></div>
+						<!-- sitenotice -->
+			<div id="siteNotice"><!-- centralNotice loads here --></div>
+			<!-- /sitenotice -->
+						<!-- firstHeading -->
+			<h1 id="firstHeading" class="firstHeading">Earley parser</h1>
+			<!-- /firstHeading -->
+			<!-- bodyContent -->
+			<div id="bodyContent">
+				<!-- tagline -->
+				<div id="siteSub">From Wikipedia, the free encyclopedia</div>
+				<!-- /tagline -->
+				<!-- subtitle -->
+				<div id="contentSub"></div>
+				<!-- /subtitle -->
+																<!-- jumpto -->
+				<div id="jump-to-nav">
+					Jump to: <a href="#mw-head">navigation</a>,
+					<a href="#p-search">search</a>
+				</div>
+				<!-- /jumpto -->
+								<!-- bodytext -->
+				<p>The <b>Earley parser</b> is a type of <a href="/wiki/Chart_parser" title="Chart parser">chart parser</a> mainly used for parsing in <a href="/wiki/Computational_linguistics" title="Computational linguistics">computational linguistics</a>, named after its inventor, <a href="/wiki/Jay_Earley" title="Jay Earley">Jay Earley</a>. The algorithm uses <a href="/wiki/Dynamic_programming" title="Dynamic programming">dynamic programming</a>.</p>
+<p>Earley parsers are appealing because they can parse all <a href="/wiki/Context-free_language" title="Context-free language">context-free languages</a>. The Earley parser executes in cubic time (<a href="/wiki/Big_O_notation" title="Big O notation">O</a>(n<sup>3</sup>), where <i>n</i> is the length of the parsed string) in the general case, quadratic time (<a href="/wiki/Big_O_notation" title="Big O notation">O</a>(n<sup>2</sup>)) for unambiguous grammars, and linear time for almost all LR(k) grammars. It performs particularly well when the rules are written <a href="/wiki/Left_recursion" title="Left recursion">left-recursively</a>.</p>
+<table id="toc" class="toc">
+<tr>
+<td>
+<div id="toctitle">
+<h2>Contents</h2>
+</div>
+<ul>
+<li class="toclevel-1 tocsection-1"><a href="#The_algorithm"><span class="tocnumber">1</span> <span class="toctext">The algorithm</span></a></li>
+<li class="toclevel-1 tocsection-2"><a href="#Example"><span class="tocnumber">2</span> <span class="toctext">Example</span></a></li>
+<li class="toclevel-1 tocsection-3"><a href="#See_also"><span class="tocnumber">3</span> <span class="toctext">See also</span></a></li>
+<li class="toclevel-1 tocsection-4"><a href="#References"><span class="tocnumber">4</span> <span class="toctext">References</span></a></li>
+<li class="toclevel-1 tocsection-5"><a href="#External_links"><span class="tocnumber">5</span> <span class="toctext">External links</span></a>
+<ul>
+<li class="toclevel-2 tocsection-6"><a href="#Implementations"><span class="tocnumber">5.1</span> <span class="toctext">Implementations</span></a>
+<ul>
+<li class="toclevel-3 tocsection-7"><a href="#C"><span class="tocnumber">5.1.1</span> <span class="toctext">C</span></a></li>
+<li class="toclevel-3 tocsection-8"><a href="#Java"><span class="tocnumber">5.1.2</span> <span class="toctext">Java</span></a></li>
+<li class="toclevel-3 tocsection-9"><a href="#Perl"><span class="tocnumber">5.1.3</span> <span class="toctext">Perl</span></a></li>
+<li class="toclevel-3 tocsection-10"><a href="#Python"><span class="tocnumber">5.1.4</span> <span class="toctext">Python</span></a></li>
+</ul>
+</li>
+<li class="toclevel-2 tocsection-11"><a href="#Resources"><span class="tocnumber">5.2</span> <span class="toctext">Resources</span></a></li>
+</ul>
+</li>
+</ul>
+</td>
+</tr>
+</table>
+<script type="text/javascript">
+//<![CDATA[
+if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } 
+//]]>
+</script>
+<h2><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=1" title="Edit section: The algorithm">edit</a>]</span> <span class="mw-headline" id="The_algorithm">The algorithm</span></h2>
+<p>In the following descriptions, α, β, and γ represent any <a href="/wiki/String_(computer_science)" title="String (computer science)">string</a> of <a href="/wiki/Terminal_and_nonterminal_symbols" title="Terminal and nonterminal symbols">terminals/nonterminals</a> (including the <a href="/wiki/Empty_string" title="Empty string">empty string</a>), X and Y represent single nonterminals, and <i>a</i> represents a terminal symbol.</p>
+<p>Earley's algorithm is a top-down <a href="/wiki/Dynamic_programming" title="Dynamic programming">dynamic programming</a> algorithm. In the following, we use Earley's dot notation: given a production X → αβ, the notation X → α • β represents a condition in which α has already been parsed and β is expected.</p>
+<p>For every input position (which represents a position <i>between</i> <a href="/wiki/Lexical_analysis" title="Lexical analysis">tokens</a>), the parser generates an ordered <i>state set</i>. Each state is a <a href="/wiki/Tuple" title="Tuple">tuple</a> (X → α • β, <i>i</i>), consisting of</p>
+<ul>
+<li>the production currently being matched (X → α β)</li>
+<li>our current position in that production (represented by the dot)</li>
+<li>the position <i>i</i> in the input at which the matching of this production began: the <i>origin position</i></li>
+</ul>
+<p>(Earley's original algorithm included a look-ahead in the state; later research showed this to have little practical effect on the parsing efficiency, and it has subsequently been dropped from most implementations.)</p>
+<p>The state set at input position <i>k</i> is called S(<i>k</i>). The parser is seeded with S(0) consisting of only the top-level rule. The parser then iteratively operates in three stages: <i>prediction</i>, <i>scanning</i>, and <i>completion</i>.</p>
+<ul>
+<li><b>Prediction</b>: For every state in S(<i>k</i>) of the form (X → α • Y β, <i>j</i>) (where <i>j</i> is the origin position as above), add (Y → • γ, <i>k</i>) to S(<i>k</i>) for every production in the grammar with Y on the left-hand side (Y → γ).</li>
+</ul>
+<ul>
+<li><b>Scanning</b>: If <i>a</i> is the next symbol in the input stream, for every state in S(<i>k</i>) of the form (X → α • <i>a</i> β, <i>j</i>), add (X → α <i>a</i> • β, <i>j</i>) to S(<i>k</i>+1).</li>
+</ul>
+<ul>
+<li><b>Completion</b>: For every state in S(<i>k</i>) of the form (X → γ •, <i>j</i>), find states in S(<i>j</i>) of the form (Y → α • X β, <i>i</i>) and add (Y → α X • β, <i>i</i>) to S(<i>k</i>).</li>
+</ul>
+<p>These steps are repeated until no more states can be added to the set. The set is generally implemented as a queue of states to process (though a given state must appear in one place only), and performing the corresponding operation depending on what kind of state it is.</p>
+<h2><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=2" title="Edit section: Example">edit</a>]</span> <span class="mw-headline" id="Example">Example</span></h2>
+<p>Consider the following simple grammar for arithmetic expressions:</p>
+<pre>
+ P → S      # the start rule
+ S → S + M
+    | M
+ M → M * T
+    | T
+ T → number
+</pre>
+<p>With the input:</p>
+<pre>
+ 2 + 3 * 4
+</pre>
+<p>This is the sequence of state sets:</p>
+<pre>
+ (state no.) Production          (Origin) # Comment
+ ---------------------------------
+ == S(0): • 2 + 3 * 4 ==
+ (1)  P → • S         (0)    # start rule
+ (2)  S → • S + M     (0)    # predict from (1)
+ (3)  S → • M         (0)    # predict from (1)
+ (4)  M → • M * T     (0)    # predict from (3)
+ (5)  M → • T         (0)    # predict from (3)
+ (6)  T → • number    (0)    # predict from (5)
+ 
+ == S(1): 2 • + 3 * 4 ==
+ (1)  T → number •    (0)    # scan from S(0)(6)
+ (2)  M → T •         (0)    # complete from S(0)(5)
+ (3)  M → M • * T     (0)    # complete from S(0)(4)
+ (4)  S → M •         (0)    # complete from S(0)(3)
+ (5)  S → S • + M     (0)    # complete from S(0)(2)
+ (6)  P → S •         (0)    # complete from S(0)(1)
+ 
+ == S(2): 2 + • 3 * 4 ==
+ (1)  S → S + • M     (0)    # scan from S(1)(5)
+ (2)  M → • M * T     (2)    # predict from (1)
+ (3)  M → • T         (2)    # predict from (1)
+ (4)  T → • number    (2)    # predict from (3)
+ 
+ == S(3): 2 + 3 • * 4 ==
+ (1)  T → number •    (2)    # scan from S(2)(4)
+ (2)  M → T •         (2)    # complete from S(2)(3)
+ (3)  M → M • * T     (2)    # complete from S(2)(2)
+ (4)  S → S + M •     (0)    # complete from S(2)(1)
+ (5)  S → S • + M     (0)    # complete from S(0)(2)
+ (6)  P → S •         (0)    # complete from S(0)(1)
+ 
+ == S(4): 2 + 3 * • 4 ==
+ (1)  M → M * • T     (2)    # scan from S(3)(3)
+ (2)  T → • number    (4)    # predict from (1)
+ 
+ == S(5): 2 + 3 * 4 • ==
+ (1)  T → number •    (4)    # scan from S(4)(2)
+ (2)  M → M * T •     (2)    # complete from S(4)(1)
+ (3)  M → M • * T     (2)    # complete from S(2)(2)
+ (4)  S → S + M •     (0)    # complete from S(2)(1)
+ (5)  S → S • + M     (0)    # complete from S(0)(2)
+ (6)  P → S •         (0)    # complete from S(0)(1)
+</pre>
+<p>The state (P → S •, 0) represents a completed parse. This state also appears in S(3) and S(1), which are complete sentences.</p>
+<h2><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=3" title="Edit section: See also">edit</a>]</span> <span class="mw-headline" id="See_also">See also</span></h2>
+<ul>
+<li><a href="/wiki/CYK_algorithm" title="CYK algorithm">CYK algorithm</a></li>
+<li><a href="/wiki/Context-free_grammar" title="Context-free grammar">Context-free grammar</a></li>
+<li><a href="/wiki/List_of_algorithms#Parsing" title="List of algorithms">Parsing Algorithms</a></li>
+</ul>
+<h2><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=4" title="Edit section: References">edit</a>]</span> <span class="mw-headline" id="References">References</span></h2>
+<ul>
+<li>J. Earley, <a href="http://portal.acm.org/citation.cfm?doid=362007.362035" class="external text" rel="nofollow">"An efficient context-free parsing algorithm"</a>, <i>Communications of the Association for Computing Machinery</i>, <b>13</b>:2:94-102, 1970.</li>
+</ul>
+<ul>
+<li>J. Aycock and R.N. Horspool. <a href="http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf" class="external text" rel="nofollow">Practical Earley Parsing</a>. <i>The Computer Journal</i>, <b>45</b>:6:620-630, 2002.</li>
+</ul>
+<h2><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=5" title="Edit section: External links">edit</a>]</span> <span class="mw-headline" id="External_links">External links</span></h2>
+<h3><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=6" title="Edit section: Implementations">edit</a>]</span> <span class="mw-headline" id="Implementations">Implementations</span></h3>
+<h4><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=7" title="Edit section: C">edit</a>]</span> <span class="mw-headline" id="C">C</span></h4>
+<ul>
+<li><a href="http://cocom.sourceforge.net/ammunition-13.html" class="external text" rel="nofollow">'early'</a> An Earley parser <a href="/wiki/C_(programming_language)" title="C (programming language)">C</a> -library.</li>
+<li><a href="https://bitbucket.org/abki/c-earley-parser/src" class="external text" rel="nofollow">'C Earley Parser'</a> An Earley parser <a href="/wiki/C_(programming_language)" title="C (programming language)">C</a>.</li>
+</ul>
+<h4><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=8" title="Edit section: Java">edit</a>]</span> <span class="mw-headline" id="Java">Java</span></h4>
+<ul>
+<li><a href="http://linguateca.dei.uc.pt/index.php?sep=recursos" class="external text" rel="nofollow">PEN</a> A Java library that implements the Earley.</li>
+<li><a href="http://www.ling.ohio-state.edu/~scott/#projects-pep" class="external text" rel="nofollow">Pep</a> A Java library that implements the Earley algorithm and provides charts and parse trees as parsing artifacts.</li>
+</ul>
+<h4><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=9" title="Edit section: Perl">edit</a>]</span> <span class="mw-headline" id="Perl">Perl</span></h4>
+<ul>
+<li><a href="http://search.cpan.org/dist/Marpa/" class="external text" rel="nofollow">Marpa</a> A <a href="/wiki/Perl" title="Perl">Perl</a> module, incorporating improvements made to the Earley algorithm by Joop Leo, and by Aycock and Horspool.</li>
+<li><a href="http://search.cpan.org/~lpalmer/Parse-Earley-0.15/Earley.pm" class="external text" rel="nofollow">Parse::Earley</a> An <a href="/wiki/Perl" title="Perl">Perl</a> module that implements Jay Earley's original algorithm.</li>
+</ul>
+<h4><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=10" title="Edit section: Python">edit</a>]</span> <span class="mw-headline" id="Python">Python</span></h4>
+<ul>
+<li><a href="http://nltk.sourceforge.net/" class="external text" rel="nofollow">NLTK</a> a <a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a> toolkit that has an Earley parser.</li>
+<li><a href="http://pages.cpsc.ucalgary.ca/~aycock/spark/" class="external text" rel="nofollow">Spark</a> an Object Oriented "little language framework" for <a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a> that implements an Earley parser.</li>
+</ul>
+<h3><span class="editsection">[<a href="/w/index.php?title=Earley_parser&amp;action=edit&amp;section=11" title="Edit section: Resources">edit</a>]</span> <span class="mw-headline" id="Resources">Resources</span></h3>
+<ul>
+<li><a href="http://accent.compilertools.net/Entire.html" class="external text" rel="nofollow">The Accent compiler-compiler</a></li>
+</ul>
+<p><span id="interwiki-pl-fa"></span></p>
+
+
+<!-- 
+NewPP limit report
+Preprocessor node count: 48/1000000
+Post-expand include size: 34/2048000 bytes
+Template argument size: 2/2048000 bytes
+Expensive parser function count: 0/500
+-->
+
+<!-- Saved in parser cache with key enwiki:pcache:idhash:9685-0!1!0!default!!en!4 and timestamp 20101114134011 -->
+<div class="printfooter">
+Retrieved from "<a href="http://en.wikipedia.org/wiki/Earley_parser">http://en.wikipedia.org/wiki/Earley_parser</a>"</div>
+				<!-- /bodytext -->
+								<!-- catlinks -->
+				<div id='catlinks' class='catlinks'><div id="mw-normal-catlinks"><a href="/wiki/Special:Categories" title="Special:Categories">Categories</a>: <span dir='ltr'><a href="/wiki/Category:Parsing_algorithms" title="Category:Parsing algorithms">Parsing algorithms</a></span> | <span dir='ltr'><a href="/wiki/Category:Dynamic_programming" title="Category:Dynamic programming">Dynamic programming</a></span></div></div>				<!-- /catlinks -->
+												<div class="visualClear"></div>
+			</div>
+			<!-- /bodyContent -->
+		</div>
+		<!-- /content -->
+		<!-- header -->
+		<div id="mw-head" class="noprint">
+			
+<!-- 0 -->
+<div id="p-personal" class="">
+	<h5>Personal tools</h5>
+	<ul>
+					<li  id="pt-prefswitch-link-anon"><a href="http://en.wikipedia.org/w/index.php?title=Special:UsabilityInitiativePrefSwitch&amp;from=Earley_parser" title="Learn about new features" class="no-text-transform">New features</a></li>
+					<li  id="pt-login"><a href="/w/index.php?title=Special:UserLogin&amp;returnto=Earley_parser" title="You are encouraged to log in; however, it is not mandatory. [o]" accesskey="o">Log in / create account</a></li>
+			</ul>
+</div>
+
+<!-- /0 -->
+			<div id="left-navigation">
+				
+<!-- 0 -->
+<div id="p-namespaces" class="vectorTabs">
+	<h5>Namespaces</h5>
+	<ul>
+					<li  id="ca-nstab-main" class="selected"><a href="/wiki/Earley_parser"  title="View the content page [c]" accesskey="c"><span>Article</span></a></li>
+					<li  id="ca-talk"><a href="/wiki/Talk:Earley_parser"  title="Discussion about the content page [t]" accesskey="t"><span>Discussion</span></a></li>
+			</ul>
+</div>
+
+<!-- /0 -->
+
+<!-- 1 -->
+<div id="p-variants" class="vectorMenu emptyPortlet">
+		<h5><span>Variants</span><a href="#"></a></h5>
+	<div class="menu">
+		<ul>
+					</ul>
+	</div>
+</div>
+
+<!-- /1 -->
+			</div>
+			<div id="right-navigation">
+				
+<!-- 0 -->
+<div id="p-views" class="vectorTabs">
+	<h5>Views</h5>
+	<ul>
+					<li id="ca-view" class="selected"><a href="/wiki/Earley_parser" ><span>Read</span></a></li>
+					<li id="ca-edit"><a href="/w/index.php?title=Earley_parser&amp;action=edit"  title="You can edit this page. &#10;Please use the preview button before saving. [e]" accesskey="e"><span>Edit</span></a></li>
+					<li id="ca-history" class="collapsible "><a href="/w/index.php?title=Earley_parser&amp;action=history"  title="Past versions of this page [h]" accesskey="h"><span>View history</span></a></li>
+			</ul>
+</div>
+
+<!-- /0 -->
+
+<!-- 1 -->
+<div id="p-cactions" class="vectorMenu emptyPortlet">
+	<h5><span>Actions</span><a href="#"></a></h5>
+	<div class="menu">
+		<ul>
+					</ul>
+	</div>
+</div>
+
+<!-- /1 -->
+
+<!-- 2 -->
+<div id="p-search">
+	<h5><label for="searchInput">Search</label></h5>
+	<form action="/w/index.php" id="searchform">
+		<input type='hidden' name="title" value="Special:Search"/>
+				<div id="simpleSearch">
+			<input id="searchInput" name="search" type="text"  title="Search Wikipedia [f]" accesskey="f"  value="" />
+			<button id="searchButton" type='submit' name='button'  title="Search Wikipedia for this text"><img src="http://bits.wikimedia.org/skins-1.5/vector/images/search-ltr.png?283-12" alt="Search" /></button>
+		</div>
+			</form>
+</div>
+
+<!-- /2 -->
+			</div>
+		</div>
+		<!-- /header -->
+		<!-- panel -->
+			<div id="mw-panel" class="noprint">
+				<!-- logo -->
+					<div id="p-logo"><a style="background-image: url(http://upload.wikimedia.org/wikipedia/commons/d/d6/Wikipedia-logo-v2-en.png);" href="/wiki/Main_Page"  title="Visit the main page"></a></div>
+				<!-- /logo -->
+				
+<!-- navigation -->
+<div class="portal" id='p-navigation'>
+	<h5>Navigation</h5>
+	<div class="body">
+				<ul>
+					<li id="n-mainpage-description"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z">Main page</a></li>
+					<li id="n-contents"><a href="/wiki/Portal:Contents" title="Guides to browsing Wikipedia">Contents</a></li>
+					<li id="n-featuredcontent"><a href="/wiki/Portal:Featured_content" title="Featured content — the best of Wikipedia">Featured content</a></li>
+					<li id="n-currentevents"><a href="/wiki/Portal:Current_events" title="Find background information on current events">Current events</a></li>
+					<li id="n-randompage"><a href="/wiki/Special:Random" title="Load a random article [x]" accesskey="x">Random article</a></li>
+					<li id="n-variablepage" class="active" ><a href="/w/index.php?title=Special:VariablePage&amp;utm_source=donate&amp;utm_medium=sidebar&amp;utm_campaign=spontaneous_donation">Donate</a></li>
+				</ul>
+			</div>
+</div>
+
+<!-- /navigation -->
+
+<!-- SEARCH -->
+
+<!-- /SEARCH -->
+
+<!-- interaction -->
+<div class="portal" id='p-interaction'>
+	<h5>Interaction</h5>
+	<div class="body">
+				<ul>
+					<li id="n-help"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia">Help</a></li>
+					<li id="n-aboutsite"><a href="/wiki/Wikipedia:About" title="Find out about Wikipedia">About Wikipedia</a></li>
+					<li id="n-portal"><a href="/wiki/Wikipedia:Community_portal" title="About the project, what you can do, where to find things">Community portal</a></li>
+					<li id="n-recentchanges"><a href="/wiki/Special:RecentChanges" title="The list of recent changes in the wiki [r]" accesskey="r">Recent changes</a></li>
+					<li id="n-contact"><a href="/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia">Contact Wikipedia</a></li>
+				</ul>
+			</div>
+</div>
+
+<!-- /interaction -->
+
+<!-- TOOLBOX -->
+<div class="portal" id="p-tb">
+	<h5>Toolbox</h5>
+	<div class="body">
+		<ul>
+					<li id="t-whatlinkshere"><a href="/wiki/Special:WhatLinksHere/Earley_parser" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j">What links here</a></li>
+						<li id="t-recentchangeslinked"><a href="/wiki/Special:RecentChangesLinked/Earley_parser" title="Recent changes in pages linked from this page [k]" accesskey="k">Related changes</a></li>
+																																					<li id="t-upload"><a href="/wiki/Wikipedia:Upload" title="Upload files [u]" accesskey="u">Upload file</a></li>
+											<li id="t-specialpages"><a href="/wiki/Special:SpecialPages" title="List of all special pages [q]" accesskey="q">Special pages</a></li>
+											<li id="t-permalink"><a href="/w/index.php?title=Earley_parser&amp;oldid=396700343" title="Permanent link to this revision of the page">Permanent link</a></li>
+				<li id="t-cite"><a href="/w/index.php?title=Special:Cite&amp;page=Earley_parser&amp;id=396700343" title="Information on how to cite this page">Cite this page</a></li>		</ul>
+	</div>
+</div>
+
+<!-- /TOOLBOX -->
+
+<!-- coll-print_export -->
+<div class="portal" id='p-coll-print_export'>
+	<h5>Print/export</h5>
+	<div class="body">
+				<ul id="collectionPortletList"><li id="coll-create_a_book"><a href="/w/index.php?title=Special:Book&amp;bookcmd=book_creator&amp;referer=Earley+parser" title="Create a book or page collection" rel="nofollow">Create a book</a></li><li id="coll-download-as-rl"><a href="/w/index.php?title=Special:Book&amp;bookcmd=render_article&amp;arttitle=Earley+parser&amp;oldid=396700343&amp;writer=rl" title="Download a PDF version of this wiki page" rel="nofollow">Download as PDF</a></li><li id="t-print"><a href="/w/index.php?title=Earley_parser&amp;printable=yes" title="Printable version of this page [p]" accesskey="p">Printable version</a></li></ul>			</div>
+</div>
+
+<!-- /coll-print_export -->
+
+<!-- LANGUAGES -->
+<div class="portal" id="p-lang">
+	<h5>Languages</h5>
+	<div class="body">
+		<ul>
+					<li class="interwiki-bg"><a href="http://bg.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%BD%D0%B0_%D0%95%D1%80%D0%BB%D0%B8" title="Алгоритъм на Ерли">Български</a></li>
+					<li class="interwiki-de"><a href="http://de.wikipedia.org/wiki/Earley-Algorithmus" title="Earley-Algorithmus">Deutsch</a></li>
+					<li class="interwiki-es"><a href="http://es.wikipedia.org/wiki/Algoritmo_de_Earley" title="Algoritmo de Earley">Español</a></li>
+					<li class="interwiki-fr"><a href="http://fr.wikipedia.org/wiki/Analyse_Earley" title="Analyse Earley">Français</a></li>
+					<li class="interwiki-ja"><a href="http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%BC%E3%83%AA%E3%83%BC%E6%B3%95" title="アーリー法">日本語</a></li>
+					<li class="interwiki-pl"><a href="http://pl.wikipedia.org/wiki/Algorytm_Earleya" title="Algorytm Earleya">Polski</a></li>
+					<li class="interwiki-pt"><a href="http://pt.wikipedia.org/wiki/Algoritmo_Earley" title="Algoritmo Earley">Português</a></li>
+					<li class="interwiki-ru"><a href="http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D1%80%D0%BB%D0%B8" title="Алгоритм Эрли">Русский</a></li>
+					<li class="interwiki-sr"><a href="http://sr.wikipedia.org/wiki/Erlijev_analizator" title="Erlijev analizator">Српски / Srpski</a></li>
+					<li class="interwiki-uk"><a href="http://uk.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D1%80%D0%BB%D1%96" title="Алгоритм Ерлі">Українська</a></li>
+				</ul>
+	</div>
+</div>
+
+<!-- /LANGUAGES -->
+			</div>
+		<!-- /panel -->
+		<!-- footer -->
+		<div id="footer">
+											<ul id="footer-info">
+																	<li id="footer-info-lastmod"> This page was last modified on 14 November 2010 at 13:40.<br /></li>
+																							<li id="footer-info-copyright">Text is available under the <a rel="license" href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License">Creative Commons Attribution-ShareAlike License</a><a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/" style="display:none;"></a>;
+additional terms may apply.
+See <a href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</a> for details.<br/>
+Wikipedia&reg; is a registered trademark of the <a href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.<br /></li><li class="noprint"><a class='internal' href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</a></li>
+															</ul>
+															<ul id="footer-places">
+																	<li id="footer-places-privacy"><a href="http://wikimediafoundation.org/wiki/Privacy_policy" title="wikimedia:Privacy policy">Privacy policy</a></li>
+																							<li id="footer-places-about"><a href="/wiki/Wikipedia:About" title="Wikipedia:About">About Wikipedia</a></li>
+																							<li id="footer-places-disclaimer"><a href="/wiki/Wikipedia:General_disclaimer" title="Wikipedia:General disclaimer">Disclaimers</a></li>
+															</ul>
+										<ul id="footer-icons" class="noprint">
+								<li id="footer-icon-poweredby"><a href="http://www.mediawiki.org/"><img src="http://bits.wikimedia.org/skins-1.5/common/images/poweredby_mediawiki_88x31.png" height="31" width="88" alt="Powered by MediaWiki" /></a></li>
+												<li id="footer-icon-copyright"><a href="http://wikimediafoundation.org/"><img src="/images/wikimedia-button.png" width="88" height="31" alt="Wikimedia Foundation"/></a></li>
+							</ul>
+			<div style="clear:both"></div>
+		</div>
+		<!-- /footer -->
+		<!-- fixalpha -->
+		<script type="text/javascript"> if ( window.isMSIE55 ) fixalpha(); </script>
+		<!-- /fixalpha -->
+		
+<script type="text/javascript">if (window.runOnloadHook) runOnloadHook();</script>
+<script type="text/javascript" src="http://geoiplookup.wikimedia.org/"></script>		<!-- Served by srv183 in 0.060 secs. -->			</body>
+</html>