Minimodul 2
Top-down parsing
7/2-00
Før vi begynder på det jeg oprindeligt havde planlagt at denne
kursusgang, skal vi have gjort leksikals analyse færdigt. Sidste
gang så vi på hvordan vi kunne beskrive tokens ved hjælp af
regulære udtryk. Det vi mangler er at se på hvordan vi så, udfra
de regulære udtryk, kan lave programmer, der genkender tokens.
En grammatik er nogle regler, der angiver opbygningen af lovelige
sætninger. For bestemte grammatikker kan vi lave programmer, kaldet
parsere, der kontrollerer at om programtekst er lovlig, dvs.
overholder grammatikken for sproget. Denne og den følgende kursusgang
skal vi se på hvordan en parser er opbygget. Igen, så har emnet en
solid teoretisk baggrund som Luca beskæftiger sig med i 5. til 7.
kursusgang.
I denne kursusgang skal vi 1) se på hvordan vi kan beskrive
syntaksen for programmerinssprog vha. kontekstfrie grammatikker, 2) en
klasse af parsere, kaldet predikative parsere, der er så
simple, at de relativt let kan håndkodes.
Tid
Tirsdag den 8. februar, klokken 10.15-12.00.
Sted
B3-104
Litteratur
Appel afsnit 3-3.2 (s40-56). Afsnit 3.1 introducerer
kontekstfrie grammatikker, afsnit 3.2 behandler predikativ parsing
(også kaldet top-down parsing).
Sethi kapitel 2. Giver en generel introduktion til
kontekstfrie grammatikker.
Supplerende litteratur
Dragebogen 4-4.4.
Opgaver
Appel 2.3, 2.4. 7/2-00 |
Appel 3.1, 3.2, 3.3, 3.4 (vigtig), 3.5 (vigtig).
Sethi 2.9, 2.14.
Næste kursusgang: Torsdag den 10. februar.
Top-down parsing er dejligt nemt at forstå, men desværre ikke så
udtryksfuldt som vi godt kunne tænke os. Næste gange skal vi se på
bottom-up parsing, der viser sig at være mere udtryksfuldt end top-down.
Til SPO hjemmesiden |
Til Dat2/F6S hjemmesiden
Josva Kleist
<kleist@cs.auc.dk>
Last modified: Mon Feb 7 11:53:33 2000