As árvores de sintaxe abstrata podem ser analisadas em tempo subexponencial?

Descrição abstrata do problema

Do meu ponto de vista, analisar significa criar um fluxo de token a partir de um AST, que quando analisado novamente produz um AST igual, ou seja, parse(unparse(AST)) = ASTdeve ser mantido.

É o mesmo que encontrar uma árvore de análise válida que produziria o mesmo AST.

A linguagem é descrita por uma gramática atribuída a S sem contexto, usando uma variante do eBNF.

Portanto, o analisador precisa encontrar um 'caminho' válido através dos nós percorridos, nos quais todas as restrições gramaticais são mantidas. Isso significa basicamente encontrar uma alocação válida de nós AST para regras de produção gramatical. Este é um problema de satisfação de restrição (CSP) em geral e pode ser resolvido, como análise, retornando em .$O(e^n)$

Felizmente para a análise, isso pode ser feito em usando GLR (ou melhor, restringindo a gramática). Como a estrutura AST é tão próxima da estrutura de regras de produção gramatical, fiquei realmente surpreso ao ver uma implementação em que o tempo de execução é pior do que analisar: o XText usa o ANTLR para analisar e retornar para não analisar.$O(n^3)$

Questões

1. Uma gramática de atributo S sem contexto é tudo o que um analisador e analisador precisa compartilhar ou existem outras restrições, por exemplo, na técnica de análise / implementação do analisador?
2. Eu tenho a sensação de que esse problema não é $O(e^n)$ em geral - algum gênio poderia me ajudar com isso?

Não recebi uma resposta para esta pergunta no StackOverflow . Foi sugerido perguntar aqui, mas eu odeio redundância, então espero que você me perdoe por pedir que responda aqui .

Existe uma versão da sua pergunta para a qual é fácil cancelar a análise e pode ser feito em tempo linear. No entanto, não tenho muita certeza se sua pergunta se refere a esta versão específica de não análise, então analisarei isso primeiro.

Você diz em sua pergunta no StackOverflow que seu AST se parece com "AnyObject -> AnyObject -> Vehicle [name =" Car "]". Sua pergunta seria muito mais fácil se o seu AST se parecesse com "Área -> Rodovia -> Carro", isto é, sabemos que produções foram feitas quando o seu AST foi construído / analisado. Em analisadores comuns sem contexto, você (quase) sempre obtém essas informações: pode decidir jogá-las fora, mas (quase) todos os algoritmos de análise também podem fornecer essas informações.

Se você não tiver essas informações, tenho certeza de que o tempo exponencial é o melhor que você pode fazer, a menos que saiba algo sobre suas expressões-S. O problema, então, é simplesmente recuperar o AST "Área -> Rodovia -> Carro", a falta de análise depois é a parte mais fácil.

Se você tiver essas informações, podemos apenas olhar para gramáticas sem contexto e tentar desemparelhá-las. Considere esta gramática:

1: $S \to a$
2: $S \to a S a$

Um AST para esta gramática pode parecer $S \to a (S \to a) a$, na entrada "aaa". É fácil remover a análise deste AST: execute uma caminhada pós-ordem da árvore e produza todos os terminais encontrados nesta caminhada. O resultado é "aaa" novamente.

As coisas se tornam um pouco mais complicadas quando você olha para gramáticas ambíguas e livres de contexto. Por um lado, as coisas ainda são fáceis: basta escolher qualquer árvore de análise de sua entrada e fazer o seguinte: você pode reconstruir todas as outras árvores de análise a partir do resultado.

No entanto, na presença de regras de desambiguação, você precisa fazer algo inteligente. Em particular, a entrada "(1 + 2) * 3" pode ser analisada como "1 + 2 * 3", que é diferente da original. É possível fazer isso em tempo linear em$LR(1)$ gramáticas (onde precedência e associatividade são impostas como no Yacc), fazendo um inverso $LR$analisar em tempo não analisado. Ignorarei os detalhes, pois isso não fez parte da sua pergunta, mas pode ser feito.