Prevodioci i interpretatori


Kurs u školskoj 2000/2001. za studente 3. godine studija na R-smeru Matematičkog fakulteta

Duško Vitas

vitas@matf.bg.ac.yu

Kratki pregled tema kursa

  • Struktura i funkcije kompilatora
  • Osnovni pojmovi iz teorije formalnih jezika
    • Azbuka, niska, jezik, gramatika
    • Regularni jezici
    • Konačni automati i transduktori
    • Kontekst-slobodne gramatike i jezici. Izvođenje i višeznačnost. Parsing
    • Potisni automati i transduktori
  • Leksička analiza
    • Regularni izrazi i konačni automati
    • Struktura skanera
    • Alati za generisanje skanera (lex)
  • Sintaksička analiza (engl. parsing)
    Analiza naniže (engl. top-down)
    • EBNF, sintaksni dijagrami i drvo izvođenja
    • Transformacije gramatika, normalne forme
    • Rekurzivni spust (engl. recursive descent parsing)
    • LL-gramatike i analiza
    Analiza naviše (engl. top-down)
    • Opšte metode
    • shift-reduce
    • SLR, kanonski LR i LALR - gramatike
    • Generator parsera (yacc)
  • Semantička analiza
  • Okruženje u vreme izvršavanja
  • Optimizacija i generisanje koda
  • Primene teorije formalnih jezika i automata u obradi prirodnih jezika
    • Reprezentacija teksta na prirodnom jeziku
    • Formalizmi morfološke analize
    • Sistem elektronskih rečnika
    • Primene u automatskoj transformaciji teksta

Program kursa: Prevodioci i interpretatori

Organizacija nastave i ispit

  • Fond časova: nedeljno 2 časa predavanja i
    2 časa vežbi, tokom 5. i 6. semestra
  • Predavanja: četvrtkom, u sali 821,
    od 14 - 16 časova
  • Konsultacije: prema dogovoru pismom na: vitas@matf.bg.ac.yu
  • Vežbe: N. Vasiljević, M. Utvić
  • Obavezni seminarski rad: student je obavezan da u toku godine, po pravilu u drugom semestru, uradi samostalno jedan seminarski rad koji koji treba da bude opremljen dokumentacijom u TeX-u i stranom u HTML-u da bi se prikazao na web-u.
  • Kolokvijumi: Tokom školske godine se organizuju dva pismena kolokvijuma: na kraju januarskog ispitnog roka i pred početak junskog ispitnog roka. Kandidat koji položi oba kolokvijuma oslobađa se pismenog dela ispita, načelno, u junskom ispitnom roku.
  • Ispit se sastoji iz pismenog i usmenog dela.
    • Pismeni ispit traje 4 sata. Redovni rokovi za polaganje ispita su junski, septembarski, oktobarski, januarski i aprilski
    • Ispitna pitanja za usmeni deo ispita iz školske 1999/2000. (važe do junskog roka 2001).
Aho-Sethi-Ullman

Levine

Appel

Osnovna literatura

Knjige:

  • Alfred, Aho; Ullman, Jeffrey D.; 1972: The Theory of Paring, Translation, and Compiling, vol. I: Parsing, Prentice-Hall, Series in Automatic Computation
  • Alfred, Aho; Sethi, Ravi; Ullman, Jeffrey D.; 1986: Compilers: Principles, Techniques, and Tools, Addison-Wesley
  • Kernighan, Brian; Ritchie, Dennis; 1988: The C Programming Language, (Second Edition), Prentice Hall, 1988 (srpski prevod: B. Kernigen, D. Riči: Programski jezik C, Savremena administracija, Beograd)
  • Hollub, Allen; 1990: Compiler Design in C, Addison-Wesley
  • Levine, J.R.; Mason, T.; Brown, D.; 1995: lexx & yacc, (Second edition; minor corrections), O'Reinly & Associates, Inc.
  • Appel, Andrew; 1997: Modern Compiler Impementation in C: Basic Techniques, Cambridge University Press
  • Knuth, Donald: 1968: The Art of Computer Programming, Addisson-Wesley, vol. I - III
  • Dostupni članci u ACM Digital Library

Zanimljive strane na web-u:


Regularni izrazi u obradi prirodnih jezika

  • LADL -- Laboratorija za automatizovanu dokumentalistku i lingvistiku Morisa Grosa; tvorci e-rečnika
  • AT&T -- FSM: General-purpose finite-state machine software tools -- grupa Mejre Morija
  • Xerox -- MLTT Finite-State Home Page -- Lauri Kartunen i Martin Kej
  • TeraGram -- Lingvistička podrška za Altavistu -- Emanuel Roš i Iv Šabes