Por que o C ++ não pode ser analisado com um analisador LR (1)?

153

Eu estava lendo sobre analisadores e geradores de analisadores e encontrei essa declaração na página de análise de LR da wikipedia:

Muitas linguagens de programação podem ser analisadas usando algumas variações de um analisador LR. Uma exceção notável é o C ++.

Por que é tão? Que propriedade específica do C ++ faz com que seja impossível analisar com analisadores LR?

Usando o google, descobri apenas que C pode ser perfeitamente analisado com LR (1), mas C ++ requer LR (∞).

Alegre
fonte
7
Assim como: você precisa entender a recursão para aprender a recursão ;-).
Toon Krijthe 28/10/08
5
"Você entenderá os analisadores assim que analisar esta frase."
ilya n.

Respostas:

92

Há um tópico interessante no Lambda the Ultimate que discute a gramática LALR para C ++ .

Ele inclui um link para uma tese de doutorado que inclui uma discussão sobre a análise de C ++, que afirma que:

"A gramática C ++ é ambígua, dependente do contexto e potencialmente requer uma visão infinita para resolver algumas ambiguidades".

A seguir, fornece vários exemplos (consulte a página 147 do pdf).

O exemplo é:

int(x), y, *const z;

significado

int x;
int y;
int *const z;

Comparado a:

int(x), y, new int;

significado

(int(x)), (y), (new int));

(uma expressão separada por vírgula).

As duas sequências de tokens têm a mesma subsequência inicial, mas diferentes árvores de análise, que dependem do último elemento. Pode haver arbitrariamente muitos tokens antes do disambiguating.

Rob Walker
fonte
29
Seria legal ter um resumo sobre a página 147 nesta página. Mas vou ler essa página. (+1)
Animador
11
O exemplo é: int (x), y, * const z; // significado: int x; int y; int * const z; (uma sequência de declarações) int (x), y, new int; // significado: (int (x)), (y), (novo int)); (uma expressão separada por vírgula) As duas seqüências de token têm a mesma subsequência inicial, mas diferentes árvores de análise, que dependem do último elemento. Pode haver arbitrariamente muitos tokens antes do disambiguating.
Blaisorblade
6
Bem, nesse contexto, ∞ significa "arbitrariamente muitos" porque a cabeça de impressão sempre será limitada pelo comprimento da entrada.
MauganRa
1
Estou bastante intrigado com a citação extraída de uma tese de doutorado. Se houver uma ambiguidade, então, por definição, o NO lookahead pode "resolver" a ambiguidade (por exemplo, decidir qual análise é a oen correta, pois pelo menos 2 análises são consideradas corretas pela gramática). Além disso, a citação menciona a ambiguidade de C, mas a explicação, não mostra uma ambiguidade, mas apenas um exemplo não ambíguo em que a decisão de analisar só pode ser tomada após um longo olhar arbitrário à frente.
Dodecaplex 13/11/19
231

Os analisadores LR não podem lidar com regras gramaticais ambíguas, por design. (Facilitou a teoria na década de 1970, quando as idéias estavam sendo elaboradas).

C e C ++ permitem a seguinte instrução:

x * y ;

Ele tem duas análises diferentes:

  1. Pode ser a declaração de y, como ponteiro para o tipo x
  2. Pode ser uma multiplicação de xey, jogando fora a resposta.

Agora, você pode pensar que o último é estúpido e deve ser ignorado. A maioria concordaria com você; no entanto, há casos em que isso pode ter um efeito colateral (por exemplo, se a multiplicação estiver sobrecarregada). mas esse não é o ponto. O ponto é que existem duas análises diferentes e, portanto, um programa pode significar coisas diferentes, dependendo de como isso deveria ter sido analisado.

O compilador deve aceitar o apropriado nas circunstâncias apropriadas e, na ausência de qualquer outra informação (por exemplo, conhecimento do tipo de x), deve coletar os dois para decidir posteriormente o que fazer. Assim, uma gramática deve permitir isso. E isso torna a gramática ambígua.

Portanto, a análise de LR pura não pode lidar com isso. Muitos outros geradores de analisadores amplamente disponíveis, como Antlr, JavaCC, YACC ou Bison tradicional, ou mesmo analisadores de estilo PEG, também não podem ser usados ​​de maneira "pura".

Existem muitos casos mais complicados (a sintaxe do modelo de análise requer um olhar arbitrário, enquanto o LALR (k) pode olhar para a frente na maioria dos k tokens), mas apenas é necessário um contraexemplo para eliminar a análise de LR pura (ou outras).

A maioria dos analisadores C / C ++ reais manipula esse exemplo usando algum tipo de analisador determinístico com um hack extra: eles entrelaçam a análise com a coleção de tabelas de símbolos ... para que, quando "x" for encontrado, o analisador saiba se x é um tipo ou não e, portanto, pode escolher entre as duas análises em potencial. Mas um analisador que faz isso não é livre de contexto, e os analisadores LR (os puros etc.) são (na melhor das hipóteses) livres de contexto.

É possível trapacear e adicionar verificações semânticas por tempo de redução por regra nos analisadores LR para fazer essa desambiguação. (Esse código geralmente não é simples). A maioria dos outros tipos de analisadores possui alguns meios para adicionar verificações semânticas em vários pontos da análise, que podem ser usadas para fazer isso.

E se você trapacear o suficiente, poderá fazer com que os analisadores LR funcionem para C e C ++. Os caras do GCC fizeram isso por um tempo, mas desistiram da análise codificada manualmente, acho que porque queriam um diagnóstico de erro melhor.

Há outra abordagem, porém, que é legal e limpa e analisa C e C ++ sem problemas, sem nenhum truque de tabela de símbolos: analisadores GLR . Esses são analisadores livres de contexto completo (com cabeçalho efetivamente infinito). Os analisadores GLR simplesmente aceitam ambos os analisadores, produzindo uma "árvore" (na verdade, um gráfico acíclico direcionado que é principalmente semelhante a uma árvore) que representa a análise ambígua. Um passe de pós-análise pode resolver as ambiguidades.

Usamos essa técnica nos front-ends C e C ++ para o nosso DMS Software Reengineering Tookit (em junho de 2017, eles lidam com C ++ 17 completo em dialetos MS e GNU). Eles foram usados ​​para processar milhões de linhas de grandes sistemas C e C ++, com análises completas e precisas, produzindo ASTs com detalhes completos do código-fonte. (Consulte o AST para a análise mais irritante do C ++. )

Ira Baxter
fonte
11
Embora o exemplo 'x * y' seja interessante, o mesmo pode acontecer em C ('y' pode ser um typedef ou uma variável). Mas C pode ser analisado por um analisador LR (1), então qual é a diferença com C ++?
Martin Cote
12
Meu atendedor já havia observado que C tinha o mesmo problema, acho que você perdeu. Não, não pode ser analisado por LR (1), pelo mesmo motivo. Er, o que você quer dizer com 'y' pode ser um typedef? Talvez você quis dizer 'x'? Isso não muda nada.
Ira Baxter
6
O Parse 2 não é necessariamente estúpido em C ++, pois * pode ser substituído para ter efeitos colaterais.
Dour High Arch
8
Eu olhei x * ye ri - é incrível como alguém pensa em pequenas ambiguidades bacanas como essa.
new123456
51
@altie Certamente ninguém sobrecarregaria um operador de deslocamento de bits para fazê-lo escrever a maioria dos tipos de variáveis ​​em um fluxo, certo?
Troy Daniels
16

O problema nunca é definido assim, embora deva ser interessante:

qual é o menor conjunto de modificações na gramática C ++ que seria necessário para que essa nova gramática pudesse ser perfeitamente analisada por um analisador yacc "sem contexto"? (usando apenas um 'hack': a desambiguação do nome do tipo / identificador, o analisador informando o lexer de cada typedef / classe / estrutura)

Eu vejo alguns:

  1. Type Type;é proibido. Um identificador declarado como um nome de tipo não pode se tornar um identificador que não seja um tipo de nome (observe que struct Type Typenão é ambíguo e ainda pode ser permitido).

    Existem 3 tipos de names tokens:

    • types : tipo interno ou devido a um typedef / class / struct
    • funções de modelo
    • identificadores: funções / métodos e variáveis ​​/ objetos

    Considerar funções de modelo como tokens diferentes resolve a func<ambiguidade. Se funcfor um nome de função de modelo, <deve ser o início de uma lista de parâmetros de modelo, caso contrário, funcé um ponteiro de função e <é o operador de comparação.

  2. Type a(2);é uma instanciação de objeto. Type a();e Type a(int)são protótipos de função.

  3. int (k); é completamente proibido, deve ser escrito int k;

  4. typedef int func_type(); e typedef int (func_type)();são proibidos.

    Uma função typedef deve ser um ponteiro de função typedef: typedef int (*func_ptr_type)();

  5. a recursão do modelo é limitada a 1024, caso contrário, um máximo aumentado pode ser passado como uma opção para o compilador.

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); também poderia ser proibido, substituído por int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    uma linha por protótipo de função ou declaração de ponteiro de função.

    Uma alternativa altamente preferida seria alterar a terrível sintaxe do ponteiro de função,

    int (MyClass::*MethodPtr)(char*);

    sendo ressintaxe como:

    int (MyClass::*)(char*) MethodPtr;

    sendo coerente com o operador de elenco (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; também pode ser proibido: uma linha por typedef. Assim se tornaria

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int, sizeof char, sizeof long longE co. pode ser declarado em cada arquivo de origem. Assim, cada arquivo de origem que utiliza o tipo intdeve começar com

    #type int : signed_integer(4)

    e unsigned_integer(4)seria proibido fora dessa #type diretiva, esse seria um grande passo para a sizeof intambiguidade estúpida presente em tantos cabeçalhos de C ++

O compilador que implementa o C ++ ressintaxe, se encontrasse uma fonte C ++ usando sintaxe ambígua, moveria source.cpptambém uma ambiguous_syntaxpasta e criaria automaticamente uma tradução inequívoca source.cppantes de compilá-la.

Por favor, adicione suas sintaxes C ++ ambíguas, se você conhece algumas!

reuns
fonte
3
C ++ está muito bem entrincheirado. Ninguém fará isso na prática. Aquelas pessoas (como nós) que constroem front-ends simplesmente mordem a bala e fazem a engenharia para fazer os analisadores funcionarem. E, enquanto houver modelos na linguagem, você não terá um analisador puro e livre de contexto.
Ira Baxter
9

Como você pode ver na minha resposta aqui , o C ++ contém sintaxe que não pode ser analisada deterministicamente por um analisador LL ou LR devido ao estágio de resolução do tipo (normalmente pós-análise) alterando a ordem das operações e, portanto, a forma fundamental do AST ( normalmente esperado que seja fornecido por uma análise de primeiro estágio).

Sam Harwell
fonte
3
A tecnologia de análise que lida com ambiguidade simplesmente produz as duas variantes AST conforme elas analisam e simplesmente elimina a incorreta, dependendo das informações de tipo.
Ira Baxter
@Ira: Sim, isso está correto. A vantagem particular disso é que permite manter a separação da análise do primeiro estágio. Embora seja mais conhecido no analisador GLR, não há motivo específico para eu perceber que você não conseguiu acessar C ++ com um "GLL?" analisador também.
Sam Harwell
"GLL"? Bem, claro, mas você terá que descobrir a teoria e escrever um artigo para o resto usar. Provavelmente, você pode usar um analisador codificado de cima para baixo ou um analisador LALR () de retorno (mas mantenha o "rejeitado") analisa ou executa um analisador Earley. A GLR tem a vantagem de ser uma solução muito boa, está bem documentada e já está comprovada. Uma tecnologia GLL teria que ter algumas vantagens bastante significativas para exibir a GLR.
Ira Baxter
O projeto Rascal (Holanda) está reivindicando que eles estão construindo um analisador GLL sem scanner. Em andamento, pode ser difícil encontrar informações on-line. en.wikipedia.org/wiki/RascalMPL
Ira Baxter
@IraBaxter Parece haver novos desenvolvimentos sobre a GLL: veja este artigo de 2010 sobre a GLL dotat.at/tmp/gll.pdf #
Sjoerd
6

Eu acho que você está bem perto da resposta.

LR (1) significa que a análise da esquerda para a direita precisa de apenas um token para olhar o futuro, enquanto LR (∞) significa um olhar infinito no futuro. Ou seja, o analisador precisaria saber tudo o que estava por vir para descobrir onde está agora.

casademora
fonte
4
Lembro-me da minha classe de compiladores que LR (n) para n> 0 é matematicamente redutível a LR (1). Isso não é verdade para n = infinito?
Rmeador 28/10/08
14
Não, há uma montanha intransitável de diferença entre n e infinito.
ephemient
4
Não é a resposta: sim, dada uma quantidade infinita de tempo? :)
Steve Fallows
7
Na verdade, pela minha vaga lembrança de como LR (n) -> LR (1) ocorre, envolve a criação de novos estados intermediários; portanto, o tempo de execução é uma função não constante de 'n'. Traduzir LR (inf) -> LR (1) levaria um tempo infinito.
Aaron
5
"Não é a resposta: sim, dada uma quantidade infinita de tempo?" - Não: a frase 'com uma quantidade infinita de tempo' é apenas uma maneira não sensorial e abreviada de dizer "não pode ser feito com uma quantidade finita de tempo". Quando vir "infinito", pense: "não finito".
21320 ChrisW
4

O problema "typedef" no C ++ pode ser analisado com um analisador LALR (1) que cria uma tabela de símbolos durante a análise (não um analisador LALR puro). O problema do "modelo" provavelmente não pode ser resolvido com esse método. A vantagem desse tipo de analisador LALR (1) é que a gramática (mostrada abaixo) é uma gramática LALR (1) (sem ambiguidade).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

A entrada a seguir pode ser analisada sem problemas:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

O gerador de analisador LRSTAR lê a notação gramatical acima e gera um analisador que lida com o problema "typedef" sem ambiguidade na árvore de análise ou AST. (Divulgação: eu sou o cara que criou o LRSTAR.)


fonte
Esse é o hack padrão usado pelo GCC com seu antigo analisador LR para lidar com a ambiguidade de coisas como "x * y"; Infelizmente, ainda existe o requisito lookahead arbitrariamente grande para analisar outras construções, portanto o LR (k) falha em ser uma solução para qualquer k fixo. (O GCC mudou para descida recursiva com mais artigos de anúncios).
Ira Baxter