O que torna o Java mais fácil de analisar do que o C?

90

Estou familiarizado com o fato de que as gramáticas de C e C ++ são sensíveis ao contexto e , em particular, você precisa de um "hack lexer" em C. Por outro lado, tenho a impressão de que você pode analisar Java apenas com 2 tokens de look-ahead, apesar da similaridade considerável entre os dois idiomas.

O que você teria que mudar em C para torná-lo mais tratável para analisar?

Eu pergunto porque todos os exemplos que eu vi de sensibilidade ao contexto de C são tecnicamente permitidos, mas terrivelmente estranhos. Por exemplo,

foo (a);

poderia estar chamando a função void foocom argumento a. Ou pode ser declarado aum objeto do tipo foo, mas você pode facilmente se livrar dos parênteses. Em parte, essa estranheza ocorre porque a regra de produção do "declarador direto" para a gramática C cumpre o duplo propósito de declarar funções e variáveis.

Por outro lado, a gramática Java possui regras de produção separadas para declaração de variável e declaração de função. Se você escrever

foo a;

então você saberá que é uma declaração de variável e foopode ser analisada sem ambigüidade como um nome de tipo. Este pode não ser um código válido se a classe foonão tiver sido definida em algum lugar no escopo atual, mas é um trabalho para análise semântica que pode ser executado em uma passagem posterior do compilador.

Já vi que C é difícil de analisar por causa do typedef, mas você também pode declarar seus próprios tipos em Java. Além disso direct_declarator, quais regras da gramática C estão em falta?

Korrok
fonte
7
Pergunta legal. Provavelmente muito amplo ou principalmente opinativo.
asteri
37
Esta é uma pergunta válida sobre analisadores e a única coisa ampla ou baseada em opinião sobre ela são as últimas frases (que provavelmente devem ser eliminadas ou alteradas). Saia com os votos de fechamento.
R .. GitHub PARAR DE AJUDAR O ICE
1
Editei a pergunta de acordo, obrigado por @R .. pelo feedback.
korrok
3
Praticamente todas as linguagens de computador (padrão) são sensíveis ao contexto ; você não pode declarar uma variável de um tipo e usá-la indevidamente na maioria das línguas . Isso é diferente de "todas as gramáticas para o idioma" são sensíveis ao contexto; a maioria das pessoas que criam analisadores constrói um analisador livre de contexto (ou até mais restritivo) e, em seguida, usa hacks fora do analisador para verificar as propriedades livres de contexto.
Ira Baxter
1
@IraBaxter Eu não chamaria isso de "hacks". Dividir o problema em dois parece uma coisa razoável a se fazer, uma vez que a análise de linguagens sensíveis ao contexto não pode ser feita de forma eficiente (e de fato, mesmo analisar linguagens livres de contexto não é eficiente, e é por isso que geralmente restringimos a subconjuntos de linguagens livres de contexto) . Uma análise livre de contexto + análise estática para verificar apenas as propriedades sensíveis ao contexto no AST é uma coisa razoável a se fazer.
Bakuriu

Respostas:

76

Analisar C ++ está ficando difícil. Analisar Java está ficando tão difícil quanto.

Veja esta resposta do SO discutindo porque C (e C ++) é "difícil" de analisar . O breve resumo é que as gramáticas C e C ++ são inerentemente ambíguas; eles fornecerão várias análises e você deve usar o contexto para resolver as ambigüidades. As pessoas então cometem o erro de presumir que você precisa resolver ambigüidades enquanto analisa; não é assim, veja abaixo. Se você insiste em resolver ambiguidades ao analisar, seu analisador se torna mais complicado e muito mais difícil de construir; mas essa complexidade é uma ferida autoinfligida.

IIRC, a gramática "óbvia" LALR (1) do Java 1.4 não era ambígua, portanto, era "fácil" de analisar. Não tenho tanta certeza de que o Java moderno não tenha pelo menos ambigüidades locais de longa distância; há sempre o problema de decidir se "... >>" fecha dois modelos ou é um "operador de turno certo". Suspeito que o Java moderno não analisa mais com LALR (1) .

Mas pode-se superar o problema de análise usando analisadores fortes (ou analisadores fracos e hacks de coleta de contexto, como os front-ends C e C ++ fazem agora), para ambas as linguagens. C e C ++ têm a complicação adicional de ter um pré-processador; estes são mais complicados na prática do que parecem. Uma afirmação é que os analisadores C e C ++ são tão difíceis que precisam ser escritos à mão. Não é verdade; você pode construir analisadores Java e C ++ muito bem com geradores de analisador GLR.

Mas a análise não é realmente onde está o problema.

Depois de analisar, você desejará fazer algo com a árvore AST / parse. Na prática, você precisa saber, para cada identificador, qual é sua definição e onde é usado ("resolução de nome e tipo", desleixadamente, construindo tabelas de símbolos). Isso acaba sendo MUITO mais trabalhoso do que acertar o analisador, composto por herança, interfaces, sobrecarga e modelos, e o confuso pelo fato de que a semântica para tudo isso é escrita em linguagem natural informal espalhada por dezenas a centenas de páginas do padrão de linguagem. C ++ é muito ruim aqui. Java 7 e 8 estão ficando terríveis desse ponto de vista. (E as tabelas de símbolos não são tudo de que você precisa; veja minha biografia para um ensaio mais longo sobre "Vida após análise").

A maioria das pessoas tem dificuldade com a parte da análise pura (muitas vezes nunca termina; verifique o próprio SO para as muitas, muitas perguntas sobre como construir analisadores funcionais para idiomas reais), de modo que nunca vêem vida após a análise. E então temos teoremas populares sobre o que é difícil de analisar e nenhum sinal sobre o que acontece após esse estágio.

Corrigir a sintaxe C ++ não levará você a lugar nenhum.

Com relação à mudança da sintaxe C ++: você descobrirá que precisa corrigir vários lugares para cuidar da variedade de ambigüidades locais e reais em qualquer gramática C ++. Se você insiste, a lista a seguir pode ser um bom ponto de partida . Eu afirmo que não há sentido em fazer isso se você não for o comitê de padrões C ++; se você fizesse isso e construísse um compilador usando isso, ninguém em sã consciência iria usá-lo. Há muito investido em aplicativos C ++ existentes para alternar para a conveniência de quem está criando analisadores; além disso, a dor acabou e os analisadores existentes funcionam bem.

Você pode querer escrever seu próprio analisador. OK, tudo bem; só não espere que o resto da comunidade permita que você mude o idioma que eles devem usar para tornar mais fácil para você. Todos querem que seja mais fácil para eles, que seja usar a linguagem documentada e implementada.

Ira Baxter
fonte
Boa resposta. Veja também D e C +, que tentam resolver alguns desses problemas. s / content / contend /
david.pfx
3
Eu li Life After Parsing antes e descobri que é uma verdadeira revelação; ficou claro para mim que há muito mais trabalho na análise semântica (resolução de nome / tipo, ...) do que na análise. Estou não tentar mudar a sintaxe de qualquer linguagem. Eu não quero entender o que as propriedades são de uma linguagem na qual você pode fazer a análise sintática em primeiro lugar e, em seguida, a análise semântica. C não é uma linguagem desse tipo (precisa do hack do Lexer); Sempre pensei que era Java e quero saber por quê.
korrok
1
@Korrok: leia minha resposta sobre a construção de Java / C ++ com analisadores GLR. Você não precisa de nenhum hack lexer . Portanto, a distinção está na mente das pessoas que usam a tecnologia de análise errada. ... Concedido, construir um front-end C ++ completo (especialmente C ++ 14, o que fizemos) é mais difícil do que fazer Java8, mas eles são difíceis (em termos de esforço e atenção aos detalhes) e análise é a peça mais fácil.
Ira Baxter
1
Eu concordo sobre sua "Vida após a análise": por exemplo, a resolução de sobrecarga em C # pode codificar qualquer problema de 3-SAT e, portanto, é NP-difícil.
Jörg W Mittag