Ver o código fonte de "Gramática libre de contexto"

Unha '''gramática libre de [[contexto]]''' en [[lingüística]] e [[informática]] é unha [[gramática formal]] na que cada regra de produción é da forma:
:V &rarr; ''w''
Onde V é un [[símbolo non terminal]] e ''w'' é unha cadea de terminais e/ou non terminais. O termo ''libre de contexto'' refírese ao feito de que o non terminal V pode sempre ser substituído por ''w'' sen ter en conta o contexto no que ocorra. Unha [[linguaxe formal]] é [[Linguaxe libre de contexto|libre de contexto]] se hai unha gramática libre de contexto que a xera.

As gramáticas libres de [[contexto]] permiten describir a maioría das [[Linguaxe de programación|linguaxes de programación]], de feito, a sintaxe da maioría de linguaxes de programación está definida mediante gramáticas libres de contexto. Doutra banda, estas gramáticas son suficientemente simples como para permitir o deseño de algoritmos eficientes de análises sintácticas que, para unha cadea de caracteres dada, determinen como pode ser xerada desde a gramática. Os [[Analizador sintáctico LL|analizadores LL]] e [[Analizador sintáctico LR|LR]] tratan subconxuntos restrinxidos de gramáticas libres de contexto.

A notación máis frecuentemente utilizada para expresar gramáticas libres de [[contexto]] é a [[forma Backus-Naur]].

==Definición formal==
Como calquera [[gramática formal]], unha gramática libre de [[contexto]] pode ser definida mediante a 4-tupla:

<math>G = (V_t, V_n, P, S)</math>
onde
*<math>V_t</math> é un conxunto finito de terminais
*<math>V_n</math> é un conxunto finito de non terminais
*<math>P</math> é un conxunto finito de producións
*<math>S \in V_n</math> o denominado Símbolo Inicial
*os elementos de math <>P</math> son da forma
::<math>V_n \longrightarrow (V_t \cup V_n)^**</math>

==Exemplos==
===Exemplo 1===
Unha simple gramática libre de contexto é
:S &rarr; aSb | &epsilon;
onde | é un ''ou lóxico'' e é usado para separar múltiples opcións para o mesmo non terminal, &epsilon; indica unha cadea baleira. Esta gramática xera a linguaxe non [[linguaxe regular|regular]] <math> \{ a^* b^* : n \ge 0 \} </math>.

===Exemplo 2===
Aquí hai unha gramática libre de contexto para expresións enteiras alxébricas sintacticamente correctas sobre as variables ''x'', ''e'' e ''z'':
:S &rarr; x | e | z | S + S | S - S | S * S | S/S | (S)
Xeraría, por exemplo, a cadea ''( x + e ) * x - z * e / ( x + x )''

===Exemplo 3===
Unha gramática libre de contexto para unha linguaxe consistente en todas as cadeas que se poden formar coas letras ''a'' e ''b'', habendo un número diferente dunha que doutra, sería:

:S &rarr; Ou | V | 0
:Ou &rarr; TaU | TaT
:V &rarr; TbV | TbT
:T &rarr; aTbT | bTaT | &epsilon;

T xera todas as cadeas coa mesma cantidade de letras a que b, ou xera todas as cadeas con máis letras a, e V todas as cadeas con máis letras b.

===Exemplo 4===
Outro exemplo para unha linguaxe é <math> \{ a^* b^* c^*{+n} : n \ge 0, m \ge 0 \} </math>. Non é un [[linguaxe regular]], pero pode ser xerado pola seguinte gramática libre de contexto.
:S &rarr; aSc | B
:B &rarr; bBc | &epsilon;

===Outros exemplos===
As gramáticas libres de contexto non están limitadas a linguaxes matemáticas formais.

A gramática de [[Lojban]], unha linguaxe artificial falada con gran capacidade expresiva, é tamén libre de contexto e non ambigua.

O lingüista indio [[Panini (lingua)|Panini]] describiu o [[sánscrito]] usando unha gramática libre de contexto.

Recentemente suxeriuse que unha clase de poesía [[Lingua támil|támil]] chamada [[Venpa]] utiliza principalmente unha gramática libre de contexto.

==Derivacións e árbores sintácticas==
Existen basicamente dúas formas de describir como nunha certa gramática unha cadea pode ser derivada desde o símbolo inicial. A forma máis simple é listar as cadeas de símbolos consecutivas, comezando polo símbolo inicial e finalizando coa cadea e as regras que foron aplicadas. Se introducimos estratexias como substituír sempre o non terminal de máis á esquerda primeiro, entón a lista de regras aplicadas é suficiente. A isto chámaselle '''derivación pola esquerda'''.

Por exemplo, se tomamos a seguinte gramática:
: (1) S &rarr; S + S
: (2) S &rarr; 1
e a cadea "1 + 1 + 1", a súa derivación á esquerda está na lista [ (1), (1), (2), (2), (2) ]. Analogamente, a '''derivación pola dereita''' defínese como a lista que obtemos se sempre substituímos primeiro o non terminal de máis á dereita. Nese caso, a lista de regras aplicadas para a derivación da cadea coa gramática anterior sería a [ (1), (2), (1), (2), (2)].

A distinción entre derivación pola esquerda e pola dereita é importante porque na maioría de analizadores, a transformación da entrada é definida dando unha parte de código para cada produción que é executada cando a regra é aplicada. De modo que é importante saber que derivación aplica o analizador, por que determina a orde no que o código será executado.

Unha derivación tamén pode ser expresada mediante unha estrutura xerárquica sobre a cadea que está sendo derivada. Por exemplo, a estrutura da derivación á esquerda da cadea "1 + 1 + 1" coa gramática anterior sería:

:S&rarr;S+S   (1)
:S&rarr;S+S+S (1)
:S&rarr;1+S+S (2)
:S&rarr;1+1+S (2)
:S&rarr;1+1+1 (2)

: { { { 1 }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub>
onde { ... }<sub>S</sub> indica a subcadena recoñecida como pertencente a S. Esta xerarquía tamén se pode representar mediante unha árbore sintáctica:

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

A derivación pola dereita:

:S&rarr; S + S      (1)
:S&rarr; 1 + S      (2)
:S&rarr; 1 + S + S  (1)
:S&rarr; 1 + 1 + S  (2) 
:S&rarr; 1 + 1 + 1  (2)

define a seguinte árbore sintáctica:

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

Se para unha cadea da linguaxe dunha gramática hai máis dunha árbore posible, entón dise que a gramática é [[gramática ambigua|ambigua]]. Normalmente estas gramáticas son máis difíciles de analizar por que o analizador non pode decidir sempre que produción aplicar.

==Formas normais==
Unha gramática que non xera a cadea baleira pode ser transformada nunha equivalente (que xera o mesmo linguaxe) en [[forma normal de Chomsky]] ou en [[forma normal de Greibach]].

A simplicidade das regras en forma normal de Chomsky ten implicacións teóricas e prácticas. Por exemplo, dada unha gramática libre de contexto, pódese usar a súa forma normal para construír un algoritmo de custo polinomial que decida se unha cadea forma parte da linguaxe definida pola gramática ou non ([[algoritmo CYK]]).

==Problemas indecidibles==
Algunhas das propiedades das gramáticas, e en xeral, das linguaxes libres do contexto son de natureza decidible, existindo polo tanto algoritmos de decisión para resolvelos. Con todo, ao contrario que no caso das linguaxes regulares, existen problemas interesantes para os cales mostrouse a súa natureza indecidible, e polo tanto, carécese do correspondente [[algoritmo]].

Un dos máis sinxelos é o de decidir se unha gramática libre do contexto dada acepta a linguaxe de todas as posibles cadeas de símbolos. Esta linguaxe vén ser unha redución do [[problema de parada]] dunha [[máquina de Turing]] cunha entrada particular, e polo tanto, un problema indecidible. A redución usa o concepto de ''historia computacional'', é dicir, unha cadea que describa o proceso de computación global dunha máquina de Turing, esta cadea podería describirse mediante unha gramática libre do contexto.  Podemos construír, xa que logo, unha gramática libre do contexto que xere todas as cadeas non aceptadas pola máquina de Turing indicada.

Unha consecuencia importante é que tamén é indecidible a comparación entre dúas gramáticas libres do contexto para comprobar se a linguaxe xerada coincide.

Pola contra, o problema sinxelo de determinar se dada unha cadea é aceptada por unha determinada gramática libre do contexto, si que é decidible, e polo tanto poderá escribirse o correspondente algoritmo para decidilo.

==Propiedades das linguaxes libres de contexto==
* Unha das definicións alternativas e equivalentes de linguaxe libre de contexto emprega autómatas non deterministas: unha linguaxe é libre de contexto se pode ser aceptado por ese autómata.
* Unha linguaxe pode ser tamén modelado como un conxunto de todas as secuencias de terminais aceptadas pola gramática. Este modelo axuda a entender as operacións de conxuntos sobre linguaxes.
* A unión e concatenación de dúas linguaxes libres de contexto é tamén libre de contexto. A intersección non ten por que selo.
* O inverso dunha linguaxe libre de contexto é tamén libre de contexto, pero o complemento non ten por que selo.
* Os [[linguaxe regular|linguaxes regulares]] son libres de contexto por que poden ser descritos mediante unha [[gramática regular]].
* A intersección dunha linguaxe libre de contexto e unha linguaxe regular é sempre libre de contexto.
* Existen gramáticas sensibles ao contexto que non son libres de contexto.
* Para demostrar que unha linguaxe dada non é libre de contexto, pódese empregar o [[Lema do bombeo]] para linguaxes libres de contexto.
* O problema de determinar se unha gramática sensible ao contexto describe unha linguaxe libre do contexto é indecidible....

==Véxase tamén==
===Outros artigos===
* [[Gramática formal]]
* [[Gramática libre de contexto probabilística]]

{{Control de autoridades}}

[[Categoría:Gramática]]