Movatterモバイル変換

Gramática formal

Origem: Wikipédia, a enciclopédia livre.

Gramática
Classificação
Comunicação
Fonética
Fonologia
Morfologia
Sintaxe
Semântica
Etimologia
Estilística
Literatura
Tipos
Descritiva
Gerativa
Formal
Funcional
Normativa
Transformacional
Universal
Implícita
Contrastiva
Reflexiva
Histórica
Artigos Relacionados
Gramática
Linguística
Lexicologia
Retórica
Língua

Emteoria das linguagens formais, umagramática formal (algumas vezes simplesmente chamada degramática) é um conjunto deregras de produção decadeias em umalinguagem formal, ou seja, um objeto que permite especificar uma linguagem ou língua. As regras descrevem como formar cadeias ― a partir doalfabeto da linguagem ― que são válidas de acordo com asintaxe da linguagem. Uma gramática não descrevesignificado 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 umlinguagem formal;
descrição formal de parte da gramática de umalinguagem natural.

ATeoria da Linguagem Formal, disciplina que estuda gramáticas e linguagens formais, é um ramo daMatemática Aplicada. Suas aplicações podem ser encontradas naCiê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 umreconhecedor ― 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 comoTeoria 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 emlinguagem 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 comosemâ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" emgramática gerativa).

Exemplo introdutório

[editar |editar código]

Uma gramática consiste, principalmente, de um conjunto de regras para transformação de cadeias. (Se elaapenas consistisse dessas regras, ela seria considerada umsistema semi-Thue). Para gerar uma cadeia na linguagem, começa-se com uma cadeia que consiste em apenas umsímbolo inicial. Asregras de produção são, então, aplicadas em uma ordem qualquer, até que uma cadeia que não contenha nem osímbolo inicial, nem os chamadossí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 deambígua.

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

S\rightarrow aSb

S\rightarrow ba

Então começamos comS, e podemos escolher uma regra para aplicar a ele. Se nós escolhermos a regra 1, obteríamos a cadeiaaSb. Se nós escolhermos a regra 1 outra vez, nós substituiríamos oSdoaSbporaSb, e obteríamos a cadeiaaaSbb. Se agora nós escolhermos a regra 2, nós substituiríamos oS doaaSbb porba e obteríamos a cadeiaaababb,terminando o processo. 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^{n}bab^{n}|n\geq 0\right\}=\left\{ba,abab,aababb,aaababbb,...\right\}$ , em quea^k éa repetidok vezes (en, em particular, representa o número de vezes que a regra de produção 1 foi aplicada).

Definição formal

[editar |editar código]

A Sintaxe das Gramáticas

[editar |editar código]

Na formalização de gramáticas generativas primeiramente proposta porNoam Chomsky nos anos de 1950,^[1]^[2] uma gramáticaG era composta pelos seguintes componentes:

Um conjunto finitoN desímbolos não terminais, que édisjunto das cadeias formadas a partir deG.
Um conjunto finito $\Sigma$ desímbolos terminais que édisjunto deN.
Um conjunto finitoP deregras de produção, cada uma com a forma $(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$ onde ${*}$ é ooperador de Kleene e $\cup$ denota auniã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 dacadeia vazia — ou seja, não contêm símbolos - sendo, às vezes, representada com notações especiais pra evitar confusão ( $\Lambda$ ,e ou $\epsilon$ ).

Um símbolo diferenciado $S\in N$ que éo símbolo inicial, também chamado desímbolo sentença.

Uma gramática é formalmente definida como umatupla $(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.^[3]^[4]

A Semântica das Gramáticas

[editar |editar código]

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

Dada uma gramática $G=(N,\Sigma ,P,S)$ , a relação binária $\Rightarrow _{G}$ (lê-seG deriva em um passo) sobre cadeias de $(\Sigma \cup N)^{*}$ é definida por: $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 ${\Rightarrow _{G}}^{*}$ (lê-se G deriva em 0 ou mais passos) é definida como o fecho reflexivo-transitivo de $\Rightarrow _{G}$ .
Uma forma sentencial é um membro de $(\Sigma \cup N)^{*}$ que pode ser derivado, partindo do símbolo inicial $S {\displaystyle S}$ , em um número finito de passos; ou seja, uma forma sentencial é um membro de $\{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 $\Sigma ^{*}$ ) é chamada desentença.
A linguagem de $G {\displaystyle G}$ , denotada como ${\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 $S {\displaystyle S}$ ; ou seja, o conjunto $\{w\in \Sigma ^{*}\mid S{\Rightarrow _{G}}^{*}w\}$ .

Note que a gramática $G=(N,\Sigma ,P,S)$ é efetivamente umsistema semi-Thue $(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 $S {\displaystyle S}$ designado para cadeias sem símbolos não terminais.

Exemplo

[editar |editar código]

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

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

S\rightarrow aBSc

S\rightarrow abc

Ba\rightarrow aB

Bb\rightarrow bb

Essa gramática define a linguagem $L(G)=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}$ onde $a^{n}$ denota uma cadeia formada porn consecutivos $a {\displaystyle a}$ 's. Dessa forma, a linguagem é o conjunto de cadeias que é composta por um ou mais $a {\displaystyle a}$ 's, seguidos pelo mesmo número de $b {\displaystyle b}$ 's, seguidos pelo mesmo número de $c {\displaystyle 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 "A cadeiaP gera a cadeiaQ pela regra de produçãoi ". A parte gerada é, a cada vez, indicada em negrito.)

A Hierarquia de Chomsky

[editar |editar código]

Ver artigo principal:Hierarquia de Chomsky

QuandoNoam Chomsky formalizou as gramáticas generativas pela primeira vez em 1956,^[1] 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ãogramáticas livres de contexto (Tipo 2) egramáticas regulares (Tipo 3). As linguagens que podem ser descritas com tais gramáticas são chamadaslinguagens livres de contexto elinguagens regulares, respectivamente. Apesar de menos poderosas quegramáticas irrestritas (Tipo 0), que podem, na verdade, expressar qualquer linguagem que pode ser aceita por umaMáquina de Turing, esses dois tipos restritos de gramática são mais frequentemente usados porque analisadores para eles podem ser eficientemente implementados.^[5] Por exemplo, todas linguagens regulares podem ser reconhecidas por umamá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

[editar |editar código]

Umagramá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 delinguagens livre de contexto.

A linguagem $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 olema do bombeamento para linguagens livres de contexto, mas, por exemplo, a linguagem $\left\{a^{n}b^{n}|n\geq 1\right\}$ (pelo menos 1 $a {\displaystyle a}$ seguido pelo mesmo número de $b {\displaystyle b}$ 's) é livre de contexto, pois pode ser definida por uma gramática $G_{2}$ com $N=\left\{S\right\}$ , $\Sigma =\left\{a,b\right\}$ , $S {\displaystyle S}$ símbolo inicial, e as seguintes regras de produção:

S\rightarrow aSb

S\rightarrow ab

Uma linguagem livre de contexto pode ser reconhecida em tempo $O(n^{3})$ (veja:notação Big O) por um algoritmo comoalgoritmo 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 $O(n^{3})$ se a cadeia é membro da linguagem, onde $n {\displaystyle n}$ é o comprimento da cadeia.^[6] Linguagens determinísticas livres de contexto são umsubconjunto de linguagens livres de contexto que podem ser reconhecidas em tempo linear.^[7] Existem vários algoritmos que se focam nesse conjunto de linguagens ou algum subconjunto dele.

Gramáticas regulares

[editar |editar código]

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

$S\rightarrow aA$
$A\rightarrow aA$
$A\rightarrow bB$
$B\rightarrow bB$
$B\rightarrow \epsilon$

Todas as linguagens geradas por gramáticas regulares podem ser reconhecidas em tempo linear por umamáquina de estados finitos. Contudo, na prática, gramáticas regulares são comumente expressas usandoexpressõ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

[editar |editar código]

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.^[8]
Gramáticas de afixo^[9] egramáticas de atributos^[10]^[11] 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

[editar |editar código]

Não se confunda comlinguagem recursiva

Uma gramática recursiva é uma gramática que contém regras de produção que sãorecursivas. Por exemplo, uma gramática para umalinguagem livre de contexto é recursiva à esquerda se existe símbolo não terminalA que pode ser colocado através das regras de produção para produzir uma cadeia comA como o símbolo mais à esquerda.^[12] Todos os tipos de gramática daHierarquia de Chomsky podem ser recursivas.

Gramáticas analíticas

[editar |editar código]

Apesar de haver um enorme estoque de literatura sobrealgoritmos deanálise sintática, a maioria desses algoritmos assume que a linguagem a ser analisada é, inicialmente,descrita por meio de uma gramática formalgenerativa, 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 produzirthe 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 deanalisadores sintáticos top-down.^[13]
Gramática de ligação: uma forma de gramática analítica desenhada para alinguística, que deriva a estrutura sintática através do exame das relações de posicionamento entre pares de palavras.^[14]^[15]
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 umalinguagem de programação e decompiladores.^[16]

Teoria da computação

[editar |editar código]

Teoria de autômatos:linguagem formal egramá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

Referências

↑^a^bChomsky, N. (1 de setembro de 1956).«Three models for the description of language».IRE Transactions on Information Theory.2 (3): 113-124.ISSN 0096-1000.doi:10.1109/TIT.1956.1056813
↑Chomsky, Noam (1957).Syntactic Structures. The Hague:Mouton
↑Ginsburg, Seymour (1975).Algebraic and automata theoretic properties of formal languages. [S.l.]: North-Holland. pp. 8–9.ISBN 0-7204-2506-9
↑Harrison, Michael A. (1978).Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. 13 páginas.ISBN 0-201-02955-3
↑Grune, Dick & Jacobs, Ceriel H.,Parsing Techniques – A Practical Guide, Ellis Horwood, England, 1990.
↑Earley, Jay, "An Efficient Context-Free Parsing Algorithm,"Communications of the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.
↑Knuth, Donald E. (1 de dezembro de 1965).«On the translation of languages from left to right».Information and Control.8 (6): 607-639.doi:10.1016/S0019-9958(65)90426-2
↑Joshi, Aravind K.,et al., "Tree Adjunct Grammars,"Journal of Computer Systems Science, Vol. 10 No. 1, pp. 136-163, 1975.
↑Koster , Cornelis H. A., "Affix Grammars," inALGOL 68 Implementation, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
↑Knuth, Donald E., "Semantics of Context-Free Languages,"Mathematical Systems Theory, Vol. 2 No. 2, pp. 127-145, 1968.
↑Knuth, Donald E., "Semantics of Context-Free Languages (correction),"Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.
↑Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
↑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. (Revised version of above report.)
↑Ford, Bryan,Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.

Ligações externas

[editar |editar código]

Yearly Formal Grammar conference

Obtida de "https://pt.wikipedia.org/w/index.php?title=Gramática_formal&oldid=68575842"

Categorias:

[8]ページ先頭