Kompilerkonstruktion: Introduktion til parsning og top-down parsere

De grammatikker, der er interessante i forbindelse med programmeringssprog kaldes kontekstfrie grammatikker (CFG). Fordelene ved de disse er, at de er rimelig udtryksfulde samtidig med at de forholdsvis simple at håndtere rent implementeringsmæssigt.

En parser er et program, der har til opgave at kontrollere om en streng i input sproget overholder en bestemt grammatik. Der er generelt tre typer af parser.

• Generelle parsere
• top-down parsere
• bottom-up parsere

Som navnet siger er generelle parser meget bredt anvendelige. Desværre er de også meget komplekse og langsomme. Derfor er der i praksis kun to muligheder top-down eller bottom-up parsere.

Top-down parsere kan håndtere en delmængde af de kontekstfrie grammatikker. Den klasse af grammatikker kaldes LL(k) og top-down parsere kaldes derfor også LL(k) parsere. Det dejlige ved top-down parsere er, at det relativt nemt at implementere sådanne parsere.

Uheldigvis er der mange meget anvendelige kontekstfrie grammatikker, der ikke kan parses med en top-down parser. Disse kan i stedet håndteres af en bottom-up parser. Vi skal vi se på denne større delmængde af de kontekstfrie grammatikker kaldet LR(k) grammatikker og deres tilhørende bottom-up parsere (eller LR(K) parsere) i næste uge.

Litteratur

Læsevejledning

Kapitel 3 forsætter fra hvor det forrige kapitel slap med at se på regulære udtryk. Først vises at der er begrænsninger for, hvad man kan specificere med disse udtryk og at man for at specificere grammatikker for programmeringssprog må brugen en anden notation, der kaldes kontekstfrie grammatikker (CFGer).

Sektion 3.2 omhandler CFGer. Et central begreb er en produktion f.eks. P –> id := E. Det er væsentligt at forstå at den samme sætning i et sprog kan afledes på mere end en måde f.eks. som en left-most eller som en right-most afledning. Afledninger vises som et træ f.eks. figur 3.3 (som tidligere omtalt træer er en meget brugt data struktur i en kompiler).

Tvetydighed (ambiguity) i en grammatik er et stort problem, hvis man skal implementerer grammatikken i en kompiler. Heldigvis kan mange (men ikke alle) tvetydigheder håndteres vha. precendence regler eller association specificering, sæt jer ind i begge disse teknikker til at fjerne tvetydighed.

Recursive descent parseren i sektion 3.2 er en meget elegant måde at implementere en parser på uden at bruge et specielt parser genereringsværktøj som SableCC. Desværre er recursive descent parsere ikke altid kraftfulde nok. Om man kan bruge en recursive descent parser kan afgøres med FIRST og FOLLOW mængder, så brug tid på at forstå hvordan disse findes.

Generelt har LL-parsere som recursive densent parsere problemer med venstre rekursion f.eks. E –> E + T. Venstre rekursion kan altid omformes til højre rekursion. Tilsvarende kan LL-parsere hellere ikke håndtere at to produktioner har samme højreside og starter med samme venstreside. Dette kan elimineres med left factoring. Uheldigvis har både eliminering af venstre rekursion og left factoring den side effekt at en meget læsbar grammatik (for mennesker) bliver en del mere besværlig at forstå.

Til Sethi

Dette kapitel omhandler udelukkende syntaks af programmeringssprog, semantikken af programmeringssprog diskuteres kun uformelt. Dette er stadig typisk for så store sprog som Java og SQL. Dette er fordi det er meget besværligt formelt at beskrive semantikken af et sprog. Forskere er endnu ikke fundet et passende værktøj til dette.

Sektion 2.1 omhandler udtryk (expressions) bemærk de tre notationsformer prefix, infix og postfix for udtryk. I sektion 2.2 diskuteres abstrakt syntaks som er en smart måde at repræsenterer f.eks. udtryk. Brev 5 vil give flere detaljer om abstrakt syntaks. Sektion 2.3 ser på tokens, et men vi også så på i forrige brev.

Sektion 2.4 omhandler kontekstfrie grammatikker. Programmeringssprog er udtryk i disse så dette er en væsentlig sektion at forstå. Specielt skal i kigge på BNF syntaksen, denne er meget brugt også i andre sammenhænge end kompilerkonstruktion.

Sektion 2.5 giver et eksempel på brugen af BNF. Læg mærke til hvordan associativity og precendence håndteres i en grammatik.

Sektion 2.6 giver en overbygning til BNF kaldet Extended BNF (EBNF). Da en grammatik i EBNF typisk er kortere end den samme grammatik i BNF bruges EBNF som oftest. Bemærk at mange bøger ikke skelner mellem BNF og EBNF men blot kalder det hele BNF. Endeligt beskrives syntax chars. Det synes jeg selv er det mest læselig måde at se på en grammatik på. Syntax chars kaldes også ofte railroad diagrams.

Opgaver

Venlig hilsen
Kristian Torp
torp (at) cs (dot) auc (dot) dk