Bezkontextová gramatika

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

A → β

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

Termíny

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

Přepsání je operace, při které se v řetězci složeném z terminálů a neterminálů nahradí podřetězec tvořící levou stranu nějakého pravidla gramatiky pravou stranou tohoto pravidla. Někdy se používá termín bezprostřední přepsání pro zdůraznění, že se jedná o jedno použití přepisovacího pravidla.

Odvození neboli derivace je postup, při kterém se na řetězec uplatní konečný počet (žádné, jedno nebo více) přepsání.

Větná forma (anglicky sentential form) určité gramatiky je libovolný řetězec složený z terminálů a neterminálů, který lze získat z počátečního symbolu konečným počtem přepsání.

Řetězec generovaný danou gramatikou, méně formálně věta gramatiky je větná forma, která je tvořena pouze terminálními symboly.

Jazyk generovaný gramatikou je množina všech řetězců, generovaných gramatikou.

Levá derivace neboli levé odvození (anglicky leftmost derivation) je takový postup při generování určitého slova v bezkontextové gramatice, že se vždy přepisuje první neterminální symbol zleva. Bezkontextovost gramatiky umožňuje přepisovat neterminály v libovolném pořadí.

Pravá derivace neboli pravé odvození (anglicky rightmost derivation) je takový postup při generování určitého slova v bezkontextové gramatice, že se vždy přepisuje poslední neterminální symbol (tj. první zprava).

Formální definice

Bezkontextová gramatika je čtveřice G = (V_N, V_T, P, S), kde

• V_N je konečná množina neterminálních symbolů, krátce neterminálů,
• V_T je konečná množina terminálních symbolů, krátce terminálů, přičemž tyto dvě množiny nemají žádné společné prvky (V_T ∩ V_N = ø)
• P je konečná množina přepisovacích pravidel tvaru A → β, kde
  • A je neterminál, A ∈ V_N
  • β je řetězec složený z terminálů a neterminálů, β ∈ (V_N ∪ V_T)*.
• S je počáteční symbol, který patří do množiny V_N neterminálů.

Přepsání αAγ ⊨ αβγ je nahrazení řetězce αAγ řetězcem αβγ, kde A → β je pravidlo gramatiky a α,γ ∈ (V_N ∪ V_T)*.

Derivace ⊨^* je tranzitivní a reflexívní uzávěr přepsání.

Jazyk generovaný gramatikou G je L(G) = { w | w ∈ V_T^* & S ⊨^* w }.

Příklady

Příklad 1

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ⁿbⁿ, kde $n\geq 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ⁿbⁿ, kde $n\geq 0$. Tato přepisovací pravidlo obsahuje i přepis na prázdný řetězec, který původní gramatika neobsahuje.

Příklad 2

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

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

Dalším příkladem je bezkontextová gramatika, která generuje jazyk {bⁿa^m2*bⁿ, kde $m\geq 0$, $n\geq 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

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 než 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

Ke každé bezkontextové gramatice lze sestrojit gramatiku v Chomského normální formě a v Greibachové normální formě, které jsou s původní gramatikou ekvivalentní. 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

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řijme 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.

Odkazy

Externí odkazy

• Regulární a bezkontextové jazyky II. Archivováno 31. 5. 2020 na Wayback Machine.

Autoritní data	NKC: ph214655 BNF: cb180900709 (data)