Fase van de compiler die controleert of de reeks tokens past bij de grammatica van de taal en de structuur van het programma als een boom opbouwt. Grammaticafouten worden hier gevonden.
Japanse benaming: 構文解析
“Syntactische analyse (parsing)” komt voor in 5 oefenvragen uit 1 onderwerpen, bijv. Compilers.
Vakgebied: Compilers
De front-end van een compiler werkt in fasen. Lexicale analyse zet de tekenstroom om in tokens zoals identifiers, getallen en symbolen, en verwijdert witruimte en commentaar. Syntactische analyse, of parsing, controleert vervolgens of die reeks tokens volgens de grammatica van de taal een geldig programma vormt en legt vast hoe de onderdelen genest zijn: welke statements de body van een lus vormen, welke operanden bij welke operator horen. Fouten zoals een ontbrekende puntkomma of ongebalanceerde haakjes worden hier gemeld. Daarna volgt semantische analyse, die types controleert en nagaat of namen zijn gedeclareerd, voordat het programma wordt omgezet naar een tussenrepresentatie voor optimalisatie en codegeneratie.
Regels voor tokens zijn eenvoudig genoeg voor reguliere expressies en snelle eindige automaten, maar programmastructuur is dat niet. Geneste haakjes en if-statements binnen if-statements vragen om tellen tot onbeperkte diepte, wat geen reguliere expressie kan. Programmeertalen worden daarom beschreven met contextvrije grammatica's, verzamelingen herschrijfregels zoals expr → expr + term, vaak genoteerd in Backus-Naurvorm. Een goed ontworpen grammatica legt ook operatorprioriteit en associativiteit vast, zodat in a + b * c de vermenigvuldiging eerst wordt gegroepeerd. Ambigue grammatica's, waarbij één invoer twee mogelijke bomen heeft, moeten worden vermeden of met extra regels worden opgelost.
LL-parsers werken top-down: vanaf het startsymbool voorspellen ze welke regel moet worden toegepast door naar het volgende token of de volgende paar tokens te kijken. Handgeschreven recursive-descent-parsers, met één functie per grammaticaregel, zijn LL van stijl en worden veel gebruikt vanwege hun helderheid en goede foutmeldingen, maar ze vereisen dat links-recursieve regels worden herschreven. LR-parsers werken bottom-up: ze schuiven tokens op een stack (shift) en reduceren ze tot regels zodra een volledige rechterkant is herkend (reduce). LR kan een bredere klasse grammatica's aan, en parsergeneratoren zoals yacc en Bison bouwen LALR-tabellen automatisch.
Wie de grammatica letterlijk volgt, krijgt een concrete syntaxboom of parse tree met elk haakje, elk scheidingsteken en elke tussenregel. Latere fasen hebben veel minder nodig, dus parsers bouwen meestal in plaats daarvan een abstract syntax tree (AST). In de AST voor (a + b) * c staat de optellingsknoop gewoon onder de vermenigvuldigingsknoop; de vorm van de boom draagt nu de evaluatievolgorde en de haakjes verdwijnen. De AST is de datastructuur die semantische analyse annoteert met types en scopes en die de compiler later vertaalt naar tussencode.
Antwoord: C. De reeks tokens aan de grammatica toetsen en de structuur van het programma in boomvorm opbouwen
Parsing controleert of de door lexicale analyse verkregen reeks tokens voldoet aan de grammatica van de taal en bouwt structuren, zoals de voorwaarde en de body van een if-statement en de combinatie van operaties in een expressie, op als een boom (syntaxisboom). Grammaticafouten zoals een vergeten puntkomma of niet bij elkaar passende haakjes worden in deze fase gevonden. Het verwijderen van witruimte en het verdelen in woorden is lexicale analyse, en het tijdens de uitvoering vertalen naar machinecode is JIT-compilatie.
Antwoord: C. Contextvrije grammatica
Genestelde haakjes en structuren waarin een if-statement een ander if-statement bevat, kunnen niet met reguliere expressies worden weergegeven. De grammatica van de meeste programmeertalen wordt weergegeven met een contextvrije grammatica, een verzameling herschrijfregels zoals "expressie → expressie + term", en parsing gebeurt op basis van deze grammatica. Er zijn parsingmethoden zoals LL, waarbij regels van boven af worden toegepast, en LR, waarbij van onder af wordt opgebouwd, en er zijn ook tools die parsers automatisch uit een grammatica maken. Reguliere grammatica's zijn geschikt voor lexicale analyse en kunnen geen geneste structuren aan.
Lexicale analyse splitst brontekst in tokens en verwijdert witruimte en commentaar. Syntactische analyse neemt die tokens, toetst ze aan de grammatica en bouwt een boom die de programmastructuur beschrijft.
Een abstract syntax tree is een boomweergave van een programma die alleen de bewerkingen en statements bewaart die voor de betekenis nodig zijn. Groeperingssymbolen zoals haakjes vallen weg, omdat de vorm van de boom zelf prioriteit en nesting uitdrukt.
LL-parsers bouwen de boom top-down en voorspellen regels op basis van komende tokens; handgeschreven recursive-descent-parsers horen hierbij. LR-parsers bouwen bottom-up door tokens op een stack te schuiven en ze tot regels te reduceren, en accepteren een bredere klasse grammatica's.
Parsing controleert of de door lexicale analyse verkregen reeks tokens voldoet aan de grammatica van de taal en bouwt structuren, zoals de voorwaarde en de body van een if-statement en de combinatie van operaties in een expressie, op als een boom (syntaxisboom).
Wat doet de parsing (syntactische analyse) van een compiler?De grammatica van de meeste programmeertalen wordt weergegeven met een contextvrije grammatica, een verzameling herschrijfregels zoals "expressie → expressie + term", en parsing gebeurt op basis van deze grammatica.
Welk soort grammatica wordt gebruikt om de grammatica van v…Het in boomvorm controleren van de grammatica is de taak van de volgende fase, parsing (syntactische analyse), en het controleren van types en namen is de taak van semantische analyse.
Welke uitspraak over de rol van lexicale analyse in een com…Een vergeten puntkomma is een grammaticafout en wordt door parsing gevonden.
Welke fout wordt het best gevonden door de semantische anal…Parsing levert een boom op die volgens de grammaticaregels ook haakjes en scheidingstekens bevat (concrete syntaxisboom), maar die bevat veel informatie die voor de verdere verwerking niet nodig is.
Welke uitspraak over een abstracte syntaxisboom (AST) is ju…Lexicale analyse JIT-compilatie (just-in-time) Abstracte syntaxisboom (AST) Basic block Common subexpression elimination Constant folding Control-flow-graaf (CFG) Inlining Instructiescheduling Intermediaire representatie (IR)