Porque não pode C ++ ser analisado com um LR (1) parser?

Question

Eu estava lendo sobre analisadores e geradores de analisador e encontrei esta declaração em LR -page análise da Wikipédia:

Muitas linguagens de programação pode ser analisado usando alguma variação de um analisador LR. Uma exceção notável é C ++.

Por que é assim? Que propriedade particular de C ++ faz com que seja impossível de analisar com parsers LR?

Usando o Google, eu só descobri que C pode ser perfeitamente analisado com LR (1), mas C ++ requer LR (8).

Answer 1

Não é uma discussão interessante sobre Lambda the Ultimate que discute a LALR gramática para C ++ .

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

"gramática C ++ é ambígua, -Dependente do contexto e potencialmente requer lookahead infinito para resolver algumas ambiguidades".

Ele passa a dar uma série de exemplos (ver página 147 do pdf).

O exemplo é:

int(x), y, *const z;

significando

int x;
int y;
int *const z;

Comparar a:

int(x), y, new int;

significando

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

(uma expressão separados por vírgulas).

As duas seqüências de tokens têm a mesma subsequência inicial, mas diferentes árvores de análise, que dependem do último elemento. Não pode ser arbitrariamente muitas fichas antes do que disambiguating.

Answer 2

analisadores LR não pode lidar com regras gramaticais ambíguas, pelo design. (Feito a teoria mais fácil na década de 1970, quando as idéias foram sendo trabalhados).

C e C ++ ambos 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 multiplicação 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 tem um efeito secundário (por exemplo, se multiplicam está sobrecarregado). mas isso não é o ponto. O ponto é que são dois parses diferentes e, portanto, um programa pode significar coisas diferentes, dependendo de como este deve ter sido analisado.

O compilador deve aceitar o apropriado sob as circunstâncias adequadas, e na ausência de qualquer outra informação (por exemplo, o conhecimento do tipo de x) deve coletar tanto para decidir depois o que fazer. Assim, uma gramática deve permitir isso. E isso faz a gramática ambígua.

Assim pura análise LR não pode lidar com isso. Nem pode muitos outros geradores de analisador amplamente disponíveis, tais como Antlr, JavaCC, YACC, ou Bison tradicional, ou mesmo analisadores PEG-estilo, usados ??de forma "pura".

Existem muitos casos mais complicados (análise de sintaxe do modelo requer lookahead arbitrária, enquanto LALR (k) pode olhar em frente na maioria das fichas k), mas só ele só tem um contra-exemplo para abater pura LR (ou outros) a análise.

A maioria verdadeiro C / C ++ analisadores lidar com esse exemplo usando algum tipo de analisador determinista com um corte adicional: eles se entrelaçam analisar com tabela de símbolos coleção ... de modo que no momento em que "x" é encontrado, o analisador sabe se x é um tipo ou não, e pode, assim, escolher entre os dois parses potenciais. Mas um analisador que faz isso não é livre de contexto, e analisadores LR (Os puros, etc.) são (na melhor das hipóteses) livre de contexto.

Pode-se enganar, e adicionar per-regra redução do tempo de verificações de semântica na para analisadores LR fazer isso disambiguation. (Este código muitas vezes não é simples). A maioria dos outros tipos de analisador ter alguns meios para adicionar verificações de semântica em vários pontos na análise, que pode ser usado para fazer isso.

E se você enganar o suficiente, você pode fazer LR analisadores de trabalho para C e C ++. Os caras do CCG fizeram por algum tempo, mas deu-lhe -se para análise codificado à mão, acho que porque eles queriam diagnósticos melhor de erro.

Há uma outra abordagem, no entanto, que é agradável e limpo e analisa C e C ++ muito bem sem qualquer tabela de símbolos hackery: GLR parsers . Estes são os analisadores gratuitos contexto completo (tendo efetivamente infinito olhe para frente). analisadores GLR simplesmente aceitar ambos parses, produzindo uma "árvore" (na verdade, um gráfico acíclico dirigido que é principalmente árvore como) que representa o parse ambígua. Um passe de análise de pós pode resolver as ambiguidades.

Nós usamos esta técnica em front-ends do C e C ++ para o nosso DMS Software Reengineering Toolkit (a partir de junho 2017 estes pega integral C ++ 17 em MS e GNU dialetos). Eles têm sido usados ??para milhões de processos de linhas de grande C e sistemas de C ++, com completas, analisa-precisos produzir ASTs com detalhes completos do código fonte. (Veja a AST para C ++ 's mais irritante de análise. )

Answer 3

O problema nunca é definida como este, quando deveria ser interessante:

O que é o menor conjunto de modificações à gramática C ++ que seria tão necessário que esta nova gramática poderia perfeitamente ser analisado por um analisador yacc "não-livre de contexto"? (Fazendo uso de apenas um 'hack': o typename / identificador disambiguation, o analisador informando o lexer de cada typedef / class / struct)

Eu vejo uns poucos:

É proibido

1. Type Type;. Um identificador declarado como um typename não pode se tornar um identificador não-typename (note que struct Type Type não é ambígua e poderia ainda ser permitido).

   Existem 3 tipos de names tokens:

   • types: builtin-tipo ou por causa de um typedef / class / struct
   • modelo-funções
   • identificadores: funções / métodos e variáveis ??/ objetos

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

2. Type a(2); é uma instanciação 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.

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

5. recursão molde é limitado a 1,024, de outro modo um aumento máximo pode ser transmitida 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 função ou ponteiro de função declaração.

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

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

   sendo resyntaxed como:

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

   este ser coerente com o (int (MyClass::*)(char*)) operador de conversão

7. typedef int type, *type_ptr; poderia ser proibido também: uma linha por typedef. Assim que 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 fazendo uso do tipo int deve começar com

   #type int : signed_integer(4)

   e unsigned_integer(4) seria proibido fora da referida directiva #type este seria um grande passo para a sizeof int ambiguidade burro, presente em muitas cabeçalhos C ++

O compilador implementação do resyntaxed C ++ faria, se encontrar uma fonte C ++ fazendo uso de sintaxe ambígua, movimento source.cpp também uma pasta ambiguous_syntax, e criaria automaticamente uma source.cpp traduzido inequívoca antes de compilá-lo.

Por favor, adicione seu C ++ ambíguos sintaxes se você sabe alguma!

Answer 4

Como você pode ver na minha resposta href="https://stackoverflow.com/questions/1172939/is-any-part-of-c-syntax-context-sensitive/1173038#1173038"> , C ++ contém sintaxe que não pode ser deterministamente analisado por um LL ou analisador LR devido ao estágio tipo resolução (tipicamente pós-análise) mudando o ordem das operações , e, portanto, a forma fundamental do AST (normalmente esperado para ser fornecida por uma análise de primeira fase).

Answer 5

Eu acho que você é muito perto da resposta.

LR (1) significa que a análise da esquerda para a direita necessidades apenas um token para olhar em frente para o contexto, enquanto LR (8) significa um infinito olhar em frente. Ou seja, o analisador teria que saber tudo o que estava por vir, a fim de descobrir onde ele está agora.

Answer 6

O problema "typedef" em C ++ pode ser analisado com um LALR (1) parser que constrói uma tabela de símbolos durante a análise (e não um analisador LALR puro). O problema "template" provavelmente não pode ser resolvido com este método. A vantagem deste tipo de LALR (1) é que o analisador gramatical (mostrado abaixo) é um LALR (1) gramática (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 seguinte pode ser analisado sem um problema:

 typedef int x;
 x * y;

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

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