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>Van Wijngaarden grammar - 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":"6c02faa1-10cb-4265-bdf5-9693b4bd31b1","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Van_Wijngaarden_grammar","wgTitle":"Van Wijngaarden grammar","wgCurRevisionId":1249874614,"wgRevisionId":1249874614,"wgArticleId":1544998,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Vague or ambiguous geographic scope from December 2018","All articles with unsourced statements","Articles with unsourced statements from March 2016","Articles with unsourced statements from August 2015","Formal languages","Parsing","Compiler construction","Dutch inventions"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName": "Van_Wijngaarden_grammar","wgRelevantArticleId":1544998,"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":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1644674","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","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"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","site","mediawiki.page.ready","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.quicksurveys.init","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.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.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="Van Wijngaarden grammar - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Van_Wijngaarden_grammar"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Van_Wijngaarden_grammar&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/Van_Wijngaarden_grammar"> <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-Van_Wijngaarden_grammar rootpage-Van_Wijngaarden_grammar 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=Van+Wijngaarden+grammar" 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=Van+Wijngaarden+grammar" 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=Van+Wijngaarden+grammar" 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=Van+Wijngaarden+grammar" 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-Two_levels" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Two_levels"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Two levels</span> </div> </a> <ul id="toc-Two_levels-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Motivation_and_history" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Motivation_and_history"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Motivation and history</span> </div> </a> <ul id="toc-Motivation_and_history-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">3</span> <span>Examples</span> </div> </a> <button aria-controls="toc-Examples-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 Examples subsection</span> </button> <ul id="toc-Examples-sublist" class="vector-toc-list"> <li id="toc-Agreement_in_English_grammar" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Agreement_in_English_grammar"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Agreement in English grammar</span> </div> </a> <ul id="toc-Agreement_in_English_grammar-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-A_standard_non-context-free_language" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#A_standard_non-context-free_language"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>A standard non-context-free language</span> </div> </a> <ul id="toc-A_standard_non-context-free_language-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Requiring_valid_use_of_variables_in_ALGOL" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Requiring_valid_use_of_variables_in_ALGOL"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Requiring valid use of variables in ALGOL</span> </div> </a> <ul id="toc-Requiring_valid_use_of_variables_in_ALGOL-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-ALGOL_68_examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#ALGOL_68_examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>ALGOL 68 examples</span> </div> </a> <button aria-controls="toc-ALGOL_68_examples-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 ALGOL 68 examples subsection</span> </button> <ul id="toc-ALGOL_68_examples-sublist" class="vector-toc-list"> <li id="toc-ALGOL_68_as_in_the_1968_Final_Report_§2.1" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#ALGOL_68_as_in_the_1968_Final_Report_§2.1"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>ALGOL 68 as in the 1968 Final Report §2.1</span> </div> </a> <ul id="toc-ALGOL_68_as_in_the_1968_Final_Report_§2.1-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-ALGOL_68_as_in_the_1973_Revised_Report_§2.2.1,_§10.1.1" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#ALGOL_68_as_in_the_1973_Revised_Report_§2.2.1,_§10.1.1"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>ALGOL 68 as in the 1973 Revised Report §2.2.1, §10.1.1</span> </div> </a> <ul id="toc-ALGOL_68_as_in_the_1973_Revised_Report_§2.2.1,_§10.1.1-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Implementations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementations"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Implementations</span> </div> </a> <ul id="toc-Implementations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications_outside_of_ALGOL_68" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications_outside_of_ALGOL_68"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Applications outside of ALGOL 68</span> </div> </a> <ul id="toc-Applications_outside_of_ALGOL_68-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> </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">Van Wijngaarden grammar</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 6 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-6" 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">6 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Van-Wijngaarden-Grammatik" title="Van-Wijngaarden-Grammatik – German" lang="de" hreflang="de" data-title="Van-Wijngaarden-Grammatik" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Grammaires_de_van_Wijngaarden" title="Grammaires de van Wijngaarden – French" lang="fr" hreflang="fr" data-title="Grammaires de van Wijngaarden" 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-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Van_Wijngaardenova_gramatika" title="Van Wijngaardenova gramatika – Croatian" lang="hr" hreflang="hr" data-title="Van Wijngaardenova gramatika" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Van_Wijngaardengrammatica" title="Van Wijngaardengrammatica – Dutch" lang="nl" hreflang="nl" data-title="Van Wijngaardengrammatica" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Gram%C3%A1ticas_de_Van_Wijngaarden" title="Gramáticas de Van Wijngaarden – Portuguese" lang="pt" hreflang="pt" data-title="Gramáticas de Van Wijngaarden" 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-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_%D0%B2%D0%B0%D0%BD_%D0%92%D0%B5%D0%B9%D0%BD%D0%B3%D0%B0%D0%B0%D1%80%D0%B4%D0%B5%D0%BD%D0%B0" title="Грамматика ван Вейнгаардена – Russian" lang="ru" hreflang="ru" data-title="Грамматика ван Вейнгаардена" data-language-autonym="Русский" data-language-local-name="Russian" 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/Q1644674#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/Van_Wijngaarden_grammar" 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:Van_Wijngaarden_grammar" 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/Van_Wijngaarden_grammar"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Van_Wijngaarden_grammar&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=Van_Wijngaarden_grammar&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/Van_Wijngaarden_grammar"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Van_Wijngaarden_grammar&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=Van_Wijngaarden_grammar&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/Van_Wijngaarden_grammar" 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/Van_Wijngaarden_grammar" 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=Van_Wijngaarden_grammar&oldid=1249874614" 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=Van_Wijngaarden_grammar&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=Van_Wijngaarden_grammar&id=1249874614&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%2FVan_Wijngaarden_grammar"><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%2FVan_Wijngaarden_grammar"><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=Van_Wijngaarden_grammar&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=Van_Wijngaarden_grammar&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/Q1644674" 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">Notation techniques for grammars in computer science</div> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>Van Wijngaarden grammar</b> (also <b>vW-grammar</b> or <b>W-grammar</b><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>) is a formalism for defining <a href="/wiki/Formal_language" title="Formal language">formal languages</a>. The name derives from the formalism invented by <a href="/wiki/Adriaan_van_Wijngaarden" title="Adriaan van Wijngaarden">Adriaan van Wijngaarden</a><sup id="cite_ref-mr76_2-0" class="reference"><a href="#cite_note-mr76-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> for the purpose of defining the <a href="/wiki/ALGOL_68" title="ALGOL 68">ALGOL 68</a> <a href="/wiki/Programming_language" title="Programming language">programming language</a>. The resulting specification<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> remains its most notable application. </p><p>Van Wijngaarden grammars address the problem that <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a> cannot express agreement or reference, where two different parts of the sentence must agree with each other in some way. For example, the sentence "The birds was eating" is not <a href="/wiki/Standard_English" title="Standard English">Standard English</a> because it fails to <a href="/wiki/Agreement_(linguistics)" title="Agreement (linguistics)">agree on number</a>. A context-free grammar would parse "The birds was eating" and "The birds were eating" and "The bird was eating" in the same way. However, context-free grammars have the benefit of simplicity whereas van Wijngaarden grammars are considered highly complex.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Two_levels">Two levels</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=1" title="Edit section: Two levels"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>W-grammars are <b>two-level grammars</b>: they are defined by a pair of grammars, that operate on different levels: </p> <ul><li>the <i><a href="https://en.wiktionary.org/wiki/hyper-" class="extiw" title="wikt:hyper-">hypergrammar</a></i> is an <a href="/wiki/Attribute_grammar" title="Attribute grammar">attribute grammar</a>, i.e. a set of <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a> rules in which the nonterminals may have attributes; and</li> <li>the <i><a href="/wiki/Meta_(prefix)" title="Meta (prefix)">metagrammar</a></i> is a context-free grammar defining possible values for these attributes.</li></ul> <p>The set of strings generated by a W-grammar is defined by a two-stage process: </p> <ol><li>within each hyperrule, for each attribute that occurs in it, pick a value for it generated by the metagrammar; the result is a normal context-free grammar rule; do this in every possible way;</li> <li>use the resulting (possibly infinite) context-free grammar to generate strings in the normal way.</li></ol> <p>The <i>consistent substitution</i> used in the first step is the same as <a href="/wiki/Substitution_(logic)" title="Substitution (logic)">substitution in predicate logic</a>, and actually supports <a href="/wiki/Logic_programming" title="Logic programming">logic programming</a>; it corresponds to <a href="/wiki/Unification_(computing)" class="mw-redirect" title="Unification (computing)">unification</a> in <a href="/wiki/Prolog" title="Prolog">Prolog</a>, as noted by <a href="/wiki/Alain_Colmerauer" title="Alain Colmerauer">Alain Colmerauer</a><sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Naming_conventions_(geographic_names)" title="Wikipedia:Naming conventions (geographic names)"><span title="The geographic scope near this tag is ambiguous. (December 2018)">where?</span></a></i>]</sup>. </p><p>W-grammars are <a href="/wiki/Turing_complete" class="mw-redirect" title="Turing complete">Turing complete</a>;<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> hence, all decision problems regarding the languages they generate, such as </p> <ul><li>whether a W-grammar generates a given string</li> <li>whether a W-grammar generates no strings at all</li></ul> <p>are <a href="/wiki/Undecidable_problem" title="Undecidable problem">undecidable</a>. </p><p>Curtailed variants, known as <a href="/wiki/Affix_grammar" title="Affix grammar">affix grammars</a>, were developed, and applied in <a href="/wiki/Compiler-compiler" title="Compiler-compiler">compiler construction</a> and to the description of natural languages. </p><p>Definite <a href="/wiki/Logic_programming" title="Logic programming">logic programs</a>, that is, logic programs that make no use of negation, can be viewed as a subclass of W-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> </p> <div class="mw-heading mw-heading2"><h2 id="Motivation_and_history">Motivation and history</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=2" title="Edit section: Motivation and history"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the 1950s, attempts started to apply computers to the recognition, interpretation and translation of natural languages, such as English and Russian. This requires a machine-readable description of the phrase structure of sentences, that can be used to parse and interpret them, and to generate them. Context-free grammars, a concept from <a href="/wiki/Structural_linguistics" title="Structural linguistics">structural linguistics</a>, were adopted for this purpose; their rules can express how sentences are recursively built out of <a href="/wiki/Part_of_speech" title="Part of speech">parts of speech</a>, such as <a href="/wiki/Noun_phrase" title="Noun phrase">noun phrases</a> and <a href="/wiki/Verb_phrase" title="Verb phrase">verb phrases</a>, and ultimately, words, such as <a href="/wiki/Noun" title="Noun">nouns</a>, <a href="/wiki/Verb" title="Verb">verbs</a>, and <a href="/wiki/Pronoun" title="Pronoun">pronouns</a>. </p><p>This work influenced the design and implementation of <a href="/wiki/Programming_language" title="Programming language">programming languages</a>, most notably, of <a href="/wiki/ALGOL_60" title="ALGOL 60">ALGOL 60</a>, which introduced a syntax description in <a href="/wiki/Backus%E2%80%93Naur_form" title="Backus–Naur form">Backus–Naur form</a>. </p><p>However, context-free rules cannot express <a href="/wiki/Agreement_(linguistics)" title="Agreement (linguistics)">agreement</a> or reference (<a href="/wiki/Anaphora_(linguistics)" title="Anaphora (linguistics)">anaphora</a>), where two different parts of the sentence must agree with each other in some way. </p><p>These can be readily expressed in W-grammars. (See example below.) </p><p>Programming languages have the analogous notions of <a href="/wiki/Type_system" title="Type system">typing</a> and <a href="/wiki/Scope_(computer_science)" title="Scope (computer science)">scoping</a>. A compiler or interpreter for the language must recognize which uses of a variable belong together (refer to the same variable). This is typically subject to constraints such as: </p> <ul><li>A variable must be initialized before its value is used.</li> <li>In strongly typed languages, each variable is assigned a type, and all uses of the variable must respect its type.</li> <li>Often, its type must be declared explicitly, before use.</li></ul> <p>W-grammars are based on the idea of providing the nonterminal symbols of context-free grammars with <i>attributes</i> (or <i>affixes</i>) that pass information between the nodes of the <a href="/wiki/Parse_tree" title="Parse tree">parse tree</a>, used to constrain the syntax and to specify the semantics. </p><p>This idea was well known at the time; e.g. <a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a> visited the ALGOL 68 design committee while developing his own version of it, <a href="/wiki/Attribute_grammar" title="Attribute grammar">attribute grammars</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> </p><p>By augmenting the syntax description with attributes, constraints like the above can be checked, ruling many invalid programs out at compile time. As Van Wijngaarden wrote in his preface:<sup id="cite_ref-mr76_2-1" class="reference"><a href="#cite_note-mr76-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <style data-mw-deduplicate="TemplateStyles:r1244412712">.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}</style><blockquote class="templatequote"><p>My main objections were certain to me unnecessary restrictions and the definition of the syntax and semantics. Actually the syntax viewed in MR 75 produces a large number of programs, whereas I should prefer to have the subset of meaningful programs as large as possible, which requires a stricter syntax. [...] it soon became clear that some better tools than the Backus notation might be advantageous [...]. I developed a scheme [...] which enables the design of a language to carry much more information in the syntax than is normally carried.</p></blockquote> <p>Quite peculiar to W-grammars was their strict treatment of attributes as strings, defined by a context-free grammar, on which concatenation is the only possible operation; complex data structures and operations can be defined by <a href="/wiki/Pattern_matching" title="Pattern matching">pattern matching</a>. (See example below.) </p><p>After their introduction in the 1968 <a href="/wiki/ALGOL_68" title="ALGOL 68">ALGOL 68</a> "Final Report", W-grammars were widely considered as too powerful and unconstrained to be practical.<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. (March 2016)">citation needed</span></a></i>]</sup> </p><p>This was partly a consequence of the way in which they had been applied; the 1973 ALGOL 68 "Revised Report" contains a much more readable grammar, without modifying the W-grammar formalism itself. </p><p>Meanwhile, it became clear that W-grammars, when used in their full generality, are indeed too powerful for such practical purposes as serving as the input for a <a href="/wiki/Parser_generator" class="mw-redirect" title="Parser generator">parser generator</a>. They describe precisely all <a href="/wiki/Recursively_enumerable_language" title="Recursively enumerable language">recursively enumerable languages</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> which makes parsing impossible in general: it is an <a href="/wiki/Undecidable_problem" title="Undecidable problem">undecidable problem</a> to decide whether a given string can be generated by a given W-grammar. </p><p>Hence, their use must be seriously constrained when used for automatic parsing or translation. Restricted and modified variants of W-grammars were developed to address this, e.g. </p> <ul><li><a href="/wiki/Extended_Affix_Grammar" class="mw-redirect" title="Extended Affix Grammar">Extended Affix Grammars</a> (EAGs), applied to describe the grammars of <a href="/wiki/Natural_language" title="Natural language">natural language</a> such as English and Spanish);</li> <li><a href="/wiki/Q-systems" title="Q-systems">Q-systems</a>, also applied to natural language processing;</li> <li>the <a href="/wiki/Compiler_Description_Language" title="Compiler Description Language">CDL</a> series of languages, applied as <a href="/wiki/Compiler_construction" class="mw-redirect" title="Compiler construction">compiler construction</a> languages for <a href="/wiki/Programming_language" title="Programming language">programming languages</a>.</li></ul> <p>After the 1970s, interest in the approach waned; occasionally, new studies are published.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </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=Van_Wijngaarden_grammar&action=edit&section=3" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Agreement_in_English_grammar">Agreement in English grammar</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=4" title="Edit section: Agreement in English grammar"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In English, nouns, pronouns and verbs have attributes such as <a href="/wiki/Grammatical_number" title="Grammatical number">grammatical number</a>, <a href="/wiki/Grammatical_gender" title="Grammatical gender">gender</a>, and <a href="/wiki/Grammatical_person" title="Grammatical person">person</a>, which must agree between <a href="/wiki/Subject_(grammar)" title="Subject (grammar)">subject</a>, main verb, and pronouns referring to the subject: </p> <ul><li>I wash myself.</li> <li>She washes herself.</li> <li>We wash ourselves.</li></ul> <p>are valid sentences; invalid are, for instance: </p> <ul><li>*I washes ourselves.</li> <li>*She wash himself.</li> <li>*We wash herself.</li></ul> <p>Here, agreement serves to stress that both pronouns (e.g. <i>I</i> and <i>myself</i>) refer to the same person. </p><p>A context-free grammar to generate all such sentences: </p> <div class="mw-highlight mw-highlight-lang-bnf mw-content-ltr" dir="ltr"><pre><span></span> <span class="p"><</span><span class="nc">sentence</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">subject</span><span class="p">></span> <span class="p"><</span><span class="nc">verb</span><span class="p">></span> <span class="p"><</span><span class="nc">object</span><span class="p">></span> <span class="p"><</span><span class="nc">subject</span><span class="p">></span> <span class="o">::=</span> I | You | He | She | We | They <span class="p"><</span><span class="nc">verb</span><span class="p">></span> <span class="o">::=</span> wash | washes <span class="p"><</span><span class="nc">object</span><span class="p">></span> <span class="o">::=</span> myself | yourself | himself | herself | ourselves | yourselves | themselves </pre></div> <p>From <code><sentence></code>, we can generate all combinations: </p> <pre>I wash myself I wash yourself I wash himself [...] They wash yourselves They wash themselves </pre> <p>A W-grammar to generate only the valid sentences: </p> <div class="mw-highlight mw-highlight-lang-bnf mw-content-ltr" dir="ltr"><pre><span></span> <sentence <span class="p"><</span><span class="nc">NUMBER</span><span class="p">></span> <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> <span class="p"><</span><span class="nc">PERSON</span><span class="p">></span>> <span class="o">::=</span> <subject <span class="p"><</span><span class="nc">NUMBER</span><span class="p">></span> <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> <span class="p"><</span><span class="nc">PERSON</span><span class="p">></span>> <verb <span class="p"><</span><span class="nc">NUMBER</span><span class="p">></span> <span class="p"><</span><span class="nc">PERSON</span><span class="p">></span>> <object <span class="p"><</span><span class="nc">NUMBER</span><span class="p">></span> <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> <span class="p"><</span><span class="nc">PERSON</span><span class="p">></span>> <subject singular <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 1st> <span class="o">::=</span> I <subject <span class="p"><</span><span class="nc">NUMBER</span><span class="p">></span> <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 2nd> <span class="o">::=</span> You <span class="p"><</span><span class="nc">subject singular male 3rd</span><span class="p">></span> <span class="o">::=</span> He <span class="p"><</span><span class="nc">subject singular female 3rd</span><span class="p">></span> <span class="o">::=</span> She <subject plural <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 1st> <span class="o">::=</span> We <subject singular <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 3rd> <span class="o">::=</span> They <span class="p"><</span><span class="nc">verb singular 1st</span><span class="p">></span> <span class="o">::=</span> wash <span class="p"><</span><span class="nc">verb singular 2nd</span><span class="p">></span> <span class="o">::=</span> wash <span class="p"><</span><span class="nc">verb singular 3rd</span><span class="p">></span> <span class="o">::=</span> washes <verb plural <span class="p"><</span><span class="nc">PERSON</span><span class="p">></span>> <span class="o">::=</span> wash <object singular <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 1st> <span class="o">::=</span> myself <object singular <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 2nd> <span class="o">::=</span> yourself <span class="p"><</span><span class="nc">object singular male 3rd</span><span class="p">></span> <span class="o">::=</span> himself <span class="p"><</span><span class="nc">object singular female 3rd</span><span class="p">></span> <span class="o">::=</span> herself <object plural <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 1st> <span class="o">::=</span> ourselves <object plural <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 2nd> <span class="o">::=</span> yourselves <object plural <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> 3rd> <span class="o">::=</span> themselves <span class="p"><</span><span class="nc">NUMBER</span><span class="p">></span> <span class="o">::=</span>= singular | plural <span class="p"><</span><span class="nc">GENDER</span><span class="p">></span> <span class="o">::=</span>= male | female <span class="p"><</span><span class="nc">PERSON</span><span class="p">></span> <span class="o">::=</span>= 1st | 2nd | 3rd </pre></div> <div class="mw-heading mw-heading3"><h3 id="A_standard_non-context-free_language">A standard non-context-free language</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=5" title="Edit section: A standard non-context-free language"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A well-known non-context-free language is </p> <dl><dd><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^{n}b^{n}a^{n}|n\geq 1\}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>n</mi> <mo>≥</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{a^{n}b^{n}a^{n}|n\geq 1\}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af219bba532d4cc4799a14af6ed6412d82758193" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.387ex; height:2.843ex;" alt="{\displaystyle \{a^{n}b^{n}a^{n}|n\geq 1\}.}"></span></dd></dl> <p>A two-level grammar for this language is the metagrammar </p> <dl><dd>N ::= 1 | N1</dd> <dd>X ::= a | b</dd></dl> <p>together with grammar schema </p> <dl><dd>Start ::= <span class="nowrap">⟨a<sup>N</sup>⟩</span><span class="nowrap">⟨b<sup>N</sup>⟩</span><span class="nowrap">⟨a<sup>N</sup>⟩</span></dd> <dd><span class="nowrap">⟨X<sup>N1</sup>⟩</span> ::= <span class="nowrap">⟨X<sup>N</sup>⟩</span> X</dd> <dd><span class="nowrap">⟨X<sup>1</sup>⟩</span> ::= X</dd></dl> <p>Questions. If one substitutes a new letter, say C, for N1, is the language generated by the grammar preserved? Or N1 should be read as a string of two symbols, that is, N followed by 1? End of questions. </p><p><br /> </p> <div class="mw-heading mw-heading3"><h3 id="Requiring_valid_use_of_variables_in_ALGOL">Requiring valid use of variables in ALGOL</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=6" title="Edit section: Requiring valid use of variables in ALGOL"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Revised Report on the Algorithmic Language Algol 60<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> defines a full context-free syntax for the language. </p><p><a href="/wiki/Assignment_(computer_science)" title="Assignment (computer science)">Assignments</a> are defined as follows (section 4.2.1): </p> <div class="mw-highlight mw-highlight-lang-bnf mw-content-ltr" dir="ltr"><pre><span></span> <span class="p"><</span><span class="nc">left part</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">variable</span><span class="p">></span> := | <span class="p"><</span><span class="nc">procedure identifier</span><span class="p">></span> := <span class="p"><</span><span class="nc">left part list</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">left part</span><span class="p">></span> | <span class="p"><</span><span class="nc">left part list</span><span class="p">></span> <span class="p"><</span><span class="nc">left part</span><span class="p">></span> <span class="p"><</span><span class="nc">assignment statement</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">left part list</span><span class="p">></span> <span class="p"><</span><span class="nc">arithmetic expression</span><span class="p">></span> | <span class="p"><</span><span class="nc">left part list</span><span class="p">></span> <span class="p"><</span><span class="nc">Boolean expression</span><span class="p">></span> </pre></div> <p>A <code><variable></code> can be (amongst other things) an <code><identifier></code>, which in turn is defined as: </p> <pre><identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit> </pre> <p>Examples (section 4.2.2): </p> <pre>s:=p[0]:=n:=n+1+s n:=n+1 A:=B/C-v-q×S S[v,k+2]:=3-arctan(sTIMESzeta) V:=Q>Y^Z </pre> <p>Expressions and assignments must be <a href="/wiki/Type_system" title="Type system">type checked</a>: for instance, </p> <ul><li>in <code>n:=n+1</code>, n must be a number (integer or real);</li> <li>in <code>A:=B/C-v-q×S</code>, all variables must be numbers;</li> <li>in <code>V:=Q>Y^Z</code>, all variables must be of type Boolean.</li></ul> <p>The rules above distinguish between <code><arithmetic expression></code> and <code><Boolean expression></code>, but they cannot verify that the same variable always has the same type. </p><p>This (non-context-free) requirement can be expressed in a W-grammar by annotating the rules with attributes that record, for each variable used or assigned to, its name and type. </p><p>This record can then be carried along to all places in the grammar where types need to be matched, and implement type checking. </p><p>Similarly, it can be used to checking initialization of variables before use, etcetera. </p><p>One may wonder how to create and manipulate such a data structure without explicit support in the formalism for data structures and operations on them. It can be done by using the metagrammar to define a string representation for the data structure and using <a href="/wiki/Pattern_matching" title="Pattern matching">pattern matching</a> to define operations: </p> <div class="mw-highlight mw-highlight-lang-bnf mw-content-ltr" dir="ltr"><pre><span></span> <left part with <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span>> <span class="o">::=</span> <variable with <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span>> := | <procedure identifier with <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span>> := <left part list <span class="p"><</span><span class="nc">TYPEMAP1</span><span class="p">></span>> <span class="o">::=</span> <left part with <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">TYPEMAP1</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">EMPTY</span><span class="p">></span>> | <left part list <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span>> <left part with <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">TYPEMAP1</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span>> <assignment statement <span class="p"><</span><span class="nc">ASSIGNED TO</span><span class="p">></span> <span class="p"><</span><span class="nc">USED</span><span class="p">></span>> <span class="o">::=</span> <left part list <span class="p"><</span><span class="nc">ASSIGNED TO</span><span class="p">></span>> <arithmetic expression <span class="p"><</span><span class="nc">USED</span><span class="p">></span>> | <left part list <span class="p"><</span><span class="nc">ASSIGNED TO</span><span class="p">></span>> <Boolean expression <span class="p"><</span><span class="nc">USED</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">EMPTY</span><span class="p">></span>> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">TYPEMAP1</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED1</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span>> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED2</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">TYPEMAP3</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> is lexicographically before <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">TYPEMAP1</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED1</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span>> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED2</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">TYPEMAP3</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span> is lexicographically before <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">TYPEMAP3</span><span class="p">></span> is <span class="p"><</span><span class="nc">TYPED1</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> added to sorted <span class="p"><</span><span class="nc">TYPEMAP4</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">EMPTY</span><span class="p">></span> is lexicographically before <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span>> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> is <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> followed by <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> is lexicographically before <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span>> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> is <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> followed by <span class="p"><</span><span class="nc">NAME3</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span> is <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> followed by <span class="p"><</span><span class="nc">NAME4</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME3</span><span class="p">></span> is lexicographically before <span class="p"><</span><span class="nc">NAME4</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> is lexicographically before <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span>> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">NAME1</span><span class="p">></span> is <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> followed by <span class="p"><</span><span class="nc">NAME3</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">NAME2</span><span class="p">></span> is <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> followed by <span class="p"><</span><span class="nc">NAME4</span><span class="p">></span>> <where <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> precedes+ <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> <where <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> precedes+ <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> precedes <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> <where <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> precedes+ <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> <span class="o">::=</span> <where <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> precedes+ <span class="p"><</span><span class="nc">LETTER OR DIGIT 3</span><span class="p">></span> <where <span class="p"><</span><span class="nc">LETTER OR DIGIT 3</span><span class="p">></span> precedes+ <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> <span class="p"><</span><span class="nc">where a precedes b</span><span class="p">></span> :== <span class="p"><</span><span class="nc">where b precedes c</span><span class="p">></span> :== [...] <span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="o">::=</span>= real | integer | Boolean <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">LETTER</span><span class="p">></span> | <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> <span class="p"><</span><span class="nc">LETTER</span><span class="p">></span> | <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> <span class="p"><</span><span class="nc">DIGIT</span><span class="p">></span> <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">LETTER</span><span class="p">></span> | <span class="p"><</span><span class="nc">DIGIT</span><span class="p">></span> <span class="p"><</span><span class="nc">LETTER OR DIGIT 1</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> <span class="p"><</span><span class="nc">LETTER OR DIGIT 2</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> <span class="p"><</span><span class="nc">LETTER OR DIGIT 3</span><span class="p">></span> <span class="o">::=</span> <span class="p"><</span><span class="nc">LETTER OR DIGIT</span><span class="p">></span> <span class="p"><</span><span class="nc">LETTER</span><span class="p">></span> <span class="o">::=</span>= a | b | c | [...] <span class="p"><</span><span class="nc">DIGIT</span><span class="p">></span> <span class="o">::=</span>= 0 | 1 | 2 | [...] <span class="p"><</span><span class="nc">NAMES1</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">NAMES</span><span class="p">></span> <span class="p"><</span><span class="nc">NAMES2</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">NAMES</span><span class="p">></span> <span class="p"><</span><span class="nc">ASSIGNED TO</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">NAMES</span><span class="p">></span> <span class="p"><</span><span class="nc">USED</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">NAMES</span><span class="p">></span> <span class="p"><</span><span class="nc">NAMES</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> | <span class="p"><</span><span class="nc">NAME</span><span class="p">></span> <span class="p"><</span><span class="nc">NAMES</span><span class="p">></span> <span class="p"><</span><span class="nc">EMPTY</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">TYPEMAP</span><span class="p">></span> <span class="o">::=</span>= (<span class="p"><</span><span class="nc">TYPED</span><span class="p">></span> <span class="p"><</span><span class="nc">NAME</span><span class="p">></span>) <span class="p"><</span><span class="nc">TYPEMAP</span><span class="p">></span> <span class="p"><</span><span class="nc">TYPEMAP1</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">TYPEMAP</span><span class="p">></span> <span class="p"><</span><span class="nc">TYPEMAP2</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">TYPEMAP</span><span class="p">></span> <span class="p"><</span><span class="nc">TYPEMAP3</span><span class="p">></span> <span class="o">::=</span>= <span class="p"><</span><span class="nc">TYPEMAP</span><span class="p">></span> </pre></div> <p>When compared to the original grammar, three new elements have been added: </p> <ul><li>attributes to the nonterminals in what are now the hyperrules;</li> <li>metarules to specify the allowable values for the attributes;</li> <li>new hyperrules to specify operations on the attribute values.</li></ul> <p>The new hyperrules are <span class="texhtml mvar" style="font-style:italic;">ε</span>-rules: they only generate the empty string. </p> <div class="mw-heading mw-heading2"><h2 id="ALGOL_68_examples">ALGOL 68 examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=7" title="Edit section: ALGOL 68 examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The ALGOL 68 reports use a slightly different notation without <angled brackets>. </p> <div class="mw-heading mw-heading3"><h3 id="ALGOL_68_as_in_the_1968_Final_Report_§2.1"><span id="ALGOL_68_as_in_the_1968_Final_Report_.C2.A72.1"></span>ALGOL 68 as in the 1968 Final Report §2.1</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=8" title="Edit section: ALGOL 68 as in the 1968 Final Report §2.1"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <pre>a) program : open symbol, standard prelude, library prelude option, particular program, exit, library postlude option, standard postlude, close symbol. b) standard prelude : declaration prelude sequence. c) library prelude : declaration prelude sequence. d) particular program : label sequence option, strong CLOSED void clause. e) exit : go on symbol, letter e letter x letter i letter t, label symbol. f) library postlude : statement interlude. g) standard postlude : strong void clause train </pre> <div class="mw-heading mw-heading3"><h3 id="ALGOL_68_as_in_the_1973_Revised_Report_§2.2.1,_§10.1.1"><span id="ALGOL_68_as_in_the_1973_Revised_Report_.C2.A72.2.1.2C_.C2.A710.1.1"></span>ALGOL 68 as in the 1973 Revised Report §2.2.1, §10.1.1</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=9" title="Edit section: ALGOL 68 as in the 1973 Revised Report §2.2.1, §10.1.1"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <pre> program : strong void new closed clause A) EXTERNAL :: standard ; library ; system ; particular. B) STOP :: label letter s letter t letter o letter p. a) program text : STYLE begin token, new LAYER1 preludes, parallel token, new LAYER1 tasks PACK, STYLE end token. b) NEST1 preludes : NEST1 standard prelude with DECS1, NEST1 library prelude with DECSETY2, NEST1 system prelude with DECSETY3, where (NEST1) is (new EMPTY new DECS1 DECSETY2 DECSETY3). c) NEST1 EXTERNAL prelude with DECSETY1 : strong void NEST1 series with DECSETY1, go on token ; where (DECSETY1) is (EMPTY), EMPTY. d) NEST1 tasks : NEST1 system task list, and also token, NEST1 user task PACK list. e) NEST1 system task : strong void NEST1 unit. f) NEST1 user task : NEST2 particular prelude with DECS, NEST2 particular program PACK, go on token, NEST2 particular postlude, where (NEST2) is (NEST1 new DECS STOP). g) NEST2 particular program : NEST2 new LABSETY3 joined label definition of LABSETY3, strong void NEST2 new LABSETY3 ENCLOSED clause. h) NEST joined label definition of LABSETY : where (LABSETY) is (EMPTY), EMPTY ; where (LABSETY) is (LAB1 LABSETY1), NEST label definition of LAB1, NEST joined label definition of$ LABSETY1. i) NEST2 particular postlude : strong void NEST2 series with STOP. </pre> <p>A simple example of the power of W-grammars is clause </p> <pre>a) program text : STYLE begin token, new LAYER1 preludes, parallel token, new LAYER1 tasks PACK, STYLE end token. </pre> <p>This allows BEGIN ... END and { } as block delimiters, while ruling out BEGIN ... } and { ... END. </p><p>One may wish to compare the grammar in the report with the <a href="/wiki/Yacc" title="Yacc">Yacc</a> parser for a subset of ALGOL 68 by Marc van Leeuwen.<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> </p> <div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=10" title="Edit section: Implementations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Anthony Fisher wrote <i>yo-yo</i>,<sup id="cite_ref-yo-yo_12-0" class="reference"><a href="#cite_note-yo-yo-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> a parser for a large class of W-grammars, with example grammars for <i>expressions</i>, <i>eva</i>, <i>sal</i> and <a href="/wiki/Pascal_programming_language" class="mw-redirect" title="Pascal programming language">Pascal</a> (the actual <a href="/wiki/ISO_7185" class="mw-redirect" title="ISO 7185">ISO 7185</a> standard for Pascal uses <a href="/wiki/Extended_Backus%E2%80%93Naur_form" title="Extended Backus–Naur form">extended Backus–Naur form</a>). </p><p><a href="/wiki/Dick_Grune" title="Dick Grune">Dick Grune</a> created a <a href="/wiki/C_(programming_language)" title="C (programming language)">C</a> program that would generate all possible productions of a W-grammar.<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> <div class="mw-heading mw-heading2"><h2 id="Applications_outside_of_ALGOL_68">Applications outside of ALGOL 68</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Van_Wijngaarden_grammar&action=edit&section=11" title="Edit section: Applications outside of ALGOL 68"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The applications of <a href="/wiki/Extended_Affix_Grammar" class="mw-redirect" title="Extended Affix Grammar">Extended Affix Grammars</a> (EAG)s mentioned above can effectively be regarded as applications of W-grammars, since EAGs are so close to W-grammars.<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> </p><p>W-grammars have also been proposed for the description of complex human actions in <a href="/wiki/Ergonomics" title="Ergonomics">ergonomics</a>.<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 2015)">citation needed</span></a></i>]</sup> </p><p>A W-Grammar Description has also been supplied for <a href="/wiki/Ada_(programming_language)" title="Ada (programming language)">Ada</a>.<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> <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=Van_Wijngaarden_grammar&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Affix_grammar" title="Affix grammar">Affix grammar</a></li> <li><a href="/wiki/Extended_Affix_Grammar" class="mw-redirect" title="Extended Affix Grammar">Extended Affix Grammar</a></li> <li><a href="/wiki/Attribute_grammar" title="Attribute grammar">Attribute 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=Van_Wijngaarden_grammar&action=edit&section=13" 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-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</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="CITEREFCleavelandUzgalis1977" class="citation book cs1">Cleaveland, J. Craig; Uzgalis, Robert C. (1977). <i>Grammars for Programming Languages</i>. Elsevier. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-444-00199-3" title="Special:BookSources/978-0-444-00199-3"><bdi>978-0-444-00199-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Grammars+for+Programming+Languages&rft.pub=Elsevier&rft.date=1977&rft.isbn=978-0-444-00199-3&rft.aulast=Cleaveland&rft.aufirst=J.+Craig&rft.au=Uzgalis%2C+Robert+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></span> </li> <li id="cite_note-mr76-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-mr76_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-mr76_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFvan_Wijngaarden1972" class="citation techreport cs1"><a href="/wiki/Adriaan_van_Wijngaarden" title="Adriaan van Wijngaarden">van Wijngaarden, Adriaan</a> (1972-04-04) [Premature and preliminary edition 1965-10-22]. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20171002212915/http://www.eah-jena.de/~kleine/history/languages/VanWijngaarden-MR76.pdf"><i>MR 76: Orthogonal design and description of a formal language</i></a> <span class="cs1-format">(PDF)</span> (Technical report). Amsterdam: <a href="/wiki/Centrum_Wiskunde_%26_Informatica" title="Centrum Wiskunde & Informatica">CWI</a>. Archived from <a rel="nofollow" class="external text" href="http://www.eah-jena.de/~kleine/history/languages/VanWijngaarden-MR76.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2017-10-02.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=MR+76%3A+Orthogonal+design+and+description+of+a+formal+language&rft.place=Amsterdam&rft.pub=CWI&rft.date=1972-04-04&rft.aulast=van+Wijngaarden&rft.aufirst=Adriaan&rft_id=http%3A%2F%2Fwww.eah-jena.de%2F~kleine%2Fhistory%2Flanguages%2FVanWijngaarden-MR76.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" 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 id="CITEREFvan_Wijngaarden" class="citation web cs1">van Wijngaarden, A.; et al. (eds.). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20020124152423/http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm">"Revised Report on the Algorithmic Language ALGOL 68"</a>. Archived from <a rel="nofollow" class="external text" href="http://burks.bton.ac.uk/burks/language/other/a68rr/rrtoc.htm">the original</a> on 24 January 2002.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Revised+Report+on+the+Algorithmic+Language+ALGOL+68&rft_id=http%3A%2F%2Fburks.bton.ac.uk%2Fburks%2Flanguage%2Fother%2Fa68rr%2Frrtoc.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKoster1996" class="citation book cs1"><a href="/wiki/Cornelis_H._A._Koster" title="Cornelis H. A. Koster">Koster, C.H.A</a> (1996). "The making of Algol 68". In Bjørner, D; Broy, M.; Pottosin, I.V. (eds.). <a rel="nofollow" class="external text" href="https://archive.org/details/making-of-algol-68"><i>Perspectives of System Informatics</i></a>. Lecture Notes in Computer Science. Vol. 1181. Berlin: Springer. pp. 55–67. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-62064-8_6">10.1007/3-540-62064-8_6</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-62064-8" title="Special:BookSources/978-3-540-62064-8"><bdi>978-3-540-62064-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+making+of+Algol+68&rft.btitle=Perspectives+of+System+Informatics&rft.place=Berlin&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=55-67&rft.pub=Springer&rft.date=1996&rft_id=info%3Adoi%2F10.1007%2F3-540-62064-8_6&rft.isbn=978-3-540-62064-8&rft.aulast=Koster&rft.aufirst=C.H.A&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fmaking-of-algol-68&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" 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="CITEREFSintzoff1967" class="citation journal cs1">Sintzoff, M. (1967). "Existence of van Wijngaarden syntax for every recursively enumerable set". <i>Annales de la Société Scientifique de Bruxelles</i>. <b>2</b>: 115–118.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annales+de+la+Soci%C3%A9t%C3%A9+Scientifique+de+Bruxelles&rft.atitle=Existence+of+van+Wijngaarden+syntax+for+every+recursively+enumerable+set&rft.volume=2&rft.pages=115-118&rft.date=1967&rft.aulast=Sintzoff&rft.aufirst=M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" 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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDeransartMaluszynski1993" class="citation cs2">Deransart, Pierre; Maluszynski, Jan (1993), <a rel="nofollow" class="external text" href="https://dx.doi.org/10.7551/mitpress/3345.003.0008">"Grammatical Extensions of Logic Programs"</a>, <i>A Grammatical View of Logic Programming</i>, The MIT Press, pp. 109–140, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.7551%2Fmitpress%2F3345.003.0008">10.7551/mitpress/3345.003.0008</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780262290845" title="Special:BookSources/9780262290845"><bdi>9780262290845</bdi></a><span class="reference-accessdate">, retrieved <span class="nowrap">2023-06-14</span></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=A+Grammatical+View+of+Logic+Programming&rft.atitle=Grammatical+Extensions+of+Logic+Programs&rft.pages=109-140&rft.date=1993&rft_id=info%3Adoi%2F10.7551%2Fmitpress%2F3345.003.0008&rft.isbn=9780262290845&rft.aulast=Deransart&rft.aufirst=Pierre&rft.au=Maluszynski%2C+Jan&rft_id=http%3A%2F%2Fdx.doi.org%2F10.7551%2Fmitpress%2F3345.003.0008&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></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="CITEREFKnuth1990" class="citation cs2">Knuth, Donald E (1990), <a rel="nofollow" class="external text" href="http://www-cs-faculty.stanford.edu/~knuth/papers/gag.tex.gz">"The genesis of attribute grammars"</a> <span class="cs1-format">(<a href="/wiki/Plain_TeX" class="mw-redirect" title="Plain TeX">Plain TeX</a>, <a href="/wiki/GZip" class="mw-redirect" title="GZip">gZiped</a>)</span>, <i>Proceedings of the International Conference on Attribute Grammars and Their Applications</i>, <a href="/wiki/Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>: 1–12</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+International+Conference+on+Attribute+Grammars+and+Their+Applications&rft.atitle=The+genesis+of+attribute+grammars&rft.pages=1-12&rft.date=1990&rft.aulast=Knuth&rft.aufirst=Donald+E&rft_id=http%3A%2F%2Fwww-cs-faculty.stanford.edu%2F~knuth%2Fpapers%2Fgag.tex.gz&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" 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="CITEREFSintzoff1967" class="citation journal cs1"><a href="/wiki/Michel_Sintzoff" title="Michel Sintzoff">Sintzoff, M.</a> (1967). "Existence of a van Wijngaarden syntax for every recursively enumerable set". <i>Annales de la Société scientifique de Bruxelles</i>. <b>81</b>: 115–118.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annales+de+la+Soci%C3%A9t%C3%A9+scientifique+de+Bruxelles&rft.atitle=Existence+of+a+van+Wijngaarden+syntax+for+every+recursively+enumerable+set&rft.volume=81&rft.pages=115-118&rft.date=1967&rft.aulast=Sintzoff&rft.aufirst=M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAugusto2023" class="citation journal cs1">Augusto, L. M. (2023). <a rel="nofollow" class="external text" href="https://philpapers.org/archive/AUGTGS-3.pdf">"Two-level grammars: Some interesting properties of van Wijngaarden grammars"</a> <span class="cs1-format">(PDF)</span>. <i>Omega - Journal of Formal Languages</i>. <b>1</b>: 3–34.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Omega+-+Journal+of+Formal+Languages&rft.atitle=Two-level+grammars%3A+Some+interesting+properties+of+van+Wijngaarden+grammars&rft.volume=1&rft.pages=3-34&rft.date=2023&rft.aulast=Augusto&rft.aufirst=L.+M.&rft_id=https%3A%2F%2Fphilpapers.org%2Farchive%2FAUGTGS-3.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" 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"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBackus1963" class="citation journal cs1">Backus, J.W.; et al. (1963). <a rel="nofollow" class="external text" href="https://www.masswerk.at/algol60/report.htm">"Revised report on the algorithmic language ALGOL 60"</a>. <i>The Computer Journal</i>. <b>5</b> (4): 349–367. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F5.4.349">10.1093/comjnl/5.4.349</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Computer+Journal&rft.atitle=Revised+report+on+the+algorithmic+language+ALGOL+60&rft.volume=5&rft.issue=4&rft.pages=349-367&rft.date=1963&rft_id=info%3Adoi%2F10.1093%2Fcomjnl%2F5.4.349&rft.aulast=Backus&rft.aufirst=J.W.&rft_id=https%3A%2F%2Fwww.masswerk.at%2Falgol60%2Freport.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation cs2">"Syntax", <a rel="nofollow" class="external text" href="http://wwwmathlabo.univ-poitiers.fr/~maavl/algol68/syntax68"><i>Algol 68</i></a>, <a href="/wiki/France" title="France">FR</a>: Univ Poitiers</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Syntax&rft.btitle=Algol+68&rft.place=FR&rft.pub=Univ+Poitiers&rft_id=http%3A%2F%2Fwwwmathlabo.univ-poitiers.fr%2F~maavl%2Falgol68%2Fsyntax68&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></span> </li> <li id="cite_note-yo-yo-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-yo-yo_12-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFisher2024" class="citation cs2">Fisher, Anthony (30 July 2024), "yo-yo", <a rel="nofollow" class="external text" href="http://www-users.cs.york.ac.uk/~fisher/software/yoyovwg/"><i>Software</i></a>, <a href="/wiki/United_Kingdom" title="United Kingdom">UK</a>: York</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=yo-yo&rft.btitle=Software&rft.place=UK&rft.pub=York&rft.date=2024-07-30&rft.aulast=Fisher&rft.aufirst=Anthony&rft_id=http%3A%2F%2Fwww-users.cs.york.ac.uk%2F~fisher%2Fsoftware%2Fyoyovwg%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" 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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGrune" class="citation cs2">Grune, Dick, <a rel="nofollow" class="external text" href="http://dickgrune.com/CS/Formal_Languages/vw_generator/"><i>A Two-Level Sentence Generator</i></a>, <a href="/wiki/Netherlands" title="Netherlands">NL</a>: VU</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=A+Two-Level+Sentence+Generator&rft.place=NL&rft.pub=VU&rft.aulast=Grune&rft.aufirst=Dick&rft_id=http%3A%2F%2Fdickgrune.com%2FCS%2FFormal_Languages%2Fvw_generator%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span>.</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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlblasMelichar1991" class="citation book cs1">Alblas, Henk; Melichar, Borivoj (1991). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=zatWjp2ZkHMC&dq=eag+w-grammar&pg=PA371"><i>Attribute Grammars, Applications and Systems</i></a>. Lecture Notes in Computer Science. Vol. 545. Springer. p. 371. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3540545729" title="Special:BookSources/978-3540545729"><bdi>978-3540545729</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Attribute+Grammars%2C+Applications+and+Systems&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=371&rft.pub=Springer&rft.date=1991&rft.isbn=978-3540545729&rft.aulast=Alblas&rft.aufirst=Henk&rft.au=Melichar%2C+Borivoj&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DzatWjp2ZkHMC%26dq%3Deag%2Bw-grammar%26pg%3DPA371&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFlowers" class="citation cs2">Flowers, Roy, <a rel="nofollow" class="external text" href="https://apps.dtic.mil/sti/pdfs/ADA177802.pdf"><i>A W-grammar description for Ada</i></a> <span class="cs1-format">(PDF)</span> (Master thesis), Air Force Institute of Technology, Air University</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=A+W-grammar+description+for+Ada&rft.pub=Air+Force+Institute+of+Technology%2C+Air+University&rft.aulast=Flowers&rft.aufirst=Roy&rft_id=https%3A%2F%2Fapps.dtic.mil%2Fsti%2Fpdfs%2FADA177802.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></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=Van_Wijngaarden_grammar&action=edit&section=14" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAugusto2023" class="citation journal cs1">Augusto, L. M. (2023). <a rel="nofollow" class="external text" href="https://philpapers.org/archive/AUGTVW.pdf">"The van Wijngaarden grammars: A syntax primer with decidable restrictions"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Knowledge Structures and Systems</i>. <b>4</b>: 1–39.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Knowledge+Structures+and+Systems&rft.atitle=The+van+Wijngaarden+grammars%3A+A+syntax+primer+with+decidable+restrictions&rft.volume=4&rft.pages=1-39&rft.date=2023&rft.aulast=Augusto&rft.aufirst=L.+M.&rft_id=https%3A%2F%2Fphilpapers.org%2Farchive%2FAUGTVW.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPemberton2016" class="citation web cs1"><a href="/wiki/Steven_Pemberton" title="Steven Pemberton">Pemberton, Steven</a> (2016) [1982]. <a rel="nofollow" class="external text" href="http://www.cwi.nl/~steven/vw.html">"Executable Semantic Definition of Programming Languages Using Two-level Grammars (Van Wijngaarden Grammars)"</a>. Amsterdam: Centrum Wiskunde & Informatica.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Executable+Semantic+Definition+of+Programming+Languages+Using+Two-level+Grammars+%28Van+Wijngaarden+Grammars%29&rft.place=Amsterdam&rft.pub=Centrum+Wiskunde+%26+Informatica&rft.date=2016&rft.aulast=Pemberton&rft.aufirst=Steven&rft_id=http%3A%2F%2Fwww.cwi.nl%2F~steven%2Fvw.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPetersson1990" class="citation journal cs1">Petersson, Kent (1990). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20010605175158/http://www.cs.chalmers.se/~kentp/proglang.pdf">"Syntax and Semantics of Programming Languages"</a> <span class="cs1-format">(PDF)</span>. <i>Draft Lecture Notes</i>. Archived from <a rel="nofollow" class="external text" href="http://www.cs.chalmers.se/~kentp/proglang.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 5 June 2001.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Draft+Lecture+Notes&rft.atitle=Syntax+and+Semantics+of+Programming+Languages&rft.date=1990&rft.aulast=Petersson&rft.aufirst=Kent&rft_id=http%3A%2F%2Fwww.cs.chalmers.se%2F~kentp%2Fproglang.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AVan+Wijngaarden+grammar" class="Z3988"></span></li></ul>    </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=Van_Wijngaarden_grammar&oldid=1249874614">https://en.wikipedia.org/w/index.php?title=Van_Wijngaarden_grammar&oldid=1249874614</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:Formal_languages" title="Category:Formal languages">Formal languages</a></li><li><a href="/wiki/Category:Parsing" title="Category:Parsing">Parsing</a></li><li><a href="/wiki/Category:Compiler_construction" title="Category:Compiler construction">Compiler construction</a></li><li><a href="/wiki/Category:Dutch_inventions" title="Category:Dutch inventions">Dutch inventions</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_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:Vague_or_ambiguous_geographic_scope_from_December_2018" title="Category:Vague or ambiguous geographic scope from December 2018">Vague or ambiguous geographic scope from December 2018</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_March_2016" title="Category:Articles with unsourced statements from March 2016">Articles with unsourced statements from March 2016</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_August_2015" title="Category:Articles with unsourced statements from August 2015">Articles with unsourced statements from August 2015</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 7 October 2024, at 08:59<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=Van_Wijngaarden_grammar&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-694cf4987f-dlxpk","wgBackendResponseTime":177,"wgPageParseReport":{"limitreport":{"cputime":"0.391","walltime":"0.821","ppvisitednodes":{"value":1900,"limit":1000000},"postexpandincludesize":{"value":38791,"limit":2097152},"templateargumentsize":{"value":3154,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":8,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":82136,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 733.860 1 -total"," 28.79% 211.277 1 Template:Reflist"," 20.97% 153.865 1 Template:Short_description"," 15.23% 111.787 3 Template:Cite_book"," 10.08% 73.967 6 Template:Main_other"," 9.70% 71.148 1 Template:SDcat"," 9.38% 68.819 2 Template:Pagetype"," 6.40% 46.981 3 Template:Fix"," 5.29% 38.790 6 Template:Cite_journal"," 4.98% 36.513 1 Template:Where"]},"scribunto":{"limitreport-timeusage":{"value":"0.230","limit":"10.000"},"limitreport-memusage":{"value":5947625,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-nbcxx","timestamp":"20241122142302","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Van Wijngaarden grammar","url":"https:\/\/en.wikipedia.org\/wiki\/Van_Wijngaarden_grammar","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1644674","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1644674","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":"2005-02-25T19:03:51Z","dateModified":"2024-10-07T08:59:24Z","headline":"one of the two main notation techniques for context-free grammars in computer science"}</script> </body> </html>