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 analisando 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 sintaxe — 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).
Índice |
Exemplo introdutório [editar]
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 continha 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.

- 2.

então começamos com S, e podemos escolher uma regra pra aplicar a ele. Se nós escolhêssemos 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:
. A linguagem da gramática é então o conjunto infinito
, em que ak é 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 [editar]
A sintaxe das gramáticas [editar]
Na formalização clássica das gramáticas geratriz foi primeiro proposto por Noam Chomsky por volta de 1956,1 2 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 a partir de G;
- um conjunto finito
de símbolos terminais que é disjunto de N; - um conjunto finito P de regras de produção, com cada regra da forma
-
- em que
é o operador estrela de Kleene e
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
, e ou
) com o intuito de evitar confusão;
- um símbolo distinto
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.3 4
A semântica das gramáticas [editar]
A operação de uma gramática pode ser definida em termos de relações em cadeias:
- dada uma gramática
, a relação binária
(pronunciada como "G deriva em um passo") nas cadeias em
é definida por:

- a relaçao
(pronunciada como G deriva em zero ou mais passos in zero or more steps) é definida como o feixo reflexivo transitivo de 
- uma formula sentencial é um membro de
que pode ser derivado em um número finito de passos a partir do símbolo inicial
; ou seja, uma formula sentencial é um membro de
. Uma formula sentencial que não contém nenhum dos símbolos não terminais (i.e. é um membro de
) é chamada de sentença.5 - a linguagem de
, denotada como
, é definida como todas as sentenças que podem ser derivadas em um número finito de passos a partir do símbolo inicial
; isto é, o conjunto
.
Note que a gramática
é efetivamente um sistema semi-Thue
, 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 a partir do símbolo inicial
para cadeias sem símbolos não-terminais.
Exemplo [editar]
Para esses exemplos, linguagens formais são especificadas usando notação de construção de conjuntos.
Considere a gramática
em que
,
,
é o símbolo inicial, e
consiste das seguintes regras produção:
- 1.

- 2.

- 3.

- 4.

Essa gramática define a linguagem
em que
denota a cadeia de n consecutivos
's. No entanto, a linguagem é o conjunto de cadeias que consistem de 1 ou mais
's, seguidos pelo mesmo número de
's, seguidos pelo mesmo número de
's.
Alguns exemplos de derivação de cadeias em
são:
- (Note a notação:
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 [editar]
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 analisar 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ções 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;6
- 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;7 8
- 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.9
Ver também [editar]
Referências
- ↑ Chomsky, Noam. (1956). "Three Models for the Description of Language". IRE Transactions on Information Theory 2 (2): 113–123. DOI:10.1109/TIT.1956.1056813.
- ↑ Chomsky, Noam. Syntactic Structures. The Hague: Mouton, 1957.
- ↑ Ginsburg, Seymour. Algebraic and automata theoretic properties of formal languages. [S.l.]: North-Holland, 1975. 8–9 p. ISBN 0720425069
- ↑ Harrison, Michael A.. Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company, 1978. 13 p. ISBN 0201029553
- ↑ Sentential Forms, Context-Free Grammars, David Matuszek
- ↑ Birman, Alexander, The TMG Recognition Schema, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.
- ↑ Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.
- ↑ Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Third International Workshop on Parsing Technologies, 1993.
- ↑ Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.
Ligações externas [editar]
| Teoria de autômatos: linguagem formal e gramática formal | |||
|---|---|---|---|
| Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
| Tipo-0 | Irrestrita | Recursivamente enumerável | Máquina de Turing |
| -- | -- | Recursiva | Máquina de Turing que sempre para |
| Tipo-1 | Sensível ao contexto | Sensível ao contexto | Autômato linearmente limitado |
| Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
| Tipo-3 | Regular | Regular | Autômato finito |


de 
é o operador
denota
, e ou
) com o intuito de evitar confusão;
que é o símbolo inicial.
(pronunciada como "G deriva em um passo") nas cadeias em
é definida por:
(pronunciada como G deriva em zero ou mais passos in zero or more steps) é definida como o
que pode ser derivado em um número finito de passos a partir do símbolo inicial
. Uma formula sentencial que não contém nenhum dos símbolos não terminais (i.e. é um membro de
) é chamada de sentença.
, é definida como todas as sentenças que podem ser derivadas em um número finito de passos a partir do símbolo inicial
.







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