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

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 (∞).

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.

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 ++. )

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!

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).

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.

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.)