Tak for sidste. Denne gang forsætter vi sidste uges emne om parsere i denne uge med at set på en større delmængde af de kontekstfrie grammatikker end den delmængde, der kan håndteres af top-down parsere.
Fra sidste uges materiale skulle det fremgå, at hovedproblemet med top-down parsere er, at parseren må bestemme, hvilken produktion den skal anvende efter at have set k tokens af højresiden af en produktion. Denne gang ser vi se på en parseteknik kaldet bottom-up parsing (eller LR(k) parsing), der kan udskyde beslutningen om hvilken regel der skal anvendes indtil alle tokens af en højreside er undersøgt (plus k ekstra tokens).
Desværre er vi ikke helt frem ved den delmængde af de kontekstfrie grammatikker der bruges i programmeringssprog med LR(k) grammatikkerne. Det viser sig nemlig, at det ikke er praktisk at implementere LR(k) parsere, deres hukommelsesforbrug er alt for stort. Derfor må vi reducere mængden af grammatikker til LALR grammatikkerne. For denne del af de kontekstfrie grammatikker kan en bottom-up parsere implementeres med et fornuftigt hukommelsesforbrug.
Der er ikke så mange sider at læse denne gang, men det er mere teoretisk end de tidligere gange.
Figur 3.18 (sammen med tabel 3.19) er central for sektion 3.3. Brug tid på at forstå hvad det er der foregår i denne figur. Herefter er der så teori og et eksempel på hvordan en parsetabel laves. Det er en god ide at sætte sig med papir og blyant og forsøge vha. Closure og Goto metoderne at lave figur 3.24 og 3.25 og herefter figur 3.21 og tabel 3.22.
Som omtalt kan parsetabellen for LR(k) parser blive meget store så derfor anvendes LALR (k) parser i stedet. Som det fremgår på side 64 og frem kan en LALR(k) parser udledes fra en LR(k) parser.
Figur 3.29 samler op på det brev og det forgående brev ved at se hierarkiet af grammatikker der kan håndteres af de forskellige parser.
Sektion 3.4 omhandler hvor parser så kan håndteres. En af dagens opgaver er netop at få bruget JavaCC eller SableCC, det vil jeg anbefale at I gør. Bemærk hvordan fejl kan håndteres med et error token. Afsnittet "Global Error Repair" kan I springe over.
Venlig hilsen
Kristian Torp
torp (at) cs (dot) auc (dot) dk