Gramática formal

Uma gramática formal (algumas vezes simplesmente chamada de gramática) é um objeto matemático que permite especificar uma linguagem ou língua, ou seja, é um conjunto de regras de formação de cadeias numa linguagem formal. As regras descrevem como formar as cadeias do alfabeto da linguagem que são válidos de acordo com a sintaxe da linguagem. Uma gramática não descreve os significados das cadeias ou o que pode ser feito com elas em qualquer contexto.

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

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

Teoria da linguagem formal, a disciplina que estuda gramáticas e linguagens formais, é um ramo de matemática aplicada. Suas aplicações podem ser encontradas na ciência da computação teórica, linguísticas teóricas, semânticas formais, matemática lógica, entre outras áreas.

Análise sintática é o processo de reconhecer uma elocução (cadeia em linguagem natural) quebrando-a em um conjunto de símbolos e analizando cada um com a gramática da linguagem. A maioria das linguagens têm os significados de suas elocuções estruturados de acordo com a sintace — uma prática conhecida como semântica composicional. Como resultado, o primeiro passo para descrever o significado de uma elocução em ema linguagem é quebrá-la parte por parte, e olhar a sua forma analisada (conhecida como árvore de análise em ciência da computação, e como estrutura profunda em gramática gerativa).

Exemplo introdutório

Uma gramática consiste principalmente de um conjunto de regras para cadeias de transformação. (Se ele apenas consiste dessas regras, ele seria um sistema semi-Thue). Para gerar uma cadeia na linguagem, começa-se com uma cadeia que consiste em apenas um símbolo símbolo inicial. As regras de produção são, então, aplicadas em qualquer ordem, até que uma cadeia que não contnha nem o símbolo inicial, nem os designados símbolos não-terminais, seja produzida. A linguagem formada pela gramática consiste de 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 língua. Se existem várias maneiras de gerar a mesma sequência única, a gramática é chamada de ambígua. Por exemplo, assumimos que o alfabeto consiste de um a e um b, o símbolo inicial é S, e temos as seguintes regras de produção:

1. $S \rightarrow aSb$

2. $S \rightarrow ba$

então começamos com S, e podemos escolher uma regra pra aplicar a ele. Se nós escolhessemos a regra 1, obteríamos a cadeia aSb. Se nós escolhermos a regra 1 outra vez, nó substituímos S por aSb, e obtemos a cadeia aaSbb. Se agora nós escolhermos a regra 2, nós substituímos S por ba e obtemos a cadeia aababb, e terminamos. Nós podemos escrever essa série de escolhas mais sucintamente, usando símbolos: $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb$. A linguagem da gramática é então o conjunto infinito $\left \{a^nbab^n | n \ge 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).

Definição formal

A sintaxe das gramáticas

Na formalização clássica das gramáticas geratriz foi primeiro proposto por Noam Chomsky por volta de 1956, uma gramática G consiste dos seguintes componentes:

• Um conjunto finito N de símbolos não terminais, em que nenhum aparece em cadeias formadas à partir de G.
• Um conjunto finito $\Sigma$ de símbolos terminais que é disjunto de N.
• Um conjunto finito P de regras de produção, com cada regra da forma

$(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}$

em que ${*}$ é o operador estrela de Kleene e $\cup$ denota união de conjuntos. Ou seja, cada regra de produção mapeia de uma cadeia de símbolos para outro, em que a primeira cadeia (a "cabeça" ou "head") contém um número arbitrário de símbolos fornecidos, em que pelo menos um deles é um não-terminal. No caso da segunda cadeia (o "corpo" ou "body") consistir apenas da cadeia vazia – i.e., que ela não contenha símbolos – ela pode ser denotada por uma notação especial (frequentemente $\Lambda$, e ou $\epsilon$) com o intuito de evitar confusão.

• Um símbolo distinto $S \in N$ que é o símbolo inicial.

Elas são muitas vezes chamadas de sistemas de cadeias reeescritos ou de gramática de estrutura de frases na literatura.

A semântica das gramáticas

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

• Dada uma gramática $G = (N, \Sigma, P, S)$, a relação binária $\Rightarrow_G$ (pronunciada como "G deriva em um passo") nas cadeias em $(\Sigma \cup N)^{*}$ é definida por:

$x \Rightarrow_G y \mbox{ sse } \exists u, v, p, q \in (\Sigma \cup N)^*: (x = upv) \wedge (p \rightarrow q \in P) \wedge (y = uqv)$

• A relaçao ${\Rightarrow_G}^*$ (pronunciada como G deriva em zero ou mais passos in zero or more steps) é definida como o feixo reflexivo transitivo de $\Rightarrow_G$
• Uma formula sentencial é um membro de $(\Sigma \cup N)^*$ que pode ser derivado em um número finito de passos à partir do símbolo inicial $S$; ou seja, uma formula sentencial é um membro de $\{ w \in (\Sigma \cup N)^* \mid S {\Rightarrow_G}^* w \}$. Uma formula sentencial que não contém nenhum dos símbolos não terminais (i.e. é um membro de $\Sigma^*$) é chamada de sentença.
• A linguagem de $G$, denotada como $\boldsymbol{L}(G)$, é definida como todas as sentenças que podem ser derivadas em um número finito de passos à partir do símbolo inicial $S$; isto é, o conjunto $\{ w \in \Sigma^* \mid S {\Rightarrow_G}^* w \}$.

Note que a gramática $G = (N, \Sigma, P, S)$ é efetivamente um sistema semi-Thue $(N \cup \Sigma, P)$, reescrevendo cadeias exatamente do mesmo modo; a única diferença é que distinguimos símbolos não-terminais específicos que precisam ser reescritos em regras, e são os únicos que interessam em reescritas à partir do símbolo inicial $S$ para cadeias sem símbolos não-terminais.

Exemplo

Para esses exemplos, linguagens formais são especificadas usando notação de construção de conjuntos.

Considere a gramática $G$ em que $N = \left \{S, B\right \}$, $\Sigma = \left \{a, b, c\right \}$, $S$ é o símbolo inicial, e $P$ consiste das seguintes regras produção:

1. $S \rightarrow aBSc$

2. $S \rightarrow abc$

3. $Ba \rightarrow aB$

4. $Bb \rightarrow bb$

Essa gramática define a linguagem $L(G) = \left \{ a^{n}b^{n}c^{n} | n \ge 1 \right \}$ em que $a^{n}$ denota a cadeia de n consecutivos $a$'s. No entanto, a linguagem é o conjunto de cadeias que consistem de 1 ou mais $a$'s, seguidos pelo mesmo número de $b$'s, seguidos pelo mesmo número de $c$'s.

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

• $\boldsymbol{S} \Rightarrow_2 \boldsymbol{abc}$
• $\boldsymbol{S} \Rightarrow_1 \boldsymbol{aBSc} \Rightarrow_2 aB\boldsymbol{abc}c \Rightarrow_3 a\boldsymbol{aB}bcc \Rightarrow_4 aa\boldsymbol{bb}cc$
• $\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$$\Rightarrow_3 aa\boldsymbol{aB}Bbccc \Rightarrow_4 aaaB\boldsymbol{bb}ccc \Rightarrow_4 aaa\boldsymbol{bb}bccc$

(Note a notação: $P \Rightarrow_i Q$ lê-se "cadeia P gera cadeia Q por meio da produção i", e a parte gerada é cada vez indicada em negrito)

Gramáticas analíticas

Visto que existem uma vasto volume de algoritmos de análise sintática, a maioria desses algoritmos assumem que a linguagem a ser analisada é inicialmente descrita em meios de uma gramática formal gerativa, e o objetivo é transformar essa gramática gerativa em um verificador que funcione. Falando mais estritamente, uma gramática gerativa, de modo algum, corresponde ao algoritmo usado para analizar a linguagem, e vários algoritmos têm diferentes restrições na forma em que as regras de produção são consideradas bem-formadas.

Uma abordagem alternativa é formalizar a linguagem em termos de uma gramática analítica em primeiro lugar, que corresponde mais especificamente à estrutura e semântica de um verificador para uma linguagem. Exemplos de formalismos de gramáticas analíticas incluem os seguintes:

• A Linguagem de Máquina implementa diretamente gramáticas analíticas irrestritas, Substituição de regras são usadas para transformar uma entrada para produzir saídas e comportamentos. O sistema pode produzir também o diagrama de Im 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 (LATD): um formalismo de gramática analítica altamente minimalista desenvolvido recentemente nos anos 70 para estudar o comportamento dos verificadores top-down.
• Gramática Elo: uma forma de gramática analítica desenvolvida para as linguísticas, que derivam a estrutura sintática examinando os relacionamentos posicionais entre dois pares de palavras.
• Gramáticas de análise de expressões (GAEs): são uma generalização mais recente das LATD desenvolvidas em volta da prática da expressividade precisando das linguagens de programação e escritores de compiladores.

Veja também

• Árvore sintática abstrata
• Gramática ambígua
• Formalismo de Backus-Naur
• Árvore sintática concreta
• Framework de gramática
• Lojban
• Fórmula bem-formada
• Hierarquia de Chomsky

Links externos

• Yearly Formal Grammar conference