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>Top-down 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":"202497b2-3188-43e3-93b0-a8276872dad4","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Top-down_parsing","wgTitle":"Top-down parsing","wgCurRevisionId":1238178623,"wgRevisionId":1238178623,"wgArticleId":339102,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Parsing algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Top-down_parsing","wgRelevantArticleId":339102,"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":10000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q15419395","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.math.styles":"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","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","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.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%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="Top-down parsing - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Top-down_parsing"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Top-down_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/Top-down_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-Top-down_parsing rootpage-Top-down_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=Top-down+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=Top-down+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=Top-down+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=Top-down+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-Programming_language_application" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Programming_language_application"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Programming language application</span> </div> </a> <ul id="toc-Programming_language_application-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Accommodating_left_recursion_in_top-down_parsing" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Accommodating_left_recursion_in_top-down_parsing"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Accommodating left recursion in top-down parsing</span> </div> </a> <ul id="toc-Accommodating_left_recursion_in_top-down_parsing-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Time_and_space_complexity_of_top-down_parsing" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Time_and_space_complexity_of_top-down_parsing"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Time and space complexity of top-down parsing</span> </div> </a> <ul id="toc-Time_and_space_complexity_of_top-down_parsing-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-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">5</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">6</span> <span>References</span> </div> </a> <ul id="toc-References-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">7</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">Top-down 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 13 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-13" 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">13 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%A7%D9%84%D8%AA%D8%AD%D9%84%D9%8A%D9%84_%D9%85%D9%86_%D8%A3%D8%B9%D9%84%D9%89_%D8%A5%D9%84%D9%89_%D8%A3%D8%B3%D9%81%D9%84" 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-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Syntaktick%C3%A1_anal%C3%BDza_shora_dol%C5%AF" title="Syntaktická analýza shora dolů – Czech" lang="cs" hreflang="cs" data-title="Syntaktická analýza shora dolů" 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-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%AD%D9%84%DB%8C%D9%84%DA%AF%D8%B1_%D8%A8%D8%A7%D9%84%D8%A7_%D8%A8%D9%87_%D9%BE%D8%A7%DB%8C%DB%8C%D9%86" 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-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%95%98%ED%96%A5%EC%8B%9D_%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-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Parsiranje_od_vrha_prema_dnu" title="Parsiranje od vrha prema dnu – Croatian" lang="hr" hreflang="hr" data-title="Parsiranje od vrha prema dnu" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%83%E3%83%97%E3%83%80%E3%82%A6%E3%83%B3%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/Ovenfra-ned-parser" title="Ovenfra-ned-parser – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Ovenfra-ned-parser" 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-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Analiza_zst%C4%99puj%C4%85ca" title="Analiza zstępująca – Polish" lang="pl" hreflang="pl" data-title="Analiza zstępująca" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/An%C3%A1lise_de_cima_para_baixo" title="Análise de cima para baixo – Portuguese" lang="pt" hreflang="pt" data-title="Análise de cima para baixo" 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_top-down" title="Parsare top-down – Romanian" lang="ro" hreflang="ro" data-title="Parsare top-down" 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%9D%D0%B8%D1%81%D1%85%D0%BE%D0%B4%D1%8F%D1%89%D0%B8%D0%B9_%D1%81%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-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0_%D0%BD%D0%B0%D0%BD%D0%B8%D0%B6%D0%B5" title="Анализа наниже – Serbian" lang="sr" hreflang="sr" data-title="Анализа наниже" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9D%D0%B8%D0%B7%D1%85%D1%96%D0%B4%D0%BD%D0%B8%D0%B9_%D1%81%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> </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/Q15419395#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/Top-down_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:Top-down_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/Top-down_parsing"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Top-down_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=Top-down_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/Top-down_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=Top-down_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=Top-down_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/Top-down_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/Top-down_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=Top-down_parsing&oldid=1238178623" 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=Top-down_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=Top-down_parsing&id=1238178623&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%2FTop-down_parsing"><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%2FTop-down_parsing"><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=Top-down_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=Top-down_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 id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q15419395" 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">Parsing technique</div> <p><b>Top-down parsing</b> in <a href="/wiki/Computer_science" title="Computer science">computer science</a> is a <a href="/wiki/Parsing" title="Parsing">parsing</a> strategy where one first looks at the highest level of the <a href="/wiki/Parse_tree" title="Parse tree">parse tree</a> and works down the parse tree by using the rewriting rules of a <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a>.<sup id="cite_ref-GruneJacobs2007_1-0" class="reference"><a href="#cite_note-GruneJacobs2007-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> <a href="/wiki/LL_parser" title="LL parser">LL parsers</a> are a type of parser that uses a top-down parsing strategy. </p><p>Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general <a href="/wiki/Parse_tree" title="Parse tree">parse tree</a> structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural <a href="/wiki/Language" title="Language">languages</a> and <a href="/wiki/Computer_language" title="Computer language">computer languages</a>. </p><p>Top-down parsing can be viewed as an attempt to find <a href="/wiki/Context-free_grammar#Derivations_and_syntax_trees" title="Context-free grammar">left-most derivations</a> 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. Inclusive choice is used to accommodate <a href="/wiki/Syntactic_ambiguity" title="Syntactic ambiguity">ambiguity</a> by expanding all alternative right-hand-sides of grammar rules.<sup id="cite_ref-AhoSethiUllman_1986_2-0" class="reference"><a href="#cite_note-AhoSethiUllman_1986-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>Simple implementations of top-down parsing do not terminate for <a href="/wiki/Left_recursion" title="Left recursion">left-recursive</a> grammars, and top-down parsing with backtracking may have <a href="/wiki/Exponential_time" class="mw-redirect" title="Exponential time">exponential time</a> complexity with respect to the length of the input for ambiguous <a href="/wiki/Context-free_grammar" title="Context-free grammar">CFGs</a>.<sup id="cite_ref-AhoUllman_1972_3-0" class="reference"><a href="#cite_note-AhoUllman_1972-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> However, more sophisticated top-down parsers have been created by Frost, Hafiz, and Callaghan,<sup id="cite_ref-FrostHafizCallaghan_2007_4-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2007-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-FrostHafizCallaghan_2008_5-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2008-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> which do <a href="#Accommodating_left_recursion_in_top-down_parsing">accommodate ambiguity and left recursion</a> in <a href="/wiki/Time_complexity#Polynomial_time" title="Time complexity">polynomial time</a> and which generate polynomial-sized representations of the potentially exponential number of parse trees. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Programming_language_application">Programming language application</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Top-down_parsing&action=edit&section=1" title="Edit section: Programming language application"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Compiler" title="Compiler">compiler</a> parses input from a programming language to an internal representation by matching the incoming symbols to <a href="/wiki/Formal_grammar#The_syntax_of_grammars" title="Formal grammar">production rules</a>. Production rules are commonly defined using <a href="/wiki/Backus%E2%80%93Naur_form" title="Backus–Naur form">Backus–Naur form</a>. An <a href="/wiki/LL_parser" title="LL parser">LL parser</a> is a type of parser that does top-down parsing by applying each production rule to the incoming symbols, working from the left-most symbol yielded on a production rule and then proceeding to the next production rule for each non-terminal symbol encountered. In this way the parsing starts on the Left of the result side (right side) of the production rule and evaluates non-terminals from the Left first and, thus, proceeds down the parse tree for each new non-terminal before continuing to the next symbol for a production rule. </p><p>For example: </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow aBC}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>a</mi> <mi>B</mi> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\rightarrow aBC}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28d9ee9c0ebd99bf95d4efe4ecc9cbca885efa38" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.117ex; height:2.176ex;" alt="{\displaystyle A\rightarrow aBC}"></span></li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\rightarrow c\mid cd}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">→</mo> <mi>c</mi> <mo>∣</mo> <mi>c</mi> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B\rightarrow c\mid cd}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7a9e6a8871b3fd4c7f4471427dd077009654673" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.545ex; height:2.843ex;" alt="{\displaystyle B\rightarrow c\mid cd}"></span></li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\rightarrow df\mid eg}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo stretchy="false">→</mo> <mi>d</mi> <mi>f</mi> <mo>∣</mo> <mi>e</mi> <mi>g</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\rightarrow df\mid eg}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b149399fc127a4b1d34247a6babf987d78a22595" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.012ex; height:2.843ex;" alt="{\displaystyle C\rightarrow df\mid eg}"></span></li></ul> <p>which produces the string <i>A</i>=<i>acdf</i> </p><p>would match <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow aBC}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>a</mi> <mi>B</mi> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\rightarrow aBC}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28d9ee9c0ebd99bf95d4efe4ecc9cbca885efa38" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.117ex; height:2.176ex;" alt="{\displaystyle A\rightarrow aBC}"></span> and attempt to match <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\rightarrow c\mid cd}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">→</mo> <mi>c</mi> <mo>∣</mo> <mi>c</mi> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B\rightarrow c\mid cd}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7a9e6a8871b3fd4c7f4471427dd077009654673" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.545ex; height:2.843ex;" alt="{\displaystyle B\rightarrow c\mid cd}"></span> next. Then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\rightarrow df\mid eg}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo stretchy="false">→</mo> <mi>d</mi> <mi>f</mi> <mo>∣</mo> <mi>e</mi> <mi>g</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\rightarrow df\mid eg}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b149399fc127a4b1d34247a6babf987d78a22595" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.012ex; height:2.843ex;" alt="{\displaystyle C\rightarrow df\mid eg}"></span> would be tried. As one may expect, some languages are more ambiguous than others. For a non-ambiguous language, in which all productions for a non-terminal produce distinct strings, the string produced by one production will not start with the same symbol as the string produced by another production. A non-ambiguous language may be parsed by an LL(1) grammar where the (1) signifies the parser reads ahead one token at a time. For an ambiguous language to be parsed by an LL parser, the parser must lookahead more than 1 symbol, e.g. LL(3). </p><p>The common solution to this problem is to use an <a href="/wiki/LR_parser" title="LR parser">LR parser</a>, which is a type of <a href="/wiki/Shift-reduce_parser" title="Shift-reduce parser">shift-reduce parser</a>, and does <a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">bottom-up parsing</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Accommodating_left_recursion_in_top-down_parsing">Accommodating left recursion in top-down parsing</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Top-down_parsing&action=edit&section=2" title="Edit section: Accommodating left recursion in top-down parsing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a> that contains <a href="/wiki/Left_recursion" title="Left recursion">left recursion</a> cannot be <a href="/wiki/Parsing" title="Parsing">parsed</a> by a naive <a href="/wiki/Recursive_descent_parser" title="Recursive descent parser">recursive descent parser</a> unless they are converted to a weakly equivalent right-recursive form. However, recent research demonstrates that it is possible to accommodate left-recursive grammars (along with all other forms of general <a href="/wiki/Context-free_grammar" title="Context-free grammar">CFGs</a>) in a more sophisticated top-down parser by use of curtailment. A <a href="/wiki/Recognizer" class="mw-redirect" title="Recognizer">recognition</a> algorithm that accommodates <a href="/wiki/Ambiguous_grammar" title="Ambiguous grammar">ambiguous grammars</a> and curtails an ever-growing direct left-recursive parse by imposing depth restrictions with respect to input length and current input position, is described by Frost and Hafiz in 2006.<sup id="cite_ref-FrostHafiz2006_6-0" class="reference"><a href="#cite_note-FrostHafiz2006-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> That algorithm was extended to a complete <a href="/wiki/Parsing" title="Parsing">parsing</a> algorithm to accommodate indirect (by comparing previously computed context with current context) as well as direct left-recursion in <a href="/wiki/Polynomial" title="Polynomial">polynomial</a> time, and to generate compact polynomial-size representations of the potentially exponential number of parse trees for highly ambiguous grammars by Frost, Hafiz and Callaghan in 2007.<sup id="cite_ref-FrostHafizCallaghan_2007_4-1" class="reference"><a href="#cite_note-FrostHafizCallaghan_2007-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> The algorithm has since been implemented as a set of <a href="/wiki/Parser_combinator" title="Parser combinator">parser combinators</a> written in the <a href="/wiki/Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a> programming language. The implementation details of these new set of combinators can be found in a paper<sup id="cite_ref-FrostHafizCallaghan_2008_5-1" class="reference"><a href="#cite_note-FrostHafizCallaghan_2008-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> by the authors, which was presented in PADL'08. The <a rel="nofollow" class="external text" href="http://www.cs.uwindsor.ca/~hafiz/proHome.html">X-SAIGA</a> site has more about the algorithms and implementation details. </p><p>Additionally, one may use a <a href="/w/index.php?title=Graph-structured_stack_(GSS)&action=edit&redlink=1" class="new" title="Graph-structured stack (GSS) (page does not exist)">Graph-structured stack (GSS)</a> in addition to the aforementioned curtailment in order to accommodate left recursion by 'merging' stacks with common prefixes and by preventing infinite recursion, thereby reducing the number and contents of each stack, thereby reducing the time and space complexity of the parser. This leads to an algorithm known as <a href="/w/index.php?title=Generalized_LL_parsing&action=edit&redlink=1" class="new" title="Generalized LL parsing (page does not exist)">Generalized LL parsing</a>, in which you use a GSS, left-recursion curtailment, and an LL(k) parser to parse input strings relative to a given <a href="/wiki/Context-free_grammar" title="Context-free grammar">CFG.</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><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> </p> <div class="mw-heading mw-heading2"><h2 id="Time_and_space_complexity_of_top-down_parsing">Time and space complexity of top-down parsing</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Top-down_parsing&action=edit&section=3" title="Edit section: Time and space complexity of top-down parsing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>When top-down parser tries to parse an ambiguous input with respect to an ambiguous CFG, it may need exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees, which eventually would require exponential memory space. The problem of exponential time complexity in top-down parsers constructed as sets of mutually recursive functions has been solved by <a href="/wiki/Peter_Norvig" title="Peter Norvig">Norvig</a> in 1991.<sup id="cite_ref-Norvig_1991_9-0" class="reference"><a href="#cite_note-Norvig_1991-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> His technique is similar to the use of dynamic programming and state-sets in <a href="/wiki/Earley_parser" title="Earley parser">Earley's algorithm</a> (1970), and tables in the <a href="/wiki/CYK_algorithm" title="CYK algorithm">CYK algorithm</a> of Cocke, Younger and Kasami. </p><p>The key idea is to store results of applying a parser <code>p</code> at position <code>j</code> in a memorable and to reuse results whenever the same situation arises. Frost, Hafiz and Callaghan<sup id="cite_ref-FrostHafizCallaghan_2007_4-2" class="reference"><a href="#cite_note-FrostHafizCallaghan_2007-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-FrostHafizCallaghan_2008_5-2" class="reference"><a href="#cite_note-FrostHafizCallaghan_2008-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> also use <a href="/wiki/Memoization" title="Memoization">memoization</a> for refraining redundant computations to accommodate any form of CFG in <a href="/wiki/Polynomial" title="Polynomial">polynomial</a> time (<a href="/wiki/Big_O_notation" title="Big O notation">Θ</a>(n<sup>4</sup>) for left-recursive grammars and <a href="/wiki/Big_O_notation" title="Big O notation">Θ</a>(n<sup>3</sup>) for non left-recursive grammars). Their top-down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'. Their compact representation is comparable with <a href="/wiki/Masaru_Tomita" title="Masaru Tomita">Tomita</a>'s compact representation of <a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">bottom-up parsing</a>.<sup id="cite_ref-Tomita1985_10-0" class="reference"><a href="#cite_note-Tomita1985-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p><p>Using PEG's, another representation of grammars, packrat parsers provide an elegant and powerful parsing algorithm. See <a href="/wiki/Parsing_expression_grammar" title="Parsing expression grammar">Parsing expression grammar</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Top-down_parsing&action=edit&section=4" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Some of the parsers that use top-down parsing include: </p> <ul><li><a href="/wiki/Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a> parsers<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/Recursive_descent_parser" title="Recursive descent parser">Recursive descent parser</a></li> <li><a href="/wiki/Predictive_parser" class="mw-redirect" title="Predictive parser">Predictive parser</a></li> <li><a href="/wiki/Earley_parser" title="Earley parser">Earley parser</a></li></ul> <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=Top-down_parsing&action=edit&section=5" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">Bottom-up parsing</a></li> <li><a href="/wiki/Parsing" title="Parsing">Parsing</a></li> <li><a href="/wiki/Parsing_expression_grammar" title="Parsing expression grammar">Parsing expression grammar</a></li></ul> <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=Top-down_parsing&action=edit&section=6" 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-GruneJacobs2007-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-GruneJacobs2007_1-0">^</a></b></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 id="CITEREFDick_GruneCeriel_J.H._Jacobs2007" class="citation book cs1">Dick Grune; Ceriel J.H. Jacobs (29 October 2007). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=05xA_d5dSwAC&q=%22top-down%22"><i>Parsing Techniques: A Practical Guide</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-0-387-68954-8" title="Special:BookSources/978-0-387-68954-8"><bdi>978-0-387-68954-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Parsing+Techniques%3A+A+Practical+Guide&rft.pub=Springer+Science+%26+Business+Media&rft.date=2007-10-29&rft.isbn=978-0-387-68954-8&rft.au=Dick+Grune&rft.au=Ceriel+J.H.+Jacobs&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D05xA_d5dSwAC%26q%3D%2522top-down%2522&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATop-down+parsing" class="Z3988"></span></span> </li> <li id="cite_note-AhoSethiUllman_1986-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-AhoSethiUllman_1986_2-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAhoSethiUllman1986" class="citation book cs1"><a href="/wiki/Alfred_Aho" title="Alfred Aho">Aho, Alfred V.</a>; <a href="/wiki/Ravi_Sethi" title="Ravi Sethi">Sethi, Ravi</a>; <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Ullman, Jeffrey D.</a> (1986). <a rel="nofollow" class="external text" href="https://archive.org/details/compilersprincip00ahoa"><i>Compilers, principles, techniques, and tools</i></a> (Rep. with corrections. ed.). Addison-Wesley Pub. Co. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0201100884" title="Special:BookSources/978-0201100884"><bdi>978-0201100884</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Compilers%2C+principles%2C+techniques%2C+and+tools&rft.edition=Rep.+with+corrections.&rft.pub=Addison-Wesley+Pub.+Co.&rft.date=1986&rft.isbn=978-0201100884&rft.aulast=Aho&rft.aufirst=Alfred+V.&rft.au=Sethi%2C+Ravi&rft.au=Ullman%2C+Jeffrey+D.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcompilersprincip00ahoa&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATop-down+parsing" class="Z3988"></span></span> </li> <li id="cite_note-AhoUllman_1972-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-AhoUllman_1972_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAhoUllman1972" class="citation book cs1"><a href="/wiki/Alfred_Aho" title="Alfred Aho">Aho, Alfred V.</a>; <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Ullman, Jeffrey D.</a> (1972). <a rel="nofollow" class="external text" href="https://archive.org/details/theoryofparsingt00ahoa"><i>The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.)</i></a> (Repr. ed.). Englewood Cliffs, NJ: Prentice-Hall. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0139145568" title="Special:BookSources/978-0139145568"><bdi>978-0139145568</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+Theory+of+Parsing%2C+Translation%2C+and+Compiling+%28Volume+1%3A+Parsing.%29&rft.place=Englewood+Cliffs%2C+NJ&rft.edition=Repr.&rft.pub=Prentice-Hall&rft.date=1972&rft.isbn=978-0139145568&rft.aulast=Aho&rft.aufirst=Alfred+V.&rft.au=Ullman%2C+Jeffrey+D.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Ftheoryofparsingt00ahoa&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATop-down+parsing" class="Z3988"></span></span> </li> <li id="cite_note-FrostHafizCallaghan_2007-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-FrostHafizCallaghan_2007_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FrostHafizCallaghan_2007_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-FrostHafizCallaghan_2007_4-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">Frost, R., Hafiz, R. and Callaghan, P. (2007) " <a rel="nofollow" class="external text" href="https://aclanthology.info/pdf/W/W07/W07-2215.pdf">Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars</a> ." <i>10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE </i>, Pages: 109 - 120, June 2007, Prague. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20181112231051/https://aclanthology.info/pdf/W/W07/W07-2215.pdf">Archived</a> from the original on 12 November 2018.</span> </li> <li id="cite_note-FrostHafizCallaghan_2008-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-FrostHafizCallaghan_2008_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FrostHafizCallaghan_2008_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-FrostHafizCallaghan_2008_5-2"><sup><i><b>c</b></i></sup></a></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-FrostHafiz2006-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-FrostHafiz2006_6-0">^</a></b></span> <span class="reference-text">Frost, R. and Hafiz, R. (2006) " <a rel="nofollow" class="external text" href="http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/SIGPLAN_06.pdf">A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time</a>." <i>ACM SIGPLAN Notices</i>, Volume 41 Issue 5, Pages: 46 - 54. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1149982.1149988">10.1145/1149982.1149988</a></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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFScottJohnstone" class="citation web cs1">Scott, Elizabeth; Johnstone, Adrian. <a rel="nofollow" class="external text" href="http://dotat.at/tmp/gll.pdf">"GLL Parsing"</a> <span class="cs1-format">(PDF)</span>. <i>dotat.at</i>. <a href="/wiki/University_of_London" title="University of London">University of London</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=dotat.at&rft.atitle=GLL+Parsing&rft.aulast=Scott&rft.aufirst=Elizabeth&rft.au=Johnstone%2C+Adrian&rft_id=http%3A%2F%2Fdotat.at%2Ftmp%2Fgll.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATop-down+parsing" class="Z3988"></span></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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFScottJohnstone" class="citation web cs1">Scott, Elizabeth; Johnstone, Adrian. <a rel="nofollow" class="external text" href="https://pure.royalholloway.ac.uk/portal/files/26408385/postprint.pdf">"Structuring the GLL parsing algorithm for performance"</a> <span class="cs1-format">(PDF)</span>. <i>dotat.at</i>. <a href="/wiki/University_of_London" title="University of London">University of London</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=dotat.at&rft.atitle=Structuring+the+GLL+parsing+algorithm+for+performance&rft.aulast=Scott&rft.aufirst=Elizabeth&rft.au=Johnstone%2C+Adrian&rft_id=https%3A%2F%2Fpure.royalholloway.ac.uk%2Fportal%2Ffiles%2F26408385%2Fpostprint.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATop-down+parsing" class="Z3988"></span></span> </li> <li id="cite_note-Norvig_1991-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-Norvig_1991_9-0">^</a></b></span> <span class="reference-text">Norvig, P. (1991) “<a rel="nofollow" class="external text" href="https://aclanthology.info/pdf/J/J91/J91-1004.pdf">Techniques for automatic memoisation with applications to context-free parsing</a>.” <i>Journal - Computational Linguistics</i> Volume 17, Issue 1, Pages: 91 - 98.</span> </li> <li id="cite_note-Tomita1985-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-Tomita1985_10-0">^</a></b></span> <span class="reference-text">Tomita, M. (1985) “<a rel="nofollow" class="external text" href="https://books.google.com/books?id=DAjkBwAAQBAJ">Efficient Parsing for Natural Language</a>.” <i>Kluwer, Boston, MA</i>.</span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Pereira, Fernando CN, and David HD Warren. "<a rel="nofollow" class="external text" href="http://cgi.di.uoa.gr/~takis/pereira-warren.pdf">Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks</a>." Artificial intelligence 13.3 (1980): 231-278.</span> </li> </ol></div></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=Top-down_parsing&action=edit&section=7" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://www.cs.uwindsor.ca/~hafiz/proHome.html">X-SAIGA</a> - eXecutable SpecificAtIons of GrAmmars</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 href="/wiki/Parsing" title="Parsing">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a class="mw-selflink selflink">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><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=Top-down_parsing&oldid=1238178623">https://en.wikipedia.org/w/index.php?title=Top-down_parsing&oldid=1238178623</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">Category</a>: <ul><li><a href="/wiki/Category:Parsing_algorithms" title="Category:Parsing algorithms">Parsing algorithms</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:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</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 2 August 2024, at 14:32<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=Top-down_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-4zjqf","wgBackendResponseTime":610,"wgPageParseReport":{"limitreport":{"cputime":"0.301","walltime":"0.428","ppvisitednodes":{"value":749,"limit":1000000},"postexpandincludesize":{"value":18882,"limit":2097152},"templateargumentsize":{"value":400,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":34609,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 342.219 1 -total"," 41.55% 142.177 1 Template:Reflist"," 29.19% 99.909 1 Template:Short_description"," 26.26% 89.852 3 Template:Cite_book"," 25.36% 86.787 1 Template:Parsers"," 24.31% 83.187 1 Template:Navbox"," 13.04% 44.626 3 Template:Main_other"," 12.92% 44.200 2 Template:Pagetype"," 12.41% 42.482 1 Template:SDcat"," 3.46% 11.845 2 Template:Cite_web"]},"scribunto":{"limitreport-timeusage":{"value":"0.183","limit":"10.000"},"limitreport-memusage":{"value":4093426,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-4zjqf","timestamp":"20241122141527","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Top-down parsing","url":"https:\/\/en.wikipedia.org\/wiki\/Top-down_parsing","sameAs":"http:\/\/www.wikidata.org\/entity\/Q15419395","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q15419395","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-10-12T01:22:18Z","dateModified":"2024-08-02T14:32:47Z","headline":"parsing technique"}</script> </body> </html>