Gramática Formal

As regras descrevem como formar cadeias ― a partir do alfabeto da linguagem ― que são válidas de acordo com a sintaxe da linguagem. Uma gramática não descreve significado das cadeias ou o que pode ser feito com elas em um contexto ― apenas suas formas.

A expressão "gramática formal" pode ter os sentidos:

• gramática de um linguagem formal;
• descrição formal de parte da gramática de uma linguagem natural.

A Teoria da Linguagem Formal, disciplina que estuda gramáticas e linguagens formais, é um ramo da Matemática Aplicada. Suas aplicações podem ser encontradas na Ciência da Computação Teórica, Linguística Teórica, Semântica Formal, Matemática Lógica, entre outras áreas.

Uma gramática formal é um conjunto de regras para se reescrever cadeias, tomando como partida um símbolo inicial, do qual se começa a reescrita. Portanto, uma gramática é normalmente encarada como um gerador de linguagem. Entretanto, ela também pode ser usada como uma base para um reconhecedor ― uma função em computação que determina se uma dada cadeia pertence à linguagem ou está gramaticalmente incorreta. Para descrever tais reconhecedores, a teoria da linguagem formal usa formalismos distintos, conhecidos como Teoria dos Autômatos. Um dos resultados mais interessantes da teoria dos autômatos é que não é possível desenhar um reconhecedor para certas linguagens formais.

Análise sintática é o processo de reconhecer uma elocução (cadeia em linguagem natural) quebrando-a em um conjunto de símbolos e analisando cada um de acordo com a gramática da linguagem. O significado das elocuções da maioria das linguagens está estruturado conforme a sintaxe de tal linguagem — prática conhecida como semântica composicional. Como resultado, o primeiro passo para descrever o significado de uma elocução de uma linguagem é quebrá-la parte por parte, e verificar a sua forma analítica (conhecida como "árvore de análise" em Ciência da Computação, e como "estrutura profunda" em gramática gerativa).

Uma gramática consiste, principalmente, de um conjunto de regras para transformação de cadeias. (Se ela apenas consistisse dessas regras, ela seria considerada um sistema semi-Thue). Para gerar uma cadeia na linguagem, começa-se com uma cadeia que consiste em apenas um símbolo inicial. As regras de produção são, então, aplicadas em uma ordem qualquer, até que uma cadeia que não contenha nem o símbolo inicial, nem os chamados símbolos não terminais, seja produzida. Uma regra de produção é aplicada a uma cadeia substituindo-se uma ocorrência do lado esquerdo da gramática por uma do lado direito. A linguagem formada pela gramática consiste em todas as cadeias distintas que podem ser geradas dessa forma. Qualquer sequência particular de regras de produção sobre o símbolo inicial produz uma cadeia distinta na linguagem. Se existem várias maneiras de gerar a mesma cadeia, a gramática é chamada de ambígua.

Por exemplo, assumimos que o alfabeto consiste de a e b, o símbolo inicial é S, e temos as seguintes regras de produção:

1. ${\displaystyle S\rightarrow aSb}$ 
2. ${\displaystyle S\rightarrow ba}$ 

Então começamos com S, e podemos escolher uma regra para aplicar a ele. Se nós escolhermos a regra 1, obteríamos a cadeia aSb. Se nós escolhermos a regra 1 outra vez, nós substituiríamos o S do aSb por aSb, e obteríamos a cadeia aaSbb. Se agora nós escolhermos a regra 2, nós substituiríamos o S do aaSbb por ba e obteríamos a cadeia aababb, terminando o processo. Nós podemos escrever essa série de escolhas mais sucintamente, usando símbolos: ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$ . A linguagem da gramática é, então, o conjunto infinito ${\displaystyle \left\{a^{n}bab^{n}|n\geq 0\right\}=\left\{ba,abab,aababb,aaababbb,...\right\}}$ , em que a^k é a repetido k vezes (e n, em particular, representa o número de vezes que a regra de produção 1 foi aplicada).

A Sintaxe das Gramáticas

Na formalização de gramáticas generativas primeiramente proposta por Noam Chomsky nos anos de 1950, uma gramática G era composta pelos seguintes componentes:

• Um conjunto finito N de símbolos não terminais, que é disjunto das cadeias formadas a partir de G.
• Um conjunto finito ${\displaystyle \Sigma }$  de símbolos terminais que é disjunto de N.
• Um conjunto finito P de regras de produção, cada uma com a forma ${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$  onde ${\displaystyle {*}}$  é o operador de Kleene e ${\displaystyle \cup }$  denota a união entre conjuntos. Isso significa que cada regra de produção mapeia uma cadeia de símbolos para outra, onde a primeira contém um número arbitrário de símbolos, dos quais pelo menos um é não terminal. A segunda cadeia consistiria somente da cadeia vazia — ou seja, não contêm símbolos - sendo, às vezes, representada com notações especiais pra evitar confusão (${\displaystyle \Lambda }$ , e ou ${\displaystyle \epsilon }$ ).

• Um símbolo diferenciado ${\displaystyle S\in N}$  que é o símbolo inicial, também chamado de símbolo sentença.

Uma gramática é formalmente definida como uma tupla ${\displaystyle (N,\Sigma ,P,S)}$ . Tal gramática formal é, às vezes, chamada de sistema de reescrita ou de gramática de estrutura de frase na Literatura.

A Semântica das Gramáticas

A operação sobre uma gramática pode ser definida em termos das relações entre cadeias:

• Dada uma gramática ${\displaystyle G=(N,\Sigma ,P,S)}$ , a relação binária ${\displaystyle \Rightarrow _{G}}$  (lê-se G deriva em um passo) sobre cadeias de ${\displaystyle (\Sigma \cup N)^{*}}$  é definida por: ${\displaystyle x\Rightarrow _{G}y{\mbox{ iff }}\exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$ 
• A relação  ${\displaystyle {\Rightarrow _{G}}^{*}}$  (lê-se G deriva em 0 ou mais passos) é definida como o fecho reflexivo-transitivo de  ${\displaystyle \Rightarrow _{G}}$ .
• Uma forma sentencial é um membro de ${\displaystyle (\Sigma \cup N)^{*}}$  que pode ser derivado, partindo do símbolo inicial ${\displaystyle S}$ , em um número finito de passos; ou seja, uma forma sentencial é um membro de ${\displaystyle \{w\in (\Sigma \cup N)^{*}\mid S{\Rightarrow _{G}}^{*}w\}}$ . Uma forma sentencial que não contém símbolos não terminais (i.e. é um membro de ${\displaystyle \Sigma ^{*}}$ ) é chamada de sentença.
• A linguagem de ${\displaystyle G}$ , denotada como ${\displaystyle {\boldsymbol {L}}(G)}$ , é definida como todas as sentenças que podem ser derivadas em um número finito de passos partindo do símbolo inicial ${\displaystyle S}$ ; ou seja, o conjunto ${\displaystyle \{w\in \Sigma ^{*}\mid S{\Rightarrow _{G}}^{*}w\}}$ .

Note que a gramática ${\displaystyle G=(N,\Sigma ,P,S)}$  é efetivamente um sistema semi-Thue ${\displaystyle (N\cup \Sigma ,P)}$ , pois reescreve cadeias exatamente do mesmo jeito; a única diferença está no fato de que nós distinguimos especificamente símbolos não terminais que devem ser reescritos nas regras de reescrita, e estamos apenas interessados em reescritas a partir do símbolo inicial ${\displaystyle S}$  designado para cadeias sem símbolos não terminais.

Exemplo

Para esses exemplos, as linguagens formais estão especificadas utilizando a notação de construção de conjuntos.

Considere a gramática ${\displaystyle G}$  onde ${\displaystyle N=\left\{S,B\right\}}$ , ${\displaystyle \Sigma =\left\{a,b,c\right\}}$ , ${\displaystyle S}$  é o símbolo inicial, e ${\displaystyle P}$  é composto pelas seguintes regras de produção:

1. ${\displaystyle S\rightarrow aBSc}$ 
2. ${\displaystyle S\rightarrow abc}$ 
3. ${\displaystyle Ba\rightarrow aB}$ 
4. ${\displaystyle Bb\rightarrow bb}$ 

Essa gramática define a linguagem ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}}$  onde ${\displaystyle a^{n}}$  denota uma cadeia formada por n consecutivos ${\displaystyle a}$ 's. Dessa forma, a linguagem é o conjunto de cadeias que é composta por um ou mais ${\displaystyle a}$ 's, seguidos pelo mesmo número de ${\displaystyle b}$ 's, seguidos pelo mesmo número de ${\displaystyle c}$ 's.

Alguns exemplos de derivação de cadeias em ${\displaystyle L(G)}$  são:

• ${\displaystyle {\boldsymbol {S}}\Rightarrow _{2}{\boldsymbol {abc}}}$ 
• ${\displaystyle {\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{2}aB{\boldsymbol {abc}}c\Rightarrow _{3}a{\boldsymbol {aB}}bcc\Rightarrow _{4}aa{\boldsymbol {bb}}cc}$ 
• ${\displaystyle {\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{1}aB{\boldsymbol {aBSc}}c\Rightarrow _{2}aBaB{\boldsymbol {abc}}cc\Rightarrow _{3}a{\boldsymbol {aB}}Babccc\Rightarrow _{3}aaB{\boldsymbol {aB}}bccc}$ ${\displaystyle \Rightarrow _{3}aa{\boldsymbol {aB}}Bbccc\Rightarrow _{4}aaaB{\boldsymbol {bb}}ccc\Rightarrow _{4}aaa{\boldsymbol {bb}}bccc}$ 

(Note a notação: ${\displaystyle P\Rightarrow _{i}Q}$  lê-se "A cadeia P gera a cadeia Q pela regra de produção i ". A parte gerada é, a cada vez, indicada em negrito.)

 Ver artigo principal: Hierarquia de Chomsky

Quando Noam Chomsky formalizou as gramáticas generativas pela primeira vez em 1956, ele as classificou em tipos hoje conhecidos como pertencentes à hierarquia de Chomsky. A diferença entre esses tipos é que eles têm cada vez mais rigorosas regras de produção e podem expressar menos linguagens formais. Dois importantes tipos são gramáticas livres de contexto (Tipo 2) e gramáticas regulares (Tipo 3). As linguagens que podem ser descritas com tais gramáticas são chamadas linguagens livres de contexto e linguagens regulares, respectivamente. Apesar de menos poderosas que gramáticas irrestritas (Tipo 0), que podem, na verdade, expressar qualquer linguagem que pode ser aceita por uma Máquina de Turing, esses dois tipos restritos de gramática são mais frequentemente usados porque analisadores para eles podem ser eficientemente implementados. Por exemplo, todas linguagens regulares podem ser reconhecidas por uma máquina de estados finitos, e para alguns subconjuntos úteis de gramáticas de livre-contexto existem algoritmos bem conhecidos para gerar analisadores sintáticos eficientes para reconhecer as linguagens correspondentes às gramáticas geradas.

Gramáticas de livre-contexto

Uma gramática livre de contexto é uma gramática em que o lado esquerdo de cada regra de produção é formado apenas por um único símbolo não terminal. Essa restrição é não trivial; nem todas as linguagens podem ser geradas por gramáticas livre de contexto. As que podem são chamadas de linguagens livre de contexto.

A linguagem ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}}$  definida abaixo não é uma linguagem livre de contexto, e isso pode ser rigorosamente provado utilizando o lema do bombeamento para linguagens livres de contexto, mas, por exemplo, a linguagem ${\displaystyle \left\{a^{n}b^{n}|n\geq 1\right\}}$  (pelo menos 1 ${\displaystyle a}$  seguido pelo mesmo número de ${\displaystyle b}$ 's) é livre de contexto, pois pode ser definida por uma gramática ${\displaystyle G_{2}}$  com ${\displaystyle N=\left\{S\right\}}$ , ${\displaystyle \Sigma =\left\{a,b\right\}}$ , ${\displaystyle S}$  símbolo inicial, e as seguintes regras de produção:

1. ${\displaystyle S\rightarrow aSb}$ 
2. ${\displaystyle S\rightarrow ab}$ 

Uma linguagem livre de contexto pode ser reconhecida em tempo ${\displaystyle O(n^{3})}$  (veja: notação Big O) por um algoritmo como algoritmo de Earley. Isso significa que, para toda linguagem livre de contexto, uma máquina cuja entrada é uma cadeia pode ser construída, determinando em tempo ${\displaystyle O(n^{3})}$  se a cadeia é membro da linguagem, onde ${\displaystyle n}$  é o comprimento da cadeia. Linguagens determinísticas livres de contexto são um subconjunto de linguagens livres de contexto que podem ser reconhecidas em tempo linear. Existem vários algoritmos que se focam nesse conjunto de linguagens ou algum subconjunto dele.

Gramáticas regulares

Nas gramáticas regulares, o lado esquerdo é composto unicamente por símbolos não terminais, mas o lado direito também é restrito. O lado direito pode ser a cadeia vazia, ou um simples símbolo terminal, ou um símbolo terminal seguido de um símbolo não terminal e nada mais. (às vezes é usada uma definição mais ampla: pode-se permitir cadeias mais longas de terminais ou únicos não terminais sem nada mais, tornando as linguagens mais fáceis de se denotar).

A linguagem ${\displaystyle \left\{a^{n}b^{n}|n\geq 1\right\}}$  definida abaixo não é regular, mas a linguagem ${\displaystyle \left\{a^{n}b^{m}\,|\,m,n\geq 1\right\}}$  (pelo menos um ${\displaystyle a}$  seguido por pelo menos um ${\displaystyle b}$ , onde os números podem ser diferentes) é, já que pode ser definida pela gramática ${\displaystyle G_{3}}$  com ${\displaystyle N=\left\{S,A,B\right\}}$ , ${\displaystyle \Sigma =\left\{a,b\right\}}$ , ${\displaystyle S}$  o símbolo inicial, e as seguintes regras de produção:

1. ${\displaystyle S\rightarrow aA}$ 
2. ${\displaystyle A\rightarrow aA}$ 
3. ${\displaystyle A\rightarrow bB}$ 
4. ${\displaystyle B\rightarrow bB}$ 
5. ${\displaystyle B\rightarrow \epsilon }$ 

Todas as linguagens geradas por gramáticas regulares podem ser reconhecidas em tempo linear por uma máquina de estados finitos. Contudo, na prática, gramáticas regulares são comumente expressas usando expressões regulares. Algumas formas de expressão regular usadas na prática não geram rigorosamente linguagens regulares e não apresentam performance linear de reconhecimento devido a aquelas divergências.

Outras formas de gramáticas generativas

Muitas extensões e variações sobre a hierarquia original de Chomsky de gramáticas formais têm sido desenvolvidas, tanto pelos linguistas quanto pelos cientistas da computação, usualmente com o objetivo de aumentar seu poder de expressividade ou de torná-las mais facilmente analisáveis. Algumas formas de gramática desenvolvidas incluem:

• Gramáticas árvore-adjacente aumenta a expressividade de gramáticas generativas convencionais ao permitir que regras de reescrita operem sobre árvore de análise sintática em vez de apenas cadeias.
• Gramáticas de afixo e gramáticas de atributos permitem que regras de reescrita sejam ampliadas com uso de atributos e operações semânticas, úteis para aumentar a expressividade da gramática e para construir ferramentas práticas para tradução de linguagens.

Gramáticas recursivas

Não se confunda com linguagem recursiva

Uma gramática recursiva é uma gramática que contém regras de produção que são recursivas. Por exemplo, uma gramática para uma linguagem livre de contexto é recursiva à esquerda se existe símbolo não terminal A que pode ser colocado através das regras de produção para produzir uma cadeia com A como o símbolo mais à esquerda. Todos os tipos de gramática da Hierarquia de Chomsky podem ser recursivas.

Apesar de haver um enorme estoque de literatura sobre algoritmos de análise sintática, a maioria desses algoritmos assume que a linguagem a ser analisada é, inicialmente, descrita por meio de uma gramática formal generativa, e que o objetivo é transformar essa gramática em um analisador sintático que funciona. Ou seja, uma gramática generativa não corresponde, de maneira alguma, ao algoritmo usado para analisar uma linguagem, e vários algoritmos têm restrições diferentes sobre a forma de regras de produção que são consideradas bem formadas.

Uma abordagem alternativa é formalizar a linguagem em termos de uma gramática analítica, o que corresponderia mais diretamente à estrutura e semântica de um analisador sintático para a linguagem. Exemplos de formalismos de gramática analítica incluem os seguintes:

• A linguagem de máquina implementa diretamente uma gramática analítica irrestrita. Regras de substituição são usadas para transformar uma entrada e produzir saídas e comportamento. O sistema também pode produzir the lm-diagram que mostra o que acontece quando as regras de uma gramática analítica irrestrita estão sendo aplicadas.
• Linguagem de análise top-down: um formalismo de gramática analítica altamente minimalista desenvolvido no começo dos anos de 1970 para estudar o comportamento de analisadores sintáticos top-down.
• Gramática de ligação: uma forma de gramática analítica desenhada para a linguística, que deriva a estrutura sintática através do exame das relações de posicionamento entre pares de palavras.
• Gramática de análise de expressões: uma generalização mais recente de uma linguagem de análise top-down. Desenhada levando-se em conta as necessidades práticas de expressividade de uma linguagem de programação e de compiladores.