Minimodul 3

Bottom-up parsing

Problemet med top-down parsing med lookahead k (LL(k)) er, at parseren må forudsige hvilken regel den skal anvende efter at have set k tokens af højresiden. Denne gang skal vi se på en bottom-up teknik (LR(k)) parsing, der kan udskyde beslutningen om hvilken regel der skal anvendes indtil alle tokens af en højreside er blevet undersøgt (plus k ekstra tokens).

En bottom-up parsere er noget mere indviklet at programmere, og det har ført til udviklingen af parser generatorer, der udfra en grammatik laver en bottom-up parser (der findes også parser generatorer, der generer top-down parsere).

Tid

Torsdag den 10. februar, klokken 10.15-12.00.

Sted

B3-104.

Litteratur

Appel afsnit 3.3-3.4 (s57-75). Afsnit 3.3 omhandler LR(k) parsing. Afsnit 3.4 omhandler brug af parser generatorer og vil ikke blive gennemgået til forelæsningen (men bør læses af jer, der agter at bruge en parser generator).

Supplerende litteratur

Dragebogen 4.4-4.9.

Opgaver

Appel 3.8, 3.11, 3.12, 3.13.

Næste kursusgang: Tirsdag den 15. februar.
Det sidste vi mangler at se på i forbindelse med parsing er fejl og output.

Til SPO hjemmesiden | Til Dat2/F6S hjemmesiden

Josva Kleist <kleist@cs.auc.dk>

Last modified: Mon Jan 31 13:36:49 2000