O que significa "livre de contexto" no termo "gramática livre de contexto"?

Dada a quantidade de material que tenta explicar o que é uma gramática livre de contexto (CFG), achei surpreendente que muito poucos (na minha amostra, menos de 1 em 20) dê uma explicação sobre por que essas gramáticas são chamadas de "contexto - livre". E, na minha opinião, ninguém consegue fazê-lo.

Minha pergunta é: por que as gramáticas sem contexto são chamadas sem contexto? O que é "o contexto"? Tive a intuição de que o contexto poderia ser outras construções de linguagem em torno da construção atualmente analisada, mas esse parece não ser o caso. Alguém poderia fornecer uma explicação precisa?

Isso significa que todas as suas regras de produção têm um único não terminal no lado esquerdo.

Por exemplo, esta gramática que reconhece cadeias de parênteses correspondentes ("()", "() ()", "(()) ()", ...) é livre de contexto:

S → SS
S → (S)
S → ()

O lado esquerdo de todas as regras consiste em um único não terminal (nesse caso, é sempre S, mas pode haver mais).

Agora considere esta outra gramática que reconhece seqüências de caracteres da forma {a ^ nb ^ nc ^ n: n> = 1} (por exemplo, "abc", "aabbcc", "aaabbbccc"):

S  → abc
S  → aSBc
cB → WB
WB → WX
WX → BX
BX → Bc
bB → bb

Se o não terminal Bfor precedido pelo caractere terminal / literal c, você reescreverá esse termo para, WBmas se for precedido por b, expandirá para bb. Provavelmente é a isso que se refere a sensibilidade ao contexto das gramáticas sensíveis ao contexto.

Uma linguagem livre de contexto pode ser reconhecida como um autômato push-down . Enquanto uma máquina de estados finitos não utiliza armazenamento auxiliar, ou seja, sua decisão é baseada apenas em seu estado e entrada atuais, um autômato push-down também tem uma pilha à sua disposição e pode espiar no topo da pilha para tomar decisões.

Para ver isso em ação, você pode analisar parênteses aninhados movendo da esquerda para a direita e empurrando os parênteses esquerdos para uma pilha cada vez que encontrar um, e aparecendo cada vez que encontrar parênteses à direita. Se você nunca tentar sair de uma pilha vazia e a pilha estiver vazia no final da sequência, a sequência será válida.

Para uma linguagem sensível ao contexto, um PDA não é suficiente. Você precisará de um autômato de limite linear que é como uma máquina de Turing cuja fita não é ilimitada (embora a quantidade de fita disponível seja proporcional à entrada). Observe que isso descreve os computadores muito bem - gostamos de pensar neles como Máquinas de Turing, mas no mundo real você não pode obter arbitrariamente mais RAM no meio do programa. Se não for óbvio para você como um LBA é mais poderoso que um PDA, um LBA pode emular um PDA usando parte de sua fita como uma pilha, mas também pode optar por usá-la de outras maneiras.

(Se você está se perguntando o que uma Máquina de Estados Finitos pode reconhecer, a resposta são expressões regulares. Mas não as expressões regulares em esteróides com grupos de captura e olhar para trás / olhar para frente que você vê nas linguagens de programação; quero dizer as que você pode criar com operadores como [abc], |, *, +, e ?. Você pode ver que abbbzjogos regex ab*zapenas por manter a sua posição atual na seqüência e regex, nenhuma pilha necessário.)

As outras respostas são bastante longas, mesmo que precisas e corretas. Esta é a versão curta.

Se você possui uma sequência de caracteres (terminais e não terminais) e deseja substituir um não terminal na sequência, uma gramática sem contexto permite que você faça isso independentemente dos caracteres que cercam o não terminal.

Considere as seguintes regras (minúsculas são terminais, maiúsculas são não terminais):

A -> a
AB -> a

Na primeira regra, você pode substituir um A independentemente do que aparece ao seu redor (contexto). Na segunda regra, você não pode substituir, a Amenos que seja seguido por B. Embora os dois não-terminais sejam substituídos nesse caso, o ponto importante é que os não-terminais que cercam o Aassunto. Não se pode substituir BApor a, ou Bpor a: apenas um Aseguido de a Bporque a ordem, o contexto dos não-terminais é importante. Isso significa o contexto de assuntos não-terminais na segunda regra, tornando-o sensível ao contexto, enquanto a primeira regra é livre de contexto.

Para entender a distinção ea terminologia melhor, é uma boa idéia para contrastar uma linguagem livre de contexto como um ⁿ b ⁿ com um sensível ao contexto como um ⁿ b ⁿ c ⁿ . (Notação: a, bec são literais aqui e o expoente n significa repetir o literal n vezes, n > 0, digamos.) Por exemplo, aabbcou aabbbccnão está no último idioma, ao contrário aabbcc.

Um aceitador da linguagem livre de contexto a ⁿ b ⁿ pode contratar um par ae bindependentemente do que está ao seu redor (ou seja, independentemente do contexto em que ab aparece) e funcionará corretamente, aceitando apenas cadeias de caracteres na linguagem e rejeitando qualquer outra coisa, ou seja, a gramática é S -> aSb | ab. Observe que não há terminais no lado esquerdo da (s) produção (ões) . (Existem duas regras de produção, mas estamos apenas escrevendo-as de forma compacta.) O aceitador pode basicamente tomar uma decisão local, sem contexto.

Por outro lado, você não pode fazer algo assim para a linguagem sensível ao contexto a ⁿ b ⁿ c ⁿ , porque, para este último, você deve se lembrar de alguma forma do contexto em que estava, ou seja, quantas contrações de ab você faz para combiná-las com contrações de bc. Uma gramática para o último idioma é

S -> abc | aBSc
Ba -> aB
Bb -> bb

Observe que você tem terminais e não terminais à esquerda nas duas últimas regras. Os terminais à esquerda são o contexto no qual os não terminais podem ser expandidos.

Nota de rodapé sobre terminologia "contrato" x "expandir" etc .: embora as gramáticas formais sejam [formalmente, hah] generativas, a maneira como elas são realmente implementadas nos analisadores é realmente reducionista, ou seja, você entra em contato com tudo para um não terminal, basicamente aplicar as regras "ao contrário", e é por isso que até a primeira gramática fornecida acima não é prática em um programa (isso daria o famoso conflito de redução de turnos porque você não pode decidir qual regra aplicar), mas as duas acima gramáticas são suficientes para ilustrar a distinção entre livre de contexto e sensível a contexto. A questão da ambiguidade nas gramáticas sem contexto é bastante complicada, e não é realmente o tópico dessa pergunta, então não vou dizer mais aqui, principalmente porque a Wikipedia tem um artigo decente sobre isso.. Por outro lado, seus artigos sobre linguagem livre de contexto e especialmente sobre linguagem sensível ao contexto são! @ # $ @! # $, Especialmente se você é novo no tópico ... Acho que isso está mais na minha lista de tarefas.

As respostas acima dão uma boa definição do que é. Vamos ver se eu posso colocar isso com minhas próprias palavras, para que você tenha 23 explicações em vez de 20. Todo o objetivo de uma gramática, qualquer gramática, é descobrir se uma sentença específica é uma sentença no idioma especificado. No entanto, o que realmente usamos gramáticas e análises é descobrir o que a frase significa. É como o velho diagrama de uma frase que você pode ou não ter feito na aula de inglês na escola. Uma frase é feita de uma parte do sujeito e uma parte do predicado, uma parte do sujeito tem um substantivo e talvez alguns adjetivos, uma parte do predicado tem um verbo e talvez um substantivo do objeto, com mais adjetivos, etc.

Se houvesse uma gramática para o inglês (e acho que não existe, não no sentido da ciência da computação), ela teria regras da seguinte forma, denominadas produções.

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun

etc ...

Em seguida, você pode escrever um programa e entregá-lo a qualquer frase, e o programa pode usar a gramática para descobrir qual parte da frase cada palavra é e qual a relação entre elas.

Se em todas as produções houver apenas uma coisa no lado esquerdo, isso significa que, sempre que você vir o lado direito na frase, poderá substituir no lado esquerdo. Por exemplo, sempre que você vê o substantivo adjetivo, pode dizer "Essa é uma parte do sujeito" sem prestar atenção a nada fora dessa frase.

No entanto, o inglês (mesmo a descrição simplificada do inglês que forneci acima) é sensível ao contexto. "Substantivo adjetivo" nem sempre é um SubjectPart, pode ser um NounPhrase em um PredicatePart. Depende do contexto. Vamos expandir um pouco nossa gramática pseudo-inglesa:

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun
PredicatePart -> VerbPhrase ObjectNounPhrase
VerbPhrase ObjectNounPhrase -> VerbPhrase Adjective Noun

Você só pode transformar um "substantivo adjetivo" em um ObjectNounPhrase se ele vier logo após um VerbPhrase.

Basicamente, se você tem uma produção e pode aplicá-la a qualquer momento, não importa o que a rodeia, ela é livre de contexto.

Você sempre pode saber se uma gramática é livre de contexto facilmente. Basta verificar se há mais de um símbolo no lado esquerdo das setas.

Qualquer idioma pode ser descrito por mais de uma gramática. Se alguma gramática de um idioma é livre de contexto, o idioma é livre de contexto. Pode ser comprovado para alguns idiomas que não há gramática livre de contexto. Suponho que possa haver uma gramática livre de contexto para o subconjunto pseudo-inglês simplificado que estou descrevendo acima.

Quanto ao motivo, é necessário um tipo mais simples de programa para analisar uma gramática livre de contexto. Conforme observado nas outras respostas, ele não requer todo o poder de uma máquina de Turing para analisar uma gramática livre de contexto. Um analisador lookahead LR (1) (que é um tipo de máquina de empilhamento) para uma gramática livre de contexto específica pode analisar qualquer sentença nessa gramática no tempo e no espaço linear ao comprimento da sentença. Se a sentença estiver no idioma, o analisador produzirá uma árvore de estrutura identificando o significado de cada símbolo na sentença (ou pelo menos que parte ela desempenha na estrutura). Se a sentença não estiver na gramática, o analisador notará e parará no primeiro símbolo que é impossível reconciliar com a gramática e os símbolos anteriores (no primeiro "erro").

O melhor de tudo é que existem programas que você pode fornecer uma descrição de uma gramática e uma lista de instruções sobre o que fazer com cada parte (de certa forma anexando um "significado" a cada produção) e o programa escreverá o analisador para voce. O programa analisará a sentença, encontrará a estrutura e executará suas instruções em cada parte da estrutura. Esse tipo de programa é chamado de gerador de analisador ou compilador-compilador.

Esse tipo de análise de linguagem foi inventado para análise automática de linguagem natural (como o inglês), mas acontece que isso é mais útil para analisar linguagens de computador. Um designer de linguagem pode escrever uma gramática que captura seu novo idioma, depois executá-lo através do gerador de analisador para obter um programa que analisa seu idioma e traduz, interpreta, compila, executa, etc., se ele quiser.

De fato, na maioria dos casos, você realmente não pode fazer isso. Por exemplo, parênteses balanceados são uma linguagem livre de contexto, mas uma linguagem em que é necessário declarar todas as variáveis ​​antes de usá-las é sensível ao contexto. O analisador faz parte do compilador, mas é necessária lógica adicional para impor esses outros requisitos. O que você precisa fazer é escrever uma gramática que capte o máximo de seu idioma possível, executar isso através de um gerador de analisador e depois escrever um código que imponha o restante dos requisitos (manipulador de tabela de símbolos, etc.).

Geralmente, não usamos gramáticas sensíveis ao contexto porque elas são muito mais mal suportadas. Não sei se existe um equivalente a um gerador de analisador LR (k) para linguagens sensíveis ao contexto. Sim, uma máquina de Turing (ou máquina de ligação linear) pode analisar uma, mas não sei se existe um algoritmo geral para transformar uma gramática sensível ao contexto em um programa para uma máquina de Turing, no sentido de que uma LR (1 ) cria tabelas de análise para uma máquina de empilhamento. Meu palpite é que as tabelas subjacentes ao analisador seriam exponencialmente maiores. De qualquer forma, os estudantes de CS (como eu, antigamente) são geralmente ensinados gramáticas sem contexto e geradores de analisadores LR (1), como o YACC.

Gramáticas sem contexto não consideram nenhum contexto para regras de produção. Contexto são terminais ou não terminais.

Portanto: as gramáticas sem contexto têm apenas um não terminal no lado esquerdo das regras de produção.