Bezkontextová gramatika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V lingvistice a informatice označuje pojem bezkontextová gramatika (CFG) formální gramatiku, ve které mají všechna přepisovací pravidla tvar

A → β

kde A je neterminál a β je řetězec terminálů a/nebo neterminálů. Název „bezkontextová“ vychází ze skutečnosti, že neterminál se může přepsat na β bez ohledu na okolní kontext. Jazyky generované bezkontextovými gramatikami se nazývají bezkontextové. Bezkontextová gramatika je speciálním případem gramatiky kontextové (kontext je prázdný).

Formální definice[editovat | editovat zdroj]

Bezkontextová gramatika je určena konečnou množinou neterminálů (neterminálních symbolů - proměnných), konečnou množinou terminálů, která nemá společné prvky s množinou neterminálů, počátečním neterminálem S a konečnou soustavou (množinou) přepisovacích pravidel typu A → β, (A přepiš na β ), kde A je neterminál a β je řetězec z neterminálů a terminálů.

Bezkontextová gramatika G, může být chápána jako čtveřice G = (\Pi\,, \Sigma\,, P\,, S\,), kde

  • Π je konečná množina neterminálů,
  • Σ je konečná množina terminálů, kde průnik množin Π∩Σ = ø
  • P je konečná množina přepisovacích pravidel typu A → β, kde
    • A je neterminál, A ∈ Π
    • β je řetězec složený z terminálů a neterminálů, β ∈ (Π ∪ Σ)*.
  • S je počáteční proměnná, která patří do množiny Π neterminálů,

Příklady[editovat | editovat zdroj]

Příklad 1[editovat | editovat zdroj]

Jednoduchá bezkontextová gramatika je dána přepisovacím pravidlem:

S → aSb | ab (stejně jako A → β)

kde znak | separuje více možností řetězců (w) z terminálů a neterminálů, které znamenají to samé jako zápis:

S → aSb
S → ab

kde a, b označuje terminály, S je startovní symbol (neterminál). Tato gramatika generuje jazyk a^n b^n, kde n>=1. Tento jazyk není regulární. Speciální symbol ε označuje prázdný řetězec. Pokud změníme pravidlo na S → aSb | ε získáme gramatiku, která generuje jazyk a^n b^n, kde n>=0. Tato přepisovací pravidlo obsahuje i přepis na prázdný řetězec, který původní gramatika neobsahuje.

Příklad 2[editovat | editovat zdroj]

Tato bezkontextová gramatika generuje aritmetické výrazy s proměnnými x, y, z:

S → x | y | z | S + S | S - S | S * S | S/S | (S)

S touto gramatikou dokážeme například generovat řetězec "( x + y ) * x - z * y / ( x + x )". Tento řetězec získáme následujícím postupem. Startovací symbol S přepíšeme podle páté transformace [S → S - S]. Následně se S na pravé straně přepíší podle šesté a sedmé transformace na řetězec "S * S - S / S", pak použijeme poslední transformaci s uzávorkováním, tak získáme "( S ) * S - S / ( S )". Poté uzávorkovaná S přepíšeme podle transformace [S → S + S]. Takto dostanem řetězec neterminálů "( S + S ) * S - S * S / ( S + S )", z kterého výsledný řetězec "( x + y ) * x - z * y / ( x + x )" získáme převedením neterminálů S na terminály x, y, z.

Příklad 3[editovat | editovat zdroj]

Bezkontextová gramatika, která se skládá ze slov obsahující znaky a, b v různém počtu a pořadí.

S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε

Neterminál T dovoluje generovat všechny řetězce se stejným počtem áček a béček. Neterminál U generuje řetězec s větším počtem áček než béček. Poslední neterminál V generuje řetězec s větším počtem béček než áček.

Příklad 4[editovat | editovat zdroj]

Dalším příkladem je bezkontextová gramatika, která generuje jazyk {bnam2*bn, kde m>=0, n>=0}. Toto není regulární jazyk, ale je bezkontextový a může být generován bezkontextovou gramatikou:

S → bSbb | A
A → aA | ε

Derivace a syntaktický strom[editovat | editovat zdroj]

Je několik způsobů jak získat potřebný řetězec. Jedním ze způsobů jak jej získat je derivování od startovního symbolu pomocí dané gramatiky. Nejjednodušší cestou je výpis mezikroků od startovního symbolu až po výsledný řetězec a k tomu výpis použitých přepisovacích pravidel. Pokud použijeme strategii, ve které vždy nejprve nahradíme nejlevější neterminál, pak pro kontextovou gramatiku je seznam pravidel použité gramatiky dostačující. Toto nazýváme „levou derivací“ řetězce. Například pokud vezmeme tuto gramatiku:

(1) S → S + S
(2) S → 1
(3) S → a

a řetězec "1 + 1 + a", pak levá derivace tohoto řetězce bude posloupnost použitých pravidel [ (1), (1), (2), (2), (3) ]. Analogicky u pravé derivace se vždy nejprve nahradí nejpravější neterminál. V tomto případě bude seznam pravidel v následujícím pořadí [ (1), (3), (1), (2), (2)].

Rozdíl mezi levou a pravou derivací je důležitý, protože ve většině parsovacích transformací vstupu je definován kus kódu pro každé pravidlo gramatiky. Proto je důležité při parsování se rozhodnout, zdali zvolit levou nebo pravou derivaci, protože ve stejném pořadí se budou provádět části programu. Podobně jako LL syntaktický analyzátor a LR syntaktický analyzátor.

Pomocí derivace uložíme hierarchickou strukturu v řetězci, který je derivován. Jako příklad poslouží řetězec "1 + 1 + a", který je derivován podle levé derivace:

S → S + S (1)
   → S + S + S (1)
   → 1 + S + S (2)
   → 1 + 1 + S (2)
   → 1 + 1 + a (3)

řetězcová struktura může vypadat následovně:

{ { { 1 }S + { 1 }S }S + { a }S }S

kde { ... }S rozpoznaný jako podřetězec S. Tato hierarchie může být také znázorněna jako strom:

           S
          /|\
         / | \
        /  |  \
       S  '+'  S
      /|\      |
     / | \     |
    S '+' S   'a'
    |     |
   '1'   '1'

Tento strom se nazývá konkrétní syntaktický strom (nebo také abstraktní syntaktický strom) řetězce. V tomto případě levá a pravá derivace definuje stejný syntaktický strom. U tohoto řetězce můžeme pomocí levé derivace získat jinou stromovou strukturu a to záměnou prováděných přepisovacích pravidel:

S → S + S (1)
   → 1 + S (2)
   → 1 + S + S (1)
   → 1 + 1 + S (2)
   → 1 + 1 + a (3)

ta definuje následný syntaktický strom:

           S 
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   'a'

Pokud pro určitý řetězec v jazyce gramatiky existuje více jak jeden parsovací strom, potom se tato gramatika nazývá nejednoznačná gramatika. Některé gramatiky se dají těžko rozebírat, protože syntaktický analyzátor neví, které z přepisovacích pravidel má použít. Obvykle mnohoznačnost je charakteristická pro gramatiku, což neplatí pro jazyk. Jednoznačná gramatika může také generovat stejný bezkontextový jazyk jako nejednoznačná gramatika. Nicméně existují jazyky, které nelze vygenerovat žádnou jednoznačnou gramatikou, ty pak nazýváme podstatně nejednoznačné.

Normální formy[editovat | editovat zdroj]

Bezkontextová gramatika nemůže generovat prázdný řetězec, ale může být přetransformována na takovou, která bude obsahovat pravidlo, které to umožní (pravidlo s ε, kde je výsledkem samotné ε). Pokud generuje prázdný řetězec, bude zapotřebí pravidla S \rarr \epsilon, poté nebude mít další pravidlo s ε. Každá bezkontextová gramatika bez vytváření ε je ekvivalentní s Chomského normální formou nebo Greibachové normální formou. Ekvivalentní gramatiky jsou takové, které generují stejný jazyk.

Pro jednoduchost vytváření pravidel je Chomského normální forma vhodná jak pro teoretickou, tak pro praktickou realizaci. Pro případ bezkontextové gramatiky, která používá Chomského normální formu pro konstrukci časově polynomicky náročného algoritmu, kde se rozhoduje, zda daný řetězec je v jazyce reprezentovaným gramatikou nebo není (CYK algoritmus).

Nerozhodnutelné problémy[editovat | editovat zdroj]

Ačkoli některé operace s bezkontextovými gramatikami jsou rozhodnutelné v jejich omezené síle, bezkontextové gramatiky se zajímají i o nerozhodnutelné problémy. Jeden z nejjednodušších a nejvíce řešených problémů je zda gramatika příjme všechny řetězce (slova) daného jazyka. Na řešení tohoto problému může být použit dobře známý Turingův stroj. Redukce využívá koncept historie výpočtu, kde pomocí řetězce popisujeme celkový výpočet Turingova stroje. Dokážeme vytvořit bezkontextovou gramatiku, která generuje všechna slova, která neakceptují historii výpočtu pro specifický Turingův stroj pro jeho specifický vstup, čili přijímá všechna slova pouze pokud tento stroj nepřijímá tento vstup.

Externí odkazy[editovat | editovat zdroj]