Introdução

Há algum tempo eu escrevi um post sobre linguagens formais e autômatos, onde eu expliquei previamente sobre, e explanei também sobre autômatos finitos determinísticos. Para quem não sabe, compiladores são criados a partir dos conceitos em linguagens formais e hoje estou aqui para falar sobre gramática, que também por sua vez é um reconhecedor de cadeias, assim como o automato.

Linguagens não-regulares.

Como já vimos, o poder do autômato finito são restritos às linguagens regulares. Ou seja, para cada caractere que fazemos a leitura no autômato, o mesmo é limitado àquele estado, não podemos guardar informação sobre quantas leituras fizemos em um loop, por exemplo. Sendo assim, cada símbolo de uma cadeia é totalmente independente da leitura dos demais símbolos.

Ai que entra o problema do autômato, em algumas linguagens, essa independência não acontece, ou seja, é necessário armazenar informações de leituras anteriores para possibilitar a leitura de caracteres seguintes. Não está entendendo nada? Deixe-me tentar explicar com um exemplo!

Imagine que temos a seguinte linguagem: L = 0ⁿ1ⁿ /N>=1
Como que iríamos construir um autômato finito determinístico para essa linguagem? Se você seguir o passo a passo do post que eu fiz anteriomente.
Provavelmente iria fazer algo parecido com isso:

Sabendo que 0 e 1 tem um expoente n, onde n pode ser qualquer número igual ou maior que 1. Vamos montar algumas cadeias válidas considerando alguns valores de n.
n=1 | 01
n=2 | 0011
n=3 | 000111
n=4 | 00001111
n=5 | 0000011111

Como podemos perceber, precisamos da mesma quantidade de zeros e uns para que uma cadeia seja válida. Sabendo disso, me responde uma pergunta. A cadeia 00011 é uma cadeia válida? Se sua resposta foi NÃO então tu acertou.

Sabemos que uma linguagem é um conjunto de regras, e um autômato é uma representação dessas regras. "Que faz a regra ser cumprida". O autômato anterior, ele por si, não impede que o usuário chegue no estado final com uma cadeia inválida. Ele infringe a única regra para a qual foi criado, "Validar Cadeias".

É impossível escrever um algoritmo finito, que valide a linguagem L = 0ⁿ1ⁿ /N>=1.

Mas você sabe me dizer o porquê?
Por conta do expoente n, pois para saber quantos números um eu preciso ler, eu tenho que saber quantos números zeros foram lidos anteriormente, pois precisam ter a mesma quantidade.

Sendo assim, precisamos dar um jeito de guardar informações, uma espécie de memória, porém, com o autômato finito, não conseguimos fazer isso. Entendendo o problema do autômato finito, conseguimos entender o porquê de ter sido inventada a gramática para resolver linguagens onde se existe 1 ou mais vaiáveis.

Existe um autômato chamado, "Automato a pilha" que foi criado depois, esse autômato ele tem a capacidade de guardar informações.

Definição formal do que é gramática.

A gramática é uma linguagem formal que serve para definir qual subconjunto de sentenças faz parte de uma determinada linguagem. Especificamente, linguagens potencialmente infinitas de uma forma finita. Seu poder é superior aos autômatos finitos, pois abrange as linguagens regulares e também as não regulares.

A principal função das gramáticas é a construção e a descrição de interpretadores e compiladores.

Conceito.

Formalmente falando, uma gramática é uma quádrupla, formada por:

• V: Conjunto de variáveis.
• \sum:Alfabeto
• S^0:Produção Inicial. S^0 \in V. Por convenção, usaremos S como S^0
• \delta:Função de produção.

No Autômato a função de transição de estádo é o digrafo, que é usado para validar as cadêias.

Em Gramática a função de transição é a representação do "O que é cada variável. Veremos a definição mais formal adiante.

Classes de gramáticas.

Existe um cara chamado Avram Noam Chomsky. Esse cara criou uma hierarquia que organiza as gramáticas em classes, isso é chamado de Hierarquia de Chomsky, onde organiza as gramáticas mediante o seu poder.
Uma classe superior engloba todas as classes inferiores e mais um conjunto de gramáticas próprias. As quatro classes de gramáticas definidas por Chomsky são:

1. Gramáticas com Estrutura de frases;
2. Gramáticas sensíveis ao contexto;
3. Gramáticas Livres de Contexto;
4. Gramáticas Regulares;

Uma representação gráfica seria a seguinte:

Aqui não falaresmos sobre todos os tipos de gramática, pois o meu jeito de escrever as coisas para que seja de fácil leitura "Bem mastigado", iria gerar muito texto kkkk. Então vamos focar apenas nas gramáticas Livres de Contexto.

Construção de uma Gramática.

Sempre que escrevemos uma gramática, precisamos escrever sua quádrupla por completo. Considerando a seguinte linguagem L= 0ⁿ1ⁿ / n ≥ 1 Vamos escrever sua gramática:
1. Variáveis.
Ainda não sabemos como calcular a quantidade de variáveis que a linguagem irá precisar, por isso vamos declarar apenas uma e, caso seja necessário, declararemos mais. Por convenção, a primeira variável será sempre S, portanto, vamos declarar apenas o S.

2. Alfabeto.
Como já sabemos, o alfabeto são caracteres presentes na linguagem, neste caso, apenas 0 e 1;

3. Produção Inicial.
Por convenção, será sempre S a primeira variável declarada na gramática.

4. Função de produção.
A função de produção é o mecanismo gerador de todas as cadeias válidas da linguagem e é composto por duas partes. A parte "Replicação", onde se localiza a recursão geradora que vai até o infinito e a parte "Obrigatória", que é a saída da recursão e é composta pela "cadeia mínima" da estrutura que a variável representa e a próxima variável, caso exita.

A cadeia mínima, nós já aprendemos a identificar no meu post anterior. A replicação é facilmente identificada quando construímos a árvore sintática da estrutura. Uma árvore de análise sintática, ou simplesmente árvore sintática, é uma estrutura de dados em árvore, que representa a estrutura sintática de uma cadeia de acordo com alguma gramática formal. Isso significa que cada cadeia válida terá uma árvore sintática que a representa e nenhuma cadeia inválida terá essa árvore sintática.

Para analisarmos melhor as árvores sintáticas, primeiramente vamos listar as cadeias válidas da linguagem anterior.

Agora vamos construir as árvores sintáticas para algumas destas cadeias.

Árvore sintática da cadeia mínima.

Com essa árvore sintática, chegamos à conclusão que S= 01.E as demais cadeias, como poderão ser geradas? A resposta para essa pergunta é simples:Recursão

Sabemos que S= 01, agora imagine a segunda cadeia válida: 0011, assim temos 0011 = 0S1. No caso da terceira cadeia válida, temos 000111 = 00S11, e assim por diante. Vejamos as árvores sintáticas:

Árvore Sintática da segunda cadeia válida.

Árvore Sintática da terceira cadeia válida.

Chegamos a conclusão que S = 0S1, ficando assim a função de produção:

Onde do lado esquerdo da união á replicação e do lado direito da união é a Obrigatória.
Assim podemos observar por exemplo: S = 0S1 = 00S11 = 000S111 = 0000S1111
Com isso, nossa gramática fica assim:

• V = S;
• \sum = 0, 1;
• S^0 = S;
• \delta \to S = 0S1 \ U\ 01

Importante: No posicionamento das variáveis na função de produção da gramática, a variável da replicação deve está sempre do mesmo lado que se encontra a variável da cadeia mínima, e esta por sua vez, deve-se orientar sempre pela linguagem

Gramática Livre de Contexto

Em resumo, toda gramática é classificada como Livre-De-Contexto se, e somente se, no lado esquerdo da igualdade de cada produção, existe uma e apenas uma variável.

Função de produção.

Como foi dito anteriormente, na função de produção temos que descrever o que é CADA variável, para fazermos isso precisamos a princípio declarar essas variáveis, porém ainda não sabemos a quantidade de variáveis que vamos precisar, então vamos começar declarando a primeira e chamando de S, pois por convenção as variáveis possuem apenas um caractere, e a primeira delas se chama S.
Certo, mas o que S vai receber? Assim como nas linguagens de programação, precisamos instanciar as variáveis, ou seja, dizer o que é cada variável.

Como foi mostrado anteriormente, a função de produção é composta por 2 partes, "Replicação, e Obrigatória", onde a obrigatória é composta pela cadeia mínima da estrutura (Caractere(s)) que a variável representa e a próxima variável caso exista.Ficou confuso? Vamos para um exemplo prático.

Exemplo

Primeiro temos que definir as variáveis, mas como temos caracteres à direita do expoente N, precisamos aplicar a regra do balão, pois é extremamente necessário que a declaração de variáveis seja em ordem.

A declaração de variáveis é feita da esquerda para a direita, onde cada elemento independente é uma variável. Os elementos que dependem uns dos outros se juntam e formam uma variável só, ou seja, os elementos com expoentes iguais são uma variável só.

Quando temos elementos à direita do expoente, precisamos criar um balão que serve para orientação na declaração de variáveis, e quando temos um balão, as variáveis são criadas de fora para dentro, sempre em direção ao balão.

Por convenção, a primeira variável é o S, a segunda A, B, C, D… As variáveis são apenas 1 caracteres.

A figura abaixo representa a forma correta de declarar as variáveis e sua ordem para a linguagem atual.

S	1^+
A	2^+
B	0*
C	2^n\ 1^n
D	0
E	1^*

A cima temos uma tabela para representar como cada variável foi declarada conforme a linguagem anterior, porém ainda é preciso escrever a função de produção, onde vamos dizer o que tem em cada variável.

Com cada variável declarada, a gramática completa ficaria da seguinte forma:
V= S,A,B,C,D,E;
\sum = \{0,1,2\}
S^0 = S;
\delta: \\S = 1A\\A=A2\cup B2 \\B=B0\cup C\lambda\\C=2C1\cup2D1\\D=0E\\E=1E\cup\lambda

Essa é a gramática da expressão anterior, porém, para a montagem da fução de produção da mesma, foram aplicadas algumas regras:

• Como declarar variáveis;
• Regra do balão;
• Regra das constantes;
• Regra do Fecho Positivo;
• Regra do fecho Estrela;

Separação de variáveis das gramáticas livres-de-contexto.

Antes de iniciarmos os exemplos, vamos a uma pergunta importante: É possível saber a quantidade de variáveis que se precisa declarar, penas observando a linguagem? A resposta para essa pergunta é SIM!

Para cada tipo de gramática, com restrições, existe uma forma diferente de se saber a quantidade de variáveis a serem declaradas.

Em TODAS as gramáticas, devemos isolar os elementos independentes de uma linguagem, pois cada um desses elementos será uma variável.
Nas gramáticas livres de contexto, além do que já foi exposto, a contagem de variáveis possui algumas particularidades.

1. Na união, o sinal da união é uma variável e essa variável representa todas as uniões simples da linguagem;
2. Quando todos os elementos da linguagem estão dentro de um fecho, esse fecho será uma variável e será contado antes de seus elementos internos;
3. A estrutura que reconhece todas as cadeias de uma linguagem, a qual chamamos de "qualquer coisa", será uma única variável;
4. Quando existir um fecho dentro de outro, o fecho interno é uma variável independente da variável do fecho externo e não será contado na sequência normal da gramática;

Importante: Para saber o posicionamento das variáveis nas produções, deve-se sempre orientar-se pela linguagem, ou seja, na linguagem, a próxima variável está na rireita ou na esquerda na variável que está sendo resolvida. Se ela estiver na direita, a variável deve aparecer à direita dos elementos do algabeto que compõe a produção, o mesmo acontece quando a variável está a a esquerda ou dentro da variável que es´ta sendo resolvida. Numa mesma produção as variáves devem estar sempre no mesmo lado (em construções normais).

Lemas das gramáticas livres de contexto.

Lema 01: Elementos Constantes. Cada constante é uma variável e a produção não possui a parte "Replicação", pois uma constante é estática.

Lema 02: Fecho Positivo.. No fecho positivo, a parte replicação e a parte obrigatória são formadas pelo elemento que compõe o fecho.

Lema 03: Fecho Estrela. No fecho estrela, a parte replicação se dá como no fecho positivo e a parte obrigatória é vazia.

Lema 04: Fecho com mais de um elemento constante. Quando existirem duas ou mais constantes dentro de um fecho, esse fecho será uma única variável e as constantes tratadas como se fossem apenas uma.

Exemplo 01

Separando os elementos da linguagem: L=0^*1^+(10)^+1011^*, temos:

Neste exemplo, identificamos sete variáveis.

S	0^*
A	1^+
B	(10)^+
C	1
D	0
E	1
F	1^*

A gramática fica da seguinte forma:
V= S,A,B,C,D,E, F;
\sum = \{0,1\}
S^0 = S;
\delta: \\S = 0S \cup \lambda A\\A=1A\cup1B\\B=10B \cup 10C\\C= 1D\\D=0E\\E=1F\\F=1F\cup\lambda

Nas gramáticas livres-de-contexto, as variáveis devem ser contadas de fora para dentro. Os elementos variáveis (de expoente, N, M, etc.) são dependentes entre si, por isso, contam apenas uma única variável para cada um.

Esses elementos vatiáveis só devem ser contados quando todos os elementos a esquerda do primeiro e a direita do segundo já o foram. Por isso utilizamos o "balão", para nos nortear durante a declaração de variáveis.

Exemplo 02

Separando os elementos da linguagem: L=01^N1^+(110)^+010^N11^*, temos:

Neste exemplo, identificamos oito variáveis, e elas são as seguintes:

S	0
A	1^*
B	1
C	1^n\ 0^n
D	1^+
E	(110)^+
F	0
G	1

A gramática fica da seguinte forma:
V= S,A,B,C,D,E,F, G;
\sum = \{0,1\}
S^0 = S;
\delta: \\S = 0A\\A=A1\cup B\lambda\\B=C1\\C=1C0\cup1D0\\D=1D\cup1E\\E=110E\cup110F\\F=0G\\G=1

Conclusão

Esse não é o fim do conteúdo, muito menos de gramática, porém creio que seja o básico para que você consiga resolver algo relacionado. No pior dos casos, eu posso usar como resumo kkk. Enfim, existe um mar de conteúdo, porém trazer todo de uma vez seria como tentar escrever um livro.