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

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

Muitas linguagens de programação podem ser analisadas usando alguma variação 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, eu só achei 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 de C ++ é ambígua, depende do contexto e potencialmente requer uma visão infinita para resolver algumas ambiguidades”.

    Segue-se um número de exemplos (ver 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 token possuem a mesma subsequência inicial, mas diferentes trees de análise, que dependem do último elemento. Pode haver arbitrariamente muitas fichas antes da desambiguação.

    Analisadores LR não conseguem lidar com regras gramaticais ambíguas, por design. (Tornou a teoria mais fácil nos anos 70, quando as ideias estavam sendo elaboradas).

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

     x * y ; 

    Tem dois parses diferentes:

    1. Pode ser a declaração de y, como ponteiro para digitar x
    2. Pode ser uma multiplicidade de x e y, jogando fora a resposta.

    Agora, você pode pensar que o último é estúpido e deve ser ignorado. A maioria concorda com você; no entanto, há casos em que pode haver 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 ambos para decidir mais tarde o que fazer. Assim, uma gramática deve permitir isso. E isso torna a gramática ambígua.

    Assim, a análise LR pura não pode lidar com isso. Nem muitos outros geradores de analisador amplamente disponíveis, como Antlr, JavaCC, YACC ou o tradicional Bison, ou até mesmo analisadores no estilo PEG, são usados ​​de maneira “pura”.

    Há muitos casos mais complicados (a syntax do modelo de análise requer lookahead arbitrário, enquanto a LALR (k) pode olhar para a maioria dos k símbolos), mas só leva um contraexemplo para analisar LR (ou os outros).

    A maioria dos analisadores C / C ++ reais manipulam 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 … de modo que quando o “x” é encontrado, o analisador sabe se x é um tipo ou não, e pode assim escolher entre os dois parses em potencial. Mas um analisador que faz isso não é livre de contexto, e analisadores LR (os puros, etc.) são (no melhor dos casos) livres de contexto.

    Pode-se 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 tem alguns meios para adicionar verificações semânticas em vários pontos da análise, que podem ser usados ​​para fazer isso.

    E se você enganar o suficiente, você pode fazer parsers LR trabalhar para C e C + +. Os caras do GCC fizeram por algum tempo, mas desistiram da análise codificada manualmente, acho que porque eles queriam um melhor diagnóstico de erros.

    Há uma outra abordagem, que é legal e limpa, e analisa C e C ++ muito bem, sem nenhum hackery de tabela de símbolos: analisadores GLR . Estes são parsers livres de contexto completo (tendo efetivamente lookahead infinito). Analisadores GLR simplesmente aceitam ambos os parses, produzindo uma “tree” (na verdade, um gráfico acíclico dirigido que é basicamente similar a uma tree) 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 a nossa Reengenharia de Software DMS Tookit (a partir de junho de 2017, eles lidam com C ++ 17 em dialetos MS e GNU). Eles foram usados ​​para processar milhões de linhas de sistemas C e C ++ grandes, com análises completas e precisas, produzindo ASTs com detalhes completos do código-fonte. (Veja o AST para análise mais irritante do C ++. )

    O problema nunca é definido assim, ao passo que deveria ser interessante:

    Qual é o menor conjunto de modificações na gramática de C ++ que seria necessário para que essa nova gramática pudesse ser perfeitamente analisada por um analisador yacc “sem contexto”? (fazendo uso apenas de um ‘hack’: a desambiguação typename / identifier, o parser informando o lexer de cada typedef / class / struct)

    Eu vejo alguns:

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

      Existem 3 tipos de names tokens de names tokens :

      • types : builtin-type ou por causa de um typedef / class / struct
      • funções de modelo
      • identificadores: funções / methods e variables ​​/ objects

      Considerando template-functions como tokens diferentes resolve o func< ambiguidade. Se func é um nome de function de modelo, então < deve ser o início de uma lista de parâmetros de modelo, caso contrário func é um ponteiro de function e < é o operador de comparação.

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

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

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

      Uma function typedef deve ser um ponteiro de function typedef: typedef int (*func_ptr_type)();

    5. recursion de 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); poderia ser proibido também, substituído por int a,b,c[9],*d; int (*f)();

      int (*g)()[9];

      int h(char);

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

      Uma alternativa altamente preferida seria alterar a terrível syntax do ponteiro de function,

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

      sendo ressintaxado como:

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

      sendo coerente com o operador de casting (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 long e co. poderia ser declarado em cada arquivo de origem. Assim, cada arquivo de origem que faz uso do tipo int deve começar com

      #type int : signed_integer(4)

      e unsigned_integer(4) seriam proibidos fora dessa diretiva #type isso seria um grande passo para o tamanho estúpido da ambigüidade sizeof int presente em tantos headers C ++

    O compilador que implementa o C ++ ressincronizado, se encontrar uma fonte C ++ usando a syntax ambígua, moverá o source.cpp também uma pasta ambiguous_syntax , e criará automaticamente um source.cpp traduzido sem source.cpp antes de compilá-lo.

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

    Como você pode ver na minha resposta aqui , C ++ contém syntax que não pode ser analisada de forma determinística por um analisador LL ou LR devido ao estágio de resolução de tipo (geralmente pós-análise) alterando a ordem das operações e, portanto, a forma fundamental da AST ( normalmente esperado para ser 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 em frente para o contexto, enquanto que LR (∞) significa uma antecipação infinita. Ou seja, o analisador teria que saber tudo o que estava chegando para descobrir onde está agora.

    O problema “typedef” em C ++ pode ser analisado com um analisador LALR (1) que constrói uma tabela de símbolos durante a análise (não um analisador LALR puro). O problema “modelo” provavelmente não pode ser resolvido com este método. A vantagem desse tipo de analisador LALR (1) é que a gramática (mostrada abaixo) é uma gramática LALR (1) (sem ambigüidade).

     /* C Typedef Solution. */ /* Terminal Declarations. */  => lookup(); /* Symbol table lookup. */ /* Rules. */ Goal -> [Declaration]...  +> goal_ Declaration -> Type... VarList ';' +> decl_ -> typedef Type... TypeVarList ';' +> typedecl_ VarList -> Var /','... TypeVarList -> TypeVar /','... Var -> [Ptr]... Identifier TypeVar -> [Ptr]... TypeIdentifier Identifier ->  +> identifier_(1) TypeIdentifier ->  =+> typedefidentifier_(1,{typedef}) // The above line will assign {typedef} to the , // 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 input 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 manipula o problema “typedef” sem ambigüidade na tree de análise ou AST. (Divulgação: Eu sou o cara que criou o LRSTAR .)