Op weg naar de Programmeren-bijeenkomst in De Bilt bedacht ik dat ik een onzekerheidje over de juiste interpretatie van formele grammatica's (FG's) — en in het bijzonder Backus-Naur Forms (BNF's) — wel in de groep zou kunnen gooien. Na afloop stond ik inderdaad vaster in mijn schoenen, maar het was niet iedereen duidelijk geworden wat ik nu eigenlijk te berde had willen brengen. Bovendien kondigde iemand aan dat-ie er nog een appeltje met me over te schillen had. Daarom wil ik op deze plaats wat gedegener (maar nog steeds volgens de lijnen van mijn gedachtengang op die zaterdag) uiteenzetten waar het me in eerste instantie om te doen was en wat daar in latere instantie nog bij kwam. Mijn meest recente inzichten heb ik eveneens in deze tekst verwerkt. Na het aanstippen van wat een FG eigenlijk is en een greep uit de soms wat uiteenlopende terminologieën die rondwaren, zal ik de zaken die aan de orde kwamen een voor een bij langsgaan:
Formele oftewel generatieve grammatica's
Een FG is een metataal waarmee door middel van een stelsel van herschrijfregels syntactisch correcte uitdrukkingen in een doeltaal kunnen worden voortgebracht. De metaschrijver kan daarbij ambiëren de syntax van die doeltaal eenduidig en volledig in kaart te brengen, al lukt dat niet altijd vanwege de complexiteit van de doeltaal en/of de gebrekkige uitdrukkingsmiddelen van de metataal.
De doeltaal bevat een zeker alfabet aan symbolen, die in de metataal als terminale symbolen of kortweg terminals (ook wel literals genoemd) worden opgevoerd. Daarnaast kent de metataal nog andere metasymbolen. Onmisbaar zijn in elk geval de volgende twee categorieën. Ten eerste de niet-terminale symbolen of kortweg non-terminals, die als variabele of klasse worden gebruikt. Je komt hiervoor ook wel de Engelse term placeholder tegen, waar we in het Nederlands dan weer het fraaie woord pantoniem voor hebben. Ter aanduiding van de naam van de non-terminal kan het woord meta-identifier worden gebruikt. Voor deze post houd ik het verder maar consequent op 'pantoniem'. Ten tweede heeft de metataal meta-operatoren nodig.
Dit zijn voldoende ingrediënten om duidelijk te maken hoe een FG werkt. Elke regel schrijft voor hoe een pantoniem te vervangen is door een of meer combinaties van terminals en pantoniemen. Uiteindelijk moet er vanuit elk pantoniem al herschrijvend een wandeling door de regels naar ten minste één terminal te maken zijn. Ieder pantoniem heeft dus een of meer eindoplossingen. Eén pantoniem in de FG fungeert als startsymbool. Van hieruit zou je de complete syntax van de doeltaal moeten kunnen produceren.
Wat probeert een regel precies uit te drukken?
Voor dit betoog heb ik een zeer eenvoudige FG-notatie bedacht, volgens combinatiewijze I (mijn voorkeur) bijvoorbeeld:
x ?= "1" | "2" | "3"
Hierin staan de terminale symbolen tussen aanhalingstekens en is het pantoniem gecursiveerd. De verticale streep is een meta-operator met de betekenis "of". De wat breedsprakiger combinatiewijze II verduidelijkt dit met behulp van de in de wiskunde gebruikelijke logische OF-operator ∨:
(x ?= "1") ∨ (x ?= "2") ∨ (x ?= "3")
Nu heb ik helaas ook nog eens metahaakjes nodig om de evaluatievolgorde aan te geven. Combinatiewijze III doet het zonder expliciete OF-operator:
x ?= "1"
x ?= "2"
x ?= "3"
Hier is elke nieuwe herschrijfregel een impliciete uitbreiding van wat eraan voorafgaat. Of zou het juist een impliciete beperking van het voorafgaande kunnen zijn? Daar raken we het probleem waar ik mee zat. Het gaat om de vraag wat er precies met de meta-operator ?= wordt bedoeld. Voor de beantwoording moet ik de verzamelingenleer maar van stal halen en daarbij de volgende conventie aanhouden: X (vetgedrukte hoofdletter) is de verzameling van alle geldige waarden van het pantoniem x (corresponderende kleine letter in cursief). Laat nu A = {"1", "2", "4", "8"} zijn, en B = {"2", "3", "4"}. Dan is de vereniging A ∪ B = {"1", "2", "3", "4", "8"} en de doorsnede A ∩ B = {"2", "4"}. X ⊆ Y betekent: X is een deelverzameling van Y of gelijk aan Y. Van de herschrijfregel
x ?= a | b
zijn drie interpretaties mogelijk, die ik allemaal een eigen variant van de ?=-operator zal geven:
(1) x >= a | b ⟺ A ∪ B ⊆ X (productieregel)
(2) x <= a | b ⟺ X ⊆ A ∪ B (beperkingsregel)
(3) x == a | b ⟺ X = A ∪ B (volledige definitie)
Iedere regel van het type (1) is in staat geldige waarden voor het pantoniem x te produceren, maar niet per se alle mogelijke waarden. Misschien zijn er nog andere productieregels die mogeijkheden toevoegen. Regeltype (2) geeft aan dat niets buiten A ∪ B is toegestaan, maar laat in het midden of er binnen A ∪ B nog verboden vruchten hangen. Regeltype (3) is de combinatie van beide, en daarmee zowel een volledige productieregel als een volledige beperkingsregel.
Voorbeelden van type (1) met combinatiewijze III zijn te vinden in https://en.wikipedia.org/wiki/Production_%28computer_science%29 en https://en.wikipedia.org/wiki/Formal_grammar. Weliswaar hoeft elke regel op zich niet alle mogelijkheden te dekken, maar het totale stelsel van regels wordt geacht wel compleet te zijn. Genoemde artikelen laten zien dat alle regels met hetzelfde linkerlid via OF zijn gekoppeld, want iedere regel blijkt de mogelijkheden van dat pantoniem verder uit te breiden.
Type (2) zul je niet zou gauw in FG's tegenkomen. ISO/IEC 10206:1991 voor Extended Pascal lijkt zo'n mechanisme te bevatten, als ik afga op wat (https://www.cl.cam.ac.uk/~mgk25/iso-14977-paper.pdf) erover zegt. Omdat het om verdere beperkingen gaat, zal dat EN-koppelingen tussen de regels vergen. Ik vermoed dat zulke constructies alleen bedoeld zijn voor beperkingen die afhangen van de omstandigheden. Handig dan wellicht, maar het doet wel afbreuk aan de eenvoud die type (1) kenmerkt.
Type (3) is BNF in al zijn verschijningsvormen. Ten opzichte van type (1) geldt één extra voorschrift: voor ieder pantoniem mag maar één productieregel worden geschreven, die dan onontkoombaar de volledige (zij het mogelijk geparametriseerde) definitie van dat pantoniem dient te geven. De kwestie EN/OF oftewel inperking/uitbreiding is hiermee van de baan. BNF is feitelijk niets anders dan een wat compactere en meer voor zich sprekende schrijfwijze van type (1), dus de uitdrukkingsmogelijkheden zijn exact gelijk.
Waar wil je de FG voor gebruiken?
(α) Om mensen iets duidelijk te maken
(β) Om niet al te intelligente machines te instrueren
Mijn vraag kwam voort uit (α). Hoe geef ik zo efficiënt (m.b.t. de economie van het formuleren) en effectief (m.b.t. leesbaarheid en begrijpelijkheid) mogelijk de structuur van geldige uitdrukkingen in een zekere formele doeltaal aan? Wat moet ik doen wanneer ik niet volledig kan of wil zijn? Het lijkt me zaak expliciet te zijn over tekortkomingen in mijn specificaties. Dus als ik voor regels van type (3) kies, voor een BNF-achtige metataal dus, mag ik niet suggereren dat een regel compleet is terwijl dat niet het geval is. Er zijn wel middelen binnen de metataal te verzinnen om doelbewuste omissies en minder exacte formuleringen netjes af te handelen:
• x == a | b | more — (extra, niet-gespecificeerd pantoniem)
• x == a | b | ?? — (speciale sequentie, zou je een pseudoterminal kunnen noemen)
De welbespraaktheid van BNF's
Dit onderwerp kwam naar mijn gevoel per ongeluk ter sprake toen we het verschil tussen combinatiewijze I en III behandelden, en concludeerden dat deze twee maar beter niet moesten worden gecombineerd in één metataal, al doet Augmented BNF (ABNF) het echter lekker toch. Combinatiewijze II was alleen maar bedoeld om de betekenis van combinatiewijze I te illustreren, niet om in de praktijk te worden toegepast.
De oorspronkelijke BNF, daterend van 1960, is nogal spartaans. Met Extended BNF (EBNF), dat het in 1996 tot ISO/IEC-norm 14977 schopte, kregen we meer luxe. Ik heb EBNF volgens ISO/IEC 14977 alleen maar gebruikt zien worden in publicaties over EBNF volgens ISO/IEC 14977. Verder past iedereen onbekommerd zijn eigen maatwerk-EBNF toe, behalve Internetters die ABNF conform de evoluerende Internet-standaards gebruiken. Die houden zich wèl aan hun gemeenschappelijke norm, voor zover ze die kunnen bijbenen.
Natuurlijk kon ik in 2017 de aandrang niet weerstaan toch maar een eigen, ter onderscheid Overhauled BNF (OBNF) gedoopte variant samen te stellen, daarmee een ietwat pretentieus Improved BNF (IBNF) aan anderen overlatend en mijn belangstellend uitzien naar een Unified BNF (UBNF) evengoed handhavend. Voor wie nog zin heeft in beschouwingen over expressiviteit en ergonomie van BNF's, heb ik een white paper bijgesloten. Een white paper is een document om een idee aan de man te brengen zonder alles te vertellen wat de lezer zou willen weten wanneer deze het een goed idee vindt. Wikipedia verwoordt het een beetje anders.
- Wat probeert een FG-regel (Engels: rule) precies uit te drukken?
- Waar wil je de FG voor gebruiken?
- Hoe kan datgene wat in een BNF moet worden uitgedrukt zo goed mogelijk worden geformuleerd?
Formele oftewel generatieve grammatica's
Een FG is een metataal waarmee door middel van een stelsel van herschrijfregels syntactisch correcte uitdrukkingen in een doeltaal kunnen worden voortgebracht. De metaschrijver kan daarbij ambiëren de syntax van die doeltaal eenduidig en volledig in kaart te brengen, al lukt dat niet altijd vanwege de complexiteit van de doeltaal en/of de gebrekkige uitdrukkingsmiddelen van de metataal.
De doeltaal bevat een zeker alfabet aan symbolen, die in de metataal als terminale symbolen of kortweg terminals (ook wel literals genoemd) worden opgevoerd. Daarnaast kent de metataal nog andere metasymbolen. Onmisbaar zijn in elk geval de volgende twee categorieën. Ten eerste de niet-terminale symbolen of kortweg non-terminals, die als variabele of klasse worden gebruikt. Je komt hiervoor ook wel de Engelse term placeholder tegen, waar we in het Nederlands dan weer het fraaie woord pantoniem voor hebben. Ter aanduiding van de naam van de non-terminal kan het woord meta-identifier worden gebruikt. Voor deze post houd ik het verder maar consequent op 'pantoniem'. Ten tweede heeft de metataal meta-operatoren nodig.
Dit zijn voldoende ingrediënten om duidelijk te maken hoe een FG werkt. Elke regel schrijft voor hoe een pantoniem te vervangen is door een of meer combinaties van terminals en pantoniemen. Uiteindelijk moet er vanuit elk pantoniem al herschrijvend een wandeling door de regels naar ten minste één terminal te maken zijn. Ieder pantoniem heeft dus een of meer eindoplossingen. Eén pantoniem in de FG fungeert als startsymbool. Van hieruit zou je de complete syntax van de doeltaal moeten kunnen produceren.
Wat probeert een regel precies uit te drukken?
Voor dit betoog heb ik een zeer eenvoudige FG-notatie bedacht, volgens combinatiewijze I (mijn voorkeur) bijvoorbeeld:
x ?= "1" | "2" | "3"
Hierin staan de terminale symbolen tussen aanhalingstekens en is het pantoniem gecursiveerd. De verticale streep is een meta-operator met de betekenis "of". De wat breedsprakiger combinatiewijze II verduidelijkt dit met behulp van de in de wiskunde gebruikelijke logische OF-operator ∨:
(x ?= "1") ∨ (x ?= "2") ∨ (x ?= "3")
Nu heb ik helaas ook nog eens metahaakjes nodig om de evaluatievolgorde aan te geven. Combinatiewijze III doet het zonder expliciete OF-operator:
x ?= "1"
x ?= "2"
x ?= "3"
Hier is elke nieuwe herschrijfregel een impliciete uitbreiding van wat eraan voorafgaat. Of zou het juist een impliciete beperking van het voorafgaande kunnen zijn? Daar raken we het probleem waar ik mee zat. Het gaat om de vraag wat er precies met de meta-operator ?= wordt bedoeld. Voor de beantwoording moet ik de verzamelingenleer maar van stal halen en daarbij de volgende conventie aanhouden: X (vetgedrukte hoofdletter) is de verzameling van alle geldige waarden van het pantoniem x (corresponderende kleine letter in cursief). Laat nu A = {"1", "2", "4", "8"} zijn, en B = {"2", "3", "4"}. Dan is de vereniging A ∪ B = {"1", "2", "3", "4", "8"} en de doorsnede A ∩ B = {"2", "4"}. X ⊆ Y betekent: X is een deelverzameling van Y of gelijk aan Y. Van de herschrijfregel
x ?= a | b
zijn drie interpretaties mogelijk, die ik allemaal een eigen variant van de ?=-operator zal geven:
(1) x >= a | b ⟺ A ∪ B ⊆ X (productieregel)
(2) x <= a | b ⟺ X ⊆ A ∪ B (beperkingsregel)
(3) x == a | b ⟺ X = A ∪ B (volledige definitie)
Iedere regel van het type (1) is in staat geldige waarden voor het pantoniem x te produceren, maar niet per se alle mogelijke waarden. Misschien zijn er nog andere productieregels die mogeijkheden toevoegen. Regeltype (2) geeft aan dat niets buiten A ∪ B is toegestaan, maar laat in het midden of er binnen A ∪ B nog verboden vruchten hangen. Regeltype (3) is de combinatie van beide, en daarmee zowel een volledige productieregel als een volledige beperkingsregel.
Voorbeelden van type (1) met combinatiewijze III zijn te vinden in https://en.wikipedia.org/wiki/Production_%28computer_science%29 en https://en.wikipedia.org/wiki/Formal_grammar. Weliswaar hoeft elke regel op zich niet alle mogelijkheden te dekken, maar het totale stelsel van regels wordt geacht wel compleet te zijn. Genoemde artikelen laten zien dat alle regels met hetzelfde linkerlid via OF zijn gekoppeld, want iedere regel blijkt de mogelijkheden van dat pantoniem verder uit te breiden.
Type (2) zul je niet zou gauw in FG's tegenkomen. ISO/IEC 10206:1991 voor Extended Pascal lijkt zo'n mechanisme te bevatten, als ik afga op wat (https://www.cl.cam.ac.uk/~mgk25/iso-14977-paper.pdf) erover zegt. Omdat het om verdere beperkingen gaat, zal dat EN-koppelingen tussen de regels vergen. Ik vermoed dat zulke constructies alleen bedoeld zijn voor beperkingen die afhangen van de omstandigheden. Handig dan wellicht, maar het doet wel afbreuk aan de eenvoud die type (1) kenmerkt.
Type (3) is BNF in al zijn verschijningsvormen. Ten opzichte van type (1) geldt één extra voorschrift: voor ieder pantoniem mag maar één productieregel worden geschreven, die dan onontkoombaar de volledige (zij het mogelijk geparametriseerde) definitie van dat pantoniem dient te geven. De kwestie EN/OF oftewel inperking/uitbreiding is hiermee van de baan. BNF is feitelijk niets anders dan een wat compactere en meer voor zich sprekende schrijfwijze van type (1), dus de uitdrukkingsmogelijkheden zijn exact gelijk.
Waar wil je de FG voor gebruiken?
(α) Om mensen iets duidelijk te maken
(β) Om niet al te intelligente machines te instrueren
Mijn vraag kwam voort uit (α). Hoe geef ik zo efficiënt (m.b.t. de economie van het formuleren) en effectief (m.b.t. leesbaarheid en begrijpelijkheid) mogelijk de structuur van geldige uitdrukkingen in een zekere formele doeltaal aan? Wat moet ik doen wanneer ik niet volledig kan of wil zijn? Het lijkt me zaak expliciet te zijn over tekortkomingen in mijn specificaties. Dus als ik voor regels van type (3) kies, voor een BNF-achtige metataal dus, mag ik niet suggereren dat een regel compleet is terwijl dat niet het geval is. Er zijn wel middelen binnen de metataal te verzinnen om doelbewuste omissies en minder exacte formuleringen netjes af te handelen:
• x == a | b | more — (extra, niet-gespecificeerd pantoniem)
• x == a | b | ?? — (speciale sequentie, zou je een pseudoterminal kunnen noemen)
De welbespraaktheid van BNF's
Dit onderwerp kwam naar mijn gevoel per ongeluk ter sprake toen we het verschil tussen combinatiewijze I en III behandelden, en concludeerden dat deze twee maar beter niet moesten worden gecombineerd in één metataal, al doet Augmented BNF (ABNF) het echter lekker toch. Combinatiewijze II was alleen maar bedoeld om de betekenis van combinatiewijze I te illustreren, niet om in de praktijk te worden toegepast.
De oorspronkelijke BNF, daterend van 1960, is nogal spartaans. Met Extended BNF (EBNF), dat het in 1996 tot ISO/IEC-norm 14977 schopte, kregen we meer luxe. Ik heb EBNF volgens ISO/IEC 14977 alleen maar gebruikt zien worden in publicaties over EBNF volgens ISO/IEC 14977. Verder past iedereen onbekommerd zijn eigen maatwerk-EBNF toe, behalve Internetters die ABNF conform de evoluerende Internet-standaards gebruiken. Die houden zich wèl aan hun gemeenschappelijke norm, voor zover ze die kunnen bijbenen.
Natuurlijk kon ik in 2017 de aandrang niet weerstaan toch maar een eigen, ter onderscheid Overhauled BNF (OBNF) gedoopte variant samen te stellen, daarmee een ietwat pretentieus Improved BNF (IBNF) aan anderen overlatend en mijn belangstellend uitzien naar een Unified BNF (UBNF) evengoed handhavend. Voor wie nog zin heeft in beschouwingen over expressiviteit en ergonomie van BNF's, heb ik een white paper bijgesloten. Een white paper is een document om een idee aan de man te brengen zonder alles te vertellen wat de lezer zou willen weten wanneer deze het een goed idee vindt. Wikipedia verwoordt het een beetje anders.
Geaccepteerd antwoord
Stel je hebt een formele grammatica als:
<x> ::= <a> | <a> <x>
<y> ::= <a> | <y> <a>
De volgorde waarin je de alternatieven noteert maakt niets uit en rechts- of links recursie ook niet. Zowel <x> als <y> matchen met wat <a> matcht, met wat <a> <a> matcht, met wat <a> <a> <a> matcht, .....
Alleen als je een parser gaat schrijven, dan is staartrecursie handiger dan koprecursie: je zou een oneindig aantal <y>eren kunnen herkennen, voordat je aan de eerste <a> toekomt. De conventie is dat het antwoord met de laagste recursiediepte de voorkeur heeft.
<x> ::= <a> | <a> <x>
<y> ::= <a> | <y> <a>
De volgorde waarin je de alternatieven noteert maakt niets uit en rechts- of links recursie ook niet. Zowel <x> als <y> matchen met wat <a> matcht, met wat <a> <a> matcht, met wat <a> <a> <a> matcht, .....
Alleen als je een parser gaat schrijven, dan is staartrecursie handiger dan koprecursie: je zou een oneindig aantal <y>eren kunnen herkennen, voordat je aan de eerste <a> toekomt. De conventie is dat het antwoord met de laagste recursiediepte de voorkeur heeft.
Volgens mij is interpretatie (3) de geldige
Stel:
<x> ::= <a> | <b>
en A is de verzameling strings die matchen met non-terminal a en B matcht met b, en X matcht met x
dan is X = A ∪ B, mits er geen andere regels zijn die x definiëren.
Maar dan moet de doorsnede van A en B leeg zijn, anders is de definitie ambigu, zoals in uw voorbeeld.
Stel:
<x> ::= <a> | <b>
en A is de verzameling strings die matchen met non-terminal a en B matcht met b, en X matcht met x
dan is X = A ∪ B, mits er geen andere regels zijn die x definiëren.
Maar dan moet de doorsnede van A en B leeg zijn, anders is de definitie ambigu, zoals in uw voorbeeld.
Feitelijk had ik de BNF en regeltype (3) in mijn oorspronkelijke post synoniem verklaard. Misschien wat voorbarig. Maar eerst iets over de eis A ∩ B = ∅. Mijn uitgangspunt was (abstracte symbolen onderstreept en haakjes toegevoegd om de evaluatievolgorde duidelijk te maken):
x ?= (a | b) ⟺ X $ (A ∪ B)
Hierin zijn ?= en $ symbolen die nog moeten worden opgelost. Voor interpretatie (1), (2) en (3) is $ gelijk aan resp. ⊇, ⊆ en =, waarmee vervolgens de betekenis van ?= is verklaard. Van de | had ik voetstoots aangenomen dat deze een inclusieve OF voorstelt. Een exclusieve OF zou ik ter onderscheid zo kunnen presenteren:
x ?= (a ‖ b) ⟺ (X $ (A ∪ B)) ∧ (A ∩ B = ∅)
Hierbij schrijft de clausule A ∩ B = ∅ niets voor m.b.t. de doeltaal, maar legt ze eventuele exclusiviteitsfouten in de regelformuleringen bloot.
Mijn 'inclusieve' BNF-opvatting bevat nooit ambiguïteiten of contradicties. Wel is er kans op redundantie doordat A en B elkaar (al dan niet gedeeltelijk) zouden kunnen overlappen. De vraag is hoe onwenselijk dat in de praktijken (α) en (β) is. Ik heb bestaande grammatica's er niet op nageplozen of die zich werkelijk houden aan een 'exclusieve' grammatica. Mocht de 'exclusieve' BNF de gangbare norm zijn, dan zij dat zo. Hoe dan ook, we kunnen bij dezen vaststellen dat er zes interpretaties mogelijk zijn van:
x ?= (a † b)
namelijk {>=, <=, ==} × {|, ‖}. Ik nummer de erbij gekomen interpretaties ten gevolge van ‖ maar door met (4) t/m (6).
Dan mijn voorbarigheid. Wat moet ik aan met het volgende samenhangende stel regels binnen één grammatica:
x ?= (a | b) ⟺ X $ (A ∪ B)
x ¿= c ⟺ X ¥ C
Zulke constructies komen werkelijk voor, onder meer in ISO/IEC 10206:1991 voor Extended Pascal. Nu heb ik er niet zo'n moeite mee de daar toegepaste metataal zo snel mogelijk aan de vergetelheid prijs te geven. Maar Augmented BNF (https://en.wikipedia.org/wiki/Augmented_Backus%E2%80%93Naur_form) bezondigt zich er ook aan. Daarbij is ABNF niet zo gemakkelijk te negeren: een levende FG-standaard die zich nog steeds de namen van Backus en Naur aanmeet. Wat blijkt? $ is ⊇ en ¥ is ook ⊇. Regels m.b.t. dezelfde X zijn via OF aan elkaar verbonden. RFC 5234 (https://datatracker.ietf.org/doc/html/rfc5234) spreekt van 'incremental alternatives'. De eerste regel voor x gebruikt de operator ?=, geschreven als =. Alle volgende regels voor x gebruiken de operator ¿=, geschreven als =/. De betekenis van de ABNF-constructie
x ?= (a | b) ⟺ X $ (A ∪ B)
Hierin zijn ?= en $ symbolen die nog moeten worden opgelost. Voor interpretatie (1), (2) en (3) is $ gelijk aan resp. ⊇, ⊆ en =, waarmee vervolgens de betekenis van ?= is verklaard. Van de | had ik voetstoots aangenomen dat deze een inclusieve OF voorstelt. Een exclusieve OF zou ik ter onderscheid zo kunnen presenteren:
x ?= (a ‖ b) ⟺ (X $ (A ∪ B)) ∧ (A ∩ B = ∅)
Hierbij schrijft de clausule A ∩ B = ∅ niets voor m.b.t. de doeltaal, maar legt ze eventuele exclusiviteitsfouten in de regelformuleringen bloot.
Mijn 'inclusieve' BNF-opvatting bevat nooit ambiguïteiten of contradicties. Wel is er kans op redundantie doordat A en B elkaar (al dan niet gedeeltelijk) zouden kunnen overlappen. De vraag is hoe onwenselijk dat in de praktijken (α) en (β) is. Ik heb bestaande grammatica's er niet op nageplozen of die zich werkelijk houden aan een 'exclusieve' grammatica. Mocht de 'exclusieve' BNF de gangbare norm zijn, dan zij dat zo. Hoe dan ook, we kunnen bij dezen vaststellen dat er zes interpretaties mogelijk zijn van:
x ?= (a † b)
namelijk {>=, <=, ==} × {|, ‖}. Ik nummer de erbij gekomen interpretaties ten gevolge van ‖ maar door met (4) t/m (6).
Dan mijn voorbarigheid. Wat moet ik aan met het volgende samenhangende stel regels binnen één grammatica:
x ?= (a | b) ⟺ X $ (A ∪ B)
x ¿= c ⟺ X ¥ C
Zulke constructies komen werkelijk voor, onder meer in ISO/IEC 10206:1991 voor Extended Pascal. Nu heb ik er niet zo'n moeite mee de daar toegepaste metataal zo snel mogelijk aan de vergetelheid prijs te geven. Maar Augmented BNF (https://en.wikipedia.org/wiki/Augmented_Backus%E2%80%93Naur_form) bezondigt zich er ook aan. Daarbij is ABNF niet zo gemakkelijk te negeren: een levende FG-standaard die zich nog steeds de namen van Backus en Naur aanmeet. Wat blijkt? $ is ⊇ en ¥ is ook ⊇. Regels m.b.t. dezelfde X zijn via OF aan elkaar verbonden. RFC 5234 (https://datatracker.ietf.org/doc/html/rfc5234) spreekt van 'incremental alternatives'. De eerste regel voor x gebruikt de operator ?=, geschreven als =. Alle volgende regels voor x gebruiken de operator ¿=, geschreven als =/. De betekenis van de ABNF-constructie
x = a / b
x =/ c
x =/ d x = a / b / c / d
In theorie zijn alle katten grijs.....
Stel A= { "aap", "noot", "mies" } en B = { "mies", "mien", "miep"}
Laat
<a> ::= "aap", "noot", "mies"
<b> ::= "mies", "mien", "miep"
<x> ::= <a> | <b>
Stel de invoer bevat het woord "mies" en <x> is het startsymbool. De invoer matcht met deze grammatica, maar de grammatica is ambigu omdat de parser niet kan beslissen of die een <a> of een <b> moet lezen.
Stel A= { "aap", "noot", "mies" } en B = { "mies", "mien", "miep"}
Laat
<a> ::= "aap", "noot", "mies"
<b> ::= "mies", "mien", "miep"
<x> ::= <a> | <b>
Stel de invoer bevat het woord "mies" en <x> is het startsymbool. De invoer matcht met deze grammatica, maar de grammatica is ambigu omdat de parser niet kan beslissen of die een <a> of een <b> moet lezen.
Citaat uit de EBNF-standaard [ISO/IEC 14977 : 1996(E)]:
Tijdens het aftasten van de grenzen van BNF was ik nogal gefocust op aspect 2: wat zijn geldige symboolsequenties in de doeltaal? Daarbij zag ik aspect 1 vooral als een praktisch middel om het analysewerk op te knippen in hanteerbare porties. Aspect 3 is echter een wezenlijk onderdeel van grammatica: wat zijn de achterliggende betekenisdragende structuren?
Nu naar het laatste voorbeeld. Ik neem aan dat de komma's in de aangereikte BNF een relict van het knippen en plakken zijn en dat bedoeld is:
<a> ::= "aap" | "noot" | "mies"
<b> ::= "mies" | "mien" | "miep"
<x> ::= <a> | <b>
Wat aspect 2 betreft: "mies" is hoe dan ook een geldige invulling van <x>. Maar aspect 3... is BNF hier ambigu? Niet als je stelt dat de keuzemogelijkheden in de hier te lande gebruikelijke leesrichting moeten worden beproefd. Dan is <x> van het type <a> en is de eerste optie van <b> "dood hout". Het parsingproces is gedetermineerd. Maar als "mies" in de aldus beschreven taal werkelijk twee verschillende rollen <a> en <b> kan vervullen, is de doeltaal inderdaad ambigu en hebben we context nodig om tot een juiste interpretatie te kunnen komen. Daar voorziet BNF niet in.
Een interessant praktijkgeval vond ik in de scripttaal Lua. De ambitie van de makers was om het geheel zonder formele afbakening van statements te kunnen stellen. Regelovergangen hebben geen speciale betekenis, maar er wordt wel een puntkomma achter de hand gehouden voor enkele zeldzame gevallen. Dit is er zo een:
Hierin is de derde regel dubbelzinnig, want uit te leggen als:
De Lua-versies 5.1 t/m 5.4 houden de tweede interpretatie aan. De eerste interpretatie moet worden afgedwongen door tussen x = f en (a).g(42) een puntkomma te zetten. In Lua 5.1 was onderstaande — nogal suggestieve — constructie bovendien verboden:
Per 5.2 is dat hek echter van de dam gehaald, en wordt het geheel als één geldig statement gezien. Anders dan voor JavaScript heb ik voor Lua nooit dringende adviezen gelezen om alle statements toch vooral maar altijd met een puntkomma af te sluiten. Ik zou Lua-programmeurs daarom wel willen waarschuwen: kijk bij statements die met ( beginnen nog eens even goed naar wat er direct aan voorgaat.
Over mijn oorspronkelijke (maar na dit alles qua relevantie wat verblekende) kwestie "wat is een BNF?" heb ik geen duidelijkheid gekregen. Die laat ik dan verder maar rusten, met achterlating van de stelling "Het is niet mogelijk in tekstvorm een contextvrije grammatica te specificeren anders dan in BNF" en overstappend op de nieuwe vraag "Hoe dien je een BNF te lezen?"
A formal syntax definition has three distinct uses:
- it names the various syntactic parts (i.e. non-terminal symbols) of the language;
- it shows which sequences of symbols are valid sentences of the language;
- it shows the syntactic structure of any sentence of the language.
Tijdens het aftasten van de grenzen van BNF was ik nogal gefocust op aspect 2: wat zijn geldige symboolsequenties in de doeltaal? Daarbij zag ik aspect 1 vooral als een praktisch middel om het analysewerk op te knippen in hanteerbare porties. Aspect 3 is echter een wezenlijk onderdeel van grammatica: wat zijn de achterliggende betekenisdragende structuren?
Nu naar het laatste voorbeeld. Ik neem aan dat de komma's in de aangereikte BNF een relict van het knippen en plakken zijn en dat bedoeld is:
<a> ::= "aap" | "noot" | "mies"
<b> ::= "mies" | "mien" | "miep"
<x> ::= <a> | <b>
Wat aspect 2 betreft: "mies" is hoe dan ook een geldige invulling van <x>. Maar aspect 3... is BNF hier ambigu? Niet als je stelt dat de keuzemogelijkheden in de hier te lande gebruikelijke leesrichting moeten worden beproefd. Dan is <x> van het type <a> en is de eerste optie van <b> "dood hout". Het parsingproces is gedetermineerd. Maar als "mies" in de aldus beschreven taal werkelijk twee verschillende rollen <a> en <b> kan vervullen, is de doeltaal inderdaad ambigu en hebben we context nodig om tot een juiste interpretatie te kunnen komen. Daar voorziet BNF niet in.
Een interessant praktijkgeval vond ik in de scripttaal Lua. De ambitie van de makers was om het geheel zonder formele afbakening van statements te kunnen stellen. Regelovergangen hebben geen speciale betekenis, maar er wordt wel een puntkomma achter de hand gehouden voor enkele zeldzame gevallen. Dit is er zo een:
f = function (x) return x end -- een functiedefinitie
a = { g = function (x) return x end } -- een Lua-table (zoiets als een dictionary)
x = f (a).g(42)
print(x)Hierin is de derde regel dubbelzinnig, want uit te leggen als:
- het statement x = f gevolgd door het statement (a).g(42) (beide zijn syntactisch correct)
- één statement waarin de waarde van de expressie f (a).g(42) (een geldige expressie met als uitkomst 42) aan x wordt toegekend
De Lua-versies 5.1 t/m 5.4 houden de tweede interpretatie aan. De eerste interpretatie moet worden afgedwongen door tussen x = f en (a).g(42) een puntkomma te zetten. In Lua 5.1 was onderstaande — nogal suggestieve — constructie bovendien verboden:
x = f
(a).g(42)Per 5.2 is dat hek echter van de dam gehaald, en wordt het geheel als één geldig statement gezien. Anders dan voor JavaScript heb ik voor Lua nooit dringende adviezen gelezen om alle statements toch vooral maar altijd met een puntkomma af te sluiten. Ik zou Lua-programmeurs daarom wel willen waarschuwen: kijk bij statements die met ( beginnen nog eens even goed naar wat er direct aan voorgaat.
Over mijn oorspronkelijke (maar na dit alles qua relevantie wat verblekende) kwestie "wat is een BNF?" heb ik geen duidelijkheid gekregen. Die laat ik dan verder maar rusten, met achterlating van de stelling "Het is niet mogelijk in tekstvorm een contextvrije grammatica te specificeren anders dan in BNF" en overstappend op de nieuwe vraag "Hoe dien je een BNF te lezen?"
is BNF hier ambigu? Niet als je stelt dat de keuzemogelijkheden in de hier te lande gebruikelijke leesrichting moeten worden beproefd.
BNF is niet ambigu, maar de besproken grammatica is het, omdat "mies" zowel als <a> als <b> kan worden geïnterpreteerd. Het is een formele grammatica. Het maakt niet uit in welke volgorde je de alternatieven test, maar je moet wel alle alternatieven testen.
maar je moet wel alle alternatieven testen.
Helder gesproken! Waren het Algol 60-rapport en de ISO/IEC 14977-norm maar zo expliciet over de |-operator. Ik was steeds van een short-circuit OR uitgegaan. Hier te noteren als:
<x> ⏎= <a> | <b>
Oftewel: ren onmiddellijk terug met de eerste de beste match onder je arm. Wanneer de doeltaal wordt gedefinieerd door een ⏎-metataal, kan deze nooit ambigu zijn. De verwerkingsvolgorde van de alternatieven moet wel vaststaan, dus altijd van links naar rechts of (minder intuïtief naar mijn idee) altijd van rechts naar links.
Het uitputtend aftastende BNF zou ik dan zo kunnen noteren:
<x> ⊠= <a> | <b>
Dat vierkantje stelt een checkbox voor: elk alternatief heeft zo'n imaginaire checkbox, aan te kruisen als er een match bij gevonden is. Een non-terminal waarvoor aan het eind meer dan één alternatief blijkt aangekruist legt ambiguïteiten in de doeltaal bloot.
De uitkomst van het doorgaan met herschrijven totdat alle mogelijkheden zijn afgewerkt kan in theorie ook nog een andere betekenis worden gegeven:
<x> ⊙= <a> | <b>
Het rondje stelt een radiobutton voor: elk alternatief heeft een imaginaire radiobutton om bij een match in te drukken. De laatste match wint het op die manier. Ook bij gebruik van een ⊙-metataal zijn ambiguïteiten uitgesloten, mits er in een van tevoren afgesproken volgorde van alternatief naar alternatief wordt gesprongen. Zo op het eerste gezicht lijkt dit me alleen maar het omslachtige spiegelbeeld van de ⏎-benadering.
Goed, in een ⊠-metataal maakt het niet uit in welke volgorde je de verschillende herschrijfalternatieven voor een non-terminal afwerkt, want uiteindelijk moeten ze allemaal aan de beurt komen. Maar hoe zit het met de verwerking van een sequentie van elementen binnen zo'n alternatief? Wanneer er een (direct of indirect) recursief gedefinieerd element bij zit, ligt het gevaar van oneindige recursie op de loer. Er bestaat links-recursiviteit, in welk geval de sequentie binnen een alternatief van rechts naar links moet worden afgewerkt om oneindige recursie te omzeilen:
<x> ::= <x> <a>
en rechts-recursiviteit, waarbij de verwerking juist de andere kant op dient te lopen:
<x> ::= <b> <x>
Wat is de norm bij BNF? Na lezing van het Algol 60-rapport zou ik zeggen: BNF is honderd procent links-recursief. Afgaande op de examenantwoorden in https://www.csee.umbc.edu/courses/331/fall10/exams/331mt2010_b_ans.pdf (m.n. die op vraag 1.11) lijkt het echter per regel te mogen verschillen. Dat impliceert dat het ook per individueel alternatief binnen een regel mag verschillen:
<x> ::= <x> <a> | <b> <x>
Het is, als er geen vaste norm of conventie voor bestaat, aan de lezer om te onderkennen of een sequentie links- dan wel rechts-recursief is en daarnaar te handelen. Indirecte recursie is niet altijd snel te doorzien. Het kan dus flink puzzelwerk worden.
Of de syntaxbeschrijving van Lua 5.4 nog een BNF mag heten, valt in twijfel te trekken. Hier een stel regels met een nogal prominente rol:
<var> ::= Name | <prefixexp> "[" exp "]" | <prefixexp> "." Name
<exp> ::= "nil" | "false" | "true" | Numeral | LiteralString | "..."
| <functiondef> | <prefixexp> | <tableconstructor>
| <exp> <binop> <exp> | <unop> <exp>
<prefixexp> ::= <var> | <functioncall> | "(" exp ")"
<functioncall> ::= <prefixexp> <args> | <prefixexp> ":" Name <args>Prutswerk wil ik het niet noemen. Ik denk dat de stellers willens en wetens offers hebben gebracht om het geheel op één pagina te laten passen. In het voorlaatste alternatief voor <exp> komen de prioriteiten van de binaire operatoren niet tot uitdrukking. Bovendien is dit alternatief tegelijkertijd links- en rechts-recursief. Oei!
Het derde alternatief voor <var> is indirect links-recursief. Wanneer ik deze sequentie van rechts naar links toepas op de strings "a.b.c" en "-.b.c", vind ik dat de eerste voldoet en de tweede niet voldoet. Terechte uitkomsten. Werk ik de andere kant op, dan kan ik wel de geldigheid van de eerste string vaststellen, maar beland ik bij de tweede in een oneindige recursie.
Staan de onvolkomenheden de bruikbaarheid van deze Lua-BNF in de weg? Wat mijn inzichtverwerving in Lua betreft: integendeel! Operatorprioriteiten zijn veel toegankelijker in een afzonderlijk tabelletje te documenteren. Juist de compactheid van deze vereenvoudigde BNF geeft me snel inzicht in wat de taal te bieden heeft en hoe ik syntactisch correcte code moet schrijven. Zonder dat ik de juiste consumptiewijze van BNF's geheel doorgrond en ondanks de haarbal rond <prefixexp> (zie bijgesloten afbeelding).
Ik maak bij het raadplegen gewoon gebruik van mijn aangeboren en vervolgens getrainde menselijk vermogen tot patroonherkenning. Het is vast geen lineair proces. Een niet na te vertellen mix van halfbewuste maar onvolledige top-down en bottom-up analyse en dan daartussen ineens het licht zien. Zoiets. Vraag het de neuroloog.
Toch zou ik graag met een scherpere blik naar BNF's willen kunnen kijken. En weten wat ik precies voorschrijf als ik zelf een BNF opstel.
Geaccepteerd antwoord
Stel je hebt een formele grammatica als:
<x> ::= <a> | <a> <x>
<y> ::= <a> | <y> <a>
De volgorde waarin je de alternatieven noteert maakt niets uit en rechts- of links recursie ook niet. Zowel <x> als <y> matchen met wat <a> matcht, met wat <a> <a> matcht, met wat <a> <a> <a> matcht, .....
Alleen als je een parser gaat schrijven, dan is staartrecursie handiger dan koprecursie: je zou een oneindig aantal <y>eren kunnen herkennen, voordat je aan de eerste <a> toekomt. De conventie is dat het antwoord met de laagste recursiediepte de voorkeur heeft.
<x> ::= <a> | <a> <x>
<y> ::= <a> | <y> <a>
De volgorde waarin je de alternatieven noteert maakt niets uit en rechts- of links recursie ook niet. Zowel <x> als <y> matchen met wat <a> matcht, met wat <a> <a> matcht, met wat <a> <a> <a> matcht, .....
Alleen als je een parser gaat schrijven, dan is staartrecursie handiger dan koprecursie: je zou een oneindig aantal <y>eren kunnen herkennen, voordat je aan de eerste <a> toekomt. De conventie is dat het antwoord met de laagste recursiediepte de voorkeur heeft.
Afgelopen weekend heb ik ontdekt dat men nog het meest over BNF te weten komt door iets over een ander onderwerp te lezen. In mijn geval stuitte ik ergens bij toeval op een link "PEG", een afkorting die ik vagelijk herkende uit het verleden en naar https://en.wikipedia.org/wiki/Parsing_expression_grammar bleek te leiden. Daarin werd BNF in het geheel niet genoemd, maar wel helder het verschil tussen generatieve grammatica's en analytische parsing expressions belicht. Toen besefte ik dat ik een voor de hand liggend stopcriterium voor het verwerken van recursieve productieregels over het hoofd had gezien, namelijk stop met verdere expansie van non-terminals zodra de momentane oogst meer terminals bevat dan de tekst waarmee je die oogst wilt vergelijken. De volgorde waarin de specificaties zijn opgesteld maakt dan niet meer uit, volg ze gewoon van links naar rechts en de uitslag arriveert binnen eindige tijd.
Om voor iedereen inzichtelijk te maken wat ik bedoel, heb ik hier vier grammatica's opgesteld die alleen in volgorde verschillen. Ik gebruik daarvoor een heel beknopte notatie, waarin hoofdletters non-terminals voorstellen en -> en | metasymbolen zijn. Alle andere tekens zijn terminals (bij deze vier syntaxen dus alleen maar a en p):
Vervolgens heb ik handmatig getest of aap en app daaraan voldoen:
Ook bij onderstaande definitie van een floating-pointgetal om de uitdrukking 12.34 te keuren loopt de hierboven gevolgde procedure goed af.
Maar de exercitie vergt nu wel heel veel stappen. Ik kan me goed voorstellen waarom parsers niet op deze wijze te werk gaan. Dat is echter een ander onderwerp. Zoals in mijn vorige post al gesteld, gaat een menselijke lezer gewoonlijk anders met BNF-regels en de te toetsen uitdrukkingen om. Holistisch, zou je die benadering kunnen noemen. Wel met het gevaar dat eventuele ambiguïteiten niet worden opgemerkt.
Om voor iedereen inzichtelijk te maken wat ik bedoel, heb ik hier vier grammatica's opgesteld die alleen in volgorde verschillen. Ik gebruik daarvoor een heel beknopte notatie, waarin hoofdletters non-terminals voorstellen en -> en | metasymbolen zijn. Alle andere tekens zijn terminals (bij deze vier syntaxen dus alleen maar a en p):
S -> Ap
A -> a | aA
X -> Bp
B -> a | Ba
Y -> Cp
C -> aC | a
Z -> Dp
D -> Da | aVervolgens heb ik handmatig getest of aap en app daaraan voldoen:
aap? S -> Ap -> ap (too short)
Ap -> aAp -> aap (identical) => ACCEPTED
aAp -> aaAp -> aaap (too long)
aaAp -> aaaAp (too long)
app? S -> Ap -> ap (too short)
Ap -> aAp -> app (different) => REJECTED
aAp -> aaAp -> aaap (too long)
aaAp -> aaaAp (too long)
aap? X -> Bp -> ap (too short)
Bp -> Bap -> aap (identical) => ACCEPTED
Bap -> Baap -> aaap (too long)
Baap -> Baaap (too long)
app? X -> Bp -> ap (too short)
Bp -> Bap -> aap (different) => REJECTED
Bap -> Baap -> aaap (too long)
Baap -> Baaap (too long)
aap? Y -> Cp -> aCp -> aaCp -> aaaCp (too long)
aaCp -> aaap (too long)
aCp -> aap (identical) => ACCEPTED
Cp -> ap (too short)
app? Y -> Cp -> aCp -> aaCp -> aaaCp (too long)
aaCp -> aaap (too long)
aCp -> aap (different) => REJECTED
Cp -> ap (too short)
aap? Z -> Dp -> Dap -> Daap -> Daaap (too long)
Daap -> aaap (too long)
Dap -> aap (identical) => ACCEPTED
Dp -> ap (too short)
app? Z -> Dp -> Dap -> Daap -> Daaap (too long)
Daap -> aaap (too long)
Dap -> aap (different) => REJECTED
Dp -> ap (too short)Ook bij onderstaande definitie van een floating-pointgetal om de uitdrukking 12.34 te keuren loopt de hierboven gevolgde procedure goed af.
F -> N.N
N -> D | ND
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Maar de exercitie vergt nu wel heel veel stappen. Ik kan me goed voorstellen waarom parsers niet op deze wijze te werk gaan. Dat is echter een ander onderwerp. Zoals in mijn vorige post al gesteld, gaat een menselijke lezer gewoonlijk anders met BNF-regels en de te toetsen uitdrukkingen om. Holistisch, zou je die benadering kunnen noemen. Wel met het gevaar dat eventuele ambiguïteiten niet worden opgemerkt.
- Pagina :
- 1
Er zijn nog geen reacties op dit bericht.
Reageer als een van de eersten op dit bericht!
Reageer als een van de eersten op dit bericht!