CINXE.COM

<!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-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Parsing - Wikipedia</title> <script>(function(){var 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-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"07ca8fa7-e0cb-44ec-9e3b-6147cf3382ec","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Parsing","wgTitle":"Parsing","wgCurRevisionId":1254644827,"wgRevisionId":1254644827,"wgArticleId":310015,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Webarchive template wayback links","CS1 maint: multiple names: authors list","CS1 maint: numeric 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","Articles with excerpts","Parsing","Algorithms on strings","Compiler construction"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Parsing","wgRelevantArticleId":310015,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[], "wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q194152","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap", "ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <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=1120"> <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: 640px)" href="//en.m.wikipedia.org/wiki/Parsing"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Parsing&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/rest.php/v1/search" 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&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive 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"> <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> </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> </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 skin-invert"> <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" 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 vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-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-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Parsing" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Parsing" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </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-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&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&returnto=Parsing" title="You're encouraged to log in; however, it'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-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <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> <span>Human languages</span> </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 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> <span>Traditional methods</span> </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> <span>Computational methods</span> </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> <span>Psycholinguistics</span> </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> <span>Discourse analysis</span> </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> <span>Computer languages</span> </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 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> <span>Parser</span> </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> <span>Overview of process</span> </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> <span>Types of parsers</span> </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 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> <span>Implementation</span> </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> <span>Parser development software</span> </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> <span>Lookahead</span> </div> </a> <ul id="toc-Lookahead-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-List_of_parsing_algorithms" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#List_of_parsing_algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>List of parsing algorithms</span> </div> </a> <ul id="toc-List_of_parsing_algorithms-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">7</span> <span>See also</span> </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">8</span> <span>References</span> </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">9</span> <span>Further reading</span> </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">10</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav 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 37 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-37" 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">37 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" data-title="تجزئة (لغة)" data-language-autonym="العربية" data-language-local-name="Arabic" 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" data-title="বাক্যাত্মক পদপরিচয়" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</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" data-title="Syntaktická analýza" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da badge-Q70894304 mw-list-item" title=""><a href="https://da.wikipedia.org/wiki/Parsning" title="Parsning – Danish" lang="da" hreflang="da" data-title="Parsning" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de badge-Q70894304 mw-list-item" title=""><a href="https://de.wikipedia.org/wiki/Parsing" title="Parsing – German" lang="de" hreflang="de" data-title="Parsing" data-language-autonym="Deutsch" data-language-local-name="German" 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" data-title="Parsimine" data-language-autonym="Eesti" data-language-local-name="Estonian" 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" data-title="Συντακτική ανάλυση (υπολογιστές)" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</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" data-title="Sintaksa analizo" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</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" data-title="تجزیه‌کننده" data-language-autonym="فارسی" data-language-local-name="Persian" 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" data-title="Analyse syntaxique" data-language-autonym="Français" data-language-local-name="French" 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" data-title="구문 분석" data-language-autonym="한국어" data-language-local-name="Korean" 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" data-title="Շարահյուսական վերլուծություն (ինֆորմատիկա)" data-language-autonym="Հայերեն" data-language-local-name="Armenian" 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" data-title="वाक्यात्मक पदपरिचय" data-language-autonym="हिन्दी" data-language-local-name="Hindi" 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" data-title="Parsiranje" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</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" data-title="Parsing" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" 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" data-title="Parsing" data-language-autonym="Italiano" data-language-local-name="Italian" 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" data-title="ניתוח מחרוזות" data-language-autonym="עברית" data-language-local-name="Hebrew" 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" data-title="Синтаксистік талдау" data-language-autonym="Қазақша" data-language-local-name="Kazakh" 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" data-title="Elemző (informatika)" data-language-autonym="Magyar" data-language-local-name="Hungarian" 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" data-title="Расчленување (информатика)" data-language-autonym="Македонски" data-language-local-name="Macedonian" class="interlanguage-link-target"><span>Македонски</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" data-title="構文解析" data-language-autonym="日本語" data-language-local-name="Japanese" 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" data-title="Parsing" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</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" data-title="Análise sintática (computação)" data-language-autonym="Português" data-language-local-name="Portuguese" 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" data-title="Parsare" data-language-autonym="Română" data-language-local-name="Romanian" 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" data-title="Синтаксический анализ" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple badge-Q70894304 mw-list-item" title=""><a href="https://simple.wikipedia.org/wiki/Parsing" title="Parsing – Simple English" lang="en-simple" hreflang="en-simple" data-title="Parsing" data-language-autonym="Simple English" data-language-local-name="Simple English" 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" data-title="Syntaktická analýza" data-language-autonym="Slovenčina" data-language-local-name="Slovak" 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" data-title="Raščlanjivanje" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" 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" data-title="Raščlanjivanje" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" 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" data-title="Jäsentäminen" data-language-autonym="Suomi" data-language-local-name="Finnish" 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/Syntaxanalys" title="Syntaxanalys – Swedish" lang="sv" hreflang="sv" data-title="Syntaxanalys" data-language-autonym="Svenska" data-language-local-name="Swedish" 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" data-title="Parsing" data-language-autonym="Tagalog" data-language-local-name="Tagalog" 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" data-title="இலக்கணப் பாகுபடுத்தி" data-language-autonym="தமிழ்" data-language-local-name="Tamil" class="interlanguage-link-target"><span>தமிழ்</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" data-title="Синтаксичний аналіз" data-language-autonym="Українська" data-language-local-name="Ukrainian" 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" data-title="Phân tích cú pháp" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" 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" data-title="解析" data-language-autonym="粵語" data-language-local-name="Cantonese" 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" data-title="语法分析" data-language-autonym="中文" data-language-local-name="Chinese" 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="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-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">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&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&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="Page tools"> <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&action=edit" title="Edit this page [e]" accesskey="e"><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&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&oldid=1254644827" 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&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&page=Parsing&id=1254644827&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FParsing"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FParsing"><span>Download QR code</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&page=Parsing&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&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><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem 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> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </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"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Analysing a string of symbols, according to the rules of a formal grammar</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.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}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</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> <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"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></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> information.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<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>]</sup> Some parsing algorithms generate a <i>parse forest</i> or list of parse trees from a string that is <a href="/wiki/Syntactic_ambiguity" title="Syntactic ambiguity">syntactically ambiguous</a>.<sup id="cite_ref-Tomita2012_2-0" class="reference"><a href="#cite_note-Tomita2012-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></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"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></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" /> <div class="mw-heading mw-heading2"><h2 id="Human_languages">Human languages</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=1" title="Edit section: Human languages"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><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> <div class="mw-heading mw-heading3"><h3 id="Traditional_methods">Traditional methods</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=2" title="Edit section: Traditional methods"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></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;">[<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>]</sup> </p> <div class="mw-heading mw-heading3"><h3 id="Computational_methods">Computational methods</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=3" title="Edit section: Computational methods"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><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:r1251242444">.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}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</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 href="/wiki/Special:EditPage/Parsing" title="Special:EditPage/Parsing">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a> 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 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"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></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"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></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;">[<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>]</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 statistical; 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"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></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"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></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"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></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;">[<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>]</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&action=edit&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;">[<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>]</sup> In <a href="/wiki/Natural_language_understanding" 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"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Psycholinguistics">Psycholinguistics</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=4" title="Edit section: Psycholinguistics"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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. </p><p>Neurolinguistics generally understands parsing to be a function of working memory, meaning that parsing is used to keep several parts of one sentence at play in the mind at one time, all readily accessible to be analyzed as needed. Because the human working memory has limitations, so does the function of sentence parsing.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> This is evidenced by several different types of syntactically complex sentences that propose potentially issues for mental parsing of sentences. </p><p>The first, and perhaps most well-known, type of sentence that challenges parsing ability is the garden-path sentence. These sentences are designed so that the most common interpretation of the sentence appears grammatically faulty, but upon further inspection, these sentences are grammatically sound. Garden-path sentences are difficult to parse because they contain a phrase or a word with more than one meaning, often their most typical meaning being a different part of speech.<sup id="cite_ref-doi.org_11-0" class="reference"><a href="#cite_note-doi.org-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> For example, in the sentence, "the horse raced past the barn fell", raced is initially interpreted as a past tense verb, but in this sentence, it functions as part of an adjective phrase.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> Since parsing is used to identify parts of speech, these sentences challenge the parsing ability of the reader. </p><p>Another type of sentence that is difficult to parse is an attachment ambiguity, which includes a phrase that could potentially modify different parts of a sentence, and therefore presents a challenge in identifying syntactic relationship (i.e. "The boy saw the lady with the telescope", in which the ambiguous phrase with the telescope could modify the boy saw or the lady.) <sup id="cite_ref-doi.org_11-1" class="reference"><a href="#cite_note-doi.org-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p><p>A third type of sentence that challenges parsing ability is center embedding, in which phrases are placed in the center of other similarly formed phrases (i.e. "The rat the cat the man hit chased ran into the trap".) Sentences with 2 or in the most extreme cases 3 center embeddings are challenging for mental parsing, again because of ambiguity of syntactic relationship.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p><p>Within neurolinguistics there are multiple theories that aim to describe how parsing takes place in the brain. One such model is a more traditional generative model of sentence processing, which theorizes that within the brain there is a distinct module designed for sentence parsing, which is preceded by access to lexical recognition and retrieval, and then followed by syntactic processing that considers a single syntactic result of the parsing, only returning to revise that syntactic interpretation if a potential problem is detected.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> The opposing, more contemporary model theorizes that within the mind, the processing of a sentence is not modular, or happening in strict sequence. Rather, it poses that several different syntactic possibilities can be considered at the same time, because lexical access, syntactic processing, and determination of meaning occur in parallel in the brain. In this way these processes are integrated.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p><p>Although there is still much to learn about the neurology of parsing, studies have shown evidence that several areas of the brain might play a role in parsing. These include the left anterior temporal pole, the left inferior frontal gyrus, the left superior temporal gyrus, the left superior frontal gyrus, the right posterior cingulate cortex, and the left angular gyrus. Although it has not been absolutely proven, it has been suggested that these different structures might favor either phrase-structure parsing or dependency-structure parsing, meaning different types of parsing could be processed in different ways which have yet to be understood.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Discourse_analysis">Discourse analysis</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=5" title="Edit section: Discourse analysis"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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> <div class="mw-heading mw-heading2"><h2 id="Computer_languages">Computer languages</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=6" title="Edit section: Computer languages"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><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 href="/wiki/Special:EditPage/Parsing" title="Special:EditPage/Parsing">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 message</a></small>)</i></span></div></td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Parser">Parser</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=7" title="Edit section: Parser"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><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 (typically 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" 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 <a href="/wiki/Compiler" title="Compiler">compiler</a>. </p><p>The input to a parser is typically 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" 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="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> <div class="mw-heading mw-heading3"><h3 id="Overview_of_process">Overview of process</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=8" title="Edit section: Overview of process"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></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> <div class="mw-heading mw-heading2"><h2 id="Types_of_parsers">Types of parsers</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=9" title="Edit section: Types of parsers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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_18-0" class="reference"><a href="#cite_note-AhoSethiUllman_1986-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></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-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></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_20-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2007-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-FrostHafizCallaghan_2008_21-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2008-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></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_18-1" class="reference"><a href="#cite_note-AhoSethiUllman_1986-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p><p>Some <i><style data-mw-deduplicate="TemplateStyles:r1238216509">.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}</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-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></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-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></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_25-0" class="reference"><a href="#cite_note-Lehman2012-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Implementation">Implementation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=10" title="Edit section: Implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A simple parser implementation reads the entire input file, performs an intermediate computation or translation, and then writes the entire output file, such as in-memory <a href="/wiki/Multi-pass_compiler" title="Multi-pass compiler">multi-pass compilers</a>. </p><p>Alternative parser implementation approaches: </p> <ul><li><b>push parsers</b> call registered handlers (<a href="/wiki/Callback_(computer_programming)" title="Callback (computer programming)">callbacks</a>) as soon as the parser detects relevant tokens in the input stream. A push parser may skip parts of the input that are irrelevant (an example is <a href="/wiki/Expat_(software)" title="Expat (software)">Expat</a>).</li> <li><b>pull parsers</b>, such as parsers that are typically used by <a href="/wiki/Compilers" class="mw-redirect" title="Compilers">compilers</a> front-ends by "pulling" input text.</li> <li><b>incremental parsers</b> (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><b>Active</b> versus <b>passive parsers</b><sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup></li></ul> <div class="mw-heading mw-heading2"><h2 id="Parser_development_software">Parser development software</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=11" title="Edit section: Parser development software"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><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&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:r1236090951"><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:r1184024115">.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}</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></ul> </div> <div class="mw-heading mw-heading2"><h2 id="Lookahead">Lookahead</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=12" title="Edit section: Lookahead"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><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 href="/wiki/Special:EditPage/Parsing" title="Special:EditPage/Parsing">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 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-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></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 to 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;">[<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>]</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;">[<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>]</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;">[<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> – <a href="/wiki/Talk:Parsing#Dubious" title="Talk:Parsing">discuss</a></i>]</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;">[<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 ('anticipation'). (April 2019)">clarification needed</span></a></i>]</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:var(--color-subtle, #54595d); border:1px solid var(--border-color-subtle, #c8ccd1);">more efficient</span><sup class="noprint Inline-Template Template-Clarify" style="margin-left:0.1em; white-space:nowrap;">[<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't make sense here; expression efficiency isn't a matter of parsing, but of optimization. (April 2019)">clarify</span></a></i>]</sup><sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<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>]</sup> than non-lookahead parsers. This is the strategy followed in <a href="/wiki/LALR_parser" title="LALR parser">LALR parsers</a>. </p> <div class="mw-heading mw-heading2"><h2 id="List_of_parsing_algorithms">List of parsing algorithms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=13" title="Edit section: List of parsing algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="excerpt-block"><style data-mw-deduplicate="TemplateStyles:r1066933788">.mw-parser-output .excerpt-hat .mw-editsection-like{font-style:normal}</style><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable dablink excerpt-hat selfref">This section is an excerpt from <a href="/wiki/List_of_algorithms#Parsing" title="List of algorithms">List of algorithms § Parsing</a>.<span class="mw-editsection-like plainlinks"><span class="mw-editsection-bracket">[</span><a class="external text" href="https://en.wikipedia.org/w/index.php?title=List_of_algorithms&action=edit">edit</a><span class="mw-editsection-bracket">]</span></span></div><div class="excerpt"> <ul><li><a href="/wiki/CYK_algorithm" title="CYK algorithm">CYK algorithm</a>: an O(n<sup>3</sup>) algorithm for parsing <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a> in <a href="/wiki/Chomsky_normal_form" title="Chomsky normal form">Chomsky normal form</a></li> <li><a href="/wiki/Earley_parser" title="Earley parser">Earley parser</a>: another O(n<sup>3</sup>) algorithm for parsing any <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a></li> <li><a href="/wiki/GLR_parser" title="GLR parser">GLR parser</a>: an algorithm for parsing any <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a> by <a href="/wiki/Masaru_Tomita" title="Masaru Tomita">Masaru Tomita</a>. It is tuned for deterministic grammars, on which it performs almost <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a> and O(n<sup>3</sup>) in worst case.</li> <li><a href="/wiki/Inside-outside_algorithm" class="mw-redirect" title="Inside-outside algorithm">Inside-outside algorithm</a>: an O(n<sup>3</sup>) algorithm for re-estimating production probabilities in <a href="/wiki/Probabilistic_context-free_grammar" title="Probabilistic context-free grammar">probabilistic context-free grammars</a></li> <li><a href="/wiki/LL_parser" title="LL parser">LL parser</a>: a relatively simple <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a> parsing algorithm for a limited class of <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a></li> <li><a href="/wiki/LR_parser" title="LR parser">LR parser</a>: A more complex <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a> parsing algorithm for a larger class of <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a>. Variants: <ul><li><a href="/wiki/Canonical_LR_parser" title="Canonical LR parser">Canonical LR parser</a></li> <li><a href="/wiki/Look-ahead_LR_parser" class="mw-redirect" title="Look-ahead LR parser">LALR (look-ahead LR) parser</a></li> <li><a href="/wiki/Operator-precedence_parser" title="Operator-precedence parser">Operator-precedence parser</a></li> <li><a href="/wiki/Simple_LR_parser" title="Simple LR parser">SLR (Simple LR) parser</a></li> <li><a href="/wiki/Simple_precedence_parser" title="Simple precedence parser">Simple precedence parser</a></li></ul></li> <li><a href="/wiki/Packrat_parser" title="Packrat parser">Packrat parser</a>: a <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a> parsing algorithm supporting some <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a> and <a href="/wiki/Parsing_expression_grammar" title="Parsing expression grammar">parsing expression grammars</a></li> <li><a href="/wiki/Recursive_descent_parser" title="Recursive descent parser">Recursive descent parser</a>: a <a href="/wiki/Top-down_parsing" title="Top-down parsing">top-down parser</a> suitable for LL(<i>k</i>) grammars</li> <li><a href="/wiki/Shunting-yard_algorithm" class="mw-redirect" title="Shunting-yard algorithm">Shunting-yard algorithm</a>: converts an infix-notation math expression to postfix</li> <li><a href="/wiki/Pratt_parser" class="mw-redirect" title="Pratt parser">Pratt parser</a></li> <li><a href="/wiki/Lexical_analysis" title="Lexical analysis">Lexical analysis</a></li></ul></div></div> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=14" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1184024115"><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/DMS_Software_Reengineering_Toolkit" title="DMS Software Reengineering Toolkit">DMS Software Reengineering Toolkit</a></li> <li><a href="/wiki/Grammar_checker" title="Grammar checker">Grammar checker</a></li> <li><a href="/wiki/Inverse_parser" title="Inverse parser">Inverse parser</a></li> <li><a href="/wiki/LALR_parser" title="LALR parser">LALR parser</a></li> <li><a href="/wiki/Left_corner_parser" title="Left corner parser">Left corner parser</a></li> <li><a href="/wiki/Lexical_analysis" title="Lexical analysis">Lexical analysis</a></li> <li><a href="/wiki/Parsing_expression_grammar" title="Parsing expression grammar">Parsing expression grammar</a></li> <li><a href="/wiki/Pratt_parser" class="mw-redirect" title="Pratt parser">Pratt parser</a></li> <li><a href="/wiki/Program_transformation" title="Program transformation">Program transformation</a></li> <li><a href="/wiki/Shallow_parsing" title="Shallow parsing">Shallow parsing</a></li> <li><a href="/wiki/Sentence_processing" title="Sentence processing">Sentence processing</a></li> <li><a href="/wiki/Source_code_generation" class="mw-redirect" title="Source code generation">Source code generation</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=15" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.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:r1238218222">.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.id-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.id-lock-limited a,.mw-parser-output .id-lock-registration.id-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.id-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}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.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}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</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&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Parse&rft.pub=dictionary.reference.com&rft_id=https%3A%2F%2Fwww.dictionary.com%2Fbrowse%2Fparse&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:r1238218222"><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&q=%22parse+forest%22"><i>Generalized LR Parsing</i></a>. Springer Science & Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <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&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Generalized+LR+Parsing&rft.pub=Springer+Science+%26+Business+Media&rft.date=2012-12-06&rft.isbn=978-1-4615-4034-2&rft.au=Masaru+Tomita&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DVVDTBwAAQBAJ%26q%3D%2522parse%2Bforest%2522&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:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20161201190245/http://grammar.about.com/od/pq/g/parsingterm.htm">"Grammar and Composition"</a>. Archived from <a rel="nofollow" class="external text" href="http://grammar.about.com/od/pq/g/parsingterm.htm">the original</a> on 2016-12-01<span class="reference-accessdate">. Retrieved <span class="nowrap">2012-11-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Grammar+and+Composition&rft_id=http%3A%2F%2Fgrammar.about.com%2Fod%2Fpq%2Fg%2Fparsingterm.htm&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:r1238218222"><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&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> <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&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Foundations+of+Statistical+Natural+Language+Processing&rft.pub=MIT+Press&rft.date=1999&rft.isbn=978-0-262-13360-9&rft.au=Christopher+D..+Manning&rft.au=Christopher+D.+Manning&rft.au=Hinrich+Sch%C3%BCtze&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DYiFDxbEX3SUC%26q%3Dparsing&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:r1238218222"><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> <span class="id-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&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Cognitive+Science&rft.atitle=A+Probabilistic+Model+of+Lexical+and+Syntactic+Access+and+Disambiguation&rft.volume=20&rft.issue=2&rft.pages=137-194&rft.date=1996&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.150.5711%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1207%2Fs15516709cog2002_1&rft.aulast=Jurafsky&rft.aufirst=Daniel&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> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190401145141/https://aclanthology.info/pdf/A/A00/A00-2018.pdf">Archived</a> 2019-04-01 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</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:r1238218222"><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="id-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="https://arxiv.org/archive/cs.CL">cs.CL</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Data+Recombination+for+Neural+Semantic+Parsing&rft.date=2016-06-11&rft_id=info%3Aarxiv%2F1606.03622&rft.aulast=Jia&rft.aufirst=Robin&rft.au=Liang%2C+Percy&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">Sandra H. Vos, Thomas C. Gunter, Herbert Schriefers & Angela D. Friederici (2001) Syntactic parsing and working memory: The effects of syntactic complexity, reading span, and concurrent load, Language and Cognitive Processes, 16:1, 65-103, DOI: 10.1080/01690960042000085</span> </li> <li id="cite_note-doi.org-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-doi.org_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-doi.org_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Pritchett, B. L. (1988). Garden Path Phenomena and the Grammatical Basis of Language Processing. Language, 64(3), 539–576. <a rel="nofollow" class="external free" href="https://doi.org/10.2307/414532">https://doi.org/10.2307/414532</a></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:r1238218222"><cite id="CITEREFThomas_G_Bever1970" class="citation book cs1">Thomas G Bever (1970). <i>The cognitive basis for linguistic structures</i>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/43300456">43300456</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+cognitive+basis+for+linguistic+structures&rft.date=1970&rft_id=info%3Aoclcnum%2F43300456&rft.au=Thomas+G+Bever&rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text">Karlsson, F. (2010). Working Memory Constraints on Multiple Center-Embedding. Proceedings of the Annual Meeting of the Cognitive Science Society, 32. Retrieved from <a rel="nofollow" class="external free" href="https://escholarship.org/uc/item/4j00v1j2">https://escholarship.org/uc/item/4j00v1j2</a></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text">Ferreira, F., & Clifton, C. (1986). The independence of syntactic processing. Journal of Memory and Language, 25(3), 348–368. <a rel="nofollow" class="external free" href="https://doi.org/10.1016/0749-596X(86)90006-9">https://doi.org/10.1016/0749-596X(86)90006-9</a></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">Atlas, J. D. (1997). On the modularity of sentence processing: semantical generality and the language of thought. Language and Conceptualization, 213–214.</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">Lopopolo, Alessandro, van den Bosch, Antal, Petersson, Karl-Magnus, and Roel M. Willems; Distinguishing Syntactic Operations in the Brain: Dependency and Phrase-Structure Parsing. Neurobiology of Language 2021; 2 (1): 152–175. doi: <a rel="nofollow" class="external free" href="https://doi.org/10.1162/nol_a_00029">https://doi.org/10.1162/nol_a_00029</a></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">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-18"><span class="mw-cite-backlink">^ <a href="#cite_ref-AhoSethiUllman_1986_18-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-AhoSethiUllman_1986_18-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-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSikkel,_Klaas,_1954-1997" class="citation book cs1">Sikkel, Klaas, 1954- (1997). <i>Parsing schemata : 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> <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> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/606012644">606012644</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Parsing+schemata+%3A+a+framework+for+specification+and+analysis+of+parsing+algorithms&rft.place=Berlin&rft.pub=Springer&rft.date=1997&rft_id=info%3Aoclcnum%2F606012644&rft.isbn=9783642605413&rft.au=Sikkel%2C+Klaas%2C+1954-&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>) CS1 maint: numeric names: authors list (<a href="/wiki/Category:CS1_maint:_numeric_names:_authors_list" title="Category:CS1 maint: numeric names: authors list">link</a>)</span></span> </li> <li id="cite_note-FrostHafizCallaghan_2007-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-FrostHafizCallaghan_2007_20-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> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180822014649/https://aclanthology.info/pdf/W/W07/W07-2215.pdf">Archived</a> 2018-08-22 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</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-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-FrostHafizCallaghan_2008_21-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&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-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</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&as_sdt=0%2C47&q=%22graphical+parsing%22&btnG=">Defining and parsing visual languages with layered graph grammars</a>." Journal of Visual Languages & Computing 8.1 (1997): 27-55.</span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</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-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</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-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-Lehman2012_25-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><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&q=%22language+acquisition%22"><i>Adaptive Parsing: Self-Extending Natural Language Interfaces</i></a>. Springer Science & Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <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&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Adaptive+Parsing%3A+Self-Extending+Natural+Language+Interfaces&rft.pub=Springer+Science+%26+Business+Media&rft.date=2012-12-06&rft.isbn=978-1-4615-3622-2&rft.au=Jill+Fain+Lehman&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DtU_tBwAAQBAJ%26q%3D%2522language%2Bacquisition%2522&rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span></span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</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-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</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-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text">taken from <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrian_W._Kernighan_and_Dennis_M._Ritchie1988" class="citation book cs1">Brian W. Kernighan and Dennis M. Ritchie (Apr 1988). <span class="id-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 ed.). Englewood Cliffs/NJ: Prentice Hall. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0131103628" title="Special:BookSources/0131103628"><bdi>0131103628</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+C+Programming+Language&rft.place=Englewood+Cliffs%2FNJ&rft.series=Prentice+Hall+Software+Series&rft.edition=2nd&rft.pub=Prentice+Hall&rft.date=1988-04&rft.isbn=0131103628&rft.au=Brian+W.+Kernighan+and+Dennis+M.+Ritchie&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcprogramminglang00bria&rfr_id=info%3Asid%2Fen.wikipedia.org%3AParsing" class="Z3988"></span> (Appendix A.13 "Grammar", p.193 ff)</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=16" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{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}@media screen{.mw-parser-output .refbegin{font-size:90%}}</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:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <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:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-13-651431-6" title="Special:BookSources/0-13-651431-6">0-13-651431-6</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Parsing&action=edit&section=17" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.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:var(--background-color-interactive-subtle,#f8f9fa);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;min-width:0}}@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><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</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> 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:r1236075235">.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}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</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:r1239400231">.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}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</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">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Parsers" title="Template talk:Parsers"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Parsers" title="Special:EditPage/Template:Parsers"><abbr title="Edit this template">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>Statistical</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:r1236075235"></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:r1239400231"><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">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Strings" title="Template talk:Strings"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Strings" title="Special:EditPage/Template:Strings"><abbr title="Edit this template">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'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'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> <li><a href="/wiki/String_operations" title="String operations">String operations</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" 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&oldid=1254644827">https://en.wikipedia.org/w/index.php?title=Parsing&oldid=1254644827</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:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><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:CS1_maint:_numeric_names:_authors_list" title="Category:CS1 maint: numeric names: authors list">CS1 maint: numeric 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><li><a href="/wiki/Category:Articles_with_excerpts" title="Category:Articles with excerpts">Articles with excerpts</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 1 November 2024, at 00:07<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://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/Policy:Universal_Code_of_Conduct">Code of Conduct</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> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Parsing&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-gfg4b","wgBackendResponseTime":209,"wgPageParseReport":{"limitreport":{"cputime":"0.663","walltime":"0.799","ppvisitednodes":{"value":4385,"limit":1000000},"postexpandincludesize":{"value":101537,"limit":2097152},"templateargumentsize":{"value":8850,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":26,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":82528,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 666.655 1 -total"," 22.38% 149.188 1 Template:Reflist"," 13.22% 88.149 2 Template:Navbox"," 12.95% 86.324 1 Template:Parsers"," 11.93% 79.539 2 Template:Cite_web"," 10.60% 70.679 1 Template:Excerpt"," 10.39% 69.247 7 Template:Citation_needed"," 9.56% 63.740 8 Template:Fix"," 8.67% 57.817 1 Template:Short_description"," 6.78% 45.196 4 Template:Ambox"]},"scribunto":{"limitreport-timeusage":{"value":"0.381","limit":"10.000"},"limitreport-memusage":{"value":6579807,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-849f99967d-frntz","timestamp":"20241122140100","ttl":2592000,"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":"2024-11-01T00:07:29Z","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>