2- Formální jazyky a gramatiky
comp_p02.doc
2 Formální jazyky a gramatiky 2.1
Úvod
Teorie formálních gramatik a jazyků je důležitou součástí informatiky. Její využití je hlavně v oblasti tvorby překladačů, kompilátorů. Vznik teorie se datuje přibližně do roku 1956, kdy matematik polského původu Noam Chomsky na základě studia a výzkumu zákonitostí v přirozených jazycích vytvořil matematický model gramatiky. V dalším období se ukázala úzká souvislost mezi teorií formálních jazyků a teorií automatů. Chomsky vytvořil klasifikaci formálních jazyků a gramatik, přičemž je rozdělil, jak si ukážeme v této kapitole, do čtyř skupin. Co je to vlastně jazyk? Naučný Websterův slovník jej definuje jako „soubor slov a metod skládání slov, které chápe a používá dostatečně velká společnost lidí“. S touto definici samozřejmě pro naše účely nevystačíme. Pro potřeby matematické teorie jazyků je třeba definovat formální jazyk abstraktně jako matematický systém.
2.2
Základní pojmy
V této části uvedeme základní pojmy z teorie formálních jazyků a gramatik. Podobně jako je tomu u přirozených jazyků, budeme i ve formálních jazycích používat pojmy jako jsou písmeno, slovo, věta. ¾
Abeceda A je konečná množina symbolů, ze kterých se v daném jazyku vytváření vyšší významové celky.
Příklad 1.
{a, b, c, d, ... z, A, B, C, ... Z} písmena (velké i malé) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} číslice {+ - * / . , : ‘ “ = { } [ ] ( ) < >} speciální znaky {and, array, begin, case, ..., var, while, with} vyhrazené slova Pascalu
¾
Řetězec w je libovolná konečná posloupnost symbolů dané abecedy A.
¾
Délka řetězce | w | je definovaná jako počet symbolů v řetězci w.
V jazyku je možné teoreticky odvodit různé řetězce různé délky až po nekonečné řetězce. Z praktických důvodů mají však význam řetězce konečné délky. Zvláštní postavení má tzv. prázdný řetězec. ¾
Prázdny řetězec ε je řetězec s nulovou délkou.
¾
Obrácený řetězec wR je řetězec obsahující symboly původního řetězce v opačném pořadí. R Pokud máme řetězec w = a1a2a3 ... an, tak k němu obrácený řetězec je w = anan-1 ... a3a2a1
Příklad 2.
¾
Nechť je řetězec x1 = ‘automobil‘
jeho délka je | x1 | = 9 obrácený řetězec x1R = ‘libomotua‘
Zřetězení je operace . definovaná na množině řetězců dané abecedy takto: Pokud u = a1a2 ... ak , v = b1b2 ... bl jsou řetězce nad danou abecedou, tak u.v = a1a2 ... ak b1b2 ... bl je nový řetězec uv. Zápisy u.v a uv jsou ekvivalentní.
Příklad 3.
Nechť x1 = ‘abc’ a x2 = ‘de’. Potom x1.x2 = ‘abcde’ a x2.x1 = ‘deabc’.
Pro pojmy v následujících definicích použijeme řetězce x, y a z nad určitou abecedou. Řetězce w1=xy, w2=yz a w3=xyz jsou řetězce, které vznikly jejich zřetězením. ¾
Řetězec x je prefix nebo předpona řetězce w1 i řetězce w3. Řetězec y je postfix nebo přípona řetězce w2. Řetězec x, y i z jsou podřetězce řetězců w1, w2 i w3.
Množinu všech řetězců nad abecedou A (t.j. řetězců, ve kterých se nacházejí jen znaky, které jsou prvky abecedy A) * budeme označovat A .
1. 3. 2007 - 14:41 Benedikovič
1/6
2- Formální jazyky a gramatiky
comp_p02.doc
+
Množinu všech řetězců bez prázdného řetězce nad abecedou budeme označovat A . Příklad 4.
Nech x = ‘abc’. prefixy - ε, a, ab, abc postfixy - ε, c, bc, abc podreťazce - ε, a, b, c, ab, bc, abc Nech A={a, b, c}, potom: A* - {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, ...} A+ - {a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, ...}
Na tomto místě máme všechny potřebné informace k tomu, abychom uvedli první, zatím ještě příliš všeobecnou definici formálního jazyka. ¾
Nechť A je abeceda. Potom formální jazyk nad abecedou A definujeme jako libovolnou * podmnožinu množiny A .
Tato definice však umožňuje popsat samotný jazyk takovým způsobem, že vyjmenujeme všechny možné řetězce, které mají být prvky daného jazyka. Představme si však případ, kdy bychom měli tímto způsobem definovat nějaký programovací jazyk (Pascal nebo C a pod.). Vidíme, že pro tyto účely je tato základní definice prakticky nepoužitelná. Musíme hledat nějaký mechanismus, který daný jazyk úplným způsobem popíšeme. Z uvedených definicí vidíme, že abeceda i jazyk jsou množiny. Můžeme na ní tedy použít množinové operace. Nechť tedy platí, že A1 a A2 jsou abecedy a L1 ⊂ A1* a L2 ⊂ A2* jsou jazyky, potom A1 ∪ A2
= { x | x ∈ A1 ∨ x ∈ A2 }
L1 ∪ L2
= { y | y ∈ L1 ∨ y ∈ L2 }
A1 ∩ A2
= { x | x ∈ A1 ∧ x ∈ A2 }
L1 ∩ L2
= { y | y ∈ L1 ∧ y ∈ L2 }
A1 - A 2
= { x | x ∈ A1 ∧ x ∉ A2 }
L1 - L2
= { y | y ∈ L1 ∧ y ∉ L2 }
Nad jazykem se setkáváme i s následujícími operacemi:
¾ Nechť L1 a L2 jsou jazyky. Potom jejich zřetězením voláme jazyk L s vlastnostmi: L = { xy | x ∈ L1 ∧ y ∈ L2 } Příklad 5.
L1 = { a, b, ... z, A, ... Z }, L2 = { a, ... z, A, ...Z, 0, 1, ... 9 }*. L = L1 L2 je jazyk řetězců složený z písmen a číslic, které začínají písmenem.
¾
Pokud L je jazyk, tak jeho n-tou mocninu definujeme takto: L0 = { ε } Ln = L.Ln-1 pre n ≥ 1
¾
Uzávěr jazyka L je množina L* = ∪ Li
¾
Pozitivní uzávěr jazyka L je množina L+ = ∪ Li pro i ≥ 1
2.3
pro i ≥ 0
Gramatika
Již jsme zmínili, že první definice formálního jazyka uvedená v předcházející části není vhodná pro praktické použití v souvislosti s popisem nějakého programovacího jazyka. Vyžaduje vyjmenování všech možných řetězců. Potřebujeme vytvořit nějaký mechanismus vyčerpávajícím způsobem popisující daný jazyk. Tímto mechanismem je tzv. gramatika. Představuje systém syntaktických pravidel, pomocí kterého je možné vygenerovat libovolný řetězec jazyka, případně je možné zjistit, či daný řetězec do jazyka patří nebo ne. V definici gramatiky se vyskytují následující pojmy: ¾
Terminál nebo terminální symbol je prvotní symbol daného jazyka.
Jde o symbol z množiny symbolů jazyka, který už v procesu analýzy nenahrazujeme. Jde o cílový termín, který je součástí nějakého řetězce jazyka. ¾
Neterminál nebo neterminální symbol je symbol definovaný pomocí pravidel jazyka.
1. 3. 2007 - 14:41 Benedikovič
2/6
2- Formální jazyky a gramatiky
comp_p02.doc
¾
Začátečný symbol (také startovací) je jeden z neterminálních symbolů, ze kterého začíná generování vět jazyka, případně analýza věty.
¾
Přepisovací pravidlo nebo vytvářecí pravidlo, produkce je předpis, který určuje způsob náhrady neterminálu jiným podřetězcem.
Následuje všeobecná definice gramatiky, na základě které se vykonává analýza věty, t.j. zjišťuje se, zda analyzovaná věta ( může to být například program v programovacím jazyce) vyhovuje syntaktickým pravidlům jazyka. Gramatika určuje jen syntaxi jazyka – přípustnou strukturu vět. Významem věty je zabývá sémantika. Syntakticky správná věta ještě nemusí být správná z významového, sémantického hlediska. ¾
Gramatika je definovaná jako čtveřice G = ( N, T, P, S ), kde N – konečná množina neterminálních symbolů, T – konečná množina terminálních symbolů, N ∩ T = ∅, S – začáteční symbol, S ∈ N, (musí byť pouze jeden!). P – konečná množina přepisovacích pravidel z (N ∪ T)* N (N ∪ T)* x (N ∪ T)*
Stručně si vysvětlíme význam a použití symbolů v definice. Pro odlišení neterminálů (množiny N) od terminálů (množina T) často používáme v praxi zápis neterminálu uzavřeného v lomených závorkách, například
. Slovo identifikátor se může vyskytnout i přímo jako součást řetězce, tedy jako terminál. Pokud je uvedené v ostrých závorkách, potom vyjadřuje neterminál zastupující celou množinu pojmů splňujících určité vlastnosti. O které konkrétní pojmy jde, určují pravidla z množiny P. Lomené závorky použijeme pro jasné odlišení terminálů a neterminálů. Tam můžeme použít stejné slovo ve dvou významech a přitom zaručíme požadovanou disjunktnost množin N a T. Přepisovací pravidla jsou základem pro generování vět jazyka. V definici gramatiky jsou vyjádřené jako kartézský součin. Jeden konkrétní případ kartézského součinu množiny P představuje přepisovací pravidlo, ve kterém na levé musí být alespoň jeden neterminál, kvůli kterému se náhrada vykonává. Před ním a za ním můžou (ale nemusí) být řetězce složené z terminálů a neterminálů. Na pravé straně pravidla je nějaký řetězec terminálů a neterminálů (obecně může být i prázdný). Pro levé a pravé strany přepisovacího pravidla, produkce budeme někdy používat zkratky: LHS – z anglického left hand side a RHS – right hand side. Nad množinou řetězců terminálů a neterminálů definujeme relaci derivace nebo relaci odvození. ¾
Mějme gramatiku G = ( N, T, S, P ). Relace odvození - derivace ( značíme ji G⇒ ) definovaná * nad množinou (N ∪ T) je definovaná takto: * * Pokud αβγ ∈ (N ∪ T) a αδγ ∈ (N ∪ T) , potom dané řetězce jsou relací αβγ G⇒ αδγ tehdy, kdy v množině P existuje přepisovací pravidlo β Æ δ
Můžeme též používat následující pojmy. V případě, že pro řetězce α a β platí, že jsou v relaci derivace α G⇒ β, hovoříme také, že z α můžeme přímo derivovat β, nebo β můžeme derivovat z α. ¾
Inverzní relaci k derivaci nazýváme redukce .
Tuto relaci používáme například při analýze, ve které vycházíme z analyzovaného řetězce a postupnými redukcemi se snažíme dosáhnout začáteční symbol (v tomto případě ho můžeme nazývat cílový symbol) a tím vyhlásit původní řetězec za přijatý. ¾
*
Nechť G = ( N, T, S, P ) je gramatika a mějme řetězce αi ∈ (N ∪ T) pro i = 0, 1, 2, ... k. Říkáme, že αk se dá derivovat z α0 , pokud platí αi G⇒ αi+1 pro i = 0, 1, 2, ... k-1.
¾ Posloupnost řetězců α0, α1, ... αk nazýváme odvození - derivace αk z α0 Jde vlastně o posloupnost řetězců složených z terminálů a neterminálů dané gramatiky. Následující definice nám říká o skutečnosti, že ne každý řetězec (!!!) skládající se jen ze symbolů (terminálů a neterminálů) gramatiky také do této gramatiky patří! ¾
*
Množinu řetězců α ∈ (N ∪ T) gramatiky G = ( N, T, S, P ), které jsou derivovatelné ze začátečního symbolu S nazýváme množina větních forem . * * Formální zápis: V = { α | S ⇒ α, α ∈ (N ∪ T) }
1. 3. 2007 - 14:41 Benedikovič
3/6
2- Formální jazyky a gramatiky
comp_p02.doc
Teď máme pohromadě vlastně všechny potřebné pojmy pro to, abychom uvedli definici jazyka, která popisuje množinu vlastních řetězců pomocí stejného systému pravidel – gramatiky. ¾
Nechť G = ( N, T, S, P ) je gramatika. Jazyk L(G) specifikovaný gramatikou G je množina řetězců složených pouze z terminálních symbolů, pro které existuje derivace ze začátečního symbolu gramatiky. * * Formální zápis: L(G) = { w | S ⇒ w, w ∈ T }
Všimněte si zásadního rozdílu od definice větné formy (vidět ho i ve formálním zápise). Řetězec jazyka je také větnou formou, ale opačně to neplatí.
2.4
Zápis syntaxe pravidel V dalším textu budeme používat následující dohodu pro zápis pojmů:
Pojem
Všeobecný popis
a) neterminální symboly
velká latinská písmena A, B, C,
b) terminální symboly
malá latinská písmena a, b, c, ...
c) slova složená z terminálních a neterminálních symbolů d) slova složená jen z terminálních symbolů
malá řecká písmena α, β, γ, ...
e) přepisovací pravidla f) přepisovací pravidla se stejnou pravou stranou
malá latinská písmena, pokud to z kontextu není jasné, s upozorněním, že je to řetězec ve tvaru α Æ β
Konkrétnejší popis název terminálu uzavřený v lomených závorkách ve tvaru <jméno neterminálu> přímo „koncové“ symboly popisovaného jazyka skutečný řetězec skutečný řetězec BNF, Conwayův diagram (viz dále)
α Æ β1, α Æ β2, α Æ β3, ... α Æ β1 budeme zapisovat jako α Æ β1 | β2 | β3 | ... | βn
2.4.1 Backusova – Naurova forma, BNF Zápis pravidel v tomto systémů je charakterizován tímto tvarem:
::= | α1 | α2 | ... | αn kde všechny αi jsou řetězce neterminálních a terminálních symbolů nebo prázdný řetězec, kterými je definován řetězec uvedený na LHS. Neterminál na levé straně pravidla – LHS je jednotka, kterou definujeme řetězcem RHS. Metasymbol ::= můžeme číst například jako „definujeme jako...“. Tento systém je určen na popis přepisovacích pravidel gramatiky. Je to vlastně také jazyk. Protože však popisuje vlastnosti jazyka určeného pro popis jiného jazyka, budeme mu pracovně říkat metajazyk, jeho symbolům metasymboly a jeho případným předpisům metapříkazy. V BNF použijeme následující metasymboly:
metasymbol: definice ::=
význam metasymbolu: symbol nahrazení levé strany (LHS) pravou stranou pravidla (RHS) při derivaci (= „definuj jako...“)
|
alternativa
metaoperátor výběru jedné varianty z uvedených pravých stran (= „nebo“)
.
sekvence
metaoperátor zřetězení operandů v zápise pravidla (= „následuje")
*
mocnina
metaoperátor opakování výskytů metaoperandu, (..) prázdného počtu výskytů (= „opakuj“)
() < > +
Změna priority metaoperátorů Čitelné vyjádření symbolu, který nazýváme neterminál Mocnina typu „alespoň jedenkrát“
1. 3. 2007 - 14:41 Benedikovič
4/6
2- Formální jazyky a gramatiky
comp_p02.doc
Metaoperátor opakování metaoperandů s povinným výskytem (= „opakuj alespoň jednou“) *
Příklad 6.
::= . ( | <číslice> ) * ::= ( | ε ) . <číslice > . <číslice>
Zápis <číslice > . <číslice>
*
možno zkrátit na: <číslice>
+
(≡ znaky hvězdička a plus)
V uvedeném příkladě je definovaný identifikátor pro většinu běžných programovacích jazyků. Na pravé straně je zřetězením . určené, že identifikátor začíná písmenem, za kterým následuje libovolný počet znaků s tím, že každý z nich je buď písmeno nebo číslice. Metaoperátor * „vyvolává“ opakované použití daného metaoperandu (možný je i prázdný řetězec). Mocnina má vyšší prioritu než alternativa, proto je nutné použít závorky pro změnu priority zpracovávání metaoperátorů. Zamyslete se nad případem, ve kterém by jsme s touto definicí vynechali závorky. Priorita metaoperátorů: nejvyšší priorita * +
. |
nejnižší priorita
V současnosti se používá pro zápis syntaxe i rozšířená verze Backusovej – Naurovej formy(EBNF), ve které jsou na místo metaoperátoru * používají složené závorky { ... } s následujícím významem:
BNF α*
EBNF {α}
význam libovolný počet opakování řetězce α vrácení prázdného řetězce
{α }nm
---
řetězec α se může vyskytnout od m-krát do n-krát
1
{α} [α]
---
Oba dva zápisy jsou ekvivalentní Řetězec α se vyskytuje maximálně 1-krát
Definice identifikátoru z předcházejícího příkladu bude v zápise EBNF vypadat takto: Příklad 7.
::= . { | <číslice> } ::= [ ] . <číslice > . { <číslice> } < znamienko > ::= ( + | - )
2.4.2 Syntaktický diagram – Conwayův diagram Grafické vyjádření vztahů mezi neterminály a terminály uvnitř přepisovacího pravidla. Při zobrazování platí následující pravidla: terminální symbol: a (kroužek alebo ovál)
a | b | ... | A
alternativa:
a
a b
neterminální symbol: A
A
a b ... c
zř e tě z e n í: m o c n in a
* :
α*
m o c n in a
+ :
α+
...
ĺ
1. 3. 2007 - 14:41 Benedikovič
A
a
b
...
c
α α
5/6
2- Formální jazyky a gramatiky
comp_p02.doc
Příklad 8.
Na tomto příkladu jsou demonstrovány pravidla z předcházejícího příkladu:
identifikátor
celé číslo
Písm eno
Číslica Písm eno
Znam ienko
Číslica
2.5
Klasifikace gramatik
Gramatiky je možné z hlediska podmínek, kladených na přepisovací pravidla rozdělit do více skupin. Umožňuje to při přípravě analyzátoru použít více, či méně úspěšně, příslušné techniky a nástroje. V současnosti se nejčastěji používá rozdělení gramatik podle Chomského. Vycházíme z definice gramatiky, přičemž Chomského klasifikace rozlišuje čtyři skupiny gramatik:
Typ
Název
Pravidlo
Omezující podmínky
0 bez omezení Frázová-neomezená αÆβ * * + 1 Kontextová αÆβ α ∈ (N ∪ T) N (N ∪ T) a β ∈ (N ∪ T) a platí |α| ≤ |β| * 2 Bezkontextová AÆβ A ∈ N ; α ∈ (N ∪ T) 3 Regulární A ∈ N ; β = bB nebo β = b, ( kde b ∈ T a B ∈ N ) AÆβ Poznámky k tabulce: ( LHS=levá, RHS=pravá strana pravidla ) 1) U kontextové gramatiky existuje alespoň jedno pravidlo, ve kterém je na levé straně (LHS) řetězec složený z více symbolů, přičemž v každém pravidle musí být v LHS jeden neterminál A, „kterého se pravidlo týká“. Před ním nebo za ním můžou být nějaké neprázdné podřetězce α, β, přičemž derivace neterminálu se vykonává jen v kontextu s nimi. LHS tohoto pravidla nechť je tedy ve tvaru αAβ, přičemž alespoň jeden z podřetězců α, β není prázdný. Na pravé straně (RHS) každého pravidla je neprázdný řetězec terminálů a neterminálů. Na pravé straně pravidla musí být alespoň tolik symbolů jako na levé straně. Žádné pravidlo tedy nesmí(!) větní formu zkracovat! 2) Bezkontextová gramatika se vyznačuje vlastností, že v každém pravidle je na LHS samostatně stojící neterminál. Na RHS je libovolný řetězec terminálů a neterminálů (...) prázdného řetězce. 3) V regulární gramatice existují jen pravidla s jedním neterminálem na LHS a jednoduchou pravou stranou. Na RHS může být buď samostatně umístěný jeden terminál nebo jeden terminál následovaný jedním terminálem. Na tomto rozdělení gramatik si můžeme všimnout, že platí: každá regulární gramatika je současně bezkontextovou, každá bezkontextová kontextovou a každá kontextová je gramatikou bez omezení. Obráceně to ovšem neplatí! Gramatika je systémem pravidel, pomocí kterých je možné odvozovat řetězce vyhovující této gramatice. Proto je součástí jazyka, který je charakterizovaný vlastnostmi své gramatiky. ¾
Jazyk nazýváme regulární, resp. bezkontextový, resp. kontextový, resp. bez omezení (frázový) , pokud jej můžeme generovat příslušnou gramatikou (regulární, resp. bezkontextovou, resp. ...) Vztah mezi jednotlivými typy jazyků je analogický vztahu mezi jeho gramatikami.
Ještě něco pro nepozorné – gramatika je systém pravidel, jazyk je množina řetězců.
1. 3. 2007 - 14:41 Benedikovič
6/6
