5. Formální jazyky a jejich implementace. Klasifikace formálních gramatik. Proces strojového překladu. Princip lexikální a syntaktické analýzy, syntaxí řízené překladové schéma. Generování překladačů.
Toerii formálních jazyků rozpracoval koncem 50. let americký matematik Noah Chomsky, který studoval přirozené jazyky, chtěl je formalizovat a dosáhnout jejich automatizovaného zpracování. I když tento původní záměr doposud nebyl uspokojivě vyřesen, vznikla propracovaná teorie omezených formálních jazyků, pracující s konečnými abecedami a konečnými množinami gramatických pravidel. Tato teorie nachází největší uplatnění při konstrukci překladačů programovacích jazyků a sysntaktických i sémantických analyzátorů nejrůznějších (většinou textových) údajů.
Reprezentace jazyků:
- množinu řetězců (jazyk) lze reprezentovat: výčtem řetězců, matematickým zápisem množiny, formální gramatikou, automatem.
Gramatika G jazyka L je čtveřice GL = (N,suma,P,S), kde N je konečná množina nonterminálních symbolů, suma množina terminálních symbolů, P množina produkčních pravidel, S startovací symbol gramatiky. Gramatika je produkční systém, v němž lze aplikací přepisovacích pravidel ze startovacího symbolu generovat věty patřící do jazyka L. Přímá a nepřímá derivace.
Chomského klasifikace gramatik:
Typ 0 – neomezené gramatiky
Typ 1 – kontextové gramatiky
Typ 2 – bezkontextové gramatiky
Typ 3 – lineární gramatiky
Jazyky typu 3, pro vyjádření této kategorie lze využít: - lineární gramatiku, regulární gramatiku, regulární výraz, konečný automat.
Konečný automat je virtuální stroj, skládající se z řídící jednotky, která se může nacházet v konečném počtu vnitřních stavů, a ze čtecího zařízení, schopného snímat jednotlivé symboly vstupní věty ze vstupní pásky.
Činnost automatu lze znázornit posloupností konfigurací.
Žádné komentáře:
Okomentovat