Ik schrijf een kleine tolk voor een eenvoudige BASIC-achtige taal als oefening op een AVR-microcontroller in C met behulp van de avr-gcc-toolchain.
Als ik dit zou schrijven om op mijn Linux-box te draaien, zou ik flex/bison kunnen gebruiken. Nu ik mezelf heb beperkt tot een 8-bits platform, hoe zou ik de parser coderen?
Antwoord 1, autoriteit 100%
Als je een gemakkelijke manier wilt om parsers te coderen, of als je weinig ruimte hebt, moet je een recursieve descent-parser met de hand coderen; dit zijn in wezen LL(1) parsers. Dit is vooral effectief voor talen die zo “eenvoudig” zijn als Basic. (Ik heb er in de jaren 70 een aantal van gemaakt!). Het goede nieuws is dat deze geen bibliotheekcode bevatten; precies wat je schrijft.
Ze zijn vrij eenvoudig te coderen, als je al een grammatica hebt.
Eerst moet u zich ontdoen van links recursieve regels (bijv. X = X Y ).
Dit is over het algemeen vrij eenvoudig te doen, dus ik laat het als een oefening.
(Je hoeft dit niet te doen voor lijstvormende regels;
zie discussie hieronder).
Als je dan een BNF-regel van het formulier hebt:
X = A B C ;
maak een subroutine voor elk item in de regel (X, A, B, C) die een boolean retourneert
zeggende “Ik zag de bijbehorende syntaxisconstructie”. Voor X, codeer:
subroutine X()
if ~(A()) return false;
if ~(B()) { error(); return false; }
if ~(C()) { error(); return false; }
// insert semantic action here: generate code, do the work, ....
return true;
end X;
Hetzelfde geldt voor A, B, C.
Als een token een terminal is, schrijf dan code die controleert
de invoerstroom voor de tekenreeks waaruit de terminal bestaat.
Controleer bijvoorbeeld voor een nummer of de invoerstroom cijfers bevat en ga verder met de
invoerstroomcursor voorbij de cijfers. Dit is vooral gemakkelijk als je
ontleden uit een buffer (voor BASIC heb je de neiging om één regel tegelijk te krijgen)
door simpelweg een bufferscan-aanwijzer vooruit of niet vooruit te bewegen.
Deze code is in wezen het lexer-gedeelte van de parser.
Als uw BNF-regel recursief is… hoeft u zich geen zorgen te maken. Codeer gewoon de recursieve oproep.
Dit behandelt grammaticaregels zoals:
T = '(' T ')' ;
Dit kan worden gecodeerd als:
subroutine T()
if ~(left_paren()) return false;
if ~(T()) { error(); return false; }
if ~(right_paren()) { error(); return false; }
// insert semantic action here: generate code, do the work, ....
return true;
end T;
Als u een BNF-regel heeft met een alternatief:
P = Q | R ;
codeer vervolgens P met alternatieve keuzes:
subroutine P()
if ~(Q())
{if ~(R()) return false;
return true;
}
return true;
end P;
Soms kom je regels voor het vormen van lijsten tegen.
Deze hebben de neiging om recursief te blijven, en dit geval is gemakkelijk te behandelen. Het basisidee is om iteratie te gebruiken in plaats van recursie, en dat vermijdt de oneindige recursie die je zou krijgen door dit op de “voor de hand liggende” manier te doen.
Voorbeeld:
L = A | L A ;
Je kunt dit coderen met iteratie als:
subroutine L()
if ~(A()) then return false;
while (A()) do { /* loop */ }
return true;
end L;
Je kunt op deze manier honderden grammaticaregels in een dag of twee coderen.
Er zijn meer details om in te vullen, maar de basis hier zou meer dan genoeg moeten zijn.
Als je echtweinig ruimte hebt, kun je een virtuele machine bouwen die deze ideeën implementeert. Dat is wat ik deed in de jaren 70, toen 8K 16-bits woorden waren wat je kon krijgen.
Als je dit niet met de hand wilt coderen, kun je het automatiseren met een metacompiler(Meta II) die in wezen hetzelfde produceert. Dit is verbluffend technisch plezier en neemt echt al het werk weg om dit te doen, zelfs voor grote grammatica’s.
Augustus 2014:
Ik krijg veel verzoeken om “hoe bouw ik een AST met een parser”. Zie mijn andere SO-antwoord https://stackoverflow.com/a/25106688/120163
Juli 2015:
Er zijn veel mensen die een eenvoudige beoordelaar voor uitdrukkingen willen schrijven. U kunt dit doen door hetzelfde soort dingen te doen als de “AST-builder”-link hierboven suggereert; doe gewoon rekenen in plaats van boomknooppunten te bouwen.
Hier is een beoordelaar voor uitdrukkingen die op deze manier is gedaan.
Oktober 2021:
Het is vermeldenswaard dat dit soort parser werkt wanneer uw taal geen complicaties heeft die recursieve afdaling niet goed aankan. Ik bied twee soorten complicaties: a) echt dubbelzinnige parsen (bijvoorbeeld meer dan één manier om een zin te ontleden) en b) willekeurig lange vooruitkijken (bijvoorbeeld niet begrensd door een constante). In deze gevallen verandert recursieve afdaling in recursieve afdaling naar de hel, en het is tijd om een parsergenerator te krijgen die ze aankan. Zie mijn bio voor een systeem dat GLR-parsergeneratoren gebruikt om meer dan 50 verschillende talen te verwerken, inclusief al deze complicaties, zelfs tot op het punt van belachelijkheid.
Antwoord 2, autoriteit 25%
Ik heb een parser geïmplementeerd voor een eenvoudige opdrachttaal die is gericht op de ATmega328p. Deze chip heeft 32k ROM en slechts 2k RAM. Het RAM-geheugen is absoluut de belangrijkste beperking – als je nog niet aan een bepaalde chip bent gebonden, kies er dan een met zoveel mogelijk RAM. Dit zal uw leven veel gemakkelijker maken.
In eerste instantie overwoog ik om flex/bison te gebruiken. Ik heb om twee belangrijke redenen van deze optie afgezien:
- Standaard zijn Flex & Bison is afhankelijk van enkele standaard bibliotheekfuncties (vooral voor I/O) die niet beschikbaar zijn of niet hetzelfde werken in avr-libc. Ik ben er vrij zeker van dat er ondersteunde tijdelijke oplossingen zijn, maar dit is een extra inspanning waarmee u rekening moet houden.
- AVR heeft een Harvard Architecture. C is niet ontworpen om hiermee rekening te houden, dus zelfs constante variabelen worden standaard in RAM geladen. U moet speciale macro’s/functies gebruiken om gegevens op te slaan en te openen in flashen EEPROM. Flex & Bison maakt een aantal relatiefgrote opzoektabellen, en deze zullen je RAM vrij snel opeten. Tenzij ik me vergis (wat heel goed mogelijk is), zul je de uitvoerbron moeten bewerken om te profiteren van de speciale Flash & EEPROM-interfaces.
Na het afwijzen van Flex & Bison, ik ging op zoek naar ander generatorgereedschap. Hier zijn er een paar die ik heb overwogen:
Misschien wil je ook eens kijken naar Wikipedia’s vergelijking.
Uiteindelijk heb ik zowel de lexer als de parser met de hand gecodeerd.
Voor het ontleden heb ik een recursieve descent-parser gebruikt. Ik denk dat Ira Baxterheeft dit onderwerp al adequaat behandeld en er zijn tal van tutorials online.
Voor mijn lexer schreef ik reguliere expressies voor al mijn terminals, maakte een diagram van de equivalente toestandsmachine en implementeerde deze als één gigantische functie met behulp van goto‘s om tussen toestanden te springen. Dit was vervelend, maar het resultaat werkte prima. Even terzijde, gotois een geweldig hulpmiddel voor het implementeren van statusmachines — al uw statussen kunnen duidelijke labels hebben direct naast de relevante code, er is geen functieaanroep of statusvariabele overhead, en het gaat over zo snel als je kunt krijgen. C heeft echt geen betere constructie voor het bouwen van machines met een statische toestand.
Iets om over na te denken: lexers zijn eigenlijk slechts een specialisatie van parsers. Het grootste verschil is dat reguliere grammatica’s meestal voldoende zijn voor lexicale analyse, terwijl de meeste programmeertalen (meestal) contextvrije grammatica’s hebben. Er is dus echt niets dat je ervan weerhoudt om een lexer te implementeren als recursieve descent-parser of een parsergenerator te gebruiken om een lexer te schrijven. Het is gewoon niet zo handig als het gebruik van een meer gespecialiseerde tool.
Antwoord 3, autoriteit 5%
Je kunt flex/bison op Linux gebruiken met zijn native gcc om de code te genereren die je vervolgens gaat cross-compileren met je AVR gcc voor het ingesloten doel.
Antwoord 4
GCC kan cross-compileren naar verschillende platforms, maar u gebruikt flex en bison op het platform waarop u de compiler uitvoert. Ze spugen gewoon C-code uit die de compiler vervolgens bouwt. Test het om te zien hoe groot het resulterende uitvoerbare bestand werkelijk is. Merk op dat ze runtime-bibliotheken hebben (libfl.aenz.) die je ook moet cross-compileren naar je doel.