Gramática formal - Formal grammar

Na teoria da linguagem formal , uma gramática (quando o contexto não é fornecido, geralmente chamada de gramática formal para maior clareza) descreve como formar cadeias de caracteres do alfabeto de uma linguagem que são válidas de acordo com a sintaxe da linguagem . Uma gramática não descreve o significado das strings ou o que pode ser feito com elas em qualquer contexto - apenas sua forma. Uma gramática formal é definida como um conjunto de regras de produção para strings em uma linguagem formal.

A teoria da linguagem formal, a disciplina que estuda linguagens e gramáticas formais, é um ramo da matemática aplicada . Suas aplicações são encontradas em ciência teórica computador , linguística teórica , semântica formal , lógica matemática , e outras áreas.

Uma gramática formal é um conjunto de regras para reescrever strings, junto com um "símbolo de início" a partir do qual a reescrita começa. Portanto, uma gramática é geralmente considerada um gerador de linguagem. No entanto, às vezes também pode ser usado como base para um " reconhecedor " - uma função na computação que determina se uma determinada string pertence ao idioma ou é gramaticalmente incorreta. Para descrever esses reconhecedores, a teoria da linguagem formal usa formalismos separados, conhecidos como teoria dos autômatos . Um dos resultados interessantes da teoria dos autômatos é que não é possível projetar um reconhecedor para certas linguagens formais. Analisar é o processo de reconhecer uma expressão (uma string em línguas naturais) dividindo-a em um conjunto de símbolos e analisando cada um em relação à gramática da língua. A maioria das línguas tem os significados de seus enunciados estruturados de acordo com sua sintaxe - uma prática conhecida como semântica composicional . Como resultado, o primeiro passo para descrever o significado de um enunciado na linguagem é dividi-lo parte por parte e olhar para sua forma analisada (conhecida como sua árvore de análise na ciência da computação e como sua estrutura profunda na gramática gerativa ).

História

O tratado Astadyayi de Pāṇini fornece regras e definições formais de produção para descrever a gramática formal do Sânscrito . Existem diferentes usos de "forma" e "formalismo", que mudaram ao longo do tempo, dependendo dos campos com os quais o autor em questão estava em contato. Uma visão geral histórica do conceito é fornecida em

Exemplo introdutório

Uma gramática consiste principalmente em um conjunto de regras de produção , regras de reescrita para transformar strings. Cada regra especifica a substituição de uma string particular (seu lado esquerdo ) por outra (seu lado direito ). Uma regra pode ser aplicada a cada string que contém seu lado esquerdo e produz uma string na qual uma ocorrência daquele lado esquerdo foi substituída por seu lado direito.

Ao contrário de um sistema semi-Thue , que é totalmente definido por essas regras, uma gramática ainda distingue entre dois tipos de símbolos: símbolos não terminais e terminais ; cada lado esquerdo deve conter pelo menos um símbolo não terminal. Também distingue um símbolo não terminal especial, denominado símbolo inicial .

A linguagem gerada pela gramática é definida como o conjunto de todas as strings sem quaisquer símbolos não terminais que podem ser gerados a partir da string que consiste em um único símbolo inicial pela (possivelmente repetida) aplicação de suas regras de qualquer maneira possível. Se houver maneiras essencialmente diferentes de gerar a mesma string única, a gramática é considerada ambígua .

Nos exemplos seguintes, os símbolos terminais são um e b , e o símbolo inicial é S .

Exemplo 1

Suponha que 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 escolhermos a regra 1, obteremos a string aSb . Se escolhermos a regra 1 novamente, substituiremos S por aSb e obteremos a string aaSbb . Se agora escolhermos a regra 2, substituiremos S por ba e obteremos a string aababb , e pronto. Podemos escrever esta série de escolhas mais rapidamente, usando símbolos: . ${\ displaystyle S \ Rightarrow aSb \ Rightarrow aaSbb \ Rightarrow aababb}$

A linguagem da gramática é o conjunto infinito , onde é repetido vezes (e em particular representa o número de vezes que a regra de produção 1 foi aplicada). Essa gramática é livre de contexto (apenas não-terminais únicos aparecem como lados do lado esquerdo) e não ambígua. ${\ displaystyle \ {a ^ {n} bab ^ {n} \ mid n \ geq 0 \} = \ {ba, abab, aababb, aaababbb, \ dotsc \}}$ ${\ displaystyle a ^ {k}}$ ${\ displaystyle a}$ ${\ displaystyle k}$ ${\ displaystyle n}$

Exemplos 2 e 3

Suponha que as regras sejam estas:

1

{\ displaystyle S \ rightarrow a}

2

{\ displaystyle S \ rightarrow SS}

3

{\ displaystyle aSa \ rightarrow b}

Essa gramática não é independente de contexto devido à regra 3 e é ambígua devido às várias maneiras pelas quais a regra 2 pode ser usada para gerar sequências de s. ${\ displaystyle S}$

No entanto, a linguagem que ele gera é simplesmente o conjunto de todas as strings não vazias que consistem em se / ou s. Isso é fácil de ver: para gerar um a partir de um , use a regra 2 duas vezes para gerar , a seguir a regra 1 duas vezes e a regra 3 uma vez para produzir . Isso significa que podemos gerar sequências arbitrárias não vazias de se substituir cada uma delas por ou como quisermos. ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle S}$ ${\ displaystyle SSS}$ ${\ displaystyle b}$ ${\ displaystyle S}$ ${\ displaystyle a}$ ${\ displaystyle b}$

Essa mesma linguagem pode, alternativamente, ser gerada por uma gramática livre de contexto e não ambígua; por exemplo, a gramática regular com regras

1

{\ displaystyle S \ rightarrow aS}

2

{\ displaystyle S \ rightarrow bS}

3

{\ displaystyle S \ rightarrow a}

4

{\ displaystyle S \ rightarrow b}

Definição formal

A sintaxe das gramáticas

Na formalização clássica de gramáticas generativas proposta pela primeira vez por Noam Chomsky na década de 1950, uma gramática G consiste nos seguintes componentes:

Um conjunto finito N de símbolos não-terminais , que é separado com as cordas formadas a partir de L .
Um conjunto finito de símbolos terminais que é separado a partir de N . ${\ displaystyle \ Sigma}$
Um conjunto finito P de regras de produção , cada regra da forma

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

onde é o operador estrela Kleene e denota a união do conjunto . Ou seja, cada regra de produção mapeia de uma sequência de símbolos para outra, onde a primeira sequência (a "cabeça") contém um número arbitrário de símbolos, desde que pelo menos um deles seja um não terminal. No caso em que a segunda string (o "corpo") consiste apenas na string vazia - isto é, se não contém nenhum símbolo - ela pode ser denotada com uma notação especial (freqüentemente , e ou ) para evitar confusão.

{\ displaystyle {*}}

{\ displaystyle \ cup}

{\ displaystyle \ Lambda}

{\ displaystyle \ epsilon}

Um símbolo distinto que é o símbolo de início , também chamado de símbolo de frase . ${\ displaystyle S \ in N}$

Uma gramática é formalmente definida como tupla . Essa gramática formal é freqüentemente chamada de sistema de reescrita ou de gramática de estrutura de frase na literatura. ${\ displaystyle (N, \ Sigma, P, S)}$

Algumas construções matemáticas sobre gramáticas formais

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

Dada uma gramática , a relação binária (pronunciada como "G deriva em uma etapa") nas strings em é definida por: ${\ displaystyle G = (N, \ Sigma, P, S)}$ ${\ displaystyle {\ underset {G} {\ Rightarrow}}}$ ${\ displaystyle (\ Sigma \ cup N) ^ {*}}$
${\ displaystyle x {\ underset {G} {\ Rightarrow}} y \ iff \ existe u, v, p, q \ in (\ Sigma \ cup N) ^ {*} :( x = upv) \ wedge (p \ rightarrow q \ in P) \ wedge (y = uqv)}$
a relação (pronunciada como G deriva em zero ou mais etapas ) é definida como o fechamento transitivo reflexivo de ${\ displaystyle {\ overset {*} {\ underset {G} {\ Rightarrow}}}}$ ${\ displaystyle {\ underset {G} {\ Rightarrow}}}$
uma forma sentencial é um membro da que pode ser derivada em um número finito de etapas a partir do símbolo inicial ; ou seja, uma forma sentencial é membro de . Uma forma sentencial que não contém símbolos não terminais (isto é, é membro de ) é chamada de frase . ${\ displaystyle (\ Sigma \ cup N) ^ {*}}$ ${\ displaystyle S}$ ${\ displaystyle \ left \ {w \ in (\ Sigma \ cup N) ^ {*} \ mid S {\ overset {*} {\ underset {G} {\ Rightarrow}}} w \ right \}}$ ${\ displaystyle \ Sigma ^ {*}}$
a linguagem de , denotada como , é definida como o conjunto de sentenças construídas por . ${\ displaystyle G}$ ${\ displaystyle {\ boldsymbol {L}} (G)}$ ${\ displaystyle G}$

Observe que a gramática é efetivamente o sistema semi-Thue , reescrevendo strings exatamente da mesma maneira; a única diferença é que distinguimos símbolos não terminais específicos , que devem ser reescritos em regras de reescrita, e só estamos interessados em reescrever a partir do símbolo inicial designado para strings sem símbolos não terminais. ${\ displaystyle G = (N, \ Sigma, P, S)}$ ${\ displaystyle (N \ cup \ Sigma, P)}$ ${\ displaystyle S}$

Exemplo

Para esses exemplos, as linguagens formais são especificadas usando a notação set-builder .

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

1

{\ displaystyle S \ rightarrow aBSc}

2

{\ displaystyle S \ rightarrow abc}

3

{\ displaystyle Ba \ rightarrow aB}

4

{\ displaystyle Bb \ rightarrow bb}

Esta gramática define o idioma onde denota uma string de n consecutivos . Assim, o idioma é o conjunto de strings que consistem em 1 ou mais 's, seguido pelo mesmo número de ' s, seguido pelo mesmo número de 's. ${\ displaystyle L (G) = \ left \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ geq 1 \ right \}}$ ${\ displaystyle a ^ {n}}$ ${\ displaystyle a}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle c}$

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

${\ displaystyle {\ boldsymbol {S}} {\ underset {2} {\ Rightarrow}} {\ boldsymbol {abc}}}$
${\ displaystyle {\ begin {align} {\ boldsymbol {S}} & {\ underset {1} {\ Rightarrow}} {\ boldsymbol {aBSc}} \\ & {\ underset {2} {\ Rightarrow}} aB {\ boldsymbol {abc}} c \\ & {\ underset {3} {\ Rightarrow}} a {\ boldsymbol {aB}} bcc \\ & {\ underset {4} {\ Rightarrow}} aa {\ boldsymbol { bb}} cc \ end {alinhado}}}$
${\ displaystyle {\ begin {align} {\ boldsymbol {S}} & {\ underset {1} {\ Rightarrow}} {\ boldsymbol {aBSc}} {\ underset {1} {\ Rightarrow}} aB {\ boldsymbol {aBSc}} c \\ & {\ underset {2} {\ Rightarrow}} aBaB {\ boldsymbol {abc}} cc \\ & {\ underset {3} {\ Rightarrow}} a {\ boldsymbol {aB}} Babccc {\ underset {3} {\ Rightarrow}} aaB {\ boldsymbol {aB}} bccc {\ underset {3} {\ Rightarrow}} aa {\ boldsymbol {aB}} Bbccc \\ & {\ underset {4} {\ Rightarrow}} aaaB {\ boldsymbol {bb}} ccc {\ underset {4} {\ Rightarrow}} aaa {\ boldsymbol {bb}} bccc \ end {alinhado}}}$

(Nota sobre a notação: lê-se "String

P

gera string

Q

por meio da produção

i

", e a parte gerada é sempre indicada em negrito.)

{\ displaystyle P {\ underset {i} {\ Rightarrow}} Q}

A hierarquia de Chomsky

Quando Noam Chomsky formalizou as gramáticas gerativas em 1956, ele as classificou em tipos agora conhecidos como hierarquia de Chomsky . A diferença entre esses tipos é que eles têm regras de produção cada vez mais rígidas e podem, portanto, expressar menos linguagens formais. Dois tipos importantes são gramáticas livres de contexto (Tipo 2) e gramáticas regulares (Tipo 3). As línguas que podem ser descritos com tal gramática um são chamados linguagens livres de contexto e linguagens regulares , respectivamente. Embora muito menos poderosas do que as gramáticas irrestritas (Tipo 0), que podem de fato expressar qualquer linguagem que possa ser aceita por uma máquina de Turing , esses dois tipos restritos de gramáticas são usados com mais frequência porque os analisadores para eles podem ser implementados com eficiência. Por exemplo, todas as linguagens regulares podem ser reconhecidas por uma máquina de estado finito , e para subconjuntos úteis de gramáticas livres de contexto, existem algoritmos bem conhecidos para gerar analisadores LL eficientes e analisadores LR para reconhecer as linguagens correspondentes que essas gramáticas geram.

Gramáticas livres de contexto

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

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

1

{\ displaystyle S \ rightarrow aSb}

2

{\ displaystyle S \ rightarrow ab}

Uma linguagem livre de contexto pode ser reconhecida no tempo ( consulte a notação Big O ) por um algoritmo como o reconhecedor de Earley . Ou seja, para cada linguagem livre de contexto, pode ser construída uma máquina que recebe uma string como entrada e determina a tempo se a string é um membro da linguagem, onde é o comprimento da string. Linguagens livres de contexto determinísticas são um subconjunto de linguagens livres de contexto que podem ser reconhecidas em tempo linear. Existem vários algoritmos que têm como alvo esse conjunto de idiomas ou algum subconjunto dele. ${\ displaystyle O (n ^ {3})}$ ${\ displaystyle O (n ^ {3})}$ ${\ displaystyle n}$

Gramáticas regulares

Em gramáticas regulares , o lado esquerdo é novamente apenas um único símbolo não terminal, mas agora o lado direito também é restrito. O lado direito pode ser a string vazia, ou um único símbolo de terminal, ou um único símbolo de terminal seguido por um símbolo não terminal, mas nada mais. (Às vezes, uma definição mais ampla é usada: pode-se permitir strings mais longas de terminais ou não-terminais únicos sem nada mais, tornando as linguagens mais fáceis de denotar, embora ainda definindo a mesma classe de linguagens.

O idioma definido acima não é regular, mas a linguagem (pelo menos 1 seguido por pelo menos 1 , onde os números podem ser diferentes) é, como ele pode ser definido pela gramática com , , o símbolo de início, e as seguintes regras de produção : ${\ displaystyle \ left \ {a ^ {n} b ^ {n} \ mid n \ geq 1 \ right \}}$ ${\ displaystyle \ left \ {a ^ {n} b ^ {m} \ mid m, n \ geq 1 \ right \}}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle G_ {3}}$ ${\ displaystyle N = \ left \ {S, A, B \ right \}}$ ${\ displaystyle \ Sigma = \ left \ {a, b \ right \}}$ ${\ displaystyle S}$

${\ displaystyle S \ rightarrow aA}$
${\ displaystyle A \ rightarrow aA}$
${\ displaystyle A \ rightarrow bB}$
${\ displaystyle B \ rightarrow bB}$
${\ displaystyle B \ rightarrow \ epsilon}$

Todas as linguagens geradas por uma gramática regular podem ser reconhecidas no tempo por uma máquina de estados finitos. Embora, na prática, as gramáticas regulares sejam comumente expressas usando expressões regulares , algumas formas de expressão regular usadas na prática não geram estritamente as linguagens regulares e não mostram desempenho de reconhecimento linear devido a esses desvios. ${\ displaystyle O (n)}$

Outras formas de gramáticas generativas

Muitas extensões e variações da hierarquia original de gramáticas formais de Chomsky foram desenvolvidas, tanto por linguistas quanto por cientistas da computação, geralmente para aumentar seu poder expressivo ou para torná-las mais fáceis de analisar ou interpretar. Algumas formas de gramáticas desenvolvidas incluem:

Gramáticas contíguas à árvore aumentam a expressividade das gramáticas generativas convencionais, permitindo que regras de reescrita operem em árvores de análise em vez de apenas strings.
Gramáticas afixadas e gramáticas de atributos permitem que regras de reescrita sejam aumentadas com atributos e operações semânticas, úteis tanto para aumentar a expressividade da gramática quanto para construir ferramentas práticas de tradução de idiomas.

Gramáticas recursivas

Uma gramática recursiva é uma gramática que contém regras de produção recursivas . Por exemplo, uma gramática para uma linguagem livre de contexto é recursiva à esquerda se houver um símbolo não terminal A que pode ser submetido às regras de produção para produzir uma string com A como o símbolo mais à esquerda. Um exemplo de gramática recursiva é uma cláusula dentro de uma frase separada por duas vírgulas. Todos os tipos de gramáticas na hierarquia Okoye podem ser recursivas.

Gramáticas analíticas

Embora não haja um corpo enorme de literatura sobre algoritmos de análise , a maioria destes algoritmos assumir que o idioma a ser analisado é inicialmente descrito por meio de um gerador gramática formal, e que o objetivo é transformar essa gramática gerativa em um analisador de trabalho. Estritamente falando, uma gramática generativa não corresponde de forma alguma ao algoritmo usado para analisar uma linguagem, e vários algoritmos têm diferentes restrições na 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 em primeiro lugar, o que corresponde mais diretamente à estrutura e semântica de um analisador para a linguagem. Exemplos de formalismos de gramática analítica incluem o seguinte:

The Language Machine implementa diretamente gramáticas analíticas irrestritas. As regras de substituição são usadas para transformar uma entrada para produzir saídas e comportamento. O sistema também pode produzir o diagrama de filme , que mostra o que acontece quando as regras de uma gramática analítica irrestrita estão sendo aplicadas.
Linguagem de análise sintática de cima para baixo (TDPL): um formalismo de gramática analítica altamente minimalista desenvolvido no início dos anos 1970 para estudar o comportamento de analisadores de cima para baixo .
Gramáticas de ligação : uma forma de gramática analítica projetada para linguística , que deriva a estrutura sintática examinando as relações posicionais entre pares de palavras.
Parsing expression grammars (PEGs): uma generalização mais recente de TDPL projetada em torno das necessidades práticas de expressividade de linguagem de programação e escritores de compiladores .

Languages

In other projects