zaterdag 29 januari 2022
  12 Replies
  2K Visits
In hoeverre kunnen we het aan de computer overlaten om de structuur van een gegeven uitdrukking zichtbaar te maken aan de hand van een in BNF opgestelde grammatica? We hebben bijvoorbeeld de volgende productieregels voor rekenkundige uitdrukkingen bedacht:
<aexpr>   ::= <term> | <aexpr> <addop> <term>
<term> ::= <factor> | <term> <multop> <factor>
<factor> ::= <ufactor> | <addop> <factor>
<ufactor> ::= <primary> | <primary> "^" <factor>
<primary> ::= "n" | "(" <aexpr> ")"
<addop> ::= "+" | "-"
<multop> ::= "*" | "/"

En nu willen we de uitdrukking −n−(n+n)*−n^−n^n zodanig laten annoteren dat de door bovenstaande regels opgelegde evaluatievolgorde zichtbaar wordt. Bijvoorbeeld met behulp van accolades:

    {{{{{−}{{{n}}}}}}{−}{{{{{({{{{{{n}}}}}{+}{{{{n}}}}})}}}}{*}{{−}{{{n}^{{−}{{{n}^{{{n}}}}}}}}}}}

Eventueel te vereenvoudigen tot:

    {−n}−{{({n+n})}*{−{n^{−{n^n}}}}}

Het parsen van de BNF zelf is geen onderdeel van deze opgave. Je mag elke notatie kiezen waarmee je de betekenis van de regels gemakkelijk in de toegepaste programmeertaal kunt uitdrukken. Zo zou het rechterlid van de vierde productieregel in Python heel praktisch kunnen worden geformuleerd als ((primary,), (primary, '^', factor)), dus als een tuple van alternatieven die ieder op hun beurt als een tuple van opeenvolgende terminals en/of non-terminals zijn weergegeven.

BNF is een notatiewijze voor generatieve grammatica's (zie ook https://www.hcc.nl/forum/formele-grammatica-s#antwoord-21931). Daarom lijkt het me onvermijdelijk dat het te bouwen programma zich ook moet gedragen als een expressiegenerator die geen enkele mogelijkheid tot een match met de te analyseren uitdrukking over het hoofd ziet en dus ook eventuele ambiguïteiten blootlegt. Nu kan zo'n generator in theorie oneindig veel geldige expressies genereren, wat vrij veel is. Het is dus zaak te onderkennen waar het generatieproces kan worden afgebroken, omdat doorgaan op de ingeslagen weg geen enkele zin meer heeft en de resterende energie beter kan worden gestoken in kansrijkere alternatieven. Als handreiking naar criteria hiervoor heb ik één extra BNF-spelregel toegevoegd: een non-terminal mag nooit een lege string opleveren. Alle grammatica's zijn indien nodig wel zo te herformuleren dat hieraan wordt voldaan.

Is dit oplosbaar? Na mijn experimenten op papier en op de pc ziet het daar wel naar uit. Althans in theorie. Mijn poging om de hierboven gegeven uitdrukking te laten analyseren door een hiertoe geschreven Lua-script (draaiend via de LuaJIT-compiler) was na 24 uur nog steeds aan de gang. Een wat minder ambitieuze onderneming om dan maar −n−(x)*−n^−n^n te analyseren op basis van een vereenvoudigde regel <primary> ::= "n" | "(x)" duurde toch altijd nog bijna 50 minuten en had toen 232.610.143 generatoraanroepen achter de rug, die samen 53.901.073 expressies hadden voortgebracht. De grootste recursiediepte daarbij was 88. Al die tijd was de processorbelasting torenhoog, maar besloeg het benodigde werkgeheugen slechts rond de 2 MB en vond er geen I/O plaats. Het is me in elk geval duidelijk dat ik deze taak momenteel aanmerkelijk sneller zelf kan volbrengen dan mijn pc dat kan. Daar staat tegenover dat ik eerder fouten pleeg te maken.

De volgende vraag is nu: kan de performance worden verbeterd? Aperte programmeeronhandigheden had ik al verwijderd (leverde een factor 10 snelheidswinst op). Ik heb gebruik gemaakt van dynamische arrays (tables in Lua en lists in Python) die ik inderdaad laat uitdijen en inkrimpen. Proeven met constant houden van de fysieke arraygrootte en administratief alleen de daarin ondergebrachte virtuele arrays in grootte laten variëren leverde slechts marginale snelheidswinst op. Mogelijk moeten er andere datastructuren te hulp worden geroepen via talen als C, Lisp (linked lists?) en Forth (stacks?). Maar gelet op de aanwas van het aantal generatoraanroepen en geproduceerde expressies vrees ik dat het performanceprobleem daarmee slechts een paar stappen voor ons uit te schuiven zal zijn.

Daarmee wordt de kwestie eerder: valt er niet een fundamenteel beter, intelligenter algoritme te verzinnen om het stelsel van productieregels en de te analyseren uitdrukking zodanig met elkaar te confronteren dat alle theoretisch mogelijke interpretaties van die uitdrukking nog steeds worden onderkend? Misschien krijgt de computer dan toch weer de kans het van mij te winnen. Ik heb inmiddels wel twee verschillende richtingen in gedachten die uitzicht bieden op een veel economischer verwerking.

Mijn knutsels tot nu toe heb ik ondergebracht in bijgesloten ZIP-bestand. Je kunt het geheel opvatten als een spoiler, als een voetstuk om op voort te bouwen of als een na kennisneming terzijde te leggen want uitzichtloze aanpak. Doe ermee wat je wilt. Van het bestand lees-mij.txt kun je in elk geval zonder bezwaar kennisnemen, want het legt slechts uit wat er in de bundel te vinden is en welke grammatica's en testgevallen ik beproefd heb. Het geeft niets prijs over mijn algoritme. De meeverpakte Lua- en Python-scripts doen dat uiteraard wel.
Bijlagen
6 maanden geleden
·
#22029
Het is niet zo moeilijk om een parser voor rekenkundige expressies te schrijven, die aan de genoemde grammatica voldoet. Nix 'expressiegenerator'. Als je een parse tree hebt, kun je de expressie ook weer afdrukken met de accolades.

Ik kwam nog een parsing probleem tegen in de supermarkt: een artikel met een bordje met "2 + 1 gratis".

Dit lijkt me op twee manieren te parsen:
{2 (stuks betalen)} {+ (en)} {1 (artikel) gratis (krijgen)}
{{2 + 1} (3 stuks)} { gratis (krijgen)}
6 maanden geleden
·
#22033
Het gegeven voorbeeld kan ik inderdaad soepel vertalen naar — om maar iets te noemen — een PEG (https://en.wikipedia.org/wiki/Parsing_expression_grammar en als je door wilt lezen https://bford.info/pub/lang/peg.pdf):
AExpr   <- Term (AddOp Term)*
Term <- Factor (MultOp Factor)*
Factor <- UFactor / AddOp Factor
UFactor <- Primary ("^" Factor)?
Primary <- "n" / "(" AExpr ")"
AddOp <- "+" / "-"
MultOp <- "*" / "/"

Op PEG gebaseerde parsers zullen de klus vervolgens wel moeiteloos klaren, neem ik aan. Alleen de voorafgaande stap nog. Hoe een willekeurig BNF-formularium automatisch om te zetten naar een PEG-equivalent of andere gelijkwaardige parsertaal naar keuze?
6 maanden geleden
·
#22057
Ik heb er even naar gekeken. Ik neem aan dat regel 3 moet luiden:
<factor> ::= <ufactor> | <addop> <ufactor>

Anders zou de volgende string worden geaccepteerd: "+-+-++---+--++n".

Merk op dat regels 1 en 2 links-recursief zijn en de operaties links-associatief en 4 is rechts-recursief en rechts-associatief, zoals het hoort.
(deze opgave gaat niet over politiek:-)

Vervolgens vroeg ik mij of de resulterende grammatica misschien ambigu was, aangezien <addop> op twee plaatsen voorkomt (regels 1 en 3).

Dat is niet het geval, omdat een <ufactor> altijd tenminste een "^", een "n" of een "(" en een ")" moet bevatten;
zodoende is de invoer string ondubbelzinnig te groeperen tot "{-n} - {( n + n )} * {-n} ^ {-n} ^ n", enz.

Niet zo moelijk om met de hand een recursive-descent parsertje voor te schrijven, dus.
6 maanden geleden
·
#22059
Anders zou de volgende string worden geaccepteerd: "+-+-++---+--++n".
Dat was ook precies mijn bedoeling. Python en Ruby consumeren het probleemloos, want die kennen geen ++ en −− operatoren.

Niet zo moelijk om met de hand een recursive-descent parsertje voor te schrijven, dus.
Dat recursive-descent parsertje zou ik dan wel eens willen zien, of moet ik de hele post als zodanig opvatten? Het was trouwens niet mijn opzet BNF werkelijk voor serieus parsewerk in te zetten. Het ging me juist om het tegenovergestelde: ik wil een willekeurig (gegeven of zelfgeschreven) BNF-formularium kunnen toetsen aan de hand van testexpressies. Zegt het werkelijk wat ik denk te begrijpen dat het zou moeten zeggen? Hier nog twee van zulke experimenten. Het eerste Lua-script is een vertaling van je gewaarwording in de supermarkt:
local GGP = require "GGP-2"

local Bargain =
{ aanbieding = 'som prijs | som "+" aanbieding'
, som = 'getal | som "+" getal'
, getal = 'cijfer | getal cijfer'
, cijfer = '"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"'
, prijs = '"gratis"'
}

GGP.translate(Bargain)
GGP:start("2+1gratis", aanbieding)
GGP:publish()
Uitvoer:
2 unique structures match "2+1gratis" after 81146 calls generating 14748 expressions (max. depth was 38):

{{{{{2}}}+{{1}}}{gratis}}
{{{{2}}}+{{{{1}}}{gratis}}}

or reduced:

{2+1}gratis
2+{1gratis}
(Na de inbouw van een extra slimmigheidje ging de verwerking 13.000 keer zo snel. Met de oude GGP-versie duurde het bijna drie uur.) Hier heb ik de dubbelzinnigheid natuurlijk moedwillig opgezocht.

Het tweede script illustreert daarentegen de werkelijk voorkomende dangling else valkuil:
local GGP = require "GGP-2"

local Conditional =
{ cond_stmt = 'if_stmt | if_stmt "else." stmt'
, if_stmt = '"if.Cond.then." stmt'
, stmt = '"Stmt." | cond_stmt'
}

GGP.translate(Conditional)
GGP:start("if.Cond.then.if.Cond.then.Stmt.else.Stmt.", cond_stmt)
GGP:publish()
Uitvoer:
2 unique structures match "if.Cond.then.if.Cond.then.Stmt.else.Stmt." after 99 calls generating 24 expressions (max. depth was 16):

{{if.Cond.then.{{{if.Cond.then.{Stmt.}}else.{Stmt.}}}}}
{{if.Cond.then.{{{if.Cond.then.{Stmt.}}}}}else.{Stmt.}}

or reduced:

if.Cond.then.{{if.Cond.then.Stmt.}else.Stmt.}
{if.Cond.then.{if.Cond.then.Stmt.}}else.Stmt.

Natuurlijk kan ik deze situaties zo op het blote oog en eventueel gewapend met een potlood en de achterzijde van een oude envelop ook wel analyseren. Maar ik ken mijn vergissingsvermogen. Dus liever testen door middel van een waarschijnlijk correct programma dat in elk geval geen zwakkere momenten kent.
6 maanden geleden
·
#22069
Hoe moeilijk kan het zijn?
Merk op dat dit progje slechts 1 teken read-ahead nodig heeft en top-down werkt. Links-associatieve definities zijn gerealiseerd als loops, rechts-associatieve als recursie.
Bijlagen
6 maanden geleden
·
#22072
Goed, je hebt een rekenmachientje gebouwd. Wanneer ik de expressie 2+2*1 aanbiedt, antwoordt het programma met 4.

Niet helemaal wat ik zocht. De waarde van 2 + 2 * 1 interesseert me in dit verband niet zozeer. Kennis van wat de diverse operatoren en haakjes precies te betekenen hebben, hoeft wat mij betreft dus niet per se in het programma te worden opgenomen. Het enige wat ik als uitvoer graag wil zien, is een taalkundige ontleding van de aangeboden expressie. Zoiets als 2+{2*1} of {{{{{{{{2}}}}}}}{+}{{{{{{{2}}}}}}{*}{{{{{1}}}}}}}. Of nog mooier:
2+2*1 = <aexpr>
├───<aexpr>
│ └───<term>
│ └───"2"
├───<addop>
│ └───"+"
└───<term>
│───<term>
│ └───"2"
│───<multop>
│ └───"*"
└───<factor>
└───<ufactor>
└───<primary>
└───<number>
└───<digit>
└───"1"

Gelet op de structuur van calc.c lijkt het me niet zo heel moeilijk er extra rapportagevoorzieningen in te bouwen waarmee het programma een verantwoording van de gemaakte berekening (= de intern gevolgde weg, zo te zien) aflegt. Daarmee zijn we er echter nog niet. Het huidige programma kan geen BNF interpreteren. Het is zelf een interpretatie van een BNF-formularium, en wel van een specifiek formularium voor rekenkunde zoals we dat op school hebben geleerd. Voor analyse van de rekenwijze van Excel of Algol 60 zouden aparte calculators gebouwd moeten worden, en voor de grammaticale analyse van if COND then if COND then STMT else STMT zou er eveneens een daarop toegesneden zinsontleder moeten komen. Kortom, wat momenteel nog ontbreekt, is een programmaatje dat op basis van een willekeurig BNF-formularium een eenvoudige parser à la calc.c voortbrengt en vervolgens aan het werk zet. Wellicht kunnen de met de non-terminals corresponderende functies agnostischer en daardoor volgens een met de betreffende productieregel correponderend patroon worden opgezet. Dan zouden ze te genereren moeten zijn. De verschillende aanpak van L- en R-associativiteit biedt zicht op betere performance, vermoed ik.

Ik weet niet of je werkelijk met dit soort ideeën aan het programmeren bent geslagen. Het heeft er soms veel van weg dat we de hele tijd langs elkaar heen zitten te praten. Ik zoek dus een universele BNF-interpreter. Om de scheiding tussen data en algoritmes wat explicieter te maken, heb ik ze nu verder uit elkaar getrokken. Dat onderstreept nog eens waar ik heen wil. Het Lua-script test-BNF-8.lua (programmatuur!) is nu volledig generiek:
local GGP  = require "GGP-2"
local load = loadstring or load -- to be compatible with Lua 5.1 and 5.2+

local expression = arg[1]
local startrule = arg[2]

if expression and startrule then
local L =
assert(load("return {" .. (io.stdin:read "*a"):gsub("\n", ", \n") .. "}"))()
GGP.translate(L)
GGP:start(expression, assert(load("return " .. startrule))())
GGP:publish()
else
io.stderr:write [[
Two arguments required:
(1) a test expression
(2) a non-terminal to start with

]]
end

Aan de hand van de taaldefinitie die via STDIN is aangeboden (data!) vult het script zichzelf aan (zie regel 10) door voor elke productieregel een Lua-functie aan te leggen. Vervolgens wordt de als tweede scriptargument (data!) genoemde productieregel (in dit stadium tevens de naam van een van de gegenereerde Lua-functies) op de als eerste scriptargument (data!) meegegeven testexpressie toegepast (zie regel 11). Hier enkele voorbeelden van hoe het script aan te roepen is:
==> luaJIT test-BNF-8.lua "2+2*1" aexpr < arithmetic.bnf

==> luaJIT test-BNF-8.lua "2+1gratis" aanbieding < bargain.bnf

==> luaJIT test-BNF-8.lua "if Cond then if Cond then Stmt else Stmt " cond_stmt < conditional.bnf

Het bestand conditional.bnf ziet er zo uit:
cond_stmt = 'if_stmt | if_stmt "else " stmt'
if_stmt = '"if Cond then " stmt'
stmt = '"Stmt " | cond_stmt'

Er valt weliswaar nog het nodige aan dit geheel bij te schaven, maar voor een proof of concept vind ik het wel acceptabel zo. Ik heb er een pakketje van gemaakt en dat bijgesloten.

Intussen heb ik ook nog eens gekeken naar de Parsing Expression Grammar (PEG). Nu ik zo diep in de BNF-materie zit, krijg ik bedenkingen tegen notaties zoals AExpr ← Term (AddOp Term)*. Volgens Bryan Ford, de bedenker van PEG, is elke PEG-expressie e* (nul of meer keer e) te vervangen door een nieuwe non-terminal A die gedefinieerd is als A ← e A / ε (waarbij ε een lege string voorstelt). Zou dit omzettingsrecept ook voor EBNF gelden, en zo ja, wat zijn dan de gevolgen? Dat kan ik nu uitproberen. Ik heb een stukje van het PEG-formularium dat ik in mijn tweede post had getoond (grotendeels overgenomen uit het daar genoemde Wikipedia-artikel) als volgt herschreven in arithmetic-from-PEG.bnf:
aexpr  = 'term ADDING' 
term = '"n"'
ADDING = 'addop term ADDING | " "'
addop = '"+" | "-"'

Wanneer ik de expressie n−n−n ontleed m.b.v. arithmetic.bnf, is de gereduceerde uitkomst:

    {n−n}−n

Gelukkig maar. Toets ik n−n−n met arithmetic-from-PEG.bnf, dan krijg ik:

    n{−n{−n }}

Hoe zou ik deze constructie moeten interpreteren? Mijn enthousiasme over de bondige notaties van de extended BNF's is hiermee wel wat bekoeld. De recursieve schrijfwijze van de oorspronkelijke BNF (en andere CFG's) is tenminste zelfverklarend wat betreft de structuur van de taal waarvan het de grammatica beschrijft. Iedere non-terminal heeft er een 'natuurlijke' betekenis. Daarmee is deze manier in communicatief opzicht eigenlijk wel superieur, al oogt ze dan wat omslachtig.
Bijlagen
6 maanden geleden
·
#22078
Die boom was natuurlijk niet goed. Hieronder is-ie volledig uitgegroeid.
2+2*1 = <aexpr>
├───<aexpr>
│ └───<term>
│ └───<factor>
│ └───<ufactor>
│ └───<primary>
│ └───<number>
│ └───<digit>
│ └───"2"
├───<addop>
│ └───"+"
└───<term>
│───<term>
│ └───<factor>
│ └───<ufactor>
│ └───<primary>
│ └───<number>
│ └───<digit>
│ └───"2"
│───<multop>
│ └───"*"
└───<factor>
└───<ufactor>
└───<primary>
└───<number>
└───<digit>
└───"1"
6 maanden geleden
·
#22079
Als je een parser generator zoekt, die zijn er al.
6 maanden geleden
·
#22082
Legio, inderdaad. Dat is het probleem. In https://en.wikipedia.org/wiki/Comparison_of_parser_generators tel ik er 172 (die voor de regular languages niet meegerekend) in drie hoofdcategorieën. Ik ben er om te beginnen nogal sceptisch over of er werkelijk een parsergenerator bestaat die voor het beoogde doel geschikt is (het lijkt me namelijk iets waar helemaal niet veel vraag naar is), en zo ja, of ik die binnen afzienbare tijd weet te vinden. Dan heb ik op z'n minst wat criteria nodig waarop ik een voorselectie kan doen (bijvoorbeeld welke van de 20 à 30 verschillende parsing algoritmes in mijn geval het best kunnen worden toegepast). Pas daarna heeft het zin om eens te kijken naar secundaire aspecten zoals gebruiksvriendelijkheid. De negen-stappenprocedure van Hime (https://cenotelie.fr/projects/hime/tutorials/net-kickstart) is een voorbeeld waar ik van gruw. Carburetta (https://carburetta.com/) laat zien hoe het ook kan. Althans, zo op de site lijkt het wel wat.
5 maanden geleden
·
#22089
Vooralsnog ben ik toch nog maar even doorgegaan op de eenmaal ingeslagen weg.
  • Het verbod op lege strings in de BNF is nu opgeheven, zij het op straffe van verminderde zekerheid dat in geval van lege strings altijd alle oplossingen worden gevonden. Je kunt deze vergroten door het proces meer tijd te gunnen, maar 100% betrouwbaar wordt het uiteindelijk nooit.
  • Interessanter is de aanzienlijk verbeterde performance. Waar GGP.lua er niet in slaagde binnen 24 uur de expressie −n−(n+n)*−n^−n^n te analyseren, heeft GGP-3.lua er minder dan een kwart seconde voor nodig. De lat om dit te overtreffen ligt nu wel flink hoger.
Ik sluit weer een pakketje bij en ga me op andere dingen richten, al blijf ik openstaan voor wat anderen nog over deze programmeeropgave en aanverwante onderwerpen wilen zeggen. Naar serieus parsewerk volgens de boekjes wil ik in de toekomst beslist nog wel eens kijken (te beginnen bij Chomsky en Wirth), want ik weet maar nauwelijk iets van dit onderwerp af en het boeit me wel.
Bijlagen
5 maanden geleden
·
#22106
Afgelopen zaterdagochtend verliep mijn presentatie op de HCC!Programmeren-bijeenkomst niet helemaal goed, omdat mijn grammatica's voor de situatie a=a+b=42 mankementen vertoonden. De eerste leverde geen match op waar ik dat wel verwacht had, en de tweede bleek bij thuiskomst dubbelzinnig. Na een paar pogingen kreeg ik het die middag toch voor elkaar:
LuaJIT test-BNF-A.lua "a+b=c+d=e+f" expr5 < assignment.bnfx   ⟹   a+{b={c+{d={e+f}}}}
LuaJIT test-BNF-A.lua "a+b=c+d=e+f" expr6 < assignment.bnfx ⟹ {a+b}={{c+d}={e+f}}

Zo bedoelde ik het. Grammatica's opstellen is best lastig, ja. Over de consequenties van deze twee uitkomsten zal ik op een volgende bijeenkomst wel iets zeggen.

Tussen de bedrijven door heb ik de scripts ook nog een beetje verbeterd. GGP-3.lua gaat nu een fractie economischer te werk en verslikt zich niet meer bij de presentatie van zekere randgevallen. Het wat opgelapte test-BNF-A.lua kan voortaan omgaan met witregels en commentaar in een grammaticabestand. Voor degenen die zelf met het materiaal wil spelen, hier een bijgewerkt (en compleet) pakket.
5 maanden geleden
·
#22132
Jammer. Grammatica 5 zoals ik die in mijn vorige post opvoerde, is ondeugdelijk. De plusoperator is daar rechts-associatief, d.w.z. a+b+c=da+{b+{c=d}}. Dat is niet wat ik voor ogen had. Terug aan de tekentafel is het me nadien niet gelukt een ondubbelzinnige grammatica te schrijven die de plusoperator links-associatief en de toekenningsoperator rechts-associatief maakt. Ik vermoed zelfs dat het onmogelijk is, maar kan dat niet bewijzen. Het meest positieve dat ik over mijn pogingen kan zeggen, is dat grammatica 4 als eerste oplossing de correcte interpretatie geeft (wat er dan nog volgt, moet dus maar worden genegeerd). Dat roept de vraag op of er voor elke gewenste combinatie van prioriteiten en links- en recht-associativiteit van operatoren een (eventueel ambigue) grammatica in BNF op te stellen is waarvan de eerste oplossing de enige goede is. In dit geval van alleen plussen en toekenningen lijkt het aardig gelukt:
LuaJIT test-BNF-A.lua "a+b=c+d=e+f" expr4 < assignment.bnfx   ⟹   a+{b={c+{d={e+f}}}}   [1e van 5 oplossingen]
LuaJIT test-BNF-A.lua "a+b+c=d+e=f" expr4 < assignment.bnfx ⟹ {a+b}+{c={d+{e=f}}} [1e van 2 oplossingen]
LuaJIT test-BNF-A.lua "a=b+c+d+e=f" expr4 < assignment.bnfx ⟹ a={{{b+c}+d}+{e=f}} [1e van 4 oplossingen]
LuaJIT test-BNF-A.lua "a=b+c+d=e=f" expr4 < assignment.bnfx ⟹ a={{b+c}+{d={e=f}}} [1e van 3 oplossingen]
Deze vier eerste oplossingen beschrijven inderdaad hoe Ruby zich gedraagt. Onderstaande grammatica 10 is in wezen (en qua uitkomsten) gelijk aan 4, maar naar mijn idee eleganter geformuleerd:
expr10 = 'term10 | expr10 "+" term10'
term10 = 'var | number | "(" expr10 ")" | var "=" expr10'
var = '"a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "m" | "n" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"'
number = 'digit | digit number'
digit = '"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"'

De foutmelding "Can't modify addition (+) in scalar assignment" in Perl had me op de gedachte gebracht dat daarvoor grammatica 6 zou gelden: na vaststelling dat de syntax klopt, zit de compiler opgescheept met code die niet compileerbaar is. Puur speculatie mijnerzijds hoor. JScript (Microsoft's JavaScript) spreekt daarentegen expliciet van een syntaxfout. Daarvoor heb ik nu de ondubbelzinnige grammatica 11 in elkaar gezet:
expr11  = 'var "=" expr11 | aexpr11'
aexpr11 = 'term11 | aexpr11 "+" term11'
term11 = 'var | number | "(" expr11 ")"'
...
Wat er werkelijk onder de respectievelijke motorkappen zit, weet ik niet en ga ik ook niet uitzoeken. Durf ik het dan toch aan om beide talen (of delen ervan) op de manier van grammatica 11 te beschrijven? Tja...

Met al deze proeven en overpeinzingen ben ik gaandeweg wel wat afgedwaald van het oorspronkelijke onderwerp: de programmeeropgave. De mogelijkheden om nog een serieus betere performance te verkrijgen zijn behoorlijk afgenomen. Misschien is het zinvoller het huidige programma op te leuken met rapportage van een boomstructuur die de namen van de tussenliggende non-terminals weergeeft en een ingebouwde BNF-parser die de invoer van grammatica's volgens meer conventionele BNF-schrijfwijze(n) accepteert (waaronder de definitieoperator ::= en eventuele scherpe haakjes om de namen van de non-terminals). Dat ga ik ooit wel eens doen, als ik de aandrang voel.
  • Pagina :
  • 1
Er zijn nog geen reacties op dit bericht.
Reageer als een van de eersten op dit bericht!
Nog geen HCC-gebruikersaccount aangemaakt? Klik dan hier.

Inloggen