Para que um idioma seja programável, é obrigatório que seja baseado em uma gramática livre de contexto

23

Na prática, para uma linguagem que possa eventualmente ser compilada / transformada em instruções no nível do sistema, é necessário que seja uma gramática livre de contexto?

ex: todas as linguagens de programação / script possuem gramática livre de contexto? Java é baseado em CFGs, mas será que todas as linguagens de programação são baseadas em CFGs?

Não parece obrigatório, mas há lacunas no meu entendimento.

Algum contexto para a pergunta: eu estava olhando para a especificação da linguagem Java, que também fornece as regras gramaticais . Isso me fez pensar sobre essa questão.

sandeepkunkunuru
fonte
1
Geralmente, acho que você deseja que o problema de compilação seja computável, e analisar CFGs é agradável e fácil. Embora eu tenha ouvido algumas afirmações de que, por exemplo, reconhecer programas perl válidos é de fato um problema não computável.
Janne Korhonen H.
2
na verdade, tudo o que você realmente precisa é de uma sintaxe decidida em termos de tempo (que são todos os CFGs). Você também pode criar uma linguagem de programação cuja sintaxe não seja decidida por turing, mas quando você digita um erro de digitação, o compilador pode nunca parar enquanto tenta decidir se é uma sintaxe válida. isso não é realmente útil #
catraca aberração
@ratchet, você está assumindo que a sintaxe deve ser recursivamente enumerável?
David Harris
4
@JanneKorhonen: Especificamente, o Perl não pode ser analisado estaticamente , ou seja, não pode ser analisado sem também ser executado; Uma vez que a execução pode não ter fim, a análise estatística do Perl implicaria a solução do problema de parada.
Jon Purdy
@janne Quero dizer, pós-processamento que pode acarretar problemas que podem ou não ser computáveis, geralmente é o caso em que a gramática final contra a qual o programa é validado é livre de contexto. Para ser mais específico, após o pré-processamento, para identificar uma regra que se encaixe em uma sequência de tokens, precisamos examinar outros tokens ao redor da sequência. Não sei se faço sentido, desculpe por isso. Estou um pouco confuso, na verdade.
sandeepkunkunuru

Respostas:

20

Duas vezes não.

Primeiro, a maioria das HPLs não é livre de contexto. Embora eles geralmente tenham sintaxe baseada em um CFG, eles também têm o que as pessoas chamam de semântica estática (que também é frequentemente incluída no termo sintaxe). Isso pode incluir nomes e tipos que precisam ser verificados para um programa correto. Por exemplo,

class A {
  String a = "a";
  int b = a + d;
}

é um programa Java sintaticamente correto, mas não será compilado porque dnão está definido e anão possui um tipo de ajuste.

Em segundo lugar, você pode analisar linguagens que não são livres de contexto (como obviamente comprovado pela existência de compiladores). Somente os CFGs podem ser analisados ​​com eficiência, enquanto os CSGs não podem, em geral. No entanto, você pode adicionar alguns recursos que não são livres de contexto e permanecer eficientes.

Os compiladores geralmente são executados em fases: primeira tokenização (regular), depois análise sem contexto, depois análise de nome e tipo (sensível ao contexto, às vezes até mais difícil). Você pode observar esse comportamento pelo tipo de mensagem de erro recebida.

Rafael
fonte
3
Não se esqueça do public class Program { public static void main(String[] args) { ... } }... Java não vai deixar você sair tão fácil. :-)
Roy Tinker
Tecnicamente, class A { ... }é completamente suficiente, pois javaccompila coisas que você não pode realmente executar (por falta de um ponto de entrada) também. Mas sim
Raphael
20

A análise de perl não pode ser decidida.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

Niall Murphy
fonte
6
Eu sinto que este deve ser o punchline de uma piada Perl :)
Suresh Venkat
5
Suresh: Eu já fiz essa piada, embora não tenha sido uma piada muito boa, no artigo "Sobre linguagens de programação unlexable" no SIGBOVIK 2011 ( sigbovik.org/2011/proceedings.pdf - página 79- 82)
Rob Simmons
1
Nota: o intérprete Perl ainda não é não-determinista, se isso é um conforto para qualquer um :)
Roy Tinker
15

Não acredito que a gramática do Python seja livre de contexto. O requisito de que linhas no mesmo bloco de código tenham a mesma quantidade de indentação não é o tipo de coisa que as gramáticas livres de contexto lidam bem.

Mais precisamente, parece haver um homomorfismo da linguagem dos blocos Python da forma

se condição:
     linha 1
     linha 2
     line3
outro:
     line4

para o idioma sem contexto que o primeiro bloco de zeros vem do conjunto de espaços no início da linha1, o segundo bloco vem o conjunto de espaços no início da linha2, o terceiro bloco vem do conjunto de espaços no início da linha3, e as linhas restantes com o else etc estão lá para forçar a linha1, a linha2 e a linha3 a pertencer ao mesmo bloco.0 0n10n10n

David Eppstein
fonte
4
Estritamente você está certo, mas no contexto das linguagens de programação, tentamos tornar a linguagem livre de contexto resultante de uma etapa de pré-processamento chamada tokenização . Eu acho que o recuo é verificado antes disso.
Diego de Estrada
7
Sim, o lexer Python (tokenizer) possui uma pilha de profundidades de indentação; o fluxo de token possui um símbolo INDENT no início de cada bloco e um símbolo DEDENT no final que pode ser analisado de maneira livre de contexto (INDENT e DEDENT agem como os chavetas em C). C tem o problema "não posso dizer se a declaração ou expressão" é: foo * bar;uma declaração foocomo ponteiro barou multiplicação de foovezes bar?
Max
8
Ok, claro, mas você está apenas escondendo a mesma complexidade no lexer, em vez de torná-lo um transdutor de estado finito, como costumam ser.
precisa
1
@ David David Eppstein: Para ser justo, a complexidade dita não é grande de forma alguma.
Jon Purdy
1
Além da manipulação de INDENT / DEDENT no lexer, o Python possui uma gramática LL (1) muito simples.
rmmh
13

Bodo Manthey e Martin Böhme mostram que todo compilador C ++ é necessariamente Turing completo, ou seja, ele pode calcular qualquer função recursiva parcial em tempo de compilação . Portanto, é muito pior do que apenas sensível ao contexto.

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

Markus Bläser
fonte
Sim, mas o compilador nunca é apenas gramática livre de contexto. Você deve discutir a gramática em si, não o compilador.
Jeff Burdges
@ Jeff: "Tempo de compilação" na minha resposta significa "verificar se um determinado código-fonte C + está correto". Com uma pequena modificação da construção no documento, é possível reduzir todas as linguagens decidíveis ao conjunto de todos os programas C ++ corretos.
Markus Bläser
7

Penso que a declaração antes do uso de variáveis ​​e o polimorfismo de função das linguagens OOP são outros exemplos de especificações de linguagens de programação que não podem ser tratadas por gramáticas livres de contexto:

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

Fiz uma pequena pesquisa no Google e encontrei este artigo: " Uma gramática booleana para uma linguagem booleana simples " de A.Okhotin (2004); Segundo ele, o verdadeiro problema é encontrar uma linguagem de programação completamente descrita por uma gramática formal:

Uma linguagem de programação processual de brinquedo é definida e uma gramática booleana para o conjunto de programas bem formados nessa linguagem é construída. Aparentemente, essa é a primeira especificação de uma linguagem de programação inteiramente por uma gramática formal.

A seção Introdução do artigo é curta, mas muito esclarecedora.

Marzio De Biasi
fonte
6

Acredito que a gramática de C é tecnicamente livre de contexto, já que os analisadores sempre usam técnicas sem contexto para dar suporte ao dispositivo de Duff .

As linguagens baseadas em recuo não são naturalmente livres de contexto, como David disse, mas se tornam livres de contexto em relação a um token de recuo parametrizado.

Haskell permite alterar a precedência do operador com infix e infixl. O módulo estrito de pragma do Perl é implementado usando as configurações lexicais $ ^ H e% ^ H, que não o tornam livre de contexto, provavelmente outras configurações também.

Existem linguagens de expansão de macro como o TeX, nas quais a análise de afaik não faz sentido sem a execução.

Provavelmente, existem até duas gramáticas livres de contexto cuja interseção não é livre de contexto, mas ainda descreve uma máquina de Turing.

Java e assembler provavelmente são naturalmente livres de contexto.

Jeff Burdges
fonte
2
A ambiguidade de (a)-btornar C sensível ao contexto? ( aPoderia ser uma variável ou um typedef - algumas outras línguas não permitem lançando expressões menos unário por esta razão)
Random832
Peço desculpas pelo comentário muito atrasado, mas o dispositivo de Duff não envolve desvios sintáticos. Os aparelhos se equilibram corretamente. O recurso C geralmente ignorado nas discussões sobre se C é livre de contexto é o pré-processador. Estou cético quanto à existência de qualquer interpretação, por mais informal que seja, do "contexto livre" que permita usá-la para descrever uma linguagem com um processador de macro, mesmo que seja bem-comportado. E o pré-processador C é tudo menos comportado.
rici 29/05
4

Não, e muitas linguagens práticas não são livres de contexto. Por exemplo, a gramática C ++ não é, porque em alguns contextos a resolução gramatical depende da digitação de informações que não são livres de contexto.

antti.huima
fonte
4

Primeiro, deixe-me fazer uma distinção entre a sintaxe de uma linguagem de programação e a própria linguagem.

A sintaxe de muitas linguagens é (pelo menos com base em) uma gramática livre de contexto (CFG), porque elas são bem estudadas e existem algoritmos que podem analisar com eficiência uma CFG e o caso limite que não pode ser resolvido pela CFG pode ser tratado especialmente

No entanto, muitas linguagens não são livres de contexto (quando símbolos de declaração antes do uso são usados, por exemplo, em java, C (++), D).

Curiosidade: D tem uma avaliação da função de tempo de compilação completa de Turing e expansão de modelo, tornando a linguagem em si não decidível por Turing. No entanto, o criador da linguagem fez um grande esforço para tornar a sintaxe um CFG.

catraca arrepiante
fonte
A análise de nome e tipo normalmente realiza tarefas inerentemente sem contexto.
Raphael
A meta-programação de modelos em C ++ é Turing completa.
Jeff Burdges
3

No que diz respeito a "Todas as linguagens de programação / script são livres de gramática?" parte está em causa, a resposta é um número definitivo

Re: a questão principal de "para um idioma que pode eventualmente ser compilado / transformado em instruções no nível do sistema", não sei por que ele precisa necessariamente ser um CFG. No entanto, poderia haver melhores explicações.

Kris
fonte
1
Kris, você pode dar alguns exemplos de linguagens de programação baseadas em gramática sem contexto. Quero dizer, pós-pré-processamento que pode acarretar problemas que podem ou não ser computáveis, a gramática final contra a qual o programa é validado.
sandeepkunkunuru
3

Uma linguagem de programação precisa se basear em algum tipo de formalismo gramatical, do qual os CFGs são um exemplo. Embora os CFGs sejam os mais comuns (e o habitual ensinado nos cursos de compilação em universidades), existem outros formalismos, como as Gramáticas de Análise de Expressão Analisada, sobre as quais você pode ler mais aqui (pdf) ou na Wikipedia para obter uma leitura mais detalhada.

evilcandybag
fonte