Costumo ouvir afirmações de que C ++ é uma linguagem sensível ao contexto. Veja o seguinte exemplo:
a b(c);
Essa é uma definição de variável ou uma declaração de função? Isso depende do significado do símbolo c
. Se c
é uma variável , a b(c);
define uma variável com o nome b
do tipo a
. É inicializado diretamente com c
. Mas se c
for um tipo , a b(c);
declara uma função chamada b
que recebe c
ae retorna uma a
.
Se você procurar a definição de linguagens livres de contexto, basicamente lhe dirá que todas as regras gramaticais devem ter lados esquerdos que consistem em exatamente um símbolo não terminal. Gramáticas sensíveis ao contexto, por outro lado, permitem seqüências arbitrárias de símbolos terminais e não terminais no lado esquerdo.
Navegando pelo Apêndice A de "A linguagem de programação C ++", não consegui encontrar uma única regra gramatical que contenha mais nada além de um único símbolo não terminal no lado esquerdo. Isso implicaria que C ++ é livre de contexto. (Obviamente, toda linguagem livre de contexto também é sensível ao contexto, no sentido de que as linguagens livres de contexto formam um subconjunto das linguagens sensíveis ao contexto, mas esse não é o ponto.)
Então, o C ++ é livre de contexto ou sensível ao contexto?
fonte
Respostas:
Abaixo está minha demonstração favorita (atual) de por que a análise de C ++ é (provavelmente) concluída em Turing , pois mostra um programa sintaticamente correto se e somente se um número inteiro for primo.
Portanto, afirmo que o C ++ não é isento de contexto nem sensível ao contexto .
Se você permitir seqüências arbitrárias de símbolos nos dois lados de qualquer produção, produza uma gramática Tipo 0 ("irrestrita") na hierarquia de Chomsky , que é mais poderosa que uma gramática sensível ao contexto; gramáticas irrestritas são completas de Turing. Uma gramática sensível ao contexto (Tipo 1) permite vários símbolos de contexto no lado esquerdo de uma produção, mas o mesmo contexto deve aparecer no lado direito da produção (daí o nome "sensível ao contexto"). [1] Gramáticas sensíveis ao contexto são equivalentes a máquinas de Turing de limite linear .
No programa de exemplo, o cálculo principal pode ser realizado por uma máquina de Turing de limite linear, portanto não prova a equivalência de Turing, mas a parte importante é que o analisador precisa executar o cálculo para realizar a análise sintática. Poderia ter sido qualquer computação expressável como uma instanciação de modelo e há todos os motivos para acreditar que a instanciação de modelo C ++ é Turing-complete. Veja, por exemplo, o artigo de Todd L. Veldhuizen em 2003 .
Independentemente disso, o C ++ pode ser analisado por um computador, portanto certamente pode ser analisado por uma máquina de Turing. Conseqüentemente, uma gramática irrestrita poderia reconhecê-la. Escrever essa gramática seria impraticável, e é por isso que o padrão não tenta fazê-lo. (Ver abaixo.)
O problema com a "ambiguidade" de certas expressões é principalmente um arenque vermelho. Para começar, a ambiguidade é um recurso de uma gramática específica, não de um idioma. Mesmo que se prove que um idioma não possui gramáticas inequívocas, se pode ser reconhecido por uma gramática livre de contexto, é livre de contexto. Da mesma forma, se não puder ser reconhecido por uma gramática livre de contexto, mas puder ser reconhecido por uma gramática sensível ao contexto, é sensível ao contexto. A ambiguidade não é relevante.
Mas, de qualquer forma, como a linha 21 (ou seja
auto b = foo<IsPrime<234799>>::typen<1>();
) no programa abaixo, as expressões não são ambíguas; eles são simplesmente analisados de maneira diferente, dependendo do contexto. Na expressão mais simples do problema, a categoria sintática de certos identificadores depende de como eles foram declarados (tipos e funções, por exemplo), o que significa que a linguagem formal precisaria reconhecer o fato de que duas seqüências de comprimento arbitrário em o mesmo programa é idêntico (declaração e uso). Isso pode ser modelado pela gramática "copy", que é a gramática que reconhece duas cópias exatas consecutivas da mesma palavra. É fácil provar com o lema de bombeamentoque essa linguagem não é livre de contexto. Uma gramática sensível ao contexto para esse idioma é possível e uma gramática Tipo 0 é fornecida na resposta a esta pergunta: /math/163830/context-sensitive-grammar-for-the- linguagem de cópia .Se alguém tentasse escrever uma gramática sensível ao contexto (ou irrestrita) para analisar o C ++, isso provavelmente preencheria o universo com rabiscos. Escrever uma máquina de Turing para analisar C ++ seria uma tarefa igualmente impossível. Até escrever um programa em C ++ é difícil, e até onde eu sei, nenhum deles foi provado correto. É por isso que o padrão não tenta fornecer uma gramática formal completa e por que escolhe escrever algumas das regras de análise em inglês técnico.
O que parece uma gramática formal no padrão C ++ não é a definição formal completa da sintaxe da linguagem C ++. Nem sequer é a definição formal completa da linguagem após o pré-processamento, que pode ser mais fácil de formalizar. (Porém, essa não seria a linguagem: a linguagem C ++, conforme definida pelo padrão, inclui o pré-processador, e a operação do pré-processador é descrita algoritmicamente, pois seria extremamente difícil de descrever em qualquer formalismo gramatical. É nessa seção. do padrão em que a decomposição lexical é descrita, incluindo as regras em que deve ser aplicada mais de uma vez.)
As várias gramáticas (duas gramáticas sobrepostas para análise lexical, uma que ocorre antes do pré-processamento e a outra, se necessário, posteriormente, além da gramática "sintática") são coletadas no Apêndice A, com esta nota importante (ênfase adicionada):
Finalmente, aqui está o programa prometido. A linha 21 está sintaticamente correta se e somente se o N in
IsPrime<N>
for primo. Caso contrário,typen
é um número inteiro, não um modelo, portanto,typen<1>()
é analisado como(typen<1)>()
sintaticamente incorreto, porque()
não é uma expressão sintaticamente válida.[1] Para colocá-lo mais tecnicamente, toda produção em uma gramática sensível ao contexto deve ter a forma:
αAβ → αγβ
onde
A
é um terminal e nãoα
,β
são possivelmente sequências vazias de símbolos gramaticais eγ
é uma sequência não vazia. (Os símbolos gramaticais podem ser terminais ou não terminais).Isso pode ser lido como
A → γ
apenas no contexto[α, β]
. Em uma gramática livre de contexto (Tipo 2)α
eβ
deve estar vazia.Acontece que você também pode restringir gramáticas com a restrição "monotônica", em que toda produção deve ter a forma:
α → β
onde|α| ≥ |β| > 0
(|α|
significa "o comprimento deα
")É possível provar que o conjunto de idiomas reconhecidos pelas gramáticas monotônicas é exatamente o mesmo que o conjunto de idiomas reconhecidos pelas gramáticas sensíveis ao contexto, e geralmente é mais fácil basear as provas em gramáticas monotônicas. Consequentemente, é bastante comum ver "sensível ao contexto" usado como se quisesse "monotônico".
fonte
0
dentro de()
, por um simples), mas acho que é mais interessante dessa maneira, porque demonstra que você precisa da instanciação do modelo para reconhecer se uma string é um programa C ++ sintaticamente correto. Se os dois ramos forem compilados, eu teria que trabalhar mais para contestar o argumento de que a diferença é "semântica". Curiosamente, embora eu estou muitas vezes desafiados a definir "sintática", ninguém jamais ofereceu uma definição de "semântica" diferente de "coisas que eu não acho que é sintática" :)Primeiro, você observou corretamente que não existem regras sensíveis ao contexto na gramática no final do padrão C ++, de modo que a gramática é livre de contexto.
No entanto, essa gramática não descreve com precisão a linguagem C ++, porque produz programas não C ++, como
ou
A linguagem C ++ definida como "o conjunto de programas C ++ bem formados" não é livre de contexto (é possível mostrar que apenas exigir variáveis a serem declaradas o torna). Dado que você pode escrever teoricamente programas completos de Turing em modelos e criar um programa mal formado com base em seus resultados, isso nem é sensível ao contexto.
Agora, pessoas (ignorantes) (geralmente não teóricas da linguagem, mas designers de analisadores) normalmente usam "sem contexto" em alguns dos seguintes significados
A gramática na parte de trás do padrão não satisfaz essas categorias (ou seja, é ambígua, não LL (k) ...), portanto, a gramática C ++ "não é livre de contexto" para elas. E, de certa forma, eles estão certos de que é muito difícil produzir um analisador de C ++ funcional.
Observe que as propriedades aqui usadas são apenas fracamente conectadas a linguagens livres de contexto - a ambiguidade não tem nada a ver com sensibilidade ao contexto (na verdade, regras sensíveis ao contexto geralmente ajudam a desambiguar produções), as outras duas são meramente subconjuntos de contexto idiomas livres. E a análise de linguagens sem contexto não é um processo linear (embora a análise de linguagens determinísticas seja).
fonte
ambiguity doesn't have anything to do with context-sensitivity
Essa também foi minha intuição, por isso estou feliz em ver alguém (a) concordar e (b) explicá-la onde não podia. Eu acredito que desqualifica todos os argumentos que se baseiama b(c);
e satisfaz parcialmente a pergunta original cuja premissa foi "freqüentemente ouvida" reivindicações de sensibilidade ao contexto devido à ambiguidade ... especialmente quando, para a gramática , na verdade não há ambiguidade, mesmo na MVP.Sim. A expressão a seguir possui uma ordem diferente de operações, dependendo do tipo de contexto resolvido :
Editar: quando a ordem real da operação varia, torna-se incrivelmente difícil usar um compilador "regular" que analise um AST não decorado antes de decorá-lo (propagando informações de tipo). Outras coisas sensíveis ao contexto mencionadas são "bastante fáceis" em comparação com isso (não que a avaliação do modelo seja fácil).
Seguido por:
fonte
Para responder sua pergunta, você precisa distinguir duas perguntas diferentes.
A mera sintaxe de quase todas as linguagens de programação é livre de contexto. Normalmente, é fornecido como uma forma estendida de Backus-Naur ou gramar sem contexto.
No entanto, mesmo que um programa esteja em conformidade com o gramar sem contexto definido pela linguagem de programação, ele não é necessariamente um programa válido . Existem muitas propriedades sem contexto que um programa precisa satisfazer para ser um programa válido. Por exemplo, a propriedade mais simples é o escopo das variáveis.
Para concluir, se o C ++ é ou não livre de contexto depende da pergunta que você faz.
fonte
VARDECL : TYPENAME IDENTIFIER
, mas não pode tê-la, porque não é possível distinguir nomes de tipos de outros identificadores no nível CF. Outro exemplo: no nível CF, você não pode decidir se deve analisara*b
como uma declaração variável (b
do tipo ponteiro paraa
) ou como uma multiplicação.Você pode dar uma olhada no The Design & Evolution of C ++ , de Bjarne Stroustrup. Nele, ele descreve seus problemas ao tentar usar o yacc (ou similar) para analisar uma versão anterior do C ++, e desejando ter usado descida recursiva.
fonte
Sim, o C ++ é sensível ao contexto, muito sensível ao contexto. Você não pode construir a árvore de sintaxe simplesmente analisando o arquivo usando um analisador sem contexto, porque em alguns casos você precisa conhecer o símbolo do conhecimento anterior para decidir (por exemplo, criar uma tabela de símbolos durante a análise).
Primeiro exemplo:
Esta é uma expressão de multiplicação?
OU
Esta declaração de
B
variável é um ponteiro do tipoA
?Se A é uma variável, então é uma expressão, se A é do tipo, é uma declaração de ponteiro.
Segundo exemplo:
Este é um protótipo de função usando um argumento do
bar
tipo?OU
Essa variável
B
de declaração é do tipoA
e chama o construtor de A combar
constante como inicializador?Você precisa saber novamente se
bar
é uma variável ou um tipo da tabela de símbolos.Terceiro exemplo:
Este é o caso ao criar a tabela de símbolos durante a análise não ajuda, porque a declaração de xey vem após a definição da função. Portanto, você precisa examinar primeiro a definição da classe e examinar as definições do método em uma segunda passagem, para dizer que x * y é uma expressão e não uma declaração de ponteiro ou o que seja.
fonte
A B();
é uma declaração de função, mesmo em uma definição de função. Olhar para a maioria de análise irritante ...C ++ é analisado com analisador GLR. Isso significa que, durante a análise do código-fonte, o analisador pode encontrar ambiguidade, mas deve continuar e decidir qual regra gramatical usar mais tarde .
veja também
Por que o C ++ não pode ser analisado com um analisador LR (1)?
Lembre-se de que a gramática livre de contexto não pode descrever TODAS as regras de uma sintaxe da linguagem de programação. Por exemplo, a gramática de atributo é usada para verificar a validade de um tipo de expressão.
Você não pode descrever a regra a seguir com gramática livre de contexto: O lado direito da atribuição deve ser do mesmo tipo do lado esquerdo.
fonte
Sinto que há alguma confusão entre a definição formal de "sensível ao contexto" e o uso informal de "sensível ao contexto". O primeiro tem um significado bem definido. O último é usado para dizer "você precisa do contexto para analisar a entrada".
Isso também é perguntado aqui: Sensibilidade ao contexto vs Ambiguidade .
Aqui está uma gramática livre de contexto:
É ambíguo, portanto, para analisar a entrada "x", você precisa de algum contexto (ou vive com a ambiguidade ou emite "Aviso: E8271 - A entrada é ambígua na linha 115"). Mas certamente não é uma gramática sensível ao contexto.
fonte
Nenhuma linguagem semelhante ao Algol é livre de contexto, porque elas possuem regras que restringem expressões e instruções nas quais os identificadores podem aparecer com base em seu tipo e porque não há limite no número de instruções que podem ocorrer entre a declaração e o uso.
A solução usual é escrever um analisador sem contexto que realmente aceite um superconjunto de programas válidos e coloque as partes sensíveis ao contexto no código "semântico" ad hoc anexado às regras.
O C ++ vai muito além disso, graças ao seu sistema de modelos Turing-complete. Consulte Pergunta sobre estouro de pilha 794015 .
fonte
Verdade :)
J. Stanley Warford. Sistemas de computador . Páginas 341-346.
fonte
Às vezes é pior: o que as pessoas querem dizer quando dizem que C ++ tem "gramática indecidível"?
fonte
É sensível ao contexto, pois
a b(c);
possui duas declarações e análises válidas. Quando você diz "Sec
é um tipo", esse é o contexto, e você descreveu exatamente como o C ++ é sensível a ele. Se você não tivesse esse contexto de "O que éc
?" você não poderia analisar isso sem ambiguidade.Aqui, o contexto é expresso na escolha dos tokens - o analisador lê um identificador como um token de nome de tipo, se nomear um tipo. Essa é a resolução mais simples e evita grande parte da complexidade de ser sensível ao contexto (neste caso).
Editar: é claro que há mais questões de sensibilidade ao contexto, concentrei-me apenas na que você mostrou. Modelos são especialmente desagradáveis para isso.
fonte
a<b<c>>d
, certo? (O seu exemplo é realmente um clássico do C , onde é a única obstrução de ser livre de contexto.)As produções no padrão C ++ são escritas sem contexto, mas como todos sabemos, na verdade, não definimos a linguagem com precisão. Parte do que a maioria das pessoas vê como ambiguidade no idioma atual pode (acredito) ser resolvida sem ambiguidade com uma gramática sensível ao contexto.
Para o exemplo mais óbvio, vamos considerar o mais irritante Parse:
int f(X);
. E seX
é um valor, isso definef
como uma variável que será inicializada comX
. SeX
é um tipo, definef
como uma função que aceita um único parâmetro do tipoX
.Observando isso do ponto de vista gramatical, poderíamos vê-lo assim:
É claro que, para estar totalmente correto, precisaríamos adicionar algumas "coisas" extras para explicar a possibilidade de declarações de outros tipos intervenientes (ou seja, A e B deveriam realmente ser "declarações incluindo a declaração de X como ..." ou algo nessa ordem).
Isso ainda é bastante diferente de um CSG típico (ou pelo menos o que eu me lembro deles). Isso depende da construção de uma tabela de símbolos - a parte que reconhece especificamente
X
como um tipo ou valor, não apenas algum tipo de instrução anterior a isso, mas o tipo correto de instrução para o símbolo / identificador correto.Como tal, eu teria que fazer algumas coisas para ter certeza, mas meu palpite imediato é que isso realmente não se qualifica como CSG, pelo menos como o termo é normalmente usado.
fonte
O caso mais simples da gramática sem contexto envolve a análise de expressões envolvendo modelos.
Isso pode analisar como
Ou
Os dois ASTs só podem ser desambiguados examinando a declaração de 'a' - o primeiro AST se 'a' for um modelo, ou o último se não.
fonte
<
deve ser um colchete, se puder (por exemplo, segue um identificador que nomeia um modelo). O C ++ 11 adicionou o requisito de que>
o primeiro caractere>>
seja interpretado como colchetes próximos se esse uso for plausível. Isso afeta a análise dea<b>c>
ondea
está um modelo, mas não tem efeitoa<b<c>
.a();
(que é umexpr.call
ouexpr.type.conv
)?Os modelos C ++ foram mostrados como Turing Powerful. Embora não seja uma referência formal, aqui está um lugar para procurar a esse respeito:
http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html
Vou arriscar um palpite (tão antigo quanto uma prova folclórica e concisa do CACM mostrando que o ALGOL nos anos 60 não poderia ser reprimido por um CFG) e dizer que o C ++ não pode, portanto, ser corretamente analisado apenas por um CFG. CFGs, em conjunto com vários mecanismos de TP em uma passagem em árvore ou durante eventos de redução - essa é outra história. De um modo geral, devido ao Problema de Interrupção, existe algum programa C ++ que não pode ser mostrado como correto / incorreto, mas que é correto / incorreto.
{PS- Como autor do Meta-S (mencionado por várias pessoas acima) - posso dizer com toda certeza que o Thothic não está extinto, nem o software está disponível gratuitamente. Talvez eu tenha redigido esta versão da minha resposta de forma que não seja excluído ou votado para -3.}
fonte
C ++ não é livre de contexto. Eu aprendi isso há algum tempo na palestra dos compiladores. Uma pesquisa rápida deu esse link, onde a seção "Sintaxe ou semântica" explica por que C e C ++ não são livres de contexto:
Wikipedia Discussão: Gramática livre de contexto
Atenciosamente,
Ovanes
fonte
Obviamente, se você fizer a pergunta literalmente, quase todos os idiomas com identificadores são sensíveis ao contexto.
É necessário saber se um identificador é um nome de tipo (um nome de classe, um nome introduzido por typedef, um parâmetro de modelo de nome de tipo), um nome de modelo ou outro nome para poder corrigir corretamente parte do uso do identificador. Por exemplo:
é um cast se
name
for um nome de tipo e uma chamada de função sename
for um nome de função. Outro caso é a chamada "análise mais irritante", em que não é possível diferenciar a definição de variável e a declaração de função (existe uma regra dizendo que é uma declaração de função).Essa dificuldade introduziu a necessidade
typename
etemplate
com nomes dependentes. O resto do C ++ não é sensível ao contexto, tanto quanto eu sei (ou seja, é possível escrever uma gramática livre de contexto para ele).fonte
O link correto está analisando os mecanismos
Meta-S era propriedade de uma empresa extinta chamada Thothic. Posso enviar uma cópia gratuita do Meta-S para qualquer pessoa interessada e usei-a na pesquisa de análise de rna. Observe que a "gramática do pseudo-nó" incluída nas pastas de exemplos foi escrita por um programador não bioinformático, amador e basicamente não funciona. Minhas gramáticas adotam uma abordagem diferente e funcionam muito bem.
fonte
Um grande problema aqui é que os termos "livre de contexto" e "sensível ao contexto" são um pouco pouco intuitivos na ciência da computação. Para C ++, a sensibilidade ao contexto parece muito com ambiguidade, mas isso não é necessariamente verdade no caso geral.
Em C / ++, uma instrução if é permitida apenas dentro de um corpo de função. Isso parece torná-lo sensível ao contexto, certo? Bem não. Gramáticas sem contexto não precisam da propriedade onde você pode obter alguma linha de código e determinar se é válida. Na verdade, não é isso que significa livre de contexto. É realmente apenas um rótulo que implica vagamente algo meio relacionado ao que parece.
Agora, se uma declaração dentro de um corpo de função for analisada de maneira diferente, dependendo de algo definido fora dos ancestrais gramaticais imediatos (por exemplo, se um identificador descreve um tipo ou variável), como no exemplo
a * b;
caso, é, de fato, sensível ao contexto. Não há ambiguidade real aqui; será analisado como uma declaração de um ponteiro sea
for de um tipo e multiplicação.Ser sensível ao contexto não significa necessariamente "difícil de analisar". C na verdade não é tão difícil porque a infame
a * b;
"ambiguidade" pode ser resolvida com uma tabela de símbolos contendotypedef
s encontrados anteriormente. Ele não requer instâncias arbitrárias de modelos (que foram comprovadas como Turing Complete) para resolver esse caso, como o C ++ ocasionalmente. Na verdade, não é possível escrever um programa em C que não seja compilado em um período finito de tempo, mesmo que tenha a mesma sensibilidade ao contexto que o C ++.O Python (e outras linguagens sensíveis a espaço em branco) também depende do contexto, pois exige que o estado no lexer gere tokens de indentação e dedução, mas isso não dificulta a análise do que uma gramática LL-1 típica. Na verdade, ele usa um gerador de analisador, que é parte do motivo pelo qual o Python possui mensagens de erro de sintaxe não informativas. Também é importante observar aqui que não há "ambiguidade" como o
a * b;
problema no Python, fornecendo um bom exemplo concreto de uma linguagem sensível ao contexto sem gramática "ambígua" (como mencionado no primeiro parágrafo).fonte
Esta resposta diz que C ++ não é livre de contexto ... há uma implicação (não pelo respondente) de que ele não pode ser analisado, e a resposta oferece um exemplo de código difícil que produz um programa C ++ inválido se uma determinada constante não for uma número primo.
Como outros observaram, a pergunta sobre se a linguagem é sensível ao contexto / livre é diferente da mesma pergunta sobre uma gramática específica.
Para deixar a questão da parseabilidade em repouso, ofereço evidências empíricas de que existem gramáticas sem contexto para C ++, que podem ser usadas para produzir um AST para uma análise sem contexto do texto de origem, na verdade, analisando-o com uma GLR existente ferramenta baseada em analisador, dirigida por uma gramática explícita.
Sim, consegue "aceitar demais"; nem tudo o que ele aceita é um programa C ++ válido, e é por isso que é seguido de verificações adicionais (verificações de tipo). E sim, o verificador de tipos pode ter problemas de computabilidade. Na prática, as ferramentas não têm esse problema; se as pessoas escrevessem programas como esse, nenhum deles seria compilado. (Eu acho que o padrão na verdade limita a quantidade de computação que você pode desdobrar um modelo, então, na verdade, a computação é finita, mas provavelmente muito grande).
Se o que você quer dizer é determinar se o programa de origem é membro do conjunto de programas de origem válidos em C ++ , concordarei que o problema é muito mais difícil. Mas não é a análise que é o problema.
A ferramenta resolve esse problema isolando a análise da verificação de tipo do programa analisado. (Quando houver várias interpretações na ausência de contexto, ele registra uma ambiguidade nó de na árvore de análise com várias análises possíveis; a verificação de tipo decide qual está correta e elimina as subárvores inválidas). Você pode ver uma árvore de análise (parcial) no exemplo abaixo; a árvore inteira é muito grande para caber em uma resposta SO. Observe que você obtém uma árvore de análise se o valor 234797 ou 234799 é usado.
A execução do resolvedor de nome / tipo da ferramenta no AST com o valor original 234799 é bem-sucedida. Com o valor 234797, o resolvedor de nomes falha (conforme o esperado) com a mensagem de erro "typen não é um tipo". e, portanto, essa versão não é um programa C ++ válido.
fonte