markup-parse 0.0.0.2 → 0.1.0.0

raw patch · 13 files changed

+1881/−293 lines, 13 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• ChangeLog.md +4/−0
• app/diff.hs +12/−12
• app/speed.hs +16/−16
• markup-parse.cabal +12/−7
• other/Parsing - Wikipedia.html +1083/−0
• other/ex1.html +10/−0
• other/line.svg +43/−0
• other/line_.html +48/−0
• other/line_.svg +52/−0
• readme.org +192/−0
• src/MarkupParse.hs +386/−251
• src/MarkupParse/FlatParse.hs +14/−4
• src/MarkupParse/Patch.hs +9/−3

@@ -0,0 +1,4 @@+0.0.0+===++Initial split away from chart-svg

@@ -4,8 +4,9 @@  module Main (main) where +import Control.Monad import Data.ByteString (ByteString)-import Data.ByteString qualified as BS+import Data.ByteString qualified as B import Data.Foldable import Data.Function import Data.Maybe@@ -30,29 +31,28 @@   testGroup     "examples"     ( testExample-        <$> [ (Xml, "other/line.svg"),-              (Html, "other/ex1.html"),-              (Html, "other/Parsing - Wikipedia.html")+        <$> [ (Compact, Xml, "other/line.svg"),+              (Compact, Html, "other/ex1.html")             ]     ) -testExample :: (Standard, FilePath) -> TestTree-testExample (s, fp) =+testExample :: (RenderStyle, Standard, FilePath) -> TestTree+testExample (r, s, fp) =   goldenTest     fp     (getMarkupFile s fp)-    (isoMarkdownMarkup s <$> getMarkupFile s fp)+    (isoMarkdownMarkup r s <$> getMarkupFile s fp)     (\expected actual -> pure (show . ansiWlEditExpr <$> patch expected actual))     (\_ -> pure ())  getMarkupFile :: Standard -> FilePath -> IO Markup getMarkupFile s fp = do-  bs <- BS.readFile fp-  pure $ resultError $ markup s bs+  bs <- B.readFile fp+  pure $ warnError $ markup s bs  -- round trip markdown >>> markup-isoMarkdownMarkup :: Standard -> Markup -> Markup-isoMarkdownMarkup s m = m & markdown Compact & markup s & resultError+isoMarkdownMarkup :: RenderStyle -> Standard -> Markup -> Markup+isoMarkdownMarkup r s m = m & (markdown r s >=> markup s) & warnError  -- patch testing printPatchExamples :: IO ()@@ -61,7 +61,7 @@ printPatchExample :: ByteString -> (String, ByteString) -> IO () printPatchExample m (s, m') = do   print s-  case show . ansiWlEditExpr <$> patch (resultError $ markup Html m) (resultError $ markup Html m') of+  case show . ansiWlEditExpr <$> patch (warnError $ markup Html m) (warnError $ markup Html m') of     Nothing -> putStrLn ("no changes" :: String)     Just x -> putStrLn x 

@@ -11,7 +11,7 @@ import FlatParse.Basic qualified as FP import MarkupParse import MarkupParse.FlatParse-import Options.Applicative+import Options.Applicative as OA import Perf import Text.HTML.Parser qualified as HP import Text.HTML.Tree qualified as HP@@ -27,7 +27,7 @@   }   deriving (Eq, Show) -parseRun :: Parser RunType+parseRun :: OA.Parser RunType parseRun =   flag' RunDefault (long "default" <> help "run default performance test")     <|> flag' RunMarkup (long "markup" <> short 'm' <> help "run markup performance test")@@ -38,7 +38,7 @@     <|> flag' RunIsa (long "isa" <> help "test isa")     <|> pure RunDefault -speedOptions :: Parser SpeedOptions+speedOptions :: OA.Parser SpeedOptions speedOptions =   SpeedOptions     <$> parseReportOptions@@ -69,21 +69,21 @@         ts' <- ffap "html-parse tokens" HP.parseTokens t         _ <- ffap "html-parse tree" (either undefined id . HP.tokensToForest) ts'         tsHtml <--          resultError+          warnError             <$> ffap "tokenize" (tokenize Xml) bs         _ <--          resultError+          warnError             <$> ffap "gather" (gather Xml) tsHtml         m <--          resultError+          warnError             <$> ffap "markup" (markup Xml) bs         _ <- ffap "normalize" normalize m-        _ <- ffap "markdown" (markdown Compact) m+        _ <- ffap "markdown" (markdown Compact Xml) m         pure ()     RunMarkup -> do       bs <- B.readFile f       reportMainWith rep (show r) $ do-        fap "markup" (length . markupTree . markup_ Xml) bs+        fap "markup" (length . elements . markup_ Xml) bs     RunWhitespace -> do       reportMainWith rep (show r) (wsFap " \n\nx")     RunWrappedQ -> do@@ -102,10 +102,10 @@         _ <- ffap "html-parse tokens" (length . HP.parseTokens) t         _ <- ffap "html-parse tree" (either undefined length . HP.tokensToForest) ts'         _ <- ffap "tokenize" (length . tokenize Xml) bs-        _ <- ffap "gather" (length . gather_ Xml) ts-        _ <- ffap "markup" (length . markupTree . markup_ Xml) bs+        _ <- ffap "gather" (length . elements . gather_ Xml) ts+        _ <- ffap "markup" (length . elements . markup_ Xml) bs         _ <- ffap "normalize" normalize m-        _ <- ffap "markdown" (markdown Compact) m+        _ <- ffap "markdown" (markdown Compact Xml) m         pure ()  -- | Consume whitespace.@@ -158,13 +158,13 @@ fapIsa :: PerfT IO [[Double]] () fapIsa = do   fap "isa isAttrName" (FP.runParser (isa isAttrName)) "name"-  fap "attrName" (FP.runParser attrName) "name"+  fap "attrNameP" (FP.runParser attrNameP) "name"   pure ()  fapBSOf :: PerfT IO [[Double]] () fapBSOf = do-  fap "byteStringOf" (FP.runParser (byteStringOf (attrs Html))) " a=\"a\" b=b c>"-  fap "byteStringOf'" (FP.runParser (byteStringOf (attrs Html))) " a=\"a\" b=b c>"+  fap "byteStringOf" (FP.runParser (byteStringOf (attrsP Html))) " a=\"a\" b=b c>"+  fap "byteStringOf'" (FP.runParser (byteStringOf' (attrsP Html))) " a=\"a\" b=b c>"   pure ()  isAttrName :: Char -> Bool@@ -175,8 +175,8 @@       || (x == '>')       || (x == '=') -attrName :: FP.Parser e B.ByteString-attrName = byteStringOf $ some (satisfy isAttrName)+attrNameP :: FP.Parser e B.ByteString+attrNameP = byteStringOf $ some (satisfy isAttrName)  wrappedQSatisfy :: FP.Parser e B.ByteString wrappedQSatisfy =

@@ -1,6 +1,6 @@ cabal-version: 3.0 name: markup-parse-version: 0.0.0.2+version: 0.1.0.0 license: BSD-3-Clause license-file: LICENSE copyright: Copyright, Tony Day, 2023-@@ -14,6 +14,11 @@     A markup parser and printer, from and to strict bytestrings, optimised for speed. build-type: Simple tested-with: GHC == 9.6.2+extra-doc-files:+    ChangeLog.md+    other/*.html+    other/*.svg+    readme.org  source-repository head     type: git@@ -117,13 +122,13 @@     main-is: diff.hs     hs-source-dirs: app     build-depends:-        , base                 >=4.7 && <5-        , bytestring           >=0.11.3 && <0.13+        , base               >=4.7 && <5+        , bytestring         >=0.11.3 && <0.13         , markup-parse-        , string-interpolate   >=0.3 && <0.4-        , tasty                >=1.2 && <1.5-        , tasty-golden         >=2.3.1.1 && <2.4-        , tree-diff            >=0.3 && <0.4+        , string-interpolate >=0.3 && <0.4+        , tasty              >=1.2 && <1.5+        , tasty-golden       >=2.3.1.1 && <2.4+        , tree-diff          >=0.3 && <0.4     type: exitcode-stdio-1.0  benchmark markup-parse-speed

@@ -0,0 +1,1083 @@+<!DOCTYPE html>+<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-enabled vector-feature-main-menu-pinned-disabled vector-feature-limited-width-enabled vector-feature-limited-width-content-enabled vector-feature-zebra-design-disabled" lang="en" dir="ltr">+<head>+<meta charset="UTF-8">+<title>Parsing - Wikipedia</title>+<script>document.documentElement.className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-enabled vector-feature-main-menu-pinned-disabled vector-feature-limited-width-enabled vector-feature-limited-width-content-enabled vector-feature-zebra-design-disabled";(function(){var cookie=document.cookie.match(/(?:^|; )enwikimwclientprefs=([^;]+)/);if(cookie){var featureName=cookie[1];document.documentElement.className=document.documentElement.className.replace(featureName+'-enabled',featureName+'-disabled');}}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"525907c7-2c1d-4c90-bb29-5cb035efc514","wgCSPNonce":false,+"wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Parsing","wgTitle":"Parsing","wgCurRevisionId":1169191759,"wgRevisionId":1169191759,"wgArticleId":310015,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: multiple names: authors list","Articles with short description","Short description is different from Wikidata","All articles with unsourced statements","Articles with unsourced statements from August 2019","Articles with unsourced statements from August 2021","Articles needing additional references from February 2013","All articles needing additional references","Articles with unsourced statements from February 2018","Articles with unsourced statements from May 2008","Articles with unsourced statements from January 2019","Articles needing cleanup from January 2017","All pages needing cleanup",+"Articles with sections that need to be turned into prose from January 2017","Articles needing additional references from April 2012","Articles with unsourced statements from December 2008","Wikipedia articles needing clarification from April 2019","All accuracy disputes","Articles with disputed statements from April 2019","All Wikipedia articles needing clarification","Articles with unsourced statements from April 2011","Parsing","Algorithms on strings","Compiler construction"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Parsing","wgRelevantArticleId":310015,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},+"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgNoticeProject":"wikipedia","wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":10,"wgULSCurrentAutonym":"English","wgEditSubmitButtonLabelPublish":true,"wgCentralAuthMobileDomain":false,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q194152","GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"skins.vector.user.styles":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","skins.vector.user":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.pygments":"ready","codex-search-styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready",+"ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.wikimediaBadges":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","mmv.head","mmv.bootstrap.autostart","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.cx.eventlogging.campaigns","ext.quicksurveys.init","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.charinsert","ext.gadget.extra-toolbar-buttons","ext.gadget.switcher","ext.centralauth.centralautologin","ext.popups","ext.echo.centralauth","ext.uls.compactlinks","ext.uls.interface","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.growthExperiments.SuggestedEditSession"];</script>+<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.implement("user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"});});});</script>+<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=codex-search-styles%7Cext.cite.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cwikibase.client.init&amp;only=styles&amp;skin=vector-2022">+<script async="" src="/w/load.php?lang=en&amp;modules=startup&amp;only=scripts&amp;raw=1&amp;skin=vector-2022"></script>+<meta name="ResourceLoaderDynamicStyles" content="">+<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=site.styles&amp;only=styles&amp;skin=vector-2022">+<meta name="generator" content="MediaWiki 1.41.0-wmf.20">+<meta name="referrer" content="origin">+<meta name="referrer" content="origin-when-crossorigin">+<meta name="referrer" content="origin-when-cross-origin">+<meta name="robots" content="max-image-preview:standard">+<meta name="format-detection" content="telephone=no">+<meta name="viewport" content="width=1000">+<meta property="og:title" content="Parsing - Wikipedia">+<meta property="og:type" content="website">+<link rel="preconnect" href="//upload.wikimedia.org">+<link rel="alternate" media="only screen and (max-width: 720px)" href="//en.m.wikipedia.org/wiki/Parsing">+<link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Parsing&amp;action=edit">+<link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png">+<link rel="icon" href="/static/favicon/wikipedia.ico">+<link rel="search" type="application/opensearchdescription+xml" href="/w/opensearch_desc.php" title="Wikipedia (en)">+<link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd">+<link rel="canonical" href="https://en.wikipedia.org/wiki/Parsing">+<link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">+<link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&amp;feed=atom">+<link rel="dns-prefetch" href="//meta.wikimedia.org" />+<link rel="dns-prefetch" href="//login.wikimedia.org">+</head>+<body class="skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Parsing rootpage-Parsing skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a>+<div class="vector-header-container">+	<header class="vector-header mw-header">+		<div class="vector-header-start">+			<nav class="vector-main-menu-landmark" aria-label="Site" role="navigation">+				+<div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right"  >+	<input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox "  aria-label="Main menu"  >+	<label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true"  ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span>++<span class="vector-dropdown-label-text">Main menu</span>+	</label>+	<div class="vector-dropdown-content">+++				<div id="vector-main-menu-unpinned-container" class="vector-unpinned-container">+		+<div id="vector-main-menu" class="vector-main-menu vector-pinnable-element">+	<div+	class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned"+	data-feature-name="main-menu-pinned"+	data-pinnable-element-id="vector-main-menu"+	data-pinned-container-id="vector-main-menu-pinned-container"+	data-unpinned-container-id="vector-main-menu-unpinned-container"+>+	<div class="vector-pinnable-header-label">Main menu</div>+	<button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button>+	<button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button>+</div>++	+<div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation"  >+	<div class="vector-menu-heading">+		Navigation+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li><li id="n-sitesupport" class="mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&amp;utm_medium=sidebar&amp;utm_campaign=C13_en.wikipedia.org&amp;uselang=en" title="Support us by donating to the Wikimedia Foundation"><span>Donate</span></a></li>+		</ul>+		+	</div>+</div>++	+	+<div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction"  >+	<div class="vector-menu-heading">+		Contribute+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li>+		</ul>+		+	</div>+</div>++	+<div class="vector-main-menu-action vector-main-menu-action-lang-alert">+	<div class="vector-main-menu-action-item">+		<div class="vector-main-menu-action-heading vector-menu-heading">Languages</div>+		<div class="vector-main-menu-action-content vector-menu-content">+			<div class="mw-message-box cdx-message cdx-message--block mw-message-box-notice cdx-message--notice vector-language-sidebar-alert"><span class="cdx-message__icon"></span><div class="cdx-message__content">Language links are at the top of the page across from the title.</div></div>+		</div>+	</div>+</div>++</div>++				</div>++	</div>+</div>++		</nav>+			+<a href="/wiki/Main_Page" class="mw-logo">+	<img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50">+	<span class="mw-logo-container">+		<img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;">+		<img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;">+	</span>+</a>++		</div>+		<div class="vector-header-end">+			+<div id="p-search" role="search" class="vector-search-box-vue  vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box">+	<a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" id="" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span>++<span>Search</span>+	</a>+	<div class="vector-typeahead-search-container">+		<div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width">+			<form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button">+				<div id="simpleSearch" class="cdx-search-input__input-wrapper"  data-search-loc="header-moved">+					<div class="cdx-text-input cdx-text-input--has-start-icon">+						<input+							class="cdx-text-input__input"+							 type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput"+							>+						<span class="cdx-text-input__icon cdx-text-input__start-icon"></span>+					</div>+					<input type="hidden" name="title" value="Special:Search">+				</div>+				<button class="cdx-button cdx-search-input__end-button">Search</button>+			</form>+		</div>+	</div>+</div>++			<nav class="vector-user-links" aria-label="Personal tools" role="navigation" >+	+<div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet mw-portlet-vector-user-menu-overflow"  >+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&amp;returnto=Parsing" title="You are encouraged to create an account and log in; however, it is not mandatory"><span>Create account</span></a></li><li id="pt-login-2" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&amp;returnto=Parsing" title="You&#039;re encouraged to log in; however, it&#039;s not mandatory. [o]" accesskey="o"><span>Log in</span></a></li>+		</ul>+		+	</div>+</div>++	+<div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out"  title="Log in and more options" >+	<input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox "  aria-label="Personal tools"  >+	<label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true"  ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span>++<span class="vector-dropdown-label-text">Personal tools</span>+	</label>+	<div class="vector-dropdown-content">+++		+<div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item"  title="User menu" >+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&amp;returnto=Parsing" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&amp;returnto=Parsing" title="You&#039;re encouraged to log in; however, it&#039;s not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li>+		</ul>+		+	</div>+</div>++<div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor"  >+	<div class="vector-menu-heading">+		Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a>+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li>+		</ul>+		+	</div>+</div>++	+	</div>+</div>++</nav>++		</div>+	</header>+</div>+<div class="mw-page-container">+	<div class="mw-page-container-inner">+		<div class="vector-main-menu-container ">+			<div id="mw-navigation">+				<nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site" role="navigation">+					<div id="vector-main-menu-pinned-container" class="vector-pinned-container">+				+					</div>+		</nav>+			</div>+		</div>+		<div class="vector-sitenotice-container">+			<div id="siteNotice"><!-- CentralNotice --></div>+		</div>+		<input type="checkbox" id="vector-toc-collapsed-checkbox" class="vector-menu-checkbox">+		<nav id="mw-panel-toc" role="navigation" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark vector-sticky-pinned-container">+			<div id="vector-toc-pinned-container" class="vector-pinned-container">+					<div id="vector-toc" class="vector-toc vector-pinnable-element">+	<div+	class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned"+	data-feature-name="toc-pinned"+	data-pinnable-element-id="vector-toc"+	+	+>+	<h2 class="vector-pinnable-header-label">Contents</h2>+	<button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button>+	<button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button>+</div>+++	<ul class="vector-toc-contents" id="mw-panel-toc-list">+		<li id="toc-mw-content-text"+			class="vector-toc-list-item vector-toc-level-1">+			<a href="#" class="vector-toc-link">+				<div class="vector-toc-text">(Top)</div>+			</a>+		</li>+		<li id="toc-Human_languages"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#Human_languages">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">1</span>Human languages</div>+		</a>+		+			<button aria-controls="toc-Human_languages-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle">+				<span class="vector-icon vector-icon--x-small mw-ui-icon-wikimedia-expand"></span>+				<span>Toggle Human languages subsection</span>+			</button>+		+		<ul id="toc-Human_languages-sublist" class="vector-toc-list">+			<li id="toc-Traditional_methods"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Traditional_methods">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">1.1</span>Traditional methods</div>+			</a>+			+			<ul id="toc-Traditional_methods-sublist" class="vector-toc-list">+			</ul>+		</li>+		<li id="toc-Computational_methods"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Computational_methods">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">1.2</span>Computational methods</div>+			</a>+			+			<ul id="toc-Computational_methods-sublist" class="vector-toc-list">+			</ul>+		</li>+		<li id="toc-Psycholinguistics"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Psycholinguistics">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">1.3</span>Psycholinguistics</div>+			</a>+			+			<ul id="toc-Psycholinguistics-sublist" class="vector-toc-list">+			</ul>+		</li>+		<li id="toc-Discourse_analysis"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Discourse_analysis">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">1.4</span>Discourse analysis</div>+			</a>+			+			<ul id="toc-Discourse_analysis-sublist" class="vector-toc-list">+			</ul>+		</li>+	</ul>+	</li>+	<li id="toc-Computer_languages"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#Computer_languages">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">2</span>Computer languages</div>+		</a>+		+			<button aria-controls="toc-Computer_languages-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle">+				<span class="vector-icon vector-icon--x-small mw-ui-icon-wikimedia-expand"></span>+				<span>Toggle Computer languages subsection</span>+			</button>+		+		<ul id="toc-Computer_languages-sublist" class="vector-toc-list">+			<li id="toc-Parser"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Parser">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">2.1</span>Parser</div>+			</a>+			+			<ul id="toc-Parser-sublist" class="vector-toc-list">+			</ul>+		</li>+		<li id="toc-Overview_of_process"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Overview_of_process">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">2.2</span>Overview of process</div>+			</a>+			+			<ul id="toc-Overview_of_process-sublist" class="vector-toc-list">+			</ul>+		</li>+	</ul>+	</li>+	<li id="toc-Types_of_parsers"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#Types_of_parsers">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">3</span>Types of parsers</div>+		</a>+		+			<button aria-controls="toc-Types_of_parsers-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle">+				<span class="vector-icon vector-icon--x-small mw-ui-icon-wikimedia-expand"></span>+				<span>Toggle Types of parsers subsection</span>+			</button>+		+		<ul id="toc-Types_of_parsers-sublist" class="vector-toc-list">+			<li id="toc-Implementation"+			class="vector-toc-list-item vector-toc-level-2">+			<a class="vector-toc-link" href="#Implementation">+				<div class="vector-toc-text">+				<span class="vector-toc-numb">3.1</span>Implementation</div>+			</a>+			+			<ul id="toc-Implementation-sublist" class="vector-toc-list">+			</ul>+		</li>+	</ul>+	</li>+	<li id="toc-Parser_development_software"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#Parser_development_software">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">4</span>Parser development software</div>+		</a>+		+		<ul id="toc-Parser_development_software-sublist" class="vector-toc-list">+		</ul>+	</li>+	<li id="toc-Lookahead"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#Lookahead">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">5</span>Lookahead</div>+		</a>+		+		<ul id="toc-Lookahead-sublist" class="vector-toc-list">+		</ul>+	</li>+	<li id="toc-See_also"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#See_also">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">6</span>See also</div>+		</a>+		+		<ul id="toc-See_also-sublist" class="vector-toc-list">+		</ul>+	</li>+	<li id="toc-References"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#References">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">7</span>References</div>+		</a>+		+		<ul id="toc-References-sublist" class="vector-toc-list">+		</ul>+	</li>+	<li id="toc-Further_reading"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#Further_reading">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">8</span>Further reading</div>+		</a>+		+		<ul id="toc-Further_reading-sublist" class="vector-toc-list">+		</ul>+	</li>+	<li id="toc-External_links"+		class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded">+		<a class="vector-toc-link" href="#External_links">+			<div class="vector-toc-text">+			<span class="vector-toc-numb">9</span>External links</div>+		</a>+		+		<ul id="toc-External_links-sublist" class="vector-toc-list">+		</ul>+	</li>+</ul>+</div>++			</div>+		</nav>+		<div class="mw-content-container">+			<main id="content" class="mw-body" role="main">+				<header class="mw-body-header vector-page-titlebar">+					<label+						id="vector-toc-collapsed-button"+						class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet vector-button-flush-left cdx-button--icon-only"+						for="vector-toc-collapsed-checkbox"+						role="button"+						aria-controls="vector-toc"+						tabindex="0"+						title="Table of Contents">+						<span class="vector-icon mw-ui-icon-wikimedia-listBullet"></span>+						<span>Toggle the table of contents</span>+					</label>+					<nav role="navigation" aria-label="Contents" class="vector-toc-landmark">+						+<div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left"  >+	<input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox "  aria-label="Toggle the table of contents"  >+	<label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true"  ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span>++<span class="vector-dropdown-label-text">Toggle the table of contents</span>+	</label>+	<div class="vector-dropdown-content">+++							<div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container">+			</div>+		+	</div>+</div>++					</nav>+					<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Parsing</span></h1>+							+<div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang"  >+	<input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 44 languages"   >+	<label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-44" aria-hidden="true"  ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span>++<span class="vector-dropdown-label-text">44 languages</span>+	</label>+	<div class="vector-dropdown-content">++		<div class="vector-menu-content">+			+			<ul class="vector-menu-content-list">+				+				<li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AA%D8%AC%D8%B2%D8%A6%D8%A9_(%D9%84%D8%BA%D8%A9)" title="تجزئة (لغة) – Arabic" lang="ar" hreflang="ar" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%AC%E0%A6%BE%E0%A6%95%E0%A7%8D%E0%A6%AF%E0%A6%BE%E0%A6%A4%E0%A7%8D%E0%A6%AE%E0%A6%95_%E0%A6%AA%E0%A6%A6%E0%A6%AA%E0%A6%B0%E0%A6%BF%E0%A6%9A%E0%A6%AF%E0%A6%BC" title="বাক্যাত্মক পদপরিচয় – Bangla" lang="bn" hreflang="bn" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Analitzador_sint%C3%A0ctic" title="Analitzador sintàctic – Catalan" lang="ca" hreflang="ca" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Syntaktick%C3%A1_anal%C3%BDza" title="Syntaktická analýza – Czech" lang="cs" hreflang="cs" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Parser" title="Parser – Danish" lang="da" hreflang="da" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Parser" title="Parser – German" lang="de" hreflang="de" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Parsimine" title="Parsimine – Estonian" lang="et" hreflang="et" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A3%CF%85%CE%BD%CF%84%CE%B1%CE%BA%CF%84%CE%B9%CE%BA%CE%AE_%CE%B1%CE%BD%CE%AC%CE%BB%CF%85%CF%83%CE%B7_(%CF%85%CF%80%CE%BF%CE%BB%CE%BF%CE%B3%CE%B9%CF%83%CF%84%CE%AD%CF%82)" title="Συντακτική ανάλυση (υπολογιστές) – Greek" lang="el" hreflang="el" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico" title="Analizador sintáctico – Spanish" lang="es" hreflang="es" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Sintaksa_analizo" title="Sintaksa analizo – Esperanto" lang="eo" hreflang="eo" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Analizatzaile_sintaktiko" title="Analizatzaile sintaktiko – Basque" lang="eu" hreflang="eu" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%AC%D8%B2%DB%8C%D9%87%E2%80%8C%DA%A9%D9%86%D9%86%D8%AF%D9%87" title="تجزیه‌کننده – Persian" lang="fa" hreflang="fa" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Analyse_syntaxique" title="Analyse syntaxique – French" lang="fr" hreflang="fr" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B5%AC%EB%AC%B8_%EB%B6%84%EC%84%9D" title="구문 분석 – Korean" lang="ko" hreflang="ko" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D5%87%D5%A1%D6%80%D5%A1%D5%B0%D5%B5%D5%B8%D6%82%D5%BD%D5%A1%D5%AF%D5%A1%D5%B6_%D5%BE%D5%A5%D6%80%D5%AC%D5%B8%D6%82%D5%AE%D5%B8%D6%82%D5%A9%D5%B5%D5%B8%D6%82%D5%B6_(%D5%AB%D5%B6%D6%86%D5%B8%D6%80%D5%B4%D5%A1%D5%BF%D5%AB%D5%AF%D5%A1)" title="Շարահյուսական վերլուծություն (ինֆորմատիկա) – Armenian" lang="hy" hreflang="hy" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%B5%E0%A4%BE%E0%A4%95%E0%A5%8D%E0%A4%AF%E0%A4%BE%E0%A4%A4%E0%A5%8D%E0%A4%AE%E0%A4%95_%E0%A4%AA%E0%A4%A6%E0%A4%AA%E0%A4%B0%E0%A4%BF%E0%A4%9A%E0%A4%AF" title="वाक्यात्मक पदपरिचय – Hindi" lang="hi" hreflang="hi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Parsiranje" title="Parsiranje – Croatian" lang="hr" hreflang="hr" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Sintax-analizilo" title="Sintax-analizilo – Ido" lang="io" hreflang="io" class="interlanguage-link-target"><span>Ido</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Parsing" title="Parsing – Indonesian" lang="id" hreflang="id" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Parsing" title="Parsing – Italian" lang="it" hreflang="it" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A0%D7%99%D7%AA%D7%95%D7%97_%D7%9E%D7%97%D7%A8%D7%95%D7%96%D7%95%D7%AA" title="ניתוח מחרוזות – Hebrew" lang="he" hreflang="he" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-kk mw-list-item"><a href="https://kk.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%81%D1%82%D1%96%D0%BA_%D1%82%D0%B0%D0%BB%D0%B4%D0%B0%D1%83" title="Синтаксистік талдау – Kazakh" lang="kk" hreflang="kk" class="interlanguage-link-target"><span>Қазақша</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Elemz%C5%91_(informatika)" title="Elemző (informatika) – Hungarian" lang="hu" hreflang="hu" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%87%D0%BB%D0%B5%D0%BD%D1%83%D0%B2%D0%B0%D1%9A%D0%B5_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" title="Расчленување (информатика) – Macedonian" lang="mk" hreflang="mk" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Parser" title="Parser – Dutch" lang="nl" hreflang="nl" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90" title="構文解析 – Japanese" lang="ja" hreflang="ja" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Parsing" title="Parsing – Norwegian Bokmål" lang="nb" hreflang="nb" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Analizator_sk%C5%82adniowy" title="Analizator składniowy – Polish" lang="pl" hreflang="pl" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/An%C3%A1lise_sint%C3%A1tica_(computa%C3%A7%C3%A3o)" title="Análise sintática (computação) – Portuguese" lang="pt" hreflang="pt" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Parsare" title="Parsare – Romanian" lang="ro" hreflang="ro" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7" title="Синтаксический анализ – Russian" lang="ru" hreflang="ru" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Parser" title="Parser – Simple English" lang="en-simple" hreflang="en-simple" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Syntaktick%C3%A1_anal%C3%BDza" title="Syntaktická analýza – Slovak" lang="sk" hreflang="sk" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Ra%C5%A1%C4%8Dlanjivanje" title="Raščlanjivanje – Serbian" lang="sr" hreflang="sr" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Ra%C5%A1%C4%8Dlanjivanje" title="Raščlanjivanje – Serbo-Croatian" lang="sh" hreflang="sh" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/J%C3%A4sent%C3%A4minen" title="Jäsentäminen – Finnish" lang="fi" hreflang="fi" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Parser" title="Parser – Swedish" lang="sv" hreflang="sv" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Parsing" title="Parsing – Tagalog" lang="tl" hreflang="tl" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%87%E0%AE%B2%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AE%A3%E0%AE%AA%E0%AF%8D_%E0%AE%AA%E0%AE%BE%E0%AE%95%E0%AF%81%E0%AE%AA%E0%AE%9F%E0%AF%81%E0%AE%A4%E0%AF%8D%E0%AE%A4%E0%AE%BF" title="இலக்கணப் பாகுபடுத்தி – Tamil" lang="ta" hreflang="ta" class="interlanguage-link-target"><span>தமிழ்</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Ayr%C4%B1%C5%9Ft%C4%B1r%C4%B1c%C4%B1_(yaz%C4%B1l%C4%B1m)" title="Ayrıştırıcı (yazılım) – Turkish" lang="tr" hreflang="tr" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%87%D0%BD%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D1%96%D0%B7" title="Синтаксичний аналіз – Ukrainian" lang="uk" hreflang="uk" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Ph%C3%A2n_t%C3%ADch_c%C3%BA_ph%C3%A1p" title="Phân tích cú pháp – Vietnamese" lang="vi" hreflang="vi" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E8%A7%A3%E6%9E%90" title="解析 – Cantonese" lang="yue" hreflang="yue" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90" title="语法分析 – Chinese" lang="zh" hreflang="zh" class="interlanguage-link-target"><span>中文</span></a></li>+			</ul>+			<div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q194152#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div>+		</div>++	</div>+</div>+</header>+				<div class="vector-page-toolbar">+					<div class="vector-page-toolbar-container">+						<div id="left-navigation">+							<nav aria-label="Namespaces">+								+<div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages"  >+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Parsing" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Parsing" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li>+		</ul>+		+	</div>+</div>++								+<div id="p-variants" class="vector-dropdown emptyPortlet"  >+	<input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-dropdown-checkbox " aria-label="Change language variant"   >+	<label id="p-variants-label" for="p-variants-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true"  ><span class="vector-dropdown-label-text">English</span>+	</label>+	<div class="vector-dropdown-content">+++					+<div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet"  >+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			+		</ul>+		+	</div>+</div>++				+	</div>+</div>++							</nav>+						</div>+						<div id="right-navigation" class="vector-collapsible">+							<nav aria-label="Views">+								+<div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views"  >+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Parsing"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Parsing&amp;action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Parsing&amp;action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li>+		</ul>+		+	</div>+</div>++							</nav>+				+							<nav class="vector-page-tools-landmark" aria-label="More options">+								+<div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown"  >+	<input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox "  aria-label="Tools"  >+	<label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true"  ><span class="vector-dropdown-label-text">Tools</span>+	</label>+	<div class="vector-dropdown-content">+++									<div id="vector-page-tools-unpinned-container" class="vector-unpinned-container">+						+<div id="vector-page-tools" class="vector-page-tools vector-pinnable-element">+	<div+	class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned"+	data-feature-name="page-tools-pinned"+	data-pinnable-element-id="vector-page-tools"+	data-pinned-container-id="vector-page-tools-pinned-container"+	data-unpinned-container-id="vector-page-tools-unpinned-container"+>+	<div class="vector-pinnable-header-label">Tools</div>+	<button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button>+	<button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button>+</div>++	+<div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items"  title="More options" >+	<div class="vector-menu-heading">+		Actions+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Parsing"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Parsing&amp;action=edit"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Parsing&amp;action=history"><span>View history</span></a></li>+		</ul>+		+	</div>+</div>++<div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb"  >+	<div class="vector-menu-heading">+		General+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Parsing" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Parsing" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Parsing&amp;oldid=1169191759" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Parsing&amp;action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&amp;page=Parsing&amp;id=1169191759&amp;wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-wikibase" class="mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q194152" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li>+		</ul>+		+	</div>+</div>++<div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export"  >+	<div class="vector-menu-heading">+		Print/export+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&amp;page=Parsing&amp;action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Parsing&amp;printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li>+		</ul>+		+	</div>+</div>++<div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects"  >+	<div class="vector-menu-heading">+		In other projects+	</div>+	<div class="vector-menu-content">+		+		<ul class="vector-menu-content-list">+			+			<li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Parsing" hreflang="en"><span>Wikimedia Commons</span></a></li>+		</ul>+		+	</div>+</div>++</div>++									</div>+				+	</div>+</div>++							</nav>+						</div>+					</div>+				</div>+				<div class="vector-column-end">+					<nav class="vector-page-tools-landmark vector-sticky-pinned-container" aria-label="More options">+						<div id="vector-page-tools-pinned-container" class="vector-pinned-container">+			+						</div>+	</nav>+				</div>+				<div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container>+					<div class="vector-body-before-content">+							<div class="mw-indicators">+		</div>++						<div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div>+					</div>+					<div id="contentSub"><div id="mw-content-subtitle"></div></div>+					+					+					<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-parser-output"><style data-mw-deduplicate="TemplateStyles:r1033289096">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}</style><div role="note" class="hatnote navigation-not-searchable">"Parse" redirects here. For other uses, see <a href="/wiki/Parse_(disambiguation)" class="mw-disambig" title="Parse (disambiguation)">Parse (disambiguation)</a>.</div>+<div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Analysing a string of symbols, according to the rules of a formal grammar</div>+<p><b>Parsing</b>, <b>syntax analysis</b>, or <b>syntactic analysis</b> is the process of analyzing a <a href="/wiki/String_(computer_science)" title="String (computer science)">string</a> of <a href="/wiki/Symbol_(formal)" title="Symbol (formal)">symbols</a>, either in <a href="/wiki/Natural_language" title="Natural language">natural language</a>, <a href="/wiki/Computer_languages" class="mw-redirect" title="Computer languages">computer languages</a> or <a href="/wiki/Data_structure" title="Data structure">data structures</a>, conforming to the rules of a <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a>.  The term <i>parsing</i> comes from Latin <i>pars</i> (<i>orationis</i>), meaning <a href="/wiki/Part_of_speech" title="Part of speech">part (of speech)</a>.<sup id="cite_ref-dictionary.com_1-0" class="reference"><a href="#cite_note-dictionary.com-1">&#91;1&#93;</a></sup>+</p><p>The term has slightly different meanings in different branches of <a href="/wiki/Linguistics" title="Linguistics">linguistics</a> and <a href="/wiki/Computer_science" title="Computer science">computer science</a>.  Traditional <a href="/wiki/Sentence_(linguistics)" title="Sentence (linguistics)">sentence</a> parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as <a href="/wiki/Sentence_diagram" title="Sentence diagram">sentence diagrams</a>.  It usually emphasizes the importance of grammatical divisions such as <a href="/wiki/Subject_(grammar)" title="Subject (grammar)">subject</a> and <a href="/wiki/Predicate_(grammar)" title="Predicate (grammar)">predicate</a>.+</p><p>Within <a href="/wiki/Computational_linguistics" title="Computational linguistics">computational linguistics</a> the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a <a href="/wiki/Parse_tree" title="Parse tree">parse tree</a> showing their syntactic relation to each other, which may also contain <a href="/wiki/Semantics" title="Semantics">semantic</a> and other information (<a href="/wiki/P-values" class="mw-redirect" title="P-values">p-values</a>).<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (August 2019)">citation needed</span></a></i>&#93;</sup> Some parsing algorithms may generate a <i>parse forest</i> or list of parse trees for a <a href="/wiki/Syntactically_ambiguous" class="mw-redirect" title="Syntactically ambiguous">syntactically ambiguous</a> input.<sup id="cite_ref-Tomita2012_2-0" class="reference"><a href="#cite_note-Tomita2012-2">&#91;2&#93;</a></sup>+</p><p>The term is also used in <a href="/wiki/Psycholinguistics" title="Psycholinguistics">psycholinguistics</a> when describing language comprehension.  In this context, parsing refers to the way that human beings analyze a sentence or phrase (in spoken language or text) "in terms of grammatical constituents, identifying the parts of speech, syntactic relations, etc."<sup id="cite_ref-dictionary.com_1-1" class="reference"><a href="#cite_note-dictionary.com-1">&#91;1&#93;</a></sup>  This term is especially common when discussing which linguistic cues help speakers interpret <a href="/wiki/Garden_path_sentence" class="mw-redirect" title="Garden path sentence">garden-path sentences</a>.+</p><p>Within computer science, the term is used in the analysis of <a href="/wiki/Computer_languages" class="mw-redirect" title="Computer languages">computer languages</a>, referring to the syntactic analysis of the input code into its component parts in order to facilitate the writing of <a href="/wiki/Compilers" class="mw-redirect" title="Compilers">compilers</a> and <a href="/wiki/Interpreter_(computing)" title="Interpreter (computing)">interpreters</a>. The term may also be used to describe a split or separation.+</p>+<meta property="mw:PageProp/toc" />+<h2><span class="mw-headline" id="Human_languages">Human languages</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=1" title="Edit section: Human languages">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1033289096"><div role="note" class="hatnote navigation-not-searchable">Main category: <a href="/wiki/Category:Natural_language_parsing" title="Category:Natural language parsing">Natural language parsing</a></div>+<h3><span class="mw-headline" id="Traditional_methods">Traditional methods</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=2" title="Edit section: Traditional methods">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<p>The traditional grammatical exercise of parsing, sometimes known as <i>clause analysis</i>, involves breaking down a text into its component <a href="/wiki/Part_of_speech" title="Part of speech">parts of speech</a> with an explanation of the form, function, and syntactic relationship of each part.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3">&#91;3&#93;</a></sup> This is determined in large part from study of the language's <a href="/wiki/Conjugation_(grammar)" class="mw-redirect" title="Conjugation (grammar)">conjugations</a> and <a href="/wiki/Declensions" class="mw-redirect" title="Declensions">declensions</a>, which can be quite intricate for heavily <a href="/wiki/Inflection" title="Inflection">inflected</a> languages. To parse a phrase such as 'man bites dog' involves noting that the <a href="/wiki/Grammatical_number" title="Grammatical number">singular</a> noun 'man' is the <a href="/wiki/Subject_(grammar)" title="Subject (grammar)">subject</a> of the sentence, the verb 'bites' is the <a href="/wiki/Grammatical_person" title="Grammatical person">third person singular</a> of the <a href="/wiki/Present_tense" title="Present tense">present tense</a> of the verb 'to bite', and the singular noun 'dog' is the <a href="/wiki/Object_(grammar)" title="Object (grammar)">object</a> of the sentence.  Techniques such as <a href="/wiki/Sentence_diagram" title="Sentence diagram">sentence diagrams</a> are sometimes used to indicate relation between elements in the sentence.+</p><p>Parsing was formerly central to the teaching of grammar throughout the English-speaking world, and widely regarded as basic to the use and understanding of written language.  However, the general teaching of such techniques is no longer current.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (August 2021)">citation needed</span></a></i>&#93;</sup>+</p>+<h3><span class="mw-headline" id="Computational_methods">Computational methods</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=3" title="Edit section: Computational methods">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1033289096"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Syntactic_parsing_(computational_linguistics)" title="Syntactic parsing (computational linguistics)">Syntactic parsing (computational linguistics)</a></div>+<style data-mw-deduplicate="TemplateStyles:r1097763485">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}</style><table class="box-More_citations_needed_section plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Parsing&amp;action=edit">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>&#32;in this section. Unsourced material may be challenged and removed.</span>  <span class="date-container"><i>(<span class="date">February 2013</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this template message</a></small>)</i></span></div></td></tr></tbody></table>+<p>In some <a href="/wiki/Machine_translation" title="Machine translation">machine translation</a> and <a href="/wiki/Natural_language_processing" title="Natural language processing">natural language processing</a> systems, written texts in human languages are parsed by computer programs.<sup id="cite_ref-ManningManning1999_4-0" class="reference"><a href="#cite_note-ManningManning1999-4">&#91;4&#93;</a></sup> Human sentences are not easily parsed by programs, as there is substantial <a href="/wiki/Syntactic_ambiguity" title="Syntactic ambiguity">ambiguity</a> in the structure of human language, whose usage is to convey meaning (or <a href="/wiki/Semantics" title="Semantics">semantics</a>) amongst a potentially unlimited range of possibilities but only some of which are germane to the particular case.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5">&#91;5&#93;</a></sup> So an utterance "Man bites dog" versus "Dog bites man" is definite on one detail but in another language might appear as "Man dog bites" with a reliance on the larger context to distinguish between those two possibilities, if indeed that difference was of concern. It is difficult to prepare formal rules to describe informal behaviour even though it is clear that some rules are being followed.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (February 2018)">citation needed</span></a></i>&#93;</sup>+</p><p>In order to parse natural language data, researchers must first agree on the <a href="/wiki/Grammar" title="Grammar">grammar</a> to be used. The choice of syntax is affected by both <a href="/wiki/Language" title="Language">linguistic</a> and computational concerns; for instance some parsing systems use <a href="/wiki/Lexical_functional_grammar" title="Lexical functional grammar">lexical functional grammar</a>, but in general, parsing for grammars of this type is known to be <a href="/wiki/NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>. <a href="/wiki/Head-driven_phrase_structure_grammar" title="Head-driven phrase structure grammar">Head-driven phrase structure grammar</a> is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn <a href="/wiki/Treebank" title="Treebank">Treebank</a>. <a href="/wiki/Shallow_parsing" title="Shallow parsing">Shallow parsing</a> aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is <a href="/wiki/Dependency_grammar" title="Dependency grammar">dependency grammar</a> parsing.+</p><p>Most modern parsers are at least partly <a href="/wiki/Statistical_parsing" title="Statistical parsing">statistical</a>; that is, they rely on a <a href="/wiki/Text_corpus" title="Text corpus">corpus</a> of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. <i>(See <a href="/wiki/Machine_learning" title="Machine learning">machine learning</a>.)</i> Approaches which have been used include straightforward <a href="/wiki/PCFG" class="mw-redirect" title="PCFG">PCFGs</a> (probabilistic context-free grammars),<sup id="cite_ref-6" class="reference"><a href="#cite_note-6">&#91;6&#93;</a></sup> <a href="/wiki/Maximum_entropy_classifier" class="mw-redirect" title="Maximum entropy classifier">maximum entropy</a>,<sup id="cite_ref-7" class="reference"><a href="#cite_note-7">&#91;7&#93;</a></sup> and <a href="/wiki/Neural_net" class="mw-redirect" title="Neural net">neural nets</a>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8">&#91;8&#93;</a></sup> Most of the more successful systems use <i>lexical</i> statistics (that is, they consider the identities of the words involved, as well as their <a href="/wiki/Part_of_speech" title="Part of speech">part of speech</a>). However such systems are vulnerable to <a href="/wiki/Overfitting" title="Overfitting">overfitting</a> and require some kind of <a href="/wiki/Smoothing" title="Smoothing">smoothing</a> to be effective.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (May 2008)">citation needed</span></a></i>&#93;</sup>+</p><p>Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually designed grammars for programming languages. As mentioned earlier some grammar formalisms are very difficult to parse computationally; in general, even if the desired structure is not <a href="/wiki/Context-free_language" title="Context-free language">context-free</a>, some kind of context-free approximation to the grammar is used to perform a first pass. Algorithms which use context-free grammars often rely on some variant of the <a href="/wiki/CYK_algorithm" title="CYK algorithm">CYK algorithm</a>, usually with some <a href="/wiki/Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic</a> to prune away unlikely analyses to save time. <i>(See <a href="/wiki/Chart_parsing" class="mw-redirect" title="Chart parsing">chart parsing</a>.)</i> However some systems trade speed for accuracy using, e.g., linear-time versions of the <a href="/wiki/Shift-reduce_parsing" class="mw-redirect" title="Shift-reduce parsing">shift-reduce</a> algorithm. A somewhat recent development has been <a href="/w/index.php?title=Parse_reranking&amp;action=edit&amp;redlink=1" class="new" title="Parse reranking (page does not exist)">parse reranking</a> in which the parser proposes some large number of analyses, and a more complex system selects the best option.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (January 2019)">citation needed</span></a></i>&#93;</sup> In <a href="/wiki/Natural_language_understanding" class="mw-redirect" title="Natural language understanding">natural language understanding</a> applications, <a href="/wiki/Semantic_parsing" title="Semantic parsing">semantic parsers</a> convert the text into a representation of its meaning.<sup id="cite_ref-:0_9-0" class="reference"><a href="#cite_note-:0-9">&#91;9&#93;</a></sup>+</p>+<h3><span class="mw-headline" id="Psycholinguistics">Psycholinguistics</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=4" title="Edit section: Psycholinguistics">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<p>In <a href="/wiki/Psycholinguistics" title="Psycholinguistics">psycholinguistics</a>, parsing involves not just the assignment of words to categories (formation of ontological insights), but the evaluation of the meaning of a sentence according to the rules of syntax drawn by inferences made from each word in the sentence (known as <a href="/wiki/Connotation" title="Connotation">connotation</a>). This normally occurs as words are being heard or read. Consequently, psycholinguistic models of parsing are of necessity <i>incremental</i>, meaning that they build up an interpretation as the sentence is being processed, which is normally expressed in terms of a partial syntactic structure. Creation of initially wrong structures occurs when interpreting <a href="/wiki/Garden-path_sentence" title="Garden-path sentence">garden-path sentences</a>.+</p>+<h3><span class="mw-headline" id="Discourse_analysis">Discourse analysis</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=5" title="Edit section: Discourse analysis">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<p><a href="/wiki/Discourse_analysis" title="Discourse analysis">Discourse analysis</a> examines ways to analyze language use and semiotic events. Persuasive language may be called <a href="/wiki/Rhetoric" title="Rhetoric">rhetoric</a>.+</p>+<h2><span class="mw-headline" id="Computer_languages">Computer languages</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=6" title="Edit section: Computer languages">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1097763485"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Parsing&amp;action=edit">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span>  <span class="date-container"><i>(<span class="date">February 2013</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this template message</a></small>)</i></span></div></td></tr></tbody></table>+<h3><span class="mw-headline" id="Parser">Parser</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=7" title="Edit section: Parser">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1033289096"><div role="note" class="hatnote navigation-not-searchable">"Parser" redirects here. For the scripting language named Parser, see <a href="/wiki/Parser_(programming_language)" title="Parser (programming language)">Parser (programming language)</a>.</div>+<p>A <b>parser</b> is a software component that takes input data (frequently text) and builds a <a href="/wiki/Data_structure" title="Data structure">data structure</a> – often some kind of <a href="/wiki/Parse_tree" title="Parse tree">parse tree</a>, <a href="/wiki/Abstract_syntax_tree" title="Abstract syntax tree">abstract syntax tree</a> or other hierarchical structure, giving a structural representation of the input while checking for correct syntax. The parsing may be preceded or followed by other steps, or these may be combined into a single step. The parser is often preceded by a separate <a href="/wiki/Lexical_analysis" title="Lexical analysis">lexical analyser</a>, which creates tokens from the sequence of input characters; alternatively, these can be combined in <a href="/wiki/Scannerless_parsing" title="Scannerless parsing">scannerless parsing</a>. Parsers may be programmed by hand or may be automatically or semi-automatically generated by a <a href="/wiki/Parser_generator" class="mw-redirect" title="Parser generator">parser generator</a>. Parsing is complementary to <a href="/wiki/Templating_language" class="mw-redirect" title="Templating language">templating</a>, which produces formatted <i>output.</i> These may be applied to different domains, but often appear together, such as the <a href="/wiki/Scanf" class="mw-redirect" title="Scanf">scanf</a>/<a href="/wiki/Printf" title="Printf">printf</a> pair, or the input (front end parsing) and output (back end code generation) stages of a compiler.+</p><p>The input to a parser is often text in some <a href="/wiki/Computer_language" title="Computer language">computer language</a>, but may also be text in a natural language or less structured textual data, in which case generally only certain parts of the text are extracted, rather than a parse tree being constructed. Parsers range from very simple functions such as <a href="/wiki/Scanf" class="mw-redirect" title="Scanf">scanf</a>, to complex programs such as the frontend of a <a href="/wiki/C%2B%2B_compiler" class="mw-redirect" title="C++ compiler">C++ compiler</a> or the <a href="/wiki/HTML" title="HTML">HTML</a> parser of a <a href="/wiki/Web_browser" title="Web browser">web browser</a>. An important class of simple parsing is done using <a href="/wiki/Regular_expression" title="Regular expression">regular expressions</a>, in which a group of regular expressions defines a <a href="/wiki/Regular_language" title="Regular language">regular language</a> and a regular expression engine automatically generating a parser for that language, allowing <a href="/wiki/Pattern_matching" title="Pattern matching">pattern matching</a> and extraction of text. In other contexts regular expressions are instead used prior to parsing, as the lexing step whose output is then used by the parser.+</p><p>The use of parsers varies by input. In the case of data languages, a parser is often found as the file reading facility of a program, such as reading in HTML or <a href="/wiki/XML" title="XML">XML</a> text; these examples are <a href="/wiki/Markup_language" title="Markup language">markup languages</a>. In the case of <a href="/wiki/Programming_language" title="Programming language">programming languages</a>, a parser is a component of a <a href="/wiki/Compiler" title="Compiler">compiler</a> or <a href="/wiki/Interpreter_(computing)" title="Interpreter (computing)">interpreter</a>, which parses the <a href="/wiki/Source_code" title="Source code">source code</a> of a <a href="/wiki/Computer_programming_language" class="mw-redirect" title="Computer programming language">computer programming language</a> to create some form of internal representation; the parser is a key step in the <a href="/wiki/Compiler_frontend" class="mw-redirect" title="Compiler frontend">compiler frontend</a>. Programming languages tend to be specified in terms of a <a href="/wiki/Deterministic_context-free_grammar" title="Deterministic context-free grammar">deterministic context-free grammar</a> because fast and efficient parsers can be written for them. For compilers, the parsing itself can be done in one pass or multiple passes – see <a href="/wiki/One-pass_compiler" title="One-pass compiler">one-pass compiler</a> and <a href="/wiki/Multi-pass_compiler" title="Multi-pass compiler">multi-pass compiler</a>.+</p><p>The implied disadvantages of a one-pass compiler can largely be overcome by adding <a href="/wiki/Relocation_(computing)" title="Relocation (computing)">fix-ups</a>, where provision is made for code relocation during the forward pass, and the fix-ups are applied backwards when the current program segment has been recognized as having been completed. An example where such a fix-up mechanism would be useful would be a forward GOTO statement, where the target of the GOTO is unknown until the program segment is completed. In this case, the application of the fix-up would be delayed until the target of the GOTO was recognized. Conversely, a backward GOTO does not require a fix-up, as the location will already be known.+</p><p>Context-free grammars are limited in the extent to which they can express all of the requirements of a language. Informally, the reason is that the memory of such a language is limited. The grammar cannot remember the presence of a construct over an arbitrarily long input; this is necessary for a language in which, for example, a name must be declared before it may be referenced. More powerful grammars that can express this constraint, however, cannot be parsed efficiently. Thus, it is a common strategy to create a relaxed parser for a context-free grammar which accepts a superset of the desired language constructs (that is, it accepts some invalid constructs); later, the unwanted constructs can be filtered out at the <a href="/wiki/Semantic_analysis_(compilers)" title="Semantic analysis (compilers)">semantic analysis</a> (contextual analysis) step.+</p><p>For example, in <a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a> the following is syntactically valid code:+</p>+<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span></span><span class="n">x</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>+<span class="nb">print</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>+</pre></div>+<p>The following code, however, is syntactically valid in terms of the context-free grammar, yielding a syntax tree with the same structure as the previous, but violates the semantic  rule requiring variables to be initialized before use:+</p>+<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span></span><span class="n">x</span> <span class="o">=</span> <span class="mi">1</span>+<span class="nb">print</span><span class="p">(</span><span class="n">y</span><span class="p">)</span>+</pre></div>+<h3><span class="mw-headline" id="Overview_of_process">Overview of process</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=8" title="Edit section: Overview of process">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<figure class="mw-default-size mw-halign-right" typeof="mw:File"><a href="/wiki/File:Parser_Flow%D5%B8.gif" class="mw-file-description" title="Flow of data in a typical parser"><img alt="Flow of data in a typical parser" src="//upload.wikimedia.org/wikipedia/commons/d/d6/Parser_Flow%D5%B8.gif" decoding="async" width="147" height="409" class="mw-file-element" data-file-width="147" data-file-height="409" /></a><figcaption>Flow of data in a typical parser</figcaption></figure>+<p>The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.+</p><p>The first stage is the token generation, or <a href="/wiki/Lexical_analysis" title="Lexical analysis">lexical analysis</a>, by which the input character stream is split into meaningful symbols defined by a grammar of <a href="/wiki/Regular_expression" title="Regular expression">regular expressions</a>. For example, a calculator program would look at an input such as "<code>12 * (3 + 4)^2</code>" and split it into the tokens <code>12</code>, <code>*</code>, <code>(</code>, <code>3</code>, <code>+</code>, <code>4</code>, <code>)</code>, <code>^</code>, <code>2</code>, each of which is a meaningful symbol in the context of an arithmetic expression. The lexer would contain rules to tell it that the characters <code>*</code>, <code>+</code>, <code>^</code>, <code>(</code> and <code>)</code> mark the start of a new token, so meaningless tokens like "<code>12*</code>" or "<code>(3</code>" will not be generated.+</p><p>The next stage is parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a> which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with <a href="/wiki/Attribute_grammar" title="Attribute grammar">attribute grammars</a>.+</p><p>The final phase is <a href="/wiki/Semantic_analysis_(computer_science)" class="mw-redirect" title="Semantic analysis (computer science)">semantic parsing</a> or analysis, which is working out the implications of the expression just validated and taking the appropriate action.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10">&#91;10&#93;</a></sup> In the case of a calculator or interpreter, the action is to evaluate the expression or program; a compiler, on the other hand, would generate some kind of code. Attribute grammars can also be used to define these actions.+</p>+<h2><span class="mw-headline" id="Types_of_parsers">Types of parsers</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=9" title="Edit section: Types of parsers">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<p>The <i>task</i> of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:+</p>+<dl><dt><a href="/wiki/Top-down_parsing" title="Top-down parsing">Top-down parsing</a></dt>+<dd>Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for <a href="/wiki/Parse_tree" title="Parse tree">parse trees</a> using a top-down expansion of the given <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a> rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate <a href="/wiki/Ambiguity" title="Ambiguity">ambiguity</a> by expanding all alternative right-hand-sides of grammar rules.<sup id="cite_ref-AhoSethiUllman_1986_11-0" class="reference"><a href="#cite_note-AhoSethiUllman_1986-11">&#91;11&#93;</a></sup> This is known as the primordial soup approach. Very similar to sentence diagramming, primordial soup breaks down the constituencies of sentences.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12">&#91;12&#93;</a></sup></dd>+<dt><a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">Bottom-up parsing</a></dt>+<dd>A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. <a href="/wiki/LR_parser" title="LR parser">LR parsers</a> are examples of bottom-up parsers. Another term used for this type of parser is <a href="/wiki/Shift-reduce_parser" title="Shift-reduce parser">Shift-Reduce</a> parsing.</dd></dl>+<p><a href="/wiki/LL_parser" title="LL parser">LL parsers</a> and <a href="/wiki/Recursive-descent_parser" class="mw-redirect" title="Recursive-descent parser">recursive-descent parser</a>  are examples of top-down parsers that cannot accommodate <a href="/wiki/Left_recursion" title="Left recursion">left recursive</a> <a href="/wiki/Formal_grammar#The_syntax_of_grammars" title="Formal grammar">production rules</a>. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsing <a href="/wiki/Ambiguous_grammar" title="Ambiguous grammar">ambiguous context-free grammars</a>, more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan<sup id="cite_ref-FrostHafizCallaghan_2007_13-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2007-13">&#91;13&#93;</a></sup><sup id="cite_ref-FrostHafizCallaghan_2008_14-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2008-14">&#91;14&#93;</a></sup> which accommodate <a href="/wiki/Ambiguity" title="Ambiguity">ambiguity</a> and <a href="/wiki/Left_recursion" title="Left recursion">left recursion</a> in polynomial time and which generate polynomial-size representations of the potentially exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a given <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a>.+</p><p>An important distinction with regard to parsers is whether a parser generates a <i>leftmost derivation</i> or a <i>rightmost derivation</i> (see <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a>). LL parsers will generate a leftmost <a href="/wiki/Parse_tree" title="Parse tree">derivation</a> and LR parsers will generate a rightmost derivation (although usually in reverse).<sup id="cite_ref-AhoSethiUllman_1986_11-1" class="reference"><a href="#cite_note-AhoSethiUllman_1986-11">&#91;11&#93;</a></sup>+</p><p>Some <i><style data-mw-deduplicate="TemplateStyles:r1023754711">.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}</style><span class="vanchor"><span id="graphical_parsing"></span><span class="vanchor-text">graphical parsing</span></span></i> algorithms have been designed for <a href="/wiki/Visual_programming_languages" class="mw-redirect" title="Visual programming languages">visual programming languages</a>.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15">&#91;15&#93;</a></sup><sup id="cite_ref-16" class="reference"><a href="#cite_note-16">&#91;16&#93;</a></sup> Parsers for visual languages are sometimes based on <a href="/wiki/Graph_grammar" class="mw-redirect" title="Graph grammar">graph grammars</a>.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17">&#91;17&#93;</a></sup>+</p><p><a href="/wiki/Adaptive_parsing" class="mw-redirect" title="Adaptive parsing">Adaptive parsing</a> algorithms have been used to construct "self-extending" <a href="/wiki/Natural_language_user_interface" class="mw-redirect" title="Natural language user interface">natural language user interfaces</a>.<sup id="cite_ref-Lehman2012_18-0" class="reference"><a href="#cite_note-Lehman2012-18">&#91;18&#93;</a></sup>+</p>+<h3><span class="mw-headline" id="Implementation">Implementation</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=10" title="Edit section: Implementation">edit</a><span class="mw-editsection-bracket">]</span></span></h3>+<p>The simplest parser APIs read the entire input file, do some intermediate computation, and then write the entire output file.+(Such as in-memory <a href="/wiki/Multi-pass_compiler" title="Multi-pass compiler">multi-pass compilers</a>).+</p><p>Those simple parsers won't work when there isn't enough memory to store the entire input file or the entire output file.+They also won't work for never-ending streams of data from the real world.+</p><p>Some alternative API approaches for parsing such data:+</p>+<ul><li><b>push parsers</b> that call the registered handlers (callbacks) as soon as the parser detects relevant tokens in the input stream (such as <a href="/wiki/Expat_(software)" title="Expat (software)">Expat</a>)</li>+<li><b>pull parsers</b></li>+<li>incremental parsers (such as incremental <a href="/wiki/Chart_parser" title="Chart parser">chart parsers</a>) that, as the text of the file is edited by a user, does not need to completely re-parse the entire file.</li>+<li>Active vs passive parsers<sup id="cite_ref-19" class="reference"><a href="#cite_note-19">&#91;19&#93;</a></sup><sup id="cite_ref-20" class="reference"><a href="#cite_note-20">&#91;20&#93;</a></sup></li></ul>+<h2><span class="mw-headline" id="Parser_development_software">Parser development software</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=11" title="Edit section: Parser development software">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1097763485"><table class="box-Prose plainlinks metadata ambox ambox-style ambox-Prose" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>is in <a href="/wiki/MOS:LIST" class="mw-redirect" title="MOS:LIST">list</a> format but may read better as <a href="/wiki/MOS:PROSE" class="mw-redirect" title="MOS:PROSE">prose</a></b>.<span class="hide-when-compact"> You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Parsing&amp;action=edit">converting this article</a>, if appropriate. <a href="/wiki/Help:Editing" title="Help:Editing">Editing help</a> is available.</span>  <span class="date-container"><i>(<span class="date">January 2017</span>)</i></span></div></td></tr></tbody></table>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1033289096"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></div>+<p>Some of the well known parser development tools include the following:+</p>+<style data-mw-deduplicate="TemplateStyles:r1147244281">.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style><div class="div-col" style="column-width: 20em;">+<ul><li><a href="/wiki/ANTLR" title="ANTLR">ANTLR</a></li>+<li><a href="/wiki/GNU_Bison" title="GNU Bison">Bison</a></li>+<li><a href="/wiki/Coco/R" title="Coco/R">Coco/R</a></li>+<li><a href="/wiki/Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>+<li><a href="/wiki/GOLD_(parser)" title="GOLD (parser)">GOLD</a></li>+<li><a href="/wiki/JavaCC" title="JavaCC">JavaCC</a></li>+<li><a href="/wiki/Lemon_(parser_generator)" title="Lemon (parser generator)">Lemon</a></li>+<li><a href="/wiki/Lex_(software)" title="Lex (software)">Lex</a></li>+<li>LuZc</li>+<li><a href="/wiki/Parboiled_(Java)" title="Parboiled (Java)">Parboiled</a></li>+<li><a href="/wiki/Parsec_(parser)" title="Parsec (parser)">Parsec</a></li>+<li><a href="/wiki/Ragel" title="Ragel">Ragel</a></li>+<li><a href="/wiki/Spirit_Parser_Framework" title="Spirit Parser Framework">Spirit Parser Framework</a></li>+<li><a href="/wiki/Syntax_Definition_Formalism" title="Syntax Definition Formalism">Syntax Definition Formalism</a></li>+<li><a href="/wiki/SYNTAX" title="SYNTAX">SYNTAX</a></li>+<li><a href="/wiki/XPL" title="XPL">XPL</a></li>+<li><a href="/wiki/Yacc" title="Yacc">Yacc</a></li>+<li><a href="/wiki/PackCC" title="PackCC">PackCC</a></li></ul>+</div>+<h2><span class="mw-headline" id="Lookahead">Lookahead</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=12" title="Edit section: Lookahead">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1097763485"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Parsing&amp;action=edit">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span>  <span class="date-container"><i>(<span class="date">April 2012</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this template message</a></small>)</i></span></div></td></tr></tbody></table>+<figure typeof="mw:File/Thumb"><a href="/wiki/File:Parsing_a_C_program_that_needs_2_token_lookahead.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Parsing_a_C_program_that_needs_2_token_lookahead.svg/300px-Parsing_a_C_program_that_needs_2_token_lookahead.svg.png" decoding="async" width="300" height="259" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Parsing_a_C_program_that_needs_2_token_lookahead.svg/450px-Parsing_a_C_program_that_needs_2_token_lookahead.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Parsing_a_C_program_that_needs_2_token_lookahead.svg/600px-Parsing_a_C_program_that_needs_2_token_lookahead.svg.png 2x" data-file-width="390" data-file-height="337" /></a><figcaption><a href="/wiki/C_(programming_language)" title="C (programming language)">C</a> program that cannot be parsed with less than 2 token lookahead. <i>Top:</i> C grammar excerpt.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21">&#91;21&#93;</a></sup> <i>Bottom:</i> a parser has digested the tokens "<code class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><span class="kt">int</span><span class="w"> </span><span class="n">v</span><span class="p">;</span><span class="n">main</span><span class="p">(){</span></code>" and is about choose a rule to derive <i>Stmt</i>. Looking only at the first lookahead token "<code class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><span class="n">v</span></code>", it cannot decide which of both alternatives for <i>Stmt</i> to choose; the latter requires peeking at the second token.</figcaption></figure>+<p>Lookahead establishes the maximum incoming tokens that a parser can use to decide which rule it should use. Lookahead is especially relevant to <a href="/wiki/LL_parser" title="LL parser">LL</a>, <a href="/wiki/LR_parser" title="LR parser">LR</a>, and <a href="/wiki/LALR_parser" title="LALR parser">LALR parsers</a>, where it is often explicitly indicated by affixing the lookahead to the algorithm name in parentheses, such as LALR(1).+</p><p>Most <a href="/wiki/Programming_language" title="Programming language">programming languages</a>, the primary target of parsers, are carefully defined in such a way that a parser with limited lookahead, typically one, can parse them, because parsers with limited lookahead are often more efficient. One important change<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (December 2008)">citation needed</span></a></i>&#93;</sup> to this trend came in 1990 when <a href="/wiki/Terence_Parr" title="Terence Parr">Terence Parr</a> created <a href="/wiki/ANTLR" title="ANTLR">ANTLR</a> for his Ph.D. thesis, a <a href="/wiki/Parser_generator" class="mw-redirect" title="Parser generator">parser generator</a> for efficient LL(<i>k</i>) parsers, where <i>k</i> is any fixed value.+</p><p>LR parsers typically have only a few actions after seeing each token. They are shift (add this token to the stack for later reduction), reduce (pop tokens from the stack and form a syntactic construct), end, error (no known rule applies) or conflict (does not know whether to shift or reduce).+</p><p>Lookahead has two advantages.<sup class="noprint Inline-Template" style="margin-left:0.1em; white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="This paragraph still seems to apply only to LR parsers. (April 2019)">clarification needed</span></a></i>&#93;</sup>+</p>+<ul><li>It helps the parser take the correct action in case of conflicts. For example, parsing the if statement in the case of an else clause.</li>+<li>It eliminates many duplicate states and eases the burden of an extra stack. A C language non-lookahead parser will have around 10,000 states. A lookahead parser will have around 300 states.</li></ul>+<p>Example: Parsing the Expression  <span class="nowrap">1 + 2 * 3</span><sup class="noprint Inline-Template" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Accuracy_dispute#Disputed_statement" title="Wikipedia:Accuracy dispute"><span title="The material near this tag is possibly inaccurate or nonfactual. (April 2019)">dubious</span></a>&#32;<span class="metadata"> &#8211; <a href="/wiki/Talk:Parsing#Dubious" title="Talk:Parsing">discuss</a></span></i>&#93;</sup>+</p>+<table class="toccolours">+<tbody><tr>+<td colspan="3">Set of expression parsing rules (called grammar) is as follows,+</td></tr>+<tr>+<td>Rule1:</td>+<td>E → E + E</td>+<td style="padding-left:1em">Expression is the sum of two expressions.+</td></tr>+<tr>+<td>Rule2:</td>+<td>E → E * E</td>+<td style="padding-left:1em">Expression is the product of two expressions.+</td></tr>+<tr>+<td>Rule3:</td>+<td>E → number</td>+<td style="padding-left:1em">Expression is a simple number+</td></tr>+<tr>+<td>Rule4:</td>+<td colspan="2">+ has less precedence than *+</td></tr></tbody></table>+<p>Most programming languages (except for a few such as APL and Smalltalk) and algebraic formulas give higher precedence to multiplication than addition, in which case the correct interpretation of the example above is <span class="nowrap">1 + (2 * 3)</span>.+Note that Rule4 above is a semantic rule. It is possible to rewrite the grammar to incorporate this into the syntax. However, not all such rules can be translated into syntax.+</p>+<dl><dt>Simple non-lookahead parser actions</dt></dl>+<p>Initially Input = [1, +, 2, *, 3]+</p>+<ol><li>Shift "1" onto stack from input (in anticipation of rule3). Input = [+, 2, *, 3] Stack = [1]</li>+<li>Reduces "1" to expression "E" based on rule3. Stack = [E]</li>+<li>Shift "+" onto stack from input (in anticipation of rule1). Input = [2, *, 3] Stack = [E, +]</li>+<li>Shift "2" onto stack from input (in anticipation of rule3). Input = [*, 3] Stack = [E, +, 2]</li>+<li>Reduce stack element "2" to Expression "E" based on rule3. Stack = [E, +, E]</li>+<li>Reduce stack items [E, +, E] and new input "E" to "E" based on rule1. Stack = [E]</li>+<li>Shift "*" onto stack from input (in anticipation of rule2). Input = [3] Stack = [E,*]</li>+<li>Shift "3" onto stack from input (in anticipation of rule3). Input = [] (empty) Stack = [E, *, 3]</li>+<li>Reduce stack element "3" to expression "E" based on rule3. Stack = [E, *, E]</li>+<li>Reduce stack items [E, *, E] and new input "E" to "E" based on rule2. Stack = [E]</li></ol>+<p>The parse tree and resulting code from it is not correct according to language semantics.+</p><p>To correctly parse without lookahead, there are three solutions:+</p>+<ul><li>The user has to enclose expressions within parentheses. This often is not a viable solution.</li>+<li>The parser needs to have more logic to backtrack and retry whenever a rule is violated or not complete. The similar method is followed in LL parsers.</li>+<li>Alternatively, the parser or grammar needs to have extra logic to delay reduction and reduce only when it is absolutely sure which rule to reduce first. This method is used in LR parsers. This correctly parses the expression but with many more states and increased stack depth.</li></ul>+<dl><dt>Lookahead parser actions<sup class="noprint Inline-Template" style="margin-left:0.1em; white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="While the previous text is highly dubious, the following paragraph could possibly turned into a sensible explanation about how an LR parser uses lookahead. To this end, a parser table excerpt (implementing the precedence) should be shown, the parsing mechnism should be sketched (when to shift, when to reduce, etc.), and the exaple run should be given in more tabular form, and without magic (&#39;anticipation&#39;). (April 2019)">clarification needed</span></a></i>&#93;</sup></dt></dl>+<ol><li>Shift 1 onto stack on input 1 in anticipation of rule3. It does not reduce immediately.</li>+<li>Reduce stack item 1 to simple Expression on input + based on rule3. The lookahead is +, so we are on path to E +, so we can reduce the stack to E.</li>+<li>Shift + onto stack on input + in anticipation of rule1.</li>+<li>Shift 2 onto stack on input 2 in anticipation of rule3.</li>+<li>Reduce stack item 2 to Expression on input * based on rule3. The lookahead * expects only E before it.</li>+<li>Now stack has E + E and still the input is *. It has two choices now, either to shift based on rule2 or reduction based on rule1. Since * has higher precedence than + based on rule4, we shift * onto stack in anticipation of rule2.</li>+<li>Shift 3 onto stack on input 3 in anticipation of rule3.</li>+<li>Reduce stack item 3 to Expression after seeing end of input based on rule3.</li>+<li>Reduce stack items E * E to E based on rule2.</li>+<li>Reduce stack items E + E to E based on rule1.</li></ol>+<p>The parse tree generated is correct and simply <span class="clarify-content" style="padding-left:0.1em; padding-right:0.1em; color:#595959; border:1px solid #DDD;">more efficient</span><sup class="noprint Inline-Template Template-Clarify" style="margin-left:0.1em; white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="A parse tree and a parser cannot be compared w.r.t. efficiency. Even comparing two parse trees dosn&#39;t make sense here; expression efficiency isn&#39;t a matter of parsing, but of optimization. (April 2019)">clarify</span></a></i>&#93;</sup><sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#91;<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (April 2011)">citation needed</span></a></i>&#93;</sup> than non-lookahead parsers. This is the strategy followed in <a href="/wiki/LALR_parser" title="LALR parser">LALR parsers</a>.+</p>+<h2><span class="mw-headline" id="See_also">See also</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=13" title="Edit section: See also">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1147244281"><div class="div-col" style="column-width: 22em;">+<ul><li><a href="/wiki/Backtracking" title="Backtracking">Backtracking</a></li>+<li><a href="/wiki/Chart_parser" title="Chart parser">Chart parser</a></li>+<li><a href="/wiki/Compiler-compiler" title="Compiler-compiler">Compiler-compiler</a></li>+<li><a href="/wiki/Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>+<li><a href="/wiki/Grammar_checker" title="Grammar checker">Grammar checker</a></li>+<li><a href="/wiki/LALR_parser" title="LALR parser">LALR parser</a></li>+<li><a href="/wiki/Lexical_analysis" title="Lexical analysis">Lexical analysis</a></li>+<li><a href="/wiki/Pratt_parser" class="mw-redirect" title="Pratt parser">Pratt parser</a></li>+<li><a href="/wiki/Shallow_parsing" title="Shallow parsing">Shallow parsing</a></li>+<li><a href="/wiki/Left_corner_parser" title="Left corner parser">Left corner parser</a></li>+<li><a href="/wiki/Parsing_expression_grammar" title="Parsing expression grammar">Parsing expression grammar</a></li>+<li><a href="/wiki/DMS_Software_Reengineering_Toolkit" title="DMS Software Reengineering Toolkit">DMS Software Reengineering Toolkit</a></li>+<li><a href="/wiki/Program_transformation" title="Program transformation">Program transformation</a></li>+<li><a href="/wiki/Source_code_generation" class="mw-redirect" title="Source code generation">Source code generation</a></li>+<li><a href="/wiki/Inverse_parser" title="Inverse parser">Inverse parser</a></li></ul></div>+<h2><span class="mw-headline" id="References">References</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=14" title="Edit section: References">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<style data-mw-deduplicate="TemplateStyles:r1011085734">.mw-parser-output .reflist{font-size:90%;margin-bottom:0.5em;list-style-type:decimal}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist">+<div class="mw-references-wrap mw-references-columns"><ol class="references">+<li id="cite_note-dictionary.com-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-dictionary.com_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-dictionary.com_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1133582631">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.dictionary.com/browse/parse">"Parse"</a>. dictionary.reference.com<span class="reference-accessdate">. Retrieved <span class="nowrap">27 November</span> 2010</span>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=unknown&amp;rft.btitle=Parse&amp;rft.pub=dictionary.reference.com&amp;rft_id=https%3A%2F%2Fwww.dictionary.com%2Fbrowse%2Fparse&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-Tomita2012-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Tomita2012_2-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFMasaru_Tomita2012" class="citation book cs1">Masaru Tomita (6 December 2012). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=VVDTBwAAQBAJ&amp;q=%22parse+forest%22"><i>Generalized LR Parsing</i></a>. Springer Science &amp; Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/978-1-4615-4034-2" title="Special:BookSources/978-1-4615-4034-2"><bdi>978-1-4615-4034-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Generalized+LR+Parsing&amp;rft.pub=Springer+Science+%26+Business+Media&amp;rft.date=2012-12-06&amp;rft.isbn=978-1-4615-4034-2&amp;rft.au=Masaru+Tomita&amp;rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DVVDTBwAAQBAJ%26q%3D%2522parse%2Bforest%2522&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://grammar.about.com/od/pq/g/parsingterm.htm">"Grammar and Composition"</a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=unknown&amp;rft.btitle=Grammar+and+Composition&amp;rft_id=http%3A%2F%2Fgrammar.about.com%2Fod%2Fpq%2Fg%2Fparsingterm.htm&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-ManningManning1999-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-ManningManning1999_4-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFChristopher_D.._ManningChristopher_D._ManningHinrich_Schütze1999" class="citation book cs1">Christopher D.. Manning; Christopher D. Manning; Hinrich Schütze (1999). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=YiFDxbEX3SUC&amp;q=parsing"><i>Foundations of Statistical Natural Language Processing</i></a>. MIT Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/978-0-262-13360-9" title="Special:BookSources/978-0-262-13360-9"><bdi>978-0-262-13360-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Foundations+of+Statistical+Natural+Language+Processing&amp;rft.pub=MIT+Press&amp;rft.date=1999&amp;rft.isbn=978-0-262-13360-9&amp;rft.au=Christopher+D..+Manning&amp;rft.au=Christopher+D.+Manning&amp;rft.au=Hinrich+Sch%C3%BCtze&amp;rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DYiFDxbEX3SUC%26q%3Dparsing&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFJurafsky1996" class="citation journal cs1">Jurafsky, Daniel (1996). "A Probabilistic Model of Lexical and Syntactic Access and Disambiguation". <i>Cognitive Science</i>. <b>20</b> (2): 137–194. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a>&#160;<span class="cs1-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.5711">10.1.1.150.5711</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1207%2Fs15516709cog2002_1">10.1207/s15516709cog2002_1</a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&amp;rft.genre=article&amp;rft.jtitle=Cognitive+Science&amp;rft.atitle=A+Probabilistic+Model+of+Lexical+and+Syntactic+Access+and+Disambiguation&amp;rft.volume=20&amp;rft.issue=2&amp;rft.pages=137-194&amp;rft.date=1996&amp;rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.150.5711%23id-name%3DCiteSeerX&amp;rft_id=info%3Adoi%2F10.1207%2Fs15516709cog2002_1&amp;rft.aulast=Jurafsky&amp;rft.aufirst=Daniel&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Klein, Dan, and Christopher D. Manning. "<a rel="nofollow" class="external text" href="https://www.aclweb.org/anthology/P03-1054">Accurate unlexicalized parsing</a>." Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 1. Association for Computational Linguistics, 2003.</span>+</li>+<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Charniak, Eugene. "<a rel="nofollow" class="external text" href="https://aclanthology.info/pdf/A/A00/A00-2018.pdf">A maximum-entropy-inspired parser</a>." Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference. Association for Computational Linguistics, 2000.</span>+</li>+<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Chen, Danqi, and Christopher Manning. "<a rel="nofollow" class="external text" href="http://www.aclweb.org/anthology/D14-1082">A fast and accurate dependency parser using neural networks</a>." Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 2014.</span>+</li>+<li id="cite_note-:0-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-:0_9-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFJiaLiang2016" class="citation arxiv cs1">Jia, Robin; Liang, Percy (2016-06-11). "Data Recombination for Neural Semantic Parsing". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="cs1-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1606.03622">1606.03622</a></span> [<a rel="nofollow" class="external text" href="//arxiv.org/archive/cs.CL">cs.CL</a>].</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&amp;rft.genre=preprint&amp;rft.jtitle=arXiv&amp;rft.atitle=Data+Recombination+for+Neural+Semantic+Parsing&amp;rft.date=2016-06-11&amp;rft_id=info%3Aarxiv%2F1606.03622&amp;rft.aulast=Jia&amp;rft.aufirst=Robin&amp;rft.au=Liang%2C+Percy&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">Berant, Jonathan, and Percy Liang. "<a rel="nofollow" class="external text" href="https://www.aclweb.org/anthology/P14-1133.pdf">Semantic parsing via paraphrasing</a>." Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2014.</span>+</li>+<li id="cite_note-AhoSethiUllman_1986-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-AhoSethiUllman_1986_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-AhoSethiUllman_1986_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Aho, A.V., Sethi, R. and Ullman, J.D.  (1986) " Compilers: principles, techniques, and tools." <i> <a href="/wiki/Addison-Wesley_Longman" class="mw-redirect" title="Addison-Wesley Longman">Addison-Wesley Longman</a> Publishing Co., Inc. Boston, MA, USA. </i></span>+</li>+<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFSikkel,_Klaas,_1954-1997" class="citation book cs1">Sikkel, Klaas, 1954- (1997). <i>Parsing schemata&#160;: a framework for specification and analysis of parsing algorithms</i>. Berlin: Springer. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/9783642605413" title="Special:BookSources/9783642605413"><bdi>9783642605413</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a>&#160;<a rel="nofollow" class="external text" href="https://www.worldcat.org/oclc/606012644">606012644</a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Parsing+schemata+%3A+a+framework+for+specification+and+analysis+of+parsing+algorithms&amp;rft.place=Berlin&amp;rft.pub=Springer&amp;rft.date=1997&amp;rft_id=info%3Aoclcnum%2F606012644&amp;rft.isbn=9783642605413&amp;rft.au=Sikkel%2C+Klaas%2C+1954-&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_book" title="Template:Cite book">cite book</a>}}</code>:  CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span></span>+</li>+<li id="cite_note-FrostHafizCallaghan_2007-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-FrostHafizCallaghan_2007_13-0">^</a></b></span> <span class="reference-text">Frost, R., Hafiz, R. and Callaghan, P. (2007) " <a rel="nofollow" class="external text" href="https://aclanthology.info/pdf/W/W07/W07-2215.pdf">Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars</a> ." <i>10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE </i>, Pages: 109 - 120, June 2007, Prague.</span>+</li>+<li id="cite_note-FrostHafizCallaghan_2008-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-FrostHafizCallaghan_2008_14-0">^</a></b></span> <span class="reference-text">Frost, R., Hafiz, R. and Callaghan, P. (2008) " <a rel="nofollow" class="external text" href="http://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=1411&amp;context=etd#page=61">Parser Combinators for Ambiguous Left-Recursive Grammars</a>." <i> 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN </i>, Volume 4902/2008, Pages: 167 - 181, January 2008, San Francisco.</span>+</li>+<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">Rekers, Jan, and Andy Schürr. "<a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C47&amp;q=%22graphical+parsing%22&amp;btnG=">Defining and parsing visual languages with layered graph grammars</a>." Journal of Visual Languages &amp; Computing 8.1 (1997): 27-55.</span>+</li>+<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text">Rekers, Jan, and A. Schurr. "<a rel="nofollow" class="external text" href="https://www.researchgate.net/profile/Andy_Schuerr/publication/3660769_A_graph_grammar_approach_to_graphical_parsing/links/55e4419708aecb1a7cc9fc62.pdf">A graph grammar approach to graphical parsing</a>." Visual Languages, Proceedings., 11th IEEE International Symposium on. IEEE, 1995.</span>+</li>+<li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text">Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "<a rel="nofollow" class="external text" href="https://web.archive.org/web/20180323220143/https://pdfs.semanticscholar.org/5d3d/217d73e0f6bbeefa3749c16fbc7b2e00ec0b.pdf">A context-sensitive graph grammar formalism for the specification of visual languages</a>." The Computer Journal 44.3 (2001): 186-200.</span>+</li>+<li id="cite_note-Lehman2012-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-Lehman2012_18-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFJill_Fain_Lehman2012" class="citation book cs1">Jill Fain Lehman (6 December 2012). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=tU_tBwAAQBAJ&amp;q=%22language+acquisition%22"><i>Adaptive Parsing: Self-Extending Natural Language Interfaces</i></a>. Springer Science &amp; Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/978-1-4615-3622-2" title="Special:BookSources/978-1-4615-3622-2"><bdi>978-1-4615-3622-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Adaptive+Parsing%3A+Self-Extending+Natural+Language+Interfaces&amp;rft.pub=Springer+Science+%26+Business+Media&amp;rft.date=2012-12-06&amp;rft.isbn=978-1-4615-3622-2&amp;rft.au=Jill+Fain+Lehman&amp;rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DtU_tBwAAQBAJ%26q%3D%2522language%2Bacquisition%2522&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span>+</li>+<li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text">+Patrick Blackburn and Kristina Striegnitz.+<a rel="nofollow" class="external text" href="https://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/">"Natural Language Processing Techniques in Prolog"</a>.</span>+</li>+<li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text">+Song-Chun Zhu.+<a rel="nofollow" class="external text" href="http://www.stat.ucla.edu/~sczhu/Courses/UCLA/Stat_232B/Handouts/Ch4_chart_parsing.pdf">"Classic Parsing Algorithms"</a>.</span>+</li>+<li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text">taken from <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFBrian_W._Kernighan_and_Dennis_M._Ritchie1988" class="citation book cs1">Brian W. Kernighan and Dennis M. Ritchie (Apr 1988). <span class="cs1-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/cprogramminglang00bria"><i>The C Programming Language</i></a></span>. Prentice Hall Software Series (2nd&#160;ed.). Englewood Cliffs/NJ: Prentice Hall. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/0131103628" title="Special:BookSources/0131103628"><bdi>0131103628</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=The+C+Programming+Language&amp;rft.place=Englewood+Cliffs%2FNJ&amp;rft.series=Prentice+Hall+Software+Series&amp;rft.edition=2nd&amp;rft.pub=Prentice+Hall&amp;rft.date=1988-04&amp;rft.isbn=0131103628&amp;rft.au=Brian+W.+Kernighan+and+Dennis+M.+Ritchie&amp;rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcprogramminglang00bria&amp;rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span> (Appendix A.13 "Grammar", p.193 ff)</span>+</li>+</ol></div></div>+<h2><span class="mw-headline" id="Further_reading">Further reading</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=15" title="Edit section: Further reading">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<style data-mw-deduplicate="TemplateStyles:r1054258005">.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}</style><div class="refbegin" style="">+<ul><li>Chapman, Nigel P., <a rel="nofollow" class="external text" href="https://books.google.com/books?id=nEA9AAAAIAAJ"><i>LR Parsing: Theory and Practice</i></a>, <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, 1987. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/0-521-30413-X" title="Special:BookSources/0-521-30413-X">0-521-30413-X</a></li>+<li>Grune, Dick; Jacobs, Ceriel J.H., <a rel="nofollow" class="external text" href="http://dickgrune.com/Books/PTAPG_1st_Edition/"><i>Parsing Techniques - A Practical Guide</i></a>, <a href="/wiki/Vrije_Universiteit_Amsterdam" title="Vrije Universiteit Amsterdam">Vrije Universiteit Amsterdam</a>, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&#160;<a href="/wiki/Special:BookSources/0-13-651431-6" title="Special:BookSources/0-13-651431-6">0-13-651431-6</a></li></ul>+</div>+<h2><span class="mw-headline" id="External_links">External links</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=16" title="Edit section: External links">edit</a><span class="mw-editsection-bracket">]</span></span></h2>+<style data-mw-deduplicate="TemplateStyles:r1134653256">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:#f9f9f9;display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style>+<div class="side-box-flex">+<div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/40px-Wiktionary-logo-en-v2.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/60px-Wiktionary-logo-en-v2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/80px-Wiktionary-logo-en-v2.svg.png 2x" data-file-width="512" data-file-height="512" /></span></span></div>+<div class="side-box-text plainlist">Look up <i><b><a href="https://en.wiktionary.org/wiki/parse" class="extiw" title="wiktionary:parse">parse</a></b></i>&#160;or <i><b><a href="https://en.wiktionary.org/wiki/parsing" class="extiw" title="wiktionary:parsing">parsing</a></b></i> in Wiktionary, the free dictionary.</div></div>+</div>+<ul><li><a rel="nofollow" class="external text" href="http://www.hwaci.com/sw/lemon/">The Lemon LALR Parser Generator</a></li>+<li><a rel="nofollow" class="external text" href="http://nlp.stanford.edu/software/lex-parser.shtml">Stanford Parser</a> The Stanford Parser</li>+<li><a rel="nofollow" class="external text" href="http://www.tule.di.unito.it/">Turin University Parser</a> Natural language parser for the Italian, open source, developed in Common Lisp by Leonardo Lesmo, University of Torino, Italy.</li>+<li><a rel="nofollow" class="external text" href="http://blogs.perl.org/users/jeffrey_kegler/2014/09/parsing-a-timeline.html">Short history of parser construction</a></li></ul>+<div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1061467846">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}</style></div><div role="navigation" class="navbox" aria-labelledby="Parsing_algorithms" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1063604349">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Parsers" title="Template:Parsers"><abbr title="View this template" style=";;background:none transparent;border:none;box-shadow:none;padding:0;">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Parsers" title="Template talk:Parsers"><abbr title="Discuss this template" style=";;background:none transparent;border:none;box-shadow:none;padding:0;">t</abbr></a></li><li class="nv-edit"><a class="external text" href="https://en.wikipedia.org/w/index.php?title=Template:Parsers&amp;action=edit"><abbr title="Edit this template" style=";;background:none transparent;border:none;box-shadow:none;padding:0;">e</abbr></a></li></ul></div><div id="Parsing_algorithms" style="font-size:114%;margin:0 4em"><a class="mw-selflink selflink">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Top-down_parsing" title="Top-down parsing">Top-down</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Earley_parser" title="Earley parser">Earley</a></li>+<li><a href="/wiki/LL_parser" title="LL parser">LL</a></li>+<li><a href="/wiki/Recursive_descent_parser" title="Recursive descent parser">Recursive descent</a>+<ul><li><a href="/wiki/Tail_recursive_parser" title="Tail recursive parser">Tail recursive</a></li></ul></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">Bottom-up</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li>Precedence+<ul><li><a href="/wiki/Simple_precedence_parser" title="Simple precedence parser">Simple</a></li>+<li><a href="/wiki/Operator-precedence_parser" title="Operator-precedence parser">Operator</a>+<ul><li><a href="/wiki/Shunting_yard_algorithm" title="Shunting yard algorithm">Shunting-yard</a></li></ul></li></ul></li>+<li><a href="/wiki/LR_parser" title="LR parser">LR</a>+<ul><li><a href="/wiki/Simple_LR_parser" title="Simple LR parser">Simple</a></li>+<li><a href="/wiki/LALR_parser" title="LALR parser">Look-ahead</a></li>+<li><a href="/wiki/Canonical_LR_parser" title="Canonical LR parser">Canonical</a></li>+<li><a href="/wiki/GLR_parser" title="GLR parser">Generalized</a></li></ul></li>+<li><a href="/wiki/CYK_algorithm" title="CYK algorithm">CYK</a></li>+<li><a href="/wiki/Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent</a></li>+<li><a href="/wiki/Shift-reduce_parser" title="Shift-reduce parser">Shift-reduce</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mixed, other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Parser_combinator" title="Parser combinator">Combinator</a></li>+<li><a href="/wiki/Chart_parser" title="Chart parser">Chart</a>+<ul><li><a href="/wiki/Left_corner_parser" title="Left corner parser">Left corner</a></li></ul></li>+<li><a href="/wiki/Statistical_parsing" title="Statistical parsing">Statistical</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Parsing_expression_grammar" title="Parsing expression grammar">PEG</a></li>+<li><a href="/wiki/Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>+<li><a href="/wiki/Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>+<li><a href="/wiki/Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>+<li><a href="/wiki/Memoization" title="Memoization">Memoization</a></li>+<li><a href="/wiki/Compiler-compiler" title="Compiler-compiler">Parser generator</a>+<ul><li><a href="/wiki/LALR_parser_generator" title="LALR parser generator">LALR</a></li></ul></li>+<li><a href="/wiki/Parse_tree" title="Parse tree">Parse tree</a></li>+<li><a href="/wiki/Abstract_syntax_tree" title="Abstract syntax tree">AST</a></li>+<li><a href="/wiki/Scannerless_parsing" title="Scannerless parsing">Scannerless parsing</a></li>+<li><a href="/wiki/History_of_compiler_construction" title="History of compiler construction">History of compiler construction</a></li>+<li><a href="/wiki/Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></li>+<li><a href="/wiki/Operator-precedence_grammar" title="Operator-precedence grammar">Operator-precedence grammar</a></li></ul>+</div></td></tr></tbody></table></div>+<div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1061467846"></div><div role="navigation" class="navbox" aria-labelledby="Strings" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1063604349"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Strings" title="Template:Strings"><abbr title="View this template" style=";;background:none transparent;border:none;box-shadow:none;padding:0;">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Strings" title="Template talk:Strings"><abbr title="Discuss this template" style=";;background:none transparent;border:none;box-shadow:none;padding:0;">t</abbr></a></li><li class="nv-edit"><a class="external text" href="https://en.wikipedia.org/w/index.php?title=Template:Strings&amp;action=edit"><abbr title="Edit this template" style=";;background:none transparent;border:none;box-shadow:none;padding:0;">e</abbr></a></li></ul></div><div id="Strings" style="font-size:114%;margin:0 4em"><a href="/wiki/String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li>+<li><a href="/wiki/Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li>+<li><a href="/wiki/Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li>+<li><a href="/wiki/Edit_distance" title="Edit distance">Edit distance</a></li>+<li><a href="/wiki/Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li>+<li><a href="/wiki/Hamming_distance" title="Hamming distance">Hamming distance</a></li>+<li><a href="/wiki/Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li>+<li><a href="/wiki/Lee_distance" title="Lee distance">Lee distance</a></li>+<li><a href="/wiki/Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li>+<li><a href="/wiki/Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>+<li><a href="/wiki/Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li>+<li><a href="/wiki/Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li>+<li><a href="/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li>+<li><a href="/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li>+<li><a href="/wiki/Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li>+<li><a href="/wiki/Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li>+<li><a href="/wiki/Trigram_search" title="Trigram search">Trigram search</a></li>+<li><a href="/wiki/Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li>+<li><a href="/wiki/Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li>+<li><a href="/wiki/Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li>+<li><a href="/wiki/Regular_grammar" title="Regular grammar">Regular grammar</a></li>+<li><a href="/wiki/Thompson%27s_construction" title="Thompson&#39;s construction">Thompson's construction</a></li>+<li><a href="/wiki/Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li>+<li><a href="/wiki/Hirschberg%27s_algorithm" title="Hirschberg&#39;s algorithm">Hirschberg's algorithm</a></li>+<li><a href="/wiki/Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li>+<li><a href="/wiki/Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li>+<li><a href="/wiki/Suffix_array" title="Suffix array">Suffix array</a></li>+<li><a href="/wiki/Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li>+<li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix tree</a></li>+<li><a href="/wiki/Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li>+<li><a href="/wiki/Rope_(data_structure)" title="Rope (data structure)">Rope</a></li>+<li><a href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li>+<li><a href="/wiki/Trie" title="Trie">Trie</a></li></ul>+</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">+<ul><li><a class="mw-selflink selflink">Parsing</a></li>+<li><a href="/wiki/Pattern_matching" title="Pattern matching">Pattern matching</a></li>+<li><a href="/wiki/Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li>+<li><a href="/wiki/Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li>+<li><a href="/wiki/Longest_common_substring" title="Longest common substring">Longest common substring</a></li>+<li><a href="/wiki/Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li>+<li><a href="/wiki/Category:String_sorting_algorithms" title="Category:String sorting algorithms">Sorting</a></li>+<li><a href="/wiki/Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li></ul>+</div></td></tr></tbody></table></div>+<!-- +NewPP limit report+Parsed by mw2270+Cached time: 20230807164729+Cache expiry: 1814400+Reduced expiry: false+Complications: [vary‐revision‐sha1, show‐toc]+CPU time usage: 0.603 seconds+Real time usage: 0.765 seconds+Preprocessor visited node count: 3961/1000000+Post‐expand include size: 96252/2097152 bytes+Template argument size: 8887/2097152 bytes+Highest expansion depth: 14/100+Expensive parser function count: 23/500+Unstrip recursion depth: 1/20+Unstrip post‐expand size: 64929/5000000 bytes+Lua time usage: 0.343/10.000 seconds+Lua memory usage: 5941273/52428800 bytes+Number of Wikibase entities loaded: 0/400+-->+<!--+Transclusion expansion time report (%,ms,calls,template)+100.00%  660.937      1 -total+ 20.46%  135.235      1 Template:Reflist+ 15.70%  103.756      7 Template:Citation_needed+ 13.96%   92.254      8 Template:Fix+ 12.26%   81.020      2 Template:Navbox+ 11.96%   79.047      1 Template:Parsers+ 11.34%   74.941      2 Template:Cite_web+  9.40%   62.135     12 Template:Delink+  8.23%   54.374      1 Template:Short_description+  8.08%   53.381     21 Template:Category_handler+-->++<!-- Saved in parser cache with key enwiki:pcache:idhash:310015-0!canonical and timestamp 20230807164728 and revision id 1169191759. Rendering was triggered because: page-view+ -->+</div><!--esi <esi:include src="/esitest-fa8a495983347898/content" /> --><noscript><img src="//en.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;" /></noscript>+<div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Parsing&amp;oldid=1169191759">https://en.wikipedia.org/w/index.php?title=Parsing&amp;oldid=1169191759</a>"</div></div>+					<div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Parsing" title="Category:Parsing">Parsing</a></li><li><a href="/wiki/Category:Algorithms_on_strings" title="Category:Algorithms on strings">Algorithms on strings</a></li><li><a href="/wiki/Category:Compiler_construction" title="Category:Compiler construction">Compiler construction</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">CS1 maint: multiple names: authors list</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_August_2019" title="Category:Articles with unsourced statements from August 2019">Articles with unsourced statements from August 2019</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_August_2021" title="Category:Articles with unsourced statements from August 2021">Articles with unsourced statements from August 2021</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_February_2013" title="Category:Articles needing additional references from February 2013">Articles needing additional references from February 2013</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_February_2018" title="Category:Articles with unsourced statements from February 2018">Articles with unsourced statements from February 2018</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_May_2008" title="Category:Articles with unsourced statements from May 2008">Articles with unsourced statements from May 2008</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_January_2019" title="Category:Articles with unsourced statements from January 2019">Articles with unsourced statements from January 2019</a></li><li><a href="/wiki/Category:Articles_needing_cleanup_from_January_2017" title="Category:Articles needing cleanup from January 2017">Articles needing cleanup from January 2017</a></li><li><a href="/wiki/Category:All_pages_needing_cleanup" title="Category:All pages needing cleanup">All pages needing cleanup</a></li><li><a href="/wiki/Category:Articles_with_sections_that_need_to_be_turned_into_prose_from_January_2017" title="Category:Articles with sections that need to be turned into prose from January 2017">Articles with sections that need to be turned into prose from January 2017</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_April_2012" title="Category:Articles needing additional references from April 2012">Articles needing additional references from April 2012</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_December_2008" title="Category:Articles with unsourced statements from December 2008">Articles with unsourced statements from December 2008</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_April_2019" title="Category:Wikipedia articles needing clarification from April 2019">Wikipedia articles needing clarification from April 2019</a></li><li><a href="/wiki/Category:All_accuracy_disputes" title="Category:All accuracy disputes">All accuracy disputes</a></li><li><a href="/wiki/Category:Articles_with_disputed_statements_from_April_2019" title="Category:Articles with disputed statements from April 2019">Articles with disputed statements from April 2019</a></li><li><a href="/wiki/Category:All_Wikipedia_articles_needing_clarification" title="Category:All Wikipedia articles needing clarification">All Wikipedia articles needing clarification</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_April_2011" title="Category:Articles with unsourced statements from April 2011">Articles with unsourced statements from April 2011</a></li></ul></div></div>+				</div>+			</main>+			+		</div>+		<div class="mw-footer-container">+			+<footer id="footer" class="mw-footer" role="contentinfo" >+	<ul id="footer-info">+	<li id="footer-info-lastmod"> This page was last edited on 7 August 2023, at 16:46<span class="anonymous-show">&#160;(UTC)</span>.</li>+	<li id="footer-info-copyright">Text is available under the <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/">Creative Commons Attribution-ShareAlike License 4.0</a><a rel="license" href="//creativecommons.org/licenses/by-sa/4.0/" style="display:none;"></a>;+additional terms may apply.  By using this site, you agree to the <a href="//foundation.wikimedia.org/wiki/Terms_of_Use">Terms of Use</a> and <a href="//foundation.wikimedia.org/wiki/Privacy_policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a href="//www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li>+</ul>++	<ul id="footer-places">+	<li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li>+	<li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li>+	<li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li>+	<li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li>+	<li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Universal_Code_of_Conduct">Code of Conduct</a></li>+	<li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Parsing&amp;mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li>+	<li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li>+	<li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li>+	<li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li>+</ul>++	<ul id="footer-icons" class="noprint">+	<li id="footer-copyrightico"><a href="https://wikimediafoundation.org/"><img src="/static/images/footer/wikimedia-button.png" srcset="/static/images/footer/wikimedia-button-1.5x.png 1.5x, /static/images/footer/wikimedia-button-2x.png 2x" width="88" height="31" alt="Wikimedia Foundation" loading="lazy" /></a></li>+	<li id="footer-poweredbyico"><a href="https://www.mediawiki.org/"><img src="/static/images/footer/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" srcset="/static/images/footer/poweredby_mediawiki_132x47.png 1.5x, /static/images/footer/poweredby_mediawiki_176x62.png 2x" width="88" height="31" loading="lazy"></a></li>+</ul>++</footer>++		</div>+	</div> +</div> +<div class="vector-settings" id="p-dock-bottom">+	<ul>+		<li><button class="cdx-button cdx-button--icon-only vector-limited-width-toggle" id=""><span class="vector-icon mw-ui-icon-fullScreen mw-ui-icon-wikimedia-fullScreen"></span>++<span>Toggle limited content width</span>+</button>+</li>+	</ul>+</div>+<script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw2313","wgBackendResponseTime":110,"wgPageParseReport":{"limitreport":{"cputime":"0.603","walltime":"0.765","ppvisitednodes":{"value":3961,"limit":1000000},"postexpandincludesize":{"value":96252,"limit":2097152},"templateargumentsize":{"value":8887,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":23,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":64929,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00%  660.937      1 -total"," 20.46%  135.235      1 Template:Reflist"," 15.70%  103.756      7 Template:Citation_needed"," 13.96%   92.254      8 Template:Fix"," 12.26%   81.020      2 Template:Navbox"," 11.96%   79.047      1 Template:Parsers"," 11.34%   74.941      2 Template:Cite_web","  9.40%   62.135     12 Template:Delink","  8.23%   54.374      1 Template:Short_description","  8.08%   53.381     21 Template:Category_handler"]},"scribunto":{"limitreport-timeusage":{"value":"0.343","limit":"10.000"},"limitreport-memusage":{"value":5941273,"limit":52428800}},"cachereport":{"origin":"mw2270","timestamp":"20230807164729","ttl":1814400,"transientcontent":false}}});});</script>+<script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Parsing","url":"https:\/\/en.wikipedia.org\/wiki\/Parsing","sameAs":"http:\/\/www.wikidata.org\/entity\/Q194152","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q194152","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-09-02T13:02:50Z","dateModified":"2023-08-07T16:46:42Z","headline":"process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar"}</script><script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Parsing","url":"https:\/\/en.wikipedia.org\/wiki\/Parsing","sameAs":"http:\/\/www.wikidata.org\/entity\/Q194152","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q194152","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-09-02T13:02:50Z","dateModified":"2023-08-07T16:46:42Z","headline":"process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar"}</script>+</body>+</html>

@@ -0,0 +1,10 @@+<!DOCTYPE html>+<html>+<body>++<h1>My First Heading</h1>++<p>My first paragraph.</p>++</body>+</html>

@@ -0,0 +1,43 @@+<svg height="300" viewBox="-0.75 -0.5 1.5 1.0" width="450" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><style>svg {+  color-scheme: light dark;+}+{+  .canvas g, .title g, .axisbar g, .ticktext g, .tickglyph g, .ticklines g, .legendContent g text {+    fill: rgb(5%, 5%, 5%);+  }+  .ticklines g, .tickglyph g, .legendBorder g {+    stroke: rgb(5%, 5%, 5%);+  }+  .legendBorder g {+    fill: rgb(94%, 94%, 94%);+  }+}+@media (prefers-color-scheme:dark) {+  .canvas g, .title g, .axisbar g, .ticktext g, .tickglyph g, .ticklines g, .legendContent g text {+    fill: rgb(94%, 94%, 94%);+  }+  .ticklines g, .tickglyph g, .legendBorder g {+    stroke: rgb(94%, 94%, 94%);+  }+  .legendBorder g {+    fill: rgb(5%, 5%, 5%);+  }+}</style><g class="chart"><g class="line"><g fill="none" stroke="rgb(2%, 73%, 80%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.6059,0.1875 -0.2077,0.1875 0.1905,-0.3537"/></g><g fill="none" stroke="rgb(2%, 29%, 48%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.6059,0.3228 0.5091,-0.0831"/></g><g fill="none" stroke="rgb(66%, 7%, 55%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.4068,-0.2184 -0.4068,0.3228"/></g></g></g><g class="hud"><g class="frame"><g fill="rgb(100%, 100%, 100%)" fill-opacity="0.02" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.6866" width="1.2006" x="-0.6118" y="-0.3588"/></g></g><g class="axis"><g class="ticks"><g class="tickglyph"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.4" stroke-width="0.0040"><g transform="rotate(-90.0, -0.6357, 0.3228)"><polyline points="-0.6357,0.3378+-0.6357,0.3078"/></g><g transform="rotate(-90.0, -0.6357, 0.2551)"><polyline points="-0.6357,0.2701+-0.6357,0.2401"/></g><g transform="rotate(-90.0, -0.6357, 0.1875)"><polyline points="-0.6357,0.2025+-0.6357,0.1725"/></g><g transform="rotate(-90.0, -0.6357, 0.1198)"><polyline points="-0.6357,0.1348+-0.6357,0.1048"/></g><g transform="rotate(-90.0, -0.6357, 0.0522)"><polyline points="-0.6357,0.0672+-0.6357,0.0372"/></g><g transform="rotate(-90.0, -0.6357, -0.0155)"><polyline points="-0.6357,-0.0005+-0.6357,-0.0305"/></g><g transform="rotate(-90.0, -0.6357, -0.0831)"><polyline points="-0.6357,-0.0681+-0.6357,-0.0981"/></g><g transform="rotate(-90.0, -0.6357, -0.1508)"><polyline points="-0.6357,-0.1358+-0.6357,-0.1658"/></g><g transform="rotate(-90.0, -0.6357, -0.2184)"><polyline points="-0.6357,-0.2034+-0.6357,-0.2334"/></g><g transform="rotate(-90.0, -0.6357, -0.2861)"><polyline points="-0.6357,-0.2711+-0.6357,-0.3011"/></g><g transform="rotate(-90.0, -0.6357, -0.3537)"><polyline points="-0.6357,-0.3387+-0.6357,-0.3687"/></g></g></g><g class="ticktext"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="end"><text x="-0.6644" y="0.3321">0.0</text><text x="-0.6644" y="0.2644">0.5</text><text x="-0.6644" y="0.1968">1.0</text><text x="-0.6644" y="0.1291">1.5</text><text x="-0.6644" y="0.0615">2.0</text><text x="-0.6644" y="-0.0062">2.5</text><text x="-0.6644" y="-0.0738">3.0</text><text x="-0.6644" y="-0.1415">3.5</text><text x="-0.6644" y="-0.2091">4.0</text><text x="-0.6644" y="-0.2768">4.5</text><text x="-0.6644" y="-0.3444">5.0</text></g></g><g class="ticklines"><g fill="none" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.05" stroke-width="0.0050"><polyline points="-0.6059,0.3228 0.5887,0.3228"/><polyline points="-0.6059,0.2551 0.5887,0.2551"/><polyline points="-0.6059,0.1875 0.5887,0.1875"/><polyline points="-0.6059,0.1198 0.5887,0.1198"/><polyline points="-0.6059,0.0522 0.5887,0.0522"/><polyline points="-0.6059,-0.0155 0.5887,-0.0155"/><polyline points="-0.6059,-0.0831 0.5887,-0.0831"/><polyline points="-0.6059,-0.1508 0.5887,-0.1508"/><polyline points="-0.6059,-0.2184 0.5887,-0.2184"/><polyline points="-0.6059,-0.2861 0.5887,-0.2861"/><polyline points="-0.6059,-0.3537 0.5887,-0.3537"/></g></g></g><g class="axisbar"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.6792" width="0.0032" x="-0.6230" y="-0.3551"/></g></g></g><g class="axis"><g class="ticks"><g class="tickglyph"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.4" stroke-width="0.0040"><polyline points="-0.6059,0.3631+-0.6059,0.3331"/><polyline points="-0.4068,0.3631+-0.4068,0.3331"/><polyline points="-0.2077,0.3631+-0.2077,0.3331"/><polyline points="-0.0086,0.3631+-0.0086,0.3331"/><polyline points="0.1905,0.3631+0.1905,0.3331"/><polyline points="0.3896,0.3631+0.3896,0.3331"/><polyline points="0.5887,0.3631+0.5887,0.3331"/></g></g><g class="ticktext"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="middle"><text x="-0.6059" y="0.3911">0.0</text><text x="-0.4068" y="0.3911">0.5</text><text x="-0.2077" y="0.3911">1.0</text><text x="-0.0086" y="0.3911">1.5</text><text x="0.1905" y="0.3911">2.0</text><text x="0.3896" y="0.3911">2.5</text><text x="0.5887" y="0.3911">3.0</text></g></g><g class="ticklines"><g fill="none" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.05" stroke-width="0.0050"><polyline points="-0.6059,0.3228 -0.6059,-0.3537"/><polyline points="-0.4068,0.3228 -0.4068,-0.3537"/><polyline points="-0.2077,0.3228 -0.2077,-0.3537"/><polyline points="-0.0086,0.3228 -0.0086,-0.3537"/><polyline points="0.1905,0.3228 0.1905,-0.3537"/><polyline points="0.3896,0.3228 0.3896,-0.3537"/><polyline points="0.5887,0.3228 0.5887,-0.3537"/></g></g></g><g class="axisbar"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.0027" width="1.1978" x="-0.6074" y="0.3346"/></g></g></g><g class="title"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0796" stroke="none" stroke-width="0.0" text-anchor="middle"><text x="-0.0513" y="-0.4188">Line Chart</text></g></g><g class="title"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0478" stroke="none" stroke-width="0.0" text-anchor="end"><text x="0.6156" y="0.4608">Made with love and chart-svg</text></g></g><g class="legend"><g class="legendBorder"><g fill="rgb(99%, 99%, 99%)" fill-opacity="1.0" stroke="rgb(5%, 5%, 5%)" stroke-opacity="1.0" stroke-width="0.0025"><rect height="0.1793" width="0.3843" x="0.3299" y="0.0775"/></g></g><g class="legendContent"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.2297">palette1 2</text></g><g fill="none" stroke="rgb(66%, 7%, 55%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.2213 0.6883,0.2213"/></g><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.1756">palette1 1</text></g><g fill="none" stroke="rgb(2%, 29%, 48%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.1672 0.6883,0.1672"/></g><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.1215">palette1 0</text></g><g fill="none" stroke="rgb(2%, 73%, 80%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.1131 0.6883,0.1131"/></g></g></g><g class="frame"><g fill="rgb(100%, 100%, 100%)" fill-opacity="0.02" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="1.0" width="1.5" x="-0.75" y="-0.5"/></g></g></g></svg>

@@ -0,0 +1,48 @@+<svg height="300" viewBox="-0.75 -0.5 1.5 1.0" width="450" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">+  <style>+    svg {+  color-scheme: light dark;+}+{+  .canvas g, .title g, .axisbar g, .ticktext g, .tickglyph g, .ticklines g, .legendContent g text {+    fill: rgb(5%, 5%, 5%);+  }+  .ticklines g, .tickglyph g, .legendBorder g {+    stroke: rgb(5%, 5%, 5%);+  }+  .legendBorder g {+    fill: rgb(94%, 94%, 94%);+  }+}+@media (prefers-color-scheme:dark) {+  .canvas g, .title g, .axisbar g, .ticktext g, .tickglyph g, .ticklines g, .legendContent g text {+    fill: rgb(94%, 94%, 94%);+  }+  .ticklines g, .tickglyph g, .legendBorder g {+    stroke: rgb(94%, 94%, 94%);+  }+  .legendBorder g {+    fill: rgb(5%, 5%, 5%);+  }+}</style>+  <g class="chart">+    <g class="line">+      <g fill="none" stroke="rgb(2%, 73%, 80%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.6059,0.1875 -0.2077,0.1875 0.1905,-0.3537" /></g><g fill="none" stroke="rgb(2%, 29%, 48%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.6059,0.3228 0.5091,-0.0831" /></g><g fill="none" stroke="rgb(66%, 7%, 55%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.4068,-0.2184 -0.4068,0.3228" /></g></g></g><g class="hud"><g class="frame"><g fill="rgb(100%, 100%, 100%)" fill-opacity="0.02" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.6866" width="1.2006" x="-0.6118" y="-0.3588" /></g></g><g class="axis"><g class="ticks"><g class="tickglyph"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.4" stroke-width="0.0040"><g transform="rotate(-90.0, -0.6357, 0.3228)"><polyline points="-0.6357,0.3378+-0.6357,0.3078" /></g><g transform="rotate(-90.0, -0.6357, 0.2551)"><polyline points="-0.6357,0.2701+-0.6357,0.2401" /></g><g transform="rotate(-90.0, -0.6357, 0.1875)"><polyline points="-0.6357,0.2025+-0.6357,0.1725" /></g><g transform="rotate(-90.0, -0.6357, 0.1198)"><polyline points="-0.6357,0.1348+-0.6357,0.1048" /></g><g transform="rotate(-90.0, -0.6357, 0.0522)"><polyline points="-0.6357,0.0672+-0.6357,0.0372" /></g><g transform="rotate(-90.0, -0.6357, -0.0155)"><polyline points="-0.6357,-0.0005+-0.6357,-0.0305" /></g><g transform="rotate(-90.0, -0.6357, -0.0831)"><polyline points="-0.6357,-0.0681+-0.6357,-0.0981" /></g><g transform="rotate(-90.0, -0.6357, -0.1508)"><polyline points="-0.6357,-0.1358+-0.6357,-0.1658" /></g><g transform="rotate(-90.0, -0.6357, -0.2184)"><polyline points="-0.6357,-0.2034+-0.6357,-0.2334" /></g><g transform="rotate(-90.0, -0.6357, -0.2861)"><polyline points="-0.6357,-0.2711+-0.6357,-0.3011" /></g><g transform="rotate(-90.0, -0.6357, -0.3537)"><polyline points="-0.6357,-0.3387+-0.6357,-0.3687" /></g></g></g><g class="ticktext"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="end"><text x="-0.6644" y="0.3321">0.0</text><text x="-0.6644" y="0.2644">0.5</text><text x="-0.6644" y="0.1968">1.0</text><text x="-0.6644" y="0.1291">1.5</text><text x="-0.6644" y="0.0615">2.0</text><text x="-0.6644" y="-0.0062">2.5</text><text x="-0.6644" y="-0.0738">3.0</text><text x="-0.6644" y="-0.1415">3.5</text><text x="-0.6644" y="-0.2091">4.0</text><text x="-0.6644" y="-0.2768">4.5</text><text x="-0.6644" y="-0.3444">5.0</text></g></g><g class="ticklines"><g fill="none" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.05" stroke-width="0.0050"><polyline points="-0.6059,0.3228 0.5887,0.3228" /><polyline points="-0.6059,0.2551 0.5887,0.2551" /><polyline points="-0.6059,0.1875 0.5887,0.1875" /><polyline points="-0.6059,0.1198 0.5887,0.1198" /><polyline points="-0.6059,0.0522 0.5887,0.0522" /><polyline points="-0.6059,-0.0155 0.5887,-0.0155" /><polyline points="-0.6059,-0.0831 0.5887,-0.0831" /><polyline points="-0.6059,-0.1508 0.5887,-0.1508" /><polyline points="-0.6059,-0.2184 0.5887,-0.2184" /><polyline points="-0.6059,-0.2861 0.5887,-0.2861" /><polyline points="-0.6059,-0.3537 0.5887,-0.3537" /></g></g></g><g class="axisbar"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.6792" width="0.0032" x="-0.6230" y="-0.3551" /></g></g></g><g class="axis"><g class="ticks"><g class="tickglyph"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.4" stroke-width="0.0040"><polyline points="-0.6059,0.3631+-0.6059,0.3331" /><polyline points="-0.4068,0.3631+-0.4068,0.3331" /><polyline points="-0.2077,0.3631+-0.2077,0.3331" /><polyline points="-0.0086,0.3631+-0.0086,0.3331" /><polyline points="0.1905,0.3631+0.1905,0.3331" /><polyline points="0.3896,0.3631+0.3896,0.3331" /><polyline points="0.5887,0.3631+0.5887,0.3331" /></g></g><g class="ticktext"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="middle"><text x="-0.6059" y="0.3911">0.0</text><text x="-0.4068" y="0.3911">0.5</text><text x="-0.2077" y="0.3911">1.0</text><text x="-0.0086" y="0.3911">1.5</text><text x="0.1905" y="0.3911">2.0</text><text x="0.3896" y="0.3911">2.5</text><text x="0.5887" y="0.3911">3.0</text></g></g><g class="ticklines"><g fill="none" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.05" stroke-width="0.0050"><polyline points="-0.6059,0.3228 -0.6059,-0.3537" /><polyline points="-0.4068,0.3228 -0.4068,-0.3537" /><polyline points="-0.2077,0.3228 -0.2077,-0.3537" /><polyline points="-0.0086,0.3228 -0.0086,-0.3537" /><polyline points="0.1905,0.3228 0.1905,-0.3537" /><polyline points="0.3896,0.3228 0.3896,-0.3537" /><polyline points="0.5887,0.3228 0.5887,-0.3537" /></g></g></g><g class="axisbar"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.0027" width="1.1978" x="-0.6074" y="0.3346" /></g></g></g><g class="title"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0796" stroke="none" stroke-width="0.0" text-anchor="middle"><text x="-0.0513" y="-0.4188">Line Chart</text></g></g><g class="title"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0478" stroke="none" stroke-width="0.0" text-anchor="end"><text x="0.6156" y="0.4608">Made with love and chart-svg</text></g></g><g class="legend"><g class="legendBorder"><g fill="rgb(99%, 99%, 99%)" fill-opacity="1.0" stroke="rgb(5%, 5%, 5%)" stroke-opacity="1.0" stroke-width="0.0025"><rect height="0.1793" width="0.3843" x="0.3299" y="0.0775" /></g></g><g class="legendContent"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.2297">palette1 2</text></g><g fill="none" stroke="rgb(66%, 7%, 55%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.2213 0.6883,0.2213" /></g><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.1756">palette1 1</text></g><g fill="none" stroke="rgb(2%, 29%, 48%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.1672 0.6883,0.1672" /></g><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.1215">palette1 0</text></g><g fill="none" stroke="rgb(2%, 73%, 80%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.1131 0.6883,0.1131" /></g></g></g><g class="frame"><g fill="rgb(100%, 100%, 100%)" fill-opacity="0.02" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="1.0" width="1.5" x="-0.75" y="-0.5" /></g></g></g></svg>

@@ -0,0 +1,52 @@+<svg height="300" viewBox="-0.75 -0.5 1.5 1.0" width="450" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">+  <style>svg {+  color-scheme: light dark;+  }+  {+  .canvas g, .title g, .axisbar g, .ticktext g, .tickglyph g, .ticklines g, .legendContent g text {+  fill: rgb(5%, 5%, 5%);+  }+  .ticklines g, .tickglyph g, .legendBorder g {+  stroke: rgb(5%, 5%, 5%);+  }+  .legendBorder g {+  fill: rgb(94%, 94%, 94%);+  }+  }+  @media (prefers-color-scheme:dark) {+  .canvas g, .title g, .axisbar g, .ticktext g, .tickglyph g, .ticklines g, .legendContent g text {+  fill: rgb(94%, 94%, 94%);+  }+  .ticklines g, .tickglyph g, .legendBorder g {+  stroke: rgb(94%, 94%, 94%);+  }+  .legendBorder g {+  fill: rgb(5%, 5%, 5%);+  }+  }</style>+  <g class="chart">+    <g class="line">+      <g fill="none" stroke="rgb(2%, 73%, 80%)" stroke-opacity="1.0" stroke-width="0.0150">+        <polyline points="-0.6059,0.1875 -0.2077,0.1875 0.1905,-0.3537" />+      </g>+      <g fill="none" stroke="rgb(2%, 29%, 48%)" stroke-opacity="1.0" stroke-width="0.0150">+        <polyline points="-0.6059,0.3228 0.5091,-0.0831" />+      </g><g fill="none" stroke="rgb(66%, 7%, 55%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="-0.4068,-0.2184 -0.4068,0.3228" /></g></g></g><g class="hud"><g class="frame"><g fill="rgb(100%, 100%, 100%)" fill-opacity="0.02" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.6866" width="1.2006" x="-0.6118" y="-0.3588" /></g></g><g class="axis"><g class="ticks"><g class="tickglyph"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.4" stroke-width="0.0040"><g transform="rotate(-90.0, -0.6357, 0.3228)"><polyline points="-0.6357,0.3378+  -0.6357,0.3078" /></g><g transform="rotate(-90.0, -0.6357, 0.2551)"><polyline points="-0.6357,0.2701+  -0.6357,0.2401" /></g><g transform="rotate(-90.0, -0.6357, 0.1875)"><polyline points="-0.6357,0.2025+  -0.6357,0.1725" /></g><g transform="rotate(-90.0, -0.6357, 0.1198)"><polyline points="-0.6357,0.1348+  -0.6357,0.1048" /></g><g transform="rotate(-90.0, -0.6357, 0.0522)"><polyline points="-0.6357,0.0672+  -0.6357,0.0372" /></g><g transform="rotate(-90.0, -0.6357, -0.0155)"><polyline points="-0.6357,-0.0005+  -0.6357,-0.0305" /></g><g transform="rotate(-90.0, -0.6357, -0.0831)"><polyline points="-0.6357,-0.0681+  -0.6357,-0.0981" /></g><g transform="rotate(-90.0, -0.6357, -0.1508)"><polyline points="-0.6357,-0.1358+  -0.6357,-0.1658" /></g><g transform="rotate(-90.0, -0.6357, -0.2184)"><polyline points="-0.6357,-0.2034+  -0.6357,-0.2334" /></g><g transform="rotate(-90.0, -0.6357, -0.2861)"><polyline points="-0.6357,-0.2711+  -0.6357,-0.3011" /></g><g transform="rotate(-90.0, -0.6357, -0.3537)"><polyline points="-0.6357,-0.3387+  -0.6357,-0.3687" /></g></g></g><g class="ticktext"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="end"><text x="-0.6644" y="0.3321">0.0</text><text x="-0.6644" y="0.2644">0.5</text><text x="-0.6644" y="0.1968">1.0</text><text x="-0.6644" y="0.1291">1.5</text><text x="-0.6644" y="0.0615">2.0</text><text x="-0.6644" y="-0.0062">2.5</text><text x="-0.6644" y="-0.0738">3.0</text><text x="-0.6644" y="-0.1415">3.5</text><text x="-0.6644" y="-0.2091">4.0</text><text x="-0.6644" y="-0.2768">4.5</text><text x="-0.6644" y="-0.3444">5.0</text></g></g><g class="ticklines"><g fill="none" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.05" stroke-width="0.0050"><polyline points="-0.6059,0.3228 0.5887,0.3228" /><polyline points="-0.6059,0.2551 0.5887,0.2551" /><polyline points="-0.6059,0.1875 0.5887,0.1875" /><polyline points="-0.6059,0.1198 0.5887,0.1198" /><polyline points="-0.6059,0.0522 0.5887,0.0522" /><polyline points="-0.6059,-0.0155 0.5887,-0.0155" /><polyline points="-0.6059,-0.0831 0.5887,-0.0831" /><polyline points="-0.6059,-0.1508 0.5887,-0.1508" /><polyline points="-0.6059,-0.2184 0.5887,-0.2184" /><polyline points="-0.6059,-0.2861 0.5887,-0.2861" /><polyline points="-0.6059,-0.3537 0.5887,-0.3537" /></g></g></g><g class="axisbar"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.6792" width="0.0032" x="-0.6230" y="-0.3551" /></g></g></g><g class="axis"><g class="ticks"><g class="tickglyph"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.4" stroke-width="0.0040"><polyline points="-0.6059,0.3631+  -0.6059,0.3331" /><polyline points="-0.4068,0.3631+  -0.4068,0.3331" /><polyline points="-0.2077,0.3631+  -0.2077,0.3331" /><polyline points="-0.0086,0.3631+  -0.0086,0.3331" /><polyline points="0.1905,0.3631+  0.1905,0.3331" /><polyline points="0.3896,0.3631+  0.3896,0.3331" /><polyline points="0.5887,0.3631+  0.5887,0.3331" /></g></g><g class="ticktext"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="middle"><text x="-0.6059" y="0.3911">0.0</text><text x="-0.4068" y="0.3911">0.5</text><text x="-0.2077" y="0.3911">1.0</text><text x="-0.0086" y="0.3911">1.5</text><text x="0.1905" y="0.3911">2.0</text><text x="0.3896" y="0.3911">2.5</text><text x="0.5887" y="0.3911">3.0</text></g></g><g class="ticklines"><g fill="none" stroke="rgb(5%, 5%, 5%)" stroke-opacity="0.05" stroke-width="0.0050"><polyline points="-0.6059,0.3228 -0.6059,-0.3537" /><polyline points="-0.4068,0.3228 -0.4068,-0.3537" /><polyline points="-0.2077,0.3228 -0.2077,-0.3537" /><polyline points="-0.0086,0.3228 -0.0086,-0.3537" /><polyline points="0.1905,0.3228 0.1905,-0.3537" /><polyline points="0.3896,0.3228 0.3896,-0.3537" /><polyline points="0.5887,0.3228 0.5887,-0.3537" /></g></g></g><g class="axisbar"><g fill="rgb(5%, 5%, 5%)" fill-opacity="0.4" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="0.0027" width="1.1978" x="-0.6074" y="0.3346" /></g></g></g><g class="title"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0796" stroke="none" stroke-width="0.0" text-anchor="middle"><text x="-0.0513" y="-0.4188">Line Chart</text></g></g><g class="title"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0478" stroke="none" stroke-width="0.0" text-anchor="end"><text x="0.6156" y="0.4608">Made with love and chart-svg</text></g></g><g class="legend"><g class="legendBorder"><g fill="rgb(99%, 99%, 99%)" fill-opacity="1.0" stroke="rgb(5%, 5%, 5%)" stroke-opacity="1.0" stroke-width="0.0025"><rect height="0.1793" width="0.3843" x="0.3299" y="0.0775" /></g></g><g class="legendContent"><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.2297">palette1 2</text></g><g fill="none" stroke="rgb(66%, 7%, 55%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.2213 0.6883,0.2213" /></g><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.1756">palette1 1</text></g><g fill="none" stroke="rgb(2%, 29%, 48%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.1672 0.6883,0.1672" /></g><g fill="rgb(5%, 5%, 5%)" fill-opacity="1.0" font-size="0.0398" stroke="none" stroke-width="0.0" text-anchor="start"><text x="0.3498" y="0.1215">palette1 0</text></g><g fill="none" stroke="rgb(2%, 73%, 80%)" stroke-opacity="1.0" stroke-width="0.0150"><polyline points="0.5688,0.1131 0.6883,0.1131" /></g></g></g><g class="frame"><g fill="rgb(100%, 100%, 100%)" fill-opacity="0.02" stroke="rgb(0%, 0%, 0%)" stroke-opacity="0" stroke-width="0"><rect height="1.0" width="1.5" x="-0.75" y="-0.5" /></g></g></g></svg>

@@ -0,0 +1,192 @@+* markup-parse++[[https://hackage.haskell.org/package/markup-parse][https://img.shields.io/hackage/v/markup-parse.svg]]+[[https://github.com/tonyday567/markup-parse/actions?query=workflow%3Ahaskell-ci][https://github.com/tonyday567/markup-parse/workflows/haskell-ci/badge.svg]]++~markup-parse~ parses and prints a subset of common XML & HTML data.++* Development++#+begin_src haskell :results output+:r+:set prompt "> "+:set -Wno-type-defaults+:set -Wno-name-shadowing+:set -XOverloadedStrings+:set -XTemplateHaskell+:set -XQuasiQuotes+import Control.Monad+import MarkupParse+import MarkupParse.FlatParse+import Data.Map.Strict qualified as Map+import MarkupParse.Patch+import Data.ByteString qualified as B+import Data.ByteString.Char8 qualified as C+import Data.Function+import FlatParse.Basic hiding (take)+import Data.String.Interpolate+import Data.TreeDiff+import Control.Monad+-- import Perf+bs <- B.readFile "other/line.svg"+C.length bs+#+end_src++#+RESULTS:+: Ok, three modules loaded.+: >+: >+: 7554++* Main Pipeline++#+begin_src haskell :results output+:t tokenize Html+:t gather Html+:t Markup Html+:t normalize+:t tokenize Html >=> gather Html >>> fmap (Markup Html >>> normalize) >=> degather >>> fmap (fmap (detokenize Html) >>> mconcat)+:t detokenize Html+#+end_src++#+RESULTS:+: tokenize Html :: ByteString -> These [MarkupWarning] [Token]+: gather Html :: [Token] -> These [MarkupWarning] [Tree Token]+: Markup Html :: [Tree Token] -> Markup+: normalize :: Markup -> Markup+: tokenize Html >=> gather Html >>> fmap (Markup Html >>> normalize) >=> degather >>> fmap (fmap (detokenize Html) >>> mconcat)+:   :: ByteString -> These [MarkupWarning] ByteString+: detokenize Html :: Token -> ByteString++Round trip equality++#+begin_src haskell :results output+m = markup_ Xml bs+m == (markup_ Xml $ markdown Compact m)+#+end_src++#+RESULTS:+: True++* MarkupParse.Patch++Obviously doesn't belong here long-term but has been very useful in testing and development.++#+begin_src haskell :results output+show $ ansiWlEditExpr <$> patch [1, 2, 3, 5] [0, 1, 2, 4, 6]+#+end_src++#+RESULTS:+: Just [+0, -3, +4, -5, +6]++* wiki diff test debug++#+begin_src haskell :results output+bs <- B.readFile "other/Parsing - Wikipedia.html"+m = markup_ Html bs+m == (markup_ Html $ markdown Compact m)+#+end_src++#+RESULTS:+: True++* Reference+** Html Standards++[[https://html.spec.whatwg.org/multipage/syntax.html#elements-2:void-elements-2][HTML Standard]]++[[https://developer.mozilla.org/en-US/docs/Glossary/Void_element#self-closing_tags][void elements]]++[[https://stackoverflow.com/questions/3558119/are-non-void-self-closing-tags-valid-in-html5][html - Are (non-void) self-closing tags valid in HTML5? - Stack Overflow]]++[[https://www.w3.org/TR/2017/REC-html52-20171214/syntax.html#tree-construction][HTML 5.2: 8. The HTML syntax]]++** Prior Art++attoparsec-based+https://hackage.haskell.org/package/html-parse++event-based+https://hackage.haskell.org/package/xeno++parsec-based+https://hackage.haskell.org/package/XMLParser++https://hackage.haskell.org/package/hexml++* Performance++Most testing has been via app/speed.hs++#+begin_src elisp+(setq haskell-process-args-cabal-repl '("markup-parse:bench:markup-parse-speed"))+#+end_src++#+RESULTS:+| markup-parse:bench:markup-parse-speed |++** Benchmarks++#+begin_src sh :results output+cabal run markup-parser-speed+#+end_src++#+RESULTS:++++** Profiling++#+begin_src sh :results output+cabal configure --enable-library-profiling --enable-executable-profiling -fprof-auto -fprof --write-ghc-environment-files=always --enable-benchmarks -O2+#+end_src++cabal.project.local++#+begin_example+write-ghc-environment-files: always+ignore-project: False+flags: +prof +prof-auto+library-profiling: True+executable-profiling: True+#+end_example+++Profiling slowed the main functions significantly:++#+begin_example+./app/speed -n 1000 --best -c +RTS -s -p -hc -l -RTS+label1              label2              old_result          new_result          status++gather              time                2.08e4              3.01e4              degraded+html-parse tokens   time                4.70e5              1.72e6              degraded+html-parse tree     time                2.30e4              3.85e4              degraded+markdown            time                3.51e5              5.70e5              degraded+markup              time                2.10e5              1.05e6              degraded+normalize           time                8.43e4              1.90e5              degraded+tokenize            time                1.94e5              1.02e6              degraded+   4,520,989,296 bytes allocated in the heap+   2,668,887,592 bytes copied during GC+     287,122,272 bytes maximum residency (21 sample(s))+       1,572,000 bytes maximum slop+             560 MiB total memory in use (0 MiB lost due to fragmentation)++                                     Tot time (elapsed)  Avg pause  Max pause+  Gen  0      1073 colls,     0 par    0.471s   0.479s     0.0004s    0.0024s+  Gen  1        21 colls,     0 par    2.428s   2.575s     0.1226s    0.3303s++  INIT    time    0.007s  (  0.008s elapsed)+  MUT     time    2.142s  (  1.945s elapsed)+  GC      time    1.904s  (  2.071s elapsed)+  RP      time    0.000s  (  0.000s elapsed)+  PROF    time    0.995s  (  0.982s elapsed)+  EXIT    time    0.026s  (  0.000s elapsed)+  Total   time    5.074s  (  5.006s elapsed)++  %GC     time       0.0%  (0.0% elapsed)++  Alloc rate    2,110,654,040 bytes per MUT second++  Productivity  61.8% of total user, 58.5% of total elapsed+#+end_example+

@@ -1,14 +1,18 @@ {-# LANGUAGE DeriveAnyClass #-}+{-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE QuasiQuotes #-} {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE TypeFamilies #-} --- | A 'Markup' parser and printer of strict bytestrings. 'Markup' is a representation of data such as HTML, SVG or XML but the parsing is sub-standard.+-- | A 'Markup' parser and printer of strict 'ByteString's focused on optimising performance. 'Markup' is a representation of data such as HTML, SVG or XML but the parsing is not always at standards. module MarkupParse-  ( -- $usage+  ( -- * Usage +    --+    -- $usage+     -- * Markup     Markup (..),     Standard (..),@@ -16,31 +20,46 @@     markup_,     RenderStyle (..),     markdown,+    markdown_,     normalize,+    normContent,     wellFormed,     isWellFormed,      -- * Warnings     MarkupWarning (..),-    Result,-    resultError,-    resultEither,-    resultMaybe,+    Warn,+    warnError,+    warnEither,+    warnMaybe, +    -- * element creation+    Element,+    element,+    element_,+    emptyElem,+    elementc,+    content,+    contentRaw,+     -- * Token components-    TagName,-    name,+    NameTag,     selfClosers,+    addAttrs,+    doctypeHtml,+    doctypeXml,     AttrName,     AttrValue,     Attr (..),-    attrs,+    attrsP,+    nameP,      -- * Tokens+    OpenTagType (..),     Token (..),     tokenize,     tokenize_,-    token,+    tokenP,     detokenize,     gather,     gather_,@@ -48,12 +67,21 @@     degather_,      -- * XML specific Parsers-    xmlVersionInfo,-    xmlEncodingDecl,-    xmlStandalone,-    xmlVersionNum,-    xmlEncName,-    xmlYesNo,+    xmlVersionInfoP,+    xmlEncodingDeclP,+    xmlStandaloneP,+    xmlVersionNumP,+    xmlEncNameP,+    xmlYesNoP,++    -- * bytestring support+    utf8ToStr,+    strToUtf8,+    escapeChar,+    escape,++    -- * Tree support+    Tree (..),   ) where @@ -99,25 +127,34 @@ -- > bs <- B.readFile "other/line.svg" -- > m = markup_ bs ----- @'markdown' . ''markup_'@ is an approximate round trip from 'ByteString' to 'Markup' back to ByteString'. The underscores represent versions of main functions that throw an exception on warnings encountered along the way.+-- @'markdown_' . 'markup_'@ is an isomorphic round trip from 'Markup' to 'ByteString' to 'Markup': --+-- - This is subject to the Markup being 'wellFormed'.+--+-- - The round-trip @'markup_' . 'markdown_'@ is not isomorphic as parsing forgets whitespace within tags, comments and declarations.+--+-- - The underscores represent versions of main functions that throw an exception on warnings encountered along the way.+-- -- At a lower level, a round trip pipeline might look something like: ----- > :t tokenize Html >=> gather Html >>> fmap (Markup Html >>> normalize) >=> degather >>> fmap (fmap (detokenize Html) >>> mconcat)--- > ByteString -> These [MarkupWarning] ByteString+-- > tokenize Html >=> ----- From left to right:+-- - 'tokenize' converts a 'ByteString' to a 'Token' list. ----- - 'tokenize' converts a 'ByteString' to a 'Token' list,+-- > gather Html >=> ----- - 'gather' takes the tokens and gathers them into 'Tree's of tokens+-- - 'gather' takes the tokens and gathers them into 'Tree's of 'Token's which is what 'Markup' is. ----- - this is then wrapped into the 'Markup' data type.+-- > (normalize >>> pure) >=> -- -- - 'normalize' concatenates content, and normalizes attributes, --+-- > degather >=>+-- -- - 'degather' turns the markup tree back into a token list. Finally, --+-- > fmap (detokenize Html) >>> pure+-- -- - 'detokenize' turns a token back into a bytestring. -- -- Along the way, the kleisi fishies and compose forward usage accumulates any warnings via the 'These' monad instance.@@ -127,17 +164,16 @@ -- The xml parsing logic is based on the XML productions found in https://www.w3.org/TR/xml/ -- -- The html parsing was based on a reading of <https://hackage.haskell.org/package/html-parse html-parse>, but ignores the various '\x00' to '\xfffd' & eof directives that form part of the html standards.-data Standard = Html | Xml deriving (Eq, Show, Ord, Generic, NFData)--instance ToExpr Standard+data Standard = Html | Xml deriving (Eq, Show, Ord, Generic, NFData, ToExpr) --- | A 'Tree' list of markup 'Token's+-- | A list of 'Element's or 'Tree' 'Token's -- -- >>> markup Html "<foo class=\"bar\">baz</foo>"--- That (Markup {standard = Html, markupTree = [Node {rootLabel = StartTag "foo" [Attr "class" "bar"], subForest = [Node {rootLabel = Content "baz", subForest = []}]}]})-data Markup = Markup {standard :: Standard, markupTree :: [Tree Token]} deriving (Show, Eq, Ord, Generic, NFData)--instance ToExpr Markup+-- That (Markup {elements = [Node {rootLabel = OpenTag StartTag "foo" [Attr {attrName = "class", attrValue = "bar"}], subForest = [Node {rootLabel = Content "baz", subForest = []}]}]})+newtype Markup = Markup {elements :: [Element]}+  deriving stock (Show, Eq, Ord, Generic)+  deriving anyclass (NFData, ToExpr)+  deriving newtype (Semigroup, Monoid)  -- | markup-parse generally tries to continue on parse errors, and return what has/can still be parsed, together with any warnings. data MarkupWarning@@ -148,7 +184,7 @@   | -- | Only a 'StartTag' can have child tokens.     LeafWithChildren   | -- | A CloseTag with a different name to the currently open StartTag.-    TagMismatch TagName TagName+    TagMismatch NameTag NameTag   | -- | An EndTag with no corresponding StartTag.     UnmatchedEndTag   | -- | An EndTag with corresponding StartTag.@@ -157,150 +193,191 @@     EndTagInTree   | -- | Empty Content, Comment, Decl or Doctype     EmptyContent+  | -- | Badly formed declaration+    BadDecl   | MarkupParser ParserWarning   deriving (Eq, Show, Ord, Generic, NFData)  showWarnings :: [MarkupWarning] -> String showWarnings = List.nub >>> fmap show >>> unlines --- | The structure of many returning functions.------ A common computation pipeline is to take advantage of the 'These' Monad instance eg+-- | A type synonym for the common returning type of many functions. A common computation pipeline is to take advantage of the 'These' Monad instance eg -- -- > markup s bs = bs & (tokenize s >=> gather s) & second (Markup s)-type Result a = These [MarkupWarning] a+type Warn a = These [MarkupWarning] a  -- | Convert any warnings to an 'error' ----- >>> resultError $ (tokenize Html) "<foo"+-- >>> warnError $ (tokenize Html) "<foo" -- *** Exception: MarkupParser (ParserLeftover "<foo") -- ...-resultError :: Result a -> a-resultError = these (showWarnings >>> error) id (\xs a -> bool (error (showWarnings xs)) a (xs == []))+warnError :: Warn a -> a+warnError = these (showWarnings >>> error) id (\xs a -> bool (error (showWarnings xs)) a (xs == []))  -- | Returns Left on any warnings ----- >>> resultEither $ (tokenize Html) "<foo><baz"+-- >>> warnEither $ (tokenize Html) "<foo><baz" -- Left [MarkupParser (ParserLeftover "<baz")]-resultEither :: Result a -> Either [MarkupWarning] a-resultEither = these Left Right (\xs a -> bool (Left xs) (Right a) (xs == []))+warnEither :: Warn a -> Either [MarkupWarning] a+warnEither = these Left Right (\xs a -> bool (Left xs) (Right a) (xs == [])) --- | Returns results if any, ignoring warnings.+-- | Returns results, if any, ignoring warnings. ----- >>> resultMaybe $ (tokenize Html) "<foo><baz"--- Just [StartTag "foo" []]-resultMaybe :: Result a -> Maybe a-resultMaybe = these (const Nothing) Just (\_ a -> Just a)+-- >>> warnMaybe $ (tokenize Html) "<foo><baz"+-- Just [OpenTag StartTag "foo" []]+warnMaybe :: Warn a -> Maybe a+warnMaybe = these (const Nothing) Just (\_ a -> Just a)  -- | Convert bytestrings to 'Markup' -- -- >>> markup Html "<foo><br></foo><baz"--- These [MarkupParser (ParserLeftover "<baz")] (Markup {standard = Html, markupTree = [Node {rootLabel = StartTag "foo" [], subForest = [Node {rootLabel = StartTag "br" [], subForest = []}]}]})-markup :: Standard -> ByteString -> These [MarkupWarning] Markup-markup s bs = bs & (tokenize s >=> gather s) & second (Markup s)+-- These [MarkupParser (ParserLeftover "<baz")] (Markup {elements = [Node {rootLabel = OpenTag StartTag "foo" [], subForest = [Node {rootLabel = OpenTag StartTag "br" [], subForest = []}]}]})+markup :: Standard -> ByteString -> Warn Markup+markup s bs = bs & (tokenize s >=> gather s)  -- | markup but errors on warnings. markup_ :: Standard -> ByteString -> Markup-markup_ s bs = markup s bs & resultError+markup_ s bs = markup s bs & warnError --- | concatenate sequential content, and normalize attributes; unwording class values and removing duplicate attributes (taking last).+-- | Concatenate sequential content and normalize attributes; unwording class values and removing duplicate attributes (taking last). ----- >>> B.putStr $ markdown Compact $ normalize (markup_ Xml [i|<foo class="a" class="b" bar="first" bar="last"/>|])+-- >>> B.putStr $ warnError $ markdown Compact Xml $ normalize (markup_ Xml [i|<foo class="a" class="b" bar="first" bar="last"/>|]) -- <foo bar="last" class="a b"/> normalize :: Markup -> Markup-normalize (Markup s trees) = Markup s (normContentTrees $ fmap (fmap normTokenAttrs) trees)+normalize m = normContent $ Markup $ fmap (fmap normTokenAttrs) (elements m)  -- | Are the trees in the markup well-formed?-isWellFormed :: Markup -> Bool-isWellFormed = (== []) . wellFormed+isWellFormed :: Standard -> Markup -> Bool+isWellFormed s = (== []) . wellFormed s --- | Check for well-formedness and rerturn warnings encountered.+-- | Check for well-formedness and return warnings encountered. ----- >>> wellFormed $ Markup Html [Node (Comment "") [], Node (EndTag "foo") [], Node (EmptyElemTag "foo" []) [Node (Content "bar") []], Node (EmptyElemTag "foo" []) []]+-- >>> wellFormed Html $ Markup [Node (Comment "") [], Node (EndTag "foo") [], Node (OpenTag EmptyElemTag "foo" []) [Node (Content "bar") []], Node (OpenTag EmptyElemTag "foo" []) []] -- [EmptyContent,EndTagInTree,LeafWithChildren,BadEmptyElemTag]-wellFormed :: Markup -> [MarkupWarning]-wellFormed (Markup s trees) = List.nub $ mconcat (foldTree checkNode <$> trees)+wellFormed :: Standard -> Markup -> [MarkupWarning]+wellFormed s (Markup trees) = List.nub $ mconcat (foldTree checkNode <$> trees)   where-    checkNode (StartTag _ _) xs = mconcat xs-    checkNode (EmptyElemTag n _) [] =+    checkNode (OpenTag StartTag _ _) xs = mconcat xs+    checkNode (OpenTag EmptyElemTag n _) [] =       bool [] [BadEmptyElemTag] (not (n `elem` selfClosers) && s == Html)     checkNode (EndTag _) [] = [EndTagInTree]     checkNode (Content bs) [] = bool [] [EmptyContent] (bs == "")     checkNode (Comment bs) [] = bool [] [EmptyContent] (bs == "")-    checkNode (Decl bs) [] = bool [] [EmptyContent] (bs == "")+    checkNode (Decl bs as) []+      | bs == "" = [EmptyContent]+      | s == Html && as /= [] = [BadDecl]+      | s == Xml && ("version" `elem` (attrName <$> as)) && ("encoding" `elem` (attrName <$> as)) =+          [BadDecl]+      | otherwise = []     checkNode (Doctype bs) [] = bool [] [EmptyContent] (bs == "")     checkNode _ _ = [LeafWithChildren]  -- | Name of token-type TagName = ByteString+type NameTag = ByteString +-- | Whether an opening tag is a start tag or an empty element tag.+data OpenTagType = StartTag | EmptyElemTag deriving (Show, Ord, Eq, Generic, NFData, ToExpr)+ -- | A Markup token ----- >>> runParser_ (many (token Html)) [i|<foo>content</foo>|]--- [StartTag "foo" [],Content "content",EndTag "foo"]+-- >>> runParser_ (many (tokenP Html)) [i|<foo>content</foo>|]+-- [OpenTag StartTag "foo" [],Content "content",EndTag "foo"] ----- >>> runParser_ (token Xml) [i|<foo/>|]--- EmptyElemTag "foo" []+-- >>> runParser_ (tokenP Xml) [i|<foo/>|]+-- OpenTag EmptyElemTag "foo" [] ----- >>> runParser_ (token Html) "<!-- Comment -->"+-- >>> runParser_ (tokenP Html) "<!-- Comment -->" -- Comment " Comment " ----- >>> runParser_ (token Xml) [i|<?xml version="1.0" encoding="UTF-8"?>|]--- Decl "xml version=\"1.0\" encoding=\"UTF-8\""+-- >>> runParser_ (tokenP Xml) [i|<?xml version="1.0" encoding="UTF-8"?>|]+-- Decl "xml" [Attr {attrName = "version", attrValue = " version=\"1.0\""},Attr {attrName = "encoding", attrValue = "UTF-8"}] ----- >>> runParser_ (token Html) "<!DOCTYPE html>"+-- >>> runParser_ (tokenP Html) "<!DOCTYPE html>" -- Doctype "DOCTYPE html" ----- >>> runParser_ (token Xml) "<!DOCTYPE foo [ declarations ]>"+-- >>> runParser_ (tokenP Xml) "<!DOCTYPE foo [ declarations ]>" -- Doctype "DOCTYPE foo [ declarations ]" ----- >>> runParser (token Html) [i|<foo a="a" b="b" c=c check>|]--- OK (StartTag "foo" [Attr "a" "a",Attr "b" "b",Attr "c" "c",Attr "check" ""]) ""+-- >>> runParser (tokenP Html) [i|<foo a="a" b="b" c=c check>|]+-- OK (OpenTag StartTag "foo" [Attr {attrName = "a", attrValue = "a"},Attr {attrName = "b", attrValue = "b"},Attr {attrName = "c", attrValue = "c"},Attr {attrName = "check", attrValue = ""}]) "" ----- >>> runParser (token Xml) [i|<foo a="a" b="b" c=c check>|]+-- >>> runParser (tokenP Xml) [i|<foo a="a" b="b" c=c check>|] -- Fail data Token-  = -- | A start tag. https://developer.mozilla.org/en-US/docs/Glossary/Tag-    StartTag !TagName ![Attr]-  | -- | An empty element tag. Optional for XML and kind of not allowed in HTML.-    EmptyElemTag !TagName ![Attr]+  = -- | A tag. https://developer.mozilla.org/en-US/docs/Glossary/Tag+    OpenTag !OpenTagType !NameTag ![Attr]   | -- | A closing tag.-    EndTag !TagName+    EndTag !NameTag   | -- | The content between tags.     Content !ByteString   | -- | Contents of a comment.     Comment !ByteString   | -- | Contents of a declaration-    Decl !ByteString+    Decl !ByteString ![Attr]   | -- | Contents of a doctype declaration.     Doctype !ByteString-  deriving (Show, Ord, Eq, Generic)+  deriving (Show, Ord, Eq, Generic, NFData, ToExpr) -instance NFData Token+-- | Escape a single character.+escapeChar :: Char -> ByteString+escapeChar '<' = "&lt"+escapeChar '>' = "&gt"+escapeChar '&' = "&amp"+escapeChar '\'' = "&apos"+escapeChar '"' = "&quot"+escapeChar x = B.singleton x -instance ToExpr Token+-- | Escape Content+--+-- >>> escape [i|<foo class="a" bar='b'>|]+-- "&ltfoo class=&quota&quot bar=&aposb&apos&gt"+escape :: ByteString -> ByteString+escape bs = B.concatMap escapeChar bs +-- | Append attributes to the existing Token attribute list.+addAttrs :: [Attr] -> Token -> Maybe Token+addAttrs as (OpenTag t n as') = Just $ OpenTag t n (as <> as')+addAttrs _ _ = Nothing++-- | Standard Html Doctype+--+-- >>> markdown_ Compact Html doctypeHtml+-- "<!DOCTYPE html>"+doctypeHtml :: Markup+doctypeHtml = Markup $ pure $ pure (Doctype "DOCTYPE html")++-- | Standard Xml Doctype+--+-- >>> markdown_ Compact Xml doctypeXml+-- "<?xml version=\"1.0\" encoding=\"utf-8\"?><!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n    \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">"+doctypeXml :: Markup+doctypeXml =+  Markup+    [ pure $ Decl "xml" [Attr "version" "1.0", Attr "encoding" "utf-8"],+      pure $ Doctype "DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n    \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\""+    ]+ -- | A flatparse 'Token' parser. ----- >>> runParser (token Html) "<foo>content</foo>"--- OK (StartTag "foo" []) "content</foo>"-token :: Standard -> Parser String Token-token Html = tokenHtml-token Xml = tokenXml+-- >>> runParser (tokenP Html) "<foo>content</foo>"+-- OK (OpenTag StartTag "foo" []) "content</foo>"+tokenP :: Standard -> Parser e Token+tokenP Html = tokenHtmlP+tokenP Xml = tokenXmlP  -- | Parse a bytestring into tokens -- -- >>> tokenize Html [i|<foo>content</foo>|]--- That [StartTag "foo" [],Content "content",EndTag "foo"]-tokenize :: Standard -> ByteString -> These [MarkupWarning] [Token]-tokenize s bs = first ((: []) . MarkupParser) $ runParserWarn (many (token s)) bs+-- That [OpenTag StartTag "foo" [],Content "content",EndTag "foo"]+tokenize :: Standard -> ByteString -> Warn [Token]+tokenize s bs = first ((: []) . MarkupParser) $ runParserWarn (many (tokenP s)) bs  -- | tokenize but errors on warnings. tokenize_ :: Standard -> ByteString -> [Token]-tokenize_ s bs = tokenize s bs & resultError+tokenize_ s bs = tokenize s bs & warnError  -- | Html tags that self-close-selfClosers :: [TagName]+selfClosers :: [NameTag] selfClosers =   [ "area",     "base",@@ -318,6 +395,55 @@     "wbr"   ] +-- | Most functions return a 'Markup' rather than an 'Element' because it is more ergonimc to use the free monoid wrap (aka a list) in preference to returning a 'Maybe Element', say.+type Element = Tree Token++-- | Create a Markup element from a NameTag and attributes that wraps some other Markup.+--+-- >>> element "div" [] (element_ "br" [])+-- Markup {elements = [Node {rootLabel = OpenTag StartTag "div" [], subForest = [Node {rootLabel = OpenTag StartTag "br" [], subForest = []}]}]}+element :: NameTag -> [Attr] -> Markup -> Markup+element n as (Markup xs) = Markup [Node (OpenTag StartTag n as) xs]++-- | Create a Markup element from a NameTag and attributes that doesn't wrap some other Markup. OpenTagType is StartTag. Use 'emptyElem' if you want to create a EmptyElemTag.+--+-- >>> (element_ "br" [])+-- Markup {elements = [Node {rootLabel = OpenTag StartTag "br" [], subForest = []}]}+element_ :: NameTag -> [Attr] -> Markup+element_ n as = Markup [Node (OpenTag StartTag n as) []]++-- | Create a Markup element from a NameTag and attributes using EmptyElemTag, that doesn't wrap some other Markup. No checks are made on whether this creates well-formed Markup.+--+-- >>> emptyElem "br" []+-- Markup {elements = [Node {rootLabel = OpenTag EmptyElemTag "br" [], subForest = []}]}+emptyElem :: NameTag -> [Attr] -> Markup+emptyElem n as = Markup [Node (OpenTag EmptyElemTag n as) []]++-- | Create a Markup element from a NameTag and attributes that wraps some 'Content'.+--+-- >>> elementc "div" [] "content"+-- Markup {elements = [Node {rootLabel = OpenTag StartTag "div" [], subForest = [Node {rootLabel = Content "content", subForest = []}]}]}+elementc :: NameTag -> [Attr] -> ByteString -> Markup+elementc n as bs = element n as (content bs)++-- | Create a Markup element from a bytestring, escaping the usual characters.+--+-- >>> content "<content>"+-- Markup {elements = [Node {rootLabel = Content "&ltcontent&gt", subForest = []}]}+content :: ByteString -> Markup+content bs = Markup [pure $ Content (escape bs)]++-- | Create a Markup element from a bytestring, not escaping the usual characters.+--+-- >>> contentRaw "<content>"+-- Markup {elements = [Node {rootLabel = Content "<content>", subForest = []}]}+--+-- >>> markup_ Html $ markdown_ Compact Html $ contentRaw "<content>"+-- *** Exception: UnclosedTag+-- ...+contentRaw :: ByteString -> Markup+contentRaw bs = Markup [pure $ Content bs]+ -- | Name of an attribute. type AttrName = ByteString @@ -331,7 +457,7 @@ -- -- >>> detokenize Html <$> tokenize_ Html [i|<input checked>|] -- ["<input checked=\"\">"]-data Attr = Attr !AttrName !AttrValue+data Attr = Attr {attrName :: !AttrName, attrValue :: !AttrValue}   deriving (Generic, Show, Eq, Ord)  instance NFData Attr@@ -339,8 +465,7 @@ instance ToExpr Attr  normTokenAttrs :: Token -> Token-normTokenAttrs (StartTag n as) = StartTag n (normAttrs as)-normTokenAttrs (EmptyElemTag n as) = EmptyElemTag n (normAttrs as)+normTokenAttrs (OpenTag t n as) = OpenTag t n (normAttrs as) normTokenAttrs x = x  -- | normalize an attribution list, removing duplicate AttrNames, and space concatenating class values.@@ -366,7 +491,8 @@  -- | render attributes renderAttrs :: [Attr] -> ByteString-renderAttrs = B.unwords . fmap renderAttr+renderAttrs [] = mempty+renderAttrs xs = B.singleton ' ' <> (B.unwords . fmap renderAttr $ xs)  -- | render an attribute --@@ -374,39 +500,24 @@ renderAttr :: Attr -> ByteString renderAttr (Attr k v) = [i|#{k}="#{v}"|] -commentClose :: Parser e ()-commentClose = $(string "-->")--charNotMinus :: Parser e ByteString-charNotMinus = byteStringOf $ satisfy (/= '-')--minusPlusChar :: Parser e ByteString-minusPlusChar = byteStringOf ($(char '-') *> charNotMinus)--comment :: Parser e Token-comment = Comment <$> byteStringOf (many (charNotMinus <|> minusPlusChar)) <* commentClose--content :: Parser e Token-content = Content <$> byteStringOf (some (satisfy (/= '<')))- -- | bytestring representation of 'Token'. ----- >>> detokenize Html (StartTag "foo" [])+-- >>> detokenize Html (OpenTag StartTag "foo" []) -- "<foo>" detokenize :: Standard -> Token -> ByteString detokenize s = \case-  (StartTag n []) -> [i|<#{n}>|]-  (StartTag n as) -> [i|<#{n} #{renderAttrs as}>|]-  (EmptyElemTag n as) ->+  (OpenTag StartTag n []) -> [i|<#{n}>|]+  (OpenTag StartTag n as) -> [i|<#{n}#{renderAttrs as}>|]+  (OpenTag EmptyElemTag n as) ->     bool-      [i|<#{n} #{renderAttrs as}/>|]-      [i|<#{n} #{renderAttrs as} />|]+      [i|<#{n}#{renderAttrs as}/>|]+      [i|<#{n}#{renderAttrs as} />|]       (s == Html)   (EndTag n) -> [i|</#{n}>|]   (Content t) -> t   (Comment t) -> [i|<!--#{t}-->|]   (Doctype t) -> [i|<!#{t}>|]-  (Decl t) -> bool [i|<?#{t}?>|] [i|<!#{t}!>|] (s == Html)+  (Decl t as) -> bool [i|<?#{t}#{renderAttrs as}?>|] [i|<!#{t}!>|] (s == Html)  -- | Indented 0 puts newlines in between the tags. data RenderStyle = Compact | Indented Int deriving (Eq, Show, Generic)@@ -424,27 +535,38 @@  -- | Convert 'Markup' to bytestrings ----- >>> B.putStr $ markdown (Indented 4) (markup_ Html [i|<foo><br></foo>|])+-- >>> markdown (Indented 4) Html (markup_ Html [i|<foo><br></foo>|])+-- That "<foo>\n    <br>\n</foo>"+markdown :: RenderStyle -> Standard -> Markup -> Warn ByteString+markdown r s m = second (finalConcat r) $ concatWarns $ foldTree (renderBranch r s) <$> (elements $ normContent m)++-- | Convert 'Markup' to 'ByteString' and error on warnings.+--+-- >>> B.putStr $ markdown_ (Indented 4) Html (markup_ Html [i|<foo><br></foo>|]) -- <foo> --     <br> -- </foo>-markdown :: RenderStyle -> Markup -> ByteString-markdown r (Markup std tree) =-  finalConcat r $ mconcat $ foldTree (renderBranch r std) <$> normContentTrees tree+markdown_ :: RenderStyle -> Standard -> Markup -> ByteString+markdown_ r s = markdown r s >>> warnError  -- note that renderBranch adds in EndTags for StartTags when needed-renderBranch :: RenderStyle -> Standard -> Token -> [[ByteString]] -> [ByteString]-renderBranch r std s@(StartTag n _) children+renderBranch :: RenderStyle -> Standard -> Token -> [Warn [ByteString]] -> Warn [ByteString]+renderBranch r std s@(OpenTag StartTag n _) xs   | n `elem` selfClosers && std == Html =-      [detokenize std s] <> indentChildren r (mconcat children)+      That [detokenize std s] <> second (indentChildren r) (concatWarns xs)   | otherwise =-      [detokenize std s] <> indentChildren r (mconcat children) <> [detokenize std (EndTag n)]-renderBranch r std x children =-  -- ignoring that this should be an error-  [detokenize std x] <> indentChildren r (mconcat children)+      That [detokenize std s] <> second (indentChildren r) (concatWarns xs) <> That [detokenize std (EndTag n)]+renderBranch _ std x [] =+  That [detokenize std x]+renderBranch r std x xs =+  These [LeafWithChildren] [detokenize std x] <> second (indentChildren r) (concatWarns xs) -normContentTrees :: [Tree Token] -> [Tree Token]-normContentTrees trees = foldTree (\x xs -> Node x (filter ((/= Content "") . rootLabel) $ concatContent xs)) <$> concatContent trees+-- | Normalise Content in Markup, concatenating adjacent Content, and removing mempty Content.+--+-- >>> normContent $ content "a" <> content "" <> content "b"+-- Markup {elements = [Node {rootLabel = Content "ab", subForest = []}]}+normContent :: Markup -> Markup+normContent (Markup trees) = Markup $ foldTree (\x xs -> Node x (filter ((/= Content "") . rootLabel) $ concatContent xs)) <$> concatContent trees  concatContent :: [Tree Token] -> [Tree Token] concatContent = \case@@ -455,9 +577,9 @@ -- | Gather together token trees from a token list, placing child elements in nodes and removing EndTags. -- -- >>> gather Html =<< tokenize Html "<foo class=\"bar\">baz</foo>"--- That [Node {rootLabel = StartTag "foo" [Attr "class" "bar"], subForest = [Node {rootLabel = Content "baz", subForest = []}]}]-gather :: Standard -> [Token] -> These [MarkupWarning] [Tree Token]-gather s ts =+-- That (Markup {elements = [Node {rootLabel = OpenTag StartTag "foo" [Attr {attrName = "class", attrValue = "bar"}], subForest = [Node {rootLabel = Content "baz", subForest = []}]}]})+gather :: Standard -> [Token] -> Warn Markup+gather s ts = second Markup $   case (finalSibs, finalParents, warnings) of     (sibs, [], []) -> That (reverse sibs)     ([], [], xs) -> This xs@@ -468,20 +590,20 @@       foldl' (\(c, xs) t -> incCursor s t c & second (maybeToList >>> (<> xs))) (Cursor [] [], []) ts  -- | gather but errors on warnings.-gather_ :: Standard -> [Token] -> [Tree Token]-gather_ s ts = gather s ts & resultError+gather_ :: Standard -> [Token] -> Markup+gather_ s ts = gather s ts & warnError  incCursor :: Standard -> Token -> Cursor -> (Cursor, Maybe MarkupWarning) -- Only StartTags are ever pushed on to the parent list, here:-incCursor Xml t@(StartTag _ _) (Cursor ss ps) = (Cursor [] ((t, ss) : ps), Nothing)-incCursor Html t@(StartTag n _) (Cursor ss ps) =+incCursor Xml t@(OpenTag StartTag _ _) (Cursor ss ps) = (Cursor [] ((t, ss) : ps), Nothing)+incCursor Html t@(OpenTag StartTag n _) (Cursor ss ps) =   (bool (Cursor [] ((t, ss) : ps)) (Cursor (Node t [] : ss) ps) (n `elem` selfClosers), Nothing)-incCursor Xml t@(EmptyElemTag _ _) (Cursor ss ps) = (Cursor (Node t [] : ss) ps, Nothing)-incCursor Html t@(EmptyElemTag n _) (Cursor ss ps) =+incCursor Xml t@(OpenTag EmptyElemTag _ _) (Cursor ss ps) = (Cursor (Node t [] : ss) ps, Nothing)+incCursor Html t@(OpenTag EmptyElemTag n _) (Cursor ss ps) =   ( Cursor (Node t [] : ss) ps,     bool (Just BadEmptyElemTag) Nothing (n `elem` selfClosers)   )-incCursor _ (EndTag n) (Cursor ss ((p@(StartTag n' _), ss') : ps)) =+incCursor _ (EndTag n) (Cursor ss ((p@(OpenTag StartTag n' _), ss') : ps)) =   ( Cursor (Node p (reverse ss) : ss') ps,     bool (Just (TagMismatch n n')) Nothing (n == n')   )@@ -505,50 +627,50 @@  -- | Convert a markup into a token list, adding end tags. ----- >>> degather =<< markup Html "<foo class=\"bar\">baz</foo>"--- That [StartTag "foo" [Attr "class" "bar"],Content "baz",EndTag "foo"]-degather :: Markup -> These [MarkupWarning] [Token]-degather (Markup s tree) = rconcats $ foldTree (addCloseTags s) <$> tree+-- >>> degather Html =<< markup Html "<foo class=\"bar\">baz</foo>"+-- That [OpenTag StartTag "foo" [Attr {attrName = "class", attrValue = "bar"}],Content "baz",EndTag "foo"]+degather :: Standard -> Markup -> Warn [Token]+degather s (Markup tree) = concatWarns $ foldTree (addCloseTags s) <$> tree  -- | degather but errors on warning-degather_ :: Markup -> [Token]-degather_ m = degather m & resultError+degather_ :: Standard -> Markup -> [Token]+degather_ s m = degather s m & warnError -rconcats :: [Result [a]] -> Result [a]-rconcats rs = case bimap mconcat mconcat $ partitionHereThere rs of+concatWarns :: [Warn [a]] -> Warn [a]+concatWarns rs = case bimap mconcat mconcat $ partitionHereThere rs of   ([], xs) -> That xs   (es, []) -> This es   (es, xs) -> These es xs -addCloseTags :: Standard -> Token -> [These [MarkupWarning] [Token]] -> These [MarkupWarning] [Token]-addCloseTags std s@(StartTag n _) children+addCloseTags :: Standard -> Token -> [Warn [Token]] -> Warn [Token]+addCloseTags std s@(OpenTag StartTag n _) children   | children /= [] && n `elem` selfClosers && std == Html =-      These [SelfCloserWithChildren] [s] <> rconcats children+      These [SelfCloserWithChildren] [s] <> concatWarns children   | n `elem` selfClosers && std == Html =-      That [s] <> rconcats children+      That [s] <> concatWarns children   | otherwise =-      That [s] <> rconcats children <> That [EndTag n]+      That [s] <> concatWarns children <> That [EndTag n] addCloseTags _ x xs = case xs of   [] -> That [x]-  cs -> These [LeafWithChildren] [x] <> rconcats cs+  cs -> These [LeafWithChildren] [x] <> concatWarns cs -tokenXml :: Parser e Token-tokenXml =+tokenXmlP :: Parser e Token+tokenXmlP =   $( switch        [|          case _ of-           "<!--" -> comment-           "<!" -> doctypeXml-           "</" -> endTagXml-           "<?" -> declXml-           "<" -> startTagsXml-           _ -> content+           "<!--" -> commentP+           "<!" -> doctypeXmlP+           "</" -> endTagXmlP+           "<?" -> declXmlP+           "<" -> startTagsXmlP+           _ -> contentP          |]    )  -- [4]-nameStartChar :: Parser e Char-nameStartChar = fusedSatisfy isLatinLetter isNameStartChar isNameStartChar isNameStartChar+nameStartCharP :: Parser e Char+nameStartCharP = fusedSatisfy isLatinLetter isNameStartChar isNameStartChar isNameStartChar  isNameStartChar :: Char -> Bool isNameStartChar x =@@ -570,8 +692,8 @@     || (x >= '\x10000' && x <= '\xEFFFF')  -- [4a]-nameChar :: Parser e Char-nameChar = fusedSatisfy isNameCharAscii isNameCharExt isNameCharExt isNameCharExt+nameCharP :: Parser e Char+nameCharP = fusedSatisfy isNameCharAscii isNameCharExt isNameCharExt isNameCharExt  isNameCharAscii :: Char -> Bool isNameCharAscii x =@@ -609,39 +731,52 @@     || (x >= '\x10000' && x <= '\xEFFFF')  -- | name string according to xml production rule [5]-nameXml :: Parser e ByteString-nameXml = byteStringOf (nameStartChar >> many nameChar)+nameXmlP :: Parser e ByteString+nameXmlP = byteStringOf (nameStartCharP >> many nameCharP) +commentCloseP :: Parser e ()+commentCloseP = $(string "-->")++charNotMinusP :: Parser e ByteString+charNotMinusP = byteStringOf $ satisfy (/= '-')++minusPlusCharP :: Parser e ByteString+minusPlusCharP = byteStringOf ($(char '-') *> charNotMinusP)++commentP :: Parser e Token+commentP = Comment <$> byteStringOf (many (charNotMinusP <|> minusPlusCharP)) <* commentCloseP++contentP :: Parser e Token+contentP = Content <$> byteStringOf (some (satisfy (/= '<')))+ -- | XML declaration as per production rule [23]-declXml :: Parser e Token-declXml =-  Decl-    <$> byteStringOf-      ( $(string "xml")-          >> xmlVersionInfo-          >> optional xmlEncodingDecl-          >> optional xmlStandalone-          >> ws_-      )-    <* $(string "?>")+declXmlP :: Parser e Token+declXmlP = do+  _ <- $(string "xml")+  av <- Attr "version" <$> xmlVersionInfoP+  en <- Attr "encoding" <$> xmlEncodingDeclP+  st <- optional $ Attr "standalone" <$> xmlStandaloneP+  _ <- ws_+  _ <- $(string "?>")+  pure $ Decl "xml" $ [av, en] <> maybeToList st  -- | xml production [24]-xmlVersionInfo :: Parser e ByteString-xmlVersionInfo = byteStringOf $ ws_ >> $(string "version") >> eq >> wrappedQNoGuard xmlVersionNum+xmlVersionInfoP :: Parser e ByteString+xmlVersionInfoP = byteStringOf $ ws_ >> $(string "version") >> eq >> wrappedQNoGuard xmlVersionNumP  -- | xml production [26]-xmlVersionNum :: Parser e ByteString-xmlVersionNum =+xmlVersionNumP :: Parser e ByteString+xmlVersionNumP =   byteStringOf ($(string "1.") >> some (satisfy isDigit))  -- | Doctype declaration as per production rule [28]-doctypeXml :: Parser e Token-doctypeXml =+doctypeXmlP :: Parser e Token+doctypeXmlP =   Doctype     <$> byteStringOf       ( $(string "DOCTYPE")           >> ws_-          >> nameXml+          >> nameXmlP           >>           -- optional (ws_ >> xmlExternalID) >>           ws_@@ -651,101 +786,101 @@     <* $(char '>')  -- | Xml production [32]-xmlStandalone :: Parser e ByteString-xmlStandalone =+xmlStandaloneP :: Parser e ByteString+xmlStandaloneP =   byteStringOf $-    ws_ *> $(string "standalone") *> eq *> xmlYesNo+    ws_ *> $(string "standalone") *> eq *> xmlYesNoP  -- | Xml yes/no-xmlYesNo :: Parser e ByteString-xmlYesNo = wrappedQNoGuard (byteStringOf $ $(string "yes") <|> $(string "no"))+xmlYesNoP :: Parser e ByteString+xmlYesNoP = wrappedQNoGuard (byteStringOf $ $(string "yes") <|> $(string "no"))  -- | xml production [80]-xmlEncodingDecl :: Parser e ByteString-xmlEncodingDecl = ws_ *> $(string "encoding") *> eq *> wrappedQNoGuard xmlEncName+xmlEncodingDeclP :: Parser e ByteString+xmlEncodingDeclP = ws_ *> $(string "encoding") *> eq *> wrappedQNoGuard xmlEncNameP  -- | xml production [81]-xmlEncName :: Parser e ByteString-xmlEncName = byteStringOf (satisfyAscii isLatinLetter >> many (satisfyAscii (\x -> isLatinLetter x || isDigit x || elem x ("._-" :: [Char]))))+xmlEncNameP :: Parser e ByteString+xmlEncNameP = byteStringOf (satisfyAscii isLatinLetter >> many (satisfyAscii (\x -> isLatinLetter x || isDigit x || elem x ("._-" :: [Char]))))  -- | open xml tag as per xml production rule [40] --  self-closing xml tag as per [44]-startTagsXml :: Parser e Token-startTagsXml = do-  !n <- nameXml-  !as <- many (ws_ *> attrXml)+startTagsXmlP :: Parser e Token+startTagsXmlP = do+  !n <- nameXmlP+  !as <- many (ws_ *> attrXmlP)   _ <- ws_   $( switch        [|          case _ of-           "/>" -> pure (EmptyElemTag n as)-           ">" -> pure (StartTag n as)+           "/>" -> pure (OpenTag EmptyElemTag n as)+           ">" -> pure (OpenTag StartTag n as)          |]    ) -attrXml :: Parser e Attr-attrXml = Attr <$> (nameXml <* eq) <*> wrappedQ+attrXmlP :: Parser e Attr+attrXmlP = Attr <$> (nameXmlP <* eq) <*> wrappedQ  -- | closing tag as per [42]-endTagXml :: Parser e Token-endTagXml = EndTag <$> (nameXml <* ws_ <* $(char '>'))+endTagXmlP :: Parser e Token+endTagXmlP = EndTag <$> (nameXmlP <* ws_ <* $(char '>'))  -- | Parse a single 'Token'.-tokenHtml :: Parser e Token-tokenHtml =+tokenHtmlP :: Parser e Token+tokenHtmlP =   $( switch        [|          case _ of-           "<!--" -> comment-           "<!" -> doctypeHtml-           "</" -> endTagHtml-           "<?" -> bogusCommentHtml-           "<" -> startTagsHtml-           _ -> content+           "<!--" -> commentP+           "<!" -> doctypeHtmlP+           "</" -> endTagHtmlP+           "<?" -> bogusCommentHtmlP+           "<" -> startTagsHtmlP+           _ -> contentP          |]    ) -bogusCommentHtml :: Parser e Token-bogusCommentHtml = Comment <$> byteStringOf (some (satisfy (/= '<')))+bogusCommentHtmlP :: Parser e Token+bogusCommentHtmlP = Comment <$> byteStringOf (some (satisfy (/= '<'))) -doctypeHtml :: Parser e Token-doctypeHtml =+doctypeHtmlP :: Parser e Token+doctypeHtmlP =   Doctype     <$> byteStringOf       ( $(string "DOCTYPE")           >> ws_-          >> nameHtml+          >> nameHtmlP           >> ws_       )     <* $(char '>') -startTagsHtml :: Parser e Token-startTagsHtml = do-  n <- nameHtml-  as <- attrs Html+startTagsHtmlP :: Parser e Token+startTagsHtmlP = do+  n <- nameHtmlP+  as <- attrsP Html   _ <- ws_   $( switch        [|          case _ of-           "/>" -> pure (EmptyElemTag n as)-           ">" -> pure (StartTag n as)+           "/>" -> pure (OpenTag EmptyElemTag n as)+           ">" -> pure (OpenTag StartTag n as)          |]    ) -endTagHtml :: Parser e Token-endTagHtml = EndTag <$> nameHtml <* ws_ <* $(char '>')+endTagHtmlP :: Parser e Token+endTagHtmlP = EndTag <$> nameHtmlP <* ws_ <* $(char '>')  -- | Parse a tag name. Each standard is slightly different.-name :: Standard -> Parser e ByteString-name Html = nameHtml-name Xml = nameXml+nameP :: Standard -> Parser e ByteString+nameP Html = nameHtmlP+nameP Xml = nameXmlP -nameHtml :: Parser e ByteString-nameHtml = do-  byteStringOf (nameStartCharHtml >> many (satisfy isNameChar))+nameHtmlP :: Parser e ByteString+nameHtmlP = do+  byteStringOf (nameStartCharHtmlP >> many (satisfy isNameChar)) -nameStartCharHtml :: Parser e Char-nameStartCharHtml = satisfyAscii isLatinLetter+nameStartCharHtmlP :: Parser e Char+nameStartCharHtmlP = satisfyAscii isLatinLetter  isNameChar :: Char -> Bool isNameChar x =@@ -756,25 +891,25 @@         || (x == '>')     ) -attrHtml :: Parser e Attr-attrHtml =-  (Attr <$> (attrName <* eq) <*> (wrappedQ <|> attrBooleanName))-    <|> ((`Attr` mempty) <$> attrBooleanName)+attrHtmlP :: Parser e Attr+attrHtmlP =+  (Attr <$> (attrNameP <* eq) <*> (wrappedQ <|> attrBooleanNameP))+    <|> ((`Attr` mempty) <$> attrBooleanNameP) -attrBooleanName :: Parser e ByteString-attrBooleanName = byteStringOf $ some (satisfy isBooleanAttrName)+attrBooleanNameP :: Parser e ByteString+attrBooleanNameP = byteStringOf $ some (satisfy isBooleanAttrName)  -- | Parse an 'Attr'-attr :: Standard -> Parser a Attr-attr Html = attrHtml-attr Xml = attrXml+attrP :: Standard -> Parser a Attr+attrP Html = attrHtmlP+attrP Xml = attrXmlP  -- | Parse attributions-attrs :: Standard -> Parser a [Attr]-attrs s = many (ws_ *> attr s) <* ws_+attrsP :: Standard -> Parser a [Attr]+attrsP s = many (ws_ *> attrP s) <* ws_ -attrName :: Parser e ByteString-attrName = isa isAttrName+attrNameP :: Parser e ByteString+attrNameP = isa isAttrName  isAttrName :: Char -> Bool isAttrName x =

@@ -12,6 +12,11 @@     runParserWarn,     runParser_, +    -- * flatparse re-exports+    runParser,+    Parser,+    Result (..),+     -- * parsers     isWhitespace,     ws_,@@ -35,6 +40,7 @@     double,     signed,     byteStringOf',+    comma,   ) where @@ -71,7 +77,7 @@ -- -- >>> runParserEither ws " x" -- Right ' '-runParserEither :: Parser String a -> ByteString -> Either String a+runParserEither :: (IsString e) => Parser e a -> ByteString -> Either e a runParserEither p bs = case runParser p bs of   Err e -> Left e   OK a _ -> Right a@@ -87,7 +93,7 @@ -- -- >>> runParserWarn (ws `cut` "no whitespace") "x" -- This (ParserError "no whitespace")-data ParserWarning = ParserLeftover ByteString | ParserError String | ParserUncaught deriving (Eq, Show, Ord, Generic, NFData)+data ParserWarning = ParserLeftover ByteString | ParserError ByteString | ParserUncaught deriving (Eq, Show, Ord, Generic, NFData)  -- | Run parser, returning leftovers and errors as 'ParserWarning's. --@@ -99,7 +105,7 @@ -- -- >>> runParserWarn ws " x" -- These (ParserLeftover "x") ' '-runParserWarn :: Parser String a -> ByteString -> These ParserWarning a+runParserWarn :: Parser ByteString a -> ByteString -> These ParserWarning a runParserWarn p bs = case runParser p bs of   Err e -> This (ParserError e)   OK a "" -> That a@@ -334,7 +340,7 @@ minus :: Parser e () minus = $(char '-') --- |+-- | Parser for a signed prefix to a number. -- >>> runParser (signed double) "-1.234x" -- OK (-1.234) "x" signed :: (Num b) => Parser e b -> Parser e b@@ -343,3 +349,7 @@   case m of     Nothing -> p     Just () -> negate <$> p++-- | comma parser+comma :: Parser e ()+comma = $(char ',')

@@ -2,10 +2,13 @@ module MarkupParse.Patch   ( patch,     goldenPatch,+    showPatch,   ) where +import Control.Category ((>>>)) import Data.Foldable+import Data.Function import Data.Maybe import Data.TreeDiff import Data.TreeDiff.OMap qualified as O@@ -16,7 +19,6 @@  -- $setup -- >>> :set -XOverloadedStrings--- >>> import Data.TreeDiff -- >>> import MarkupParse.Patch  -- | compare a markup file with a round-trip transformation.@@ -88,7 +90,11 @@  -- | 'ediff' with unchanged sections filtered out ----- >>> show $ ansiWlEditExpr <$> patch [1, 2, 3, 5] [0, 1, 2, 4, 6]--- "Just [+0, -3, +4, -5, +6]"+-- >>> showPatch $ patch [1, 2, 3, 5] [0, 1, 2, 4, 6]+-- "[+0, -3, +4, -5, +6]" patch :: (ToExpr a) => a -> a -> Maybe (Edit EditExpr) patch m m' = filterChangedEdit $ ediff m m'++-- | Create a String representation of a patch.+showPatch :: Maybe (Edit EditExpr) -> String+showPatch p = p & maybe mempty (ansiWlEditExpr >>> show)