| |
Jazyky a překlady (36JPR)
předmět denního studia, v tomto semestru se nevyučuje
Rozsah (přednášky + cvičení): 3+2
Zakončení: Zápočet, zkouška
Anotace:
| |
Základní teoretické disciplíny v oblasti počítačových věd jsou teorie jazyků a teorie překladu. Na základě pojmů formální jazyk, formální překlad, atributová gramatika a automat je vybudována rozsáhlá teorie, která zahrnuje i velmi praktické výsledky ve formě algoritmů syntaktické analýzy a konstrukce syntaktických analyzátorů. Do přednášek a cvičení byly vybrány zejména ty partie, které mají praktické aplikace v celé řadě počítačových disciplín. Jmenujme alespoň počítačovou grafiku, vyhledávání, rozpoznávání a konstrukci překladačů.
|
Osnova:
| |
- Základní pojmy teorie jazyků, definice a klasifikace gramatik
- Regulární jazyky, regulární gramatiky, regulární výrazy
- Konečné automaty
- Bezkontextové (CF) gramatiky, syntaktická analýza CF jazyků
- Zásobníkové automaty, vztah CF gramatik a zásobníkových automatů
- LL gramatiky, rozkladové tabulky, algoritmus syntaktické analýzy
- Transformace bezkontextových gramatik na LL(1) gramatiky
- Formální překlady, základní pojmy, překladové gramatiky
- Překladové automaty a překladové gramatiky
- Formální překlad řízený LL analyzátorem
- Atributované překlady, atributované gramatiky
- Výpočet hodnot atributů
- LL atributované překlady
- Implementace překladů
|
Osnova cvičení:
| |
- Konstrukce gramatik pro jednoduché jazyky
- Konečné automaty pro jednoduché jazyky
- Vztah mezi regulárními gramatikami a konečnými automaty
- Vztah mezi regulárními výrazy a konečnými automaty
- Vztah mezi regulárními výrazy a regulárními gramatikami
- Bezkontextové gramatiky, základní transformace
- Zásobníkové automaty
- LL gramatiky, konstrukce rozkladové tabulky, syntaktická analýza
- Transformace bezkontextových gramatik na LL gramatiky
- Formální překlady
- Atributové gramatiky
- Výpočet atributů
- Implementace
|
Literatura:
| |
[1] Melichar, B.: Jazyky a překlady. Skripta ČVUT, Praha 1996
|
|
 
|
