Analisando gramáticas arbitrárias sem contexto, principalmente trechos curtos

20

Desejo analisar idiomas específicos do domínio definido pelo usuário. Essas linguagens são tipicamente próximas de notações matemáticas (não estou analisando uma linguagem natural). Os usuários definem sua DSL em uma notação BNF, assim:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

O tipo de entrada 1 + ( 2 * 3 )deve ser aceito, enquanto o tipo de entrada 1 +deve ser rejeitado como incorreto e o tipo de entrada 1 + 2 * 3deve ser rejeitado como ambíguo.

Uma dificuldade central aqui é lidar com gramáticas ambíguas de uma maneira fácil de usar. Restringir que a gramática seja inequívoca não é uma opção: é assim que a linguagem é - a idéia é que os escritores preferem omitir parênteses quando não são necessários para evitar ambiguidade. Desde que uma expressão não seja ambígua, preciso analisá-la e, se não for, preciso rejeitá-la.

Meu analisador deve trabalhar com qualquer gramática livre de contexto, mesmo ambígua, e deve aceitar todas as informações inequívocas. Eu preciso da árvore de análise para todas as entradas aceitas. Para entradas inválidas ou ambíguas, idealmente, quero boas mensagens de erro, mas, para começar, aceitarei o que conseguir.

Normalmente invocarei o analisador em entradas relativamente curtas, com as entradas mais longas ocasionais. Portanto, o algoritmo assintoticamente mais rápido pode não ser a melhor escolha. Eu gostaria de otimizar para uma distribuição de cerca de 80% de entradas com menos de 20 símbolos, 19% entre 20 e 50 símbolos e 1% de entradas mais raras. A velocidade de entradas inválidas não é uma grande preocupação. Além disso, espero uma modificação do DSL em torno de cada 1000 a 100000 entradas; Posso passar alguns segundos processando minha gramática, e não alguns minutos.

Quais algoritmos de análise devo investigar, dados meus tamanhos de entrada típicos? O relatório de erros deve ser um fator na minha seleção ou devo me concentrar na análise de entradas não ambíguas e possivelmente executar um analisador mais lento e completamente separado para fornecer feedback de erro?

(No projeto em que eu precisava disso (um tempo atrás), usei o CYK , que não era muito difícil de implementar e funcionou adequadamente para meus tamanhos de entrada, mas não produziu erros muito agradáveis.)

Gilles 'SO- parar de ser mau'
fonte
Parece ser difícil obter relatórios de erros especialmente bons. Você pode ter mais de uma alteração local que leva a uma entrada aceita no caso de gramáticas ambíguas.
Raphael
Acabei de responder abaixo. É um pouco estranho responder a uma modificação de uma pergunta antiga que já tem uma resposta bem recebida. Obviamente, não devo responder de maneira semelhante, mas os usuários lerão as duas respostas como se estivessem respondendo à mesma pergunta.
babou
Você realmente espera uma mensagem de erro para entrada ambígua, se um usuário gravar x+y+z.
babou
@babou Não mudei a pergunta, apenas adicionei os esclarecimentos solicitados nos comentários (agora excluídos). Para a gramática minúscula apresentada aqui, não especifiquei associatividade +, portanto x+y+zé realmente ambíguo, portanto, errôneo.
Gilles 'SO- stop be evil'
Bem, é a sua última frase, apenas adicionada, mesmo que entre parênteses. Você parece dizer: eu finalmente fiz isso com o CYK, mas não é mais adequado por alguns motivos. E eu me pergunto quais são as razões precisas ... Você é, agora , a pessoa com mais experiência com seu tipo de problema e com a solução que usa, portanto, seria de esperar mais informações suas para que mais respostas fossem fornecidas.
babou

Respostas:

19

Provavelmente o algoritmo ideal para suas necessidades é a análise Generalized LL , ou GLL. Este é um algoritmo muito novo (o artigo foi publicado em 2010). De certa forma, é o algoritmo de Earley aumentado com uma pilha estruturada de gráfico (GSS) e usando o cabeçote de leitura LL (1).

O algoritmo é bastante semelhante ao LL antigo simples (1), exceto que ele não rejeita gramáticas se não forem LL (1): ele apenas tenta todas as análises possíveis de LL (1). Ele usa um gráfico direcionado para cada ponto da análise, o que significa que, se for encontrado um estado de análise que já foi tratado anteriormente, ele simplesmente mesclará esses dois vértices. Isso o torna adequado para gramáticas recursivas à esquerda, diferentemente do LL. Para obter detalhes exatos sobre o funcionamento interno, leia o jornal (é um livro bastante legível, embora a sopa de etiquetas exija alguma perseverança).

O algoritmo tem várias vantagens claras relevantes para suas necessidades em relação aos outros algoritmos de análise geral (que eu conheço). Em primeiro lugar, a implementação é muito fácil: acho que apenas Earley é mais fácil de implementar. Em segundo lugar, o desempenho é bastante bom: na verdade, torna-se tão rápido quanto LL (1) em gramáticas que são LL (1). Em terceiro lugar, recuperar a análise é bastante fácil e verificar se há mais de uma análise possível também.

A principal vantagem da GLL é que ela é baseada no LL (1) e, portanto, é muito fácil de entender e depurar ao implementar, ao projetar gramáticas e ao analisar entradas. Além disso, ele também facilita o tratamento de erros: você sabe exatamente onde possível analisa os processos ociosos e como eles podem ter continuado. Você pode facilmente dar as análises possíveis no ponto do erro e, digamos, os 3 últimos pontos em que a análise é ociosa. Em vez disso, você pode optar por tentar se recuperar do erro e marcar a produção na qual a análise que mais avançou estava trabalhando como 'concluída' para essa análise e ver se a análise pode continuar depois disso (digamos que alguém esqueceu um parêntese). Você pode até fazer isso por, digamos, as 5 análises mais avançadas.

A única desvantagem do algoritmo é que ele é novo, o que significa que não há implementações bem estabelecidas prontamente disponíveis. Isso pode não ser um problema para você - eu mesmo implementei o algoritmo e foi bastante fácil de fazer.

Alex ten Brink
fonte
É bom aprender algo novo. Quando eu precisei disso (alguns anos atrás, em um projeto que gostaria de reviver algum dia), usei o CYK, principalmente porque foi o primeiro algoritmo que encontrei. Como a GLL lida com entradas ambíguas? O artigo não parece discutir isso, mas eu o examinei apenas.
Gilles 'SO- stop be evil'
@Gilles: cria uma pilha estruturada de gráfico e todas as análises (potencialmente exponencialmente numerosas) são representadas de forma compacta neste gráfico, semelhante à maneira como o GLR funciona. Se bem me lembro, o artigo mencionado em cstheory.stackexchange.com/questions/7374/… lida com isso.
Alex-Brink
@Gilles Este analisador de 2010 parece ter que ser programado manualmente a partir da gramática, não muito adequado se você tiver vários idiomas ou se modificar frequentemente o idioma. As técnicas para geração automática a partir da gramática de um analisador geral, seguindo qualquer estratégia escolhida (LL, LR ou outras) e produzindo uma floresta de todos os analisados, são conhecidas há cerca de 40 anos. No entanto, existem problemas ocultos em relação à complexidade e organização do gráfico que representa a análise. O número de análises pode ser pior que exponencial: infinito. A recuperação de erros pode usar técnicas mais sistemáticas e independentes do analisador.
21414
Como a GLL se relaciona com a LL (*) encontrada na ANTLR?
Raphael
6

Minha empresa (Semantic Designs) usou os analisadores GLR com muito êxito para fazer exatamente o que o OP sugere na análise de linguagens específicas de domínio e de linguagens de programação "clássicas", com o nosso DMS Software Reengineering Toolkit. Isso suporta transformações de programa fonte a fonte usadas para reestruturação de programa em larga escala / engenharia reversa / geração de código a frente. Isso inclui o reparo automático de erros de sintaxe de uma maneira bastante prática. Usando o GLR como base, e algumas outras alterações (predicados semânticos, entrada do conjunto de tokens em vez de apenas entrada de token, ...), conseguimos criar analisadores para cerca de 40 idiomas.

Tão importante quanto a capacidade de analisar instâncias completas de idiomas, o GLR também se mostrou extremamente útil na análise de regras de reescrita fonte a fonte . Estes são fragmentos de programa com muito menos contexto que um programa completo e, portanto, geralmente têm mais ambiguidade. Usamos anotações especiais (por exemplo, insistindo que uma frase corresponda a uma gramática específica não-terminal) para ajudar a resolver essas ambiguidades durante / após a análise das regras. Ao organizar o mecanismo de análise GLR e as ferramentas em torno dele, obtemos analisadores para reescrever regras de "grátis", uma vez que temos um analisador para seu idioma. O mecanismo DMS possui um aplicador de regra de regravação interno que pode ser usado para aplicar essas regras para realizar as alterações de código desejadas.

Provavelmente nosso resultado mais espetacular é a capacidade de analisar C ++ 14 completo , apesar de todas as ambiguidades, usando uma gramática livre de contexto como base. Observo que todos os compiladores C ++ clássicos (GCC, Clang) desistiram da capacidade de fazer isso e usam analisadores escritos à mão (que o IMHO os torna muito mais difíceis de manter, mas, então, eles não são problema meu). Usamos esse mecanismo para realizar grandes mudanças na arquitetura de grandes sistemas C ++.

Em termos de desempenho, nossos analisadores GLR são razoavelmente rápidos: dezenas de milhares de linhas por segundo. Isso está bem abaixo do estado da arte, mas não fizemos nenhuma tentativa séria de otimizar isso, e alguns dos gargalos estão no processamento do fluxo de caracteres (Unicode completo). Para construir esses analisadores, pré-processamos as gramáticas livres de contexto usando algo bastante próximo a um gerador de analisador LR (1); isso normalmente é executado em uma estação de trabalho moderna em dez segundos, com grandes gramáticas do tamanho de C ++. Surpreendentemente, para linguagens muito complexas como COBOL e C ++ modernos, a geração de lexers leva cerca de um minuto; alguns dos DFAs definidos no Unicode ficam bastante peludos. Eu apenas fiz Ruby (com uma subgramática completa por seus incríveis regexps) como um exercício para os dedos; O DMS pode processar seu lexer e gramática juntos em cerca de 8 segundos.

Ira Baxter
fonte
@Raphael: O link "mudanças maciças" aponta para um conjunto de trabalhos técnicos no estilo acadêmico, incluindo alguns sobre a reengenharia da arquitetura C ++, um no próprio mecanismo do DMS (bastante antigo, mas descreve bem o básico) e outro no tópico exótico de captura e reutilização de design, que era a motivação original para o DMS (ainda não alcançado, infelizmente, mas o DMS acabou se mostrando bastante útil).
Ira Baxter
1

Existem muitos analisadores gerais sem contexto que podem analisar sentenças ambíguas (de acordo com uma gramática ambígua). Eles têm vários nomes, principalmente programação dinâmica ou analisadores de gráficos. O mais conhecido, e o mais simples, provavelmente é o analisador CYK que você está usando. Essa generalidade é necessária, pois você precisa lidar com várias análises e pode não saber até o fim se está lidando com uma ambiguidade ou não.

Pelo que você diz, eu acho que o CYK não é uma escolha tão ruim. Você provavelmente não tem muito a ganhar adicionando capacidade de previsão (LL ou LR), e pode realmente ter um custo discriminando cálculos que devem ser mesclados em vez de discriminados (especialmente no caso de LR). Eles também podem ter um custo correspondente no tamanho da floresta de análise produzida (que pode ter um papel em erros de ambiguidade). Na verdade, embora não tenha certeza de como comparar formalmente a adequação dos algoritmos mais sofisticados, sei que o CYK oferece um bom compartilhamento de computação.

Agora, não creio que exista muita literatura sobre analisadores gerais de CF para gramáticas ambíguas que devem aceitar apenas contribuições não ambíguas. Não me lembro de ter visto nenhum, provavelmente porque, mesmo para documentos técnicos ou mesmo linguagens de programação, a ambiguidade sintática é aceitável desde que possa ser resolvida por outros meios (por exemplo, ambiguidade nas expressões do ADA).

Na verdade, estou me perguntando por que você deseja alterar seu algoritmo, em vez de manter o que possui. Isso pode me ajudar a entender que tipo de mudança poderia ajudá-lo melhor. É um problema de velocidade, é a representação de analisa ou é a detecção e recuperação de erros?

A melhor maneira de representar várias análises é com uma floresta compartilhada, que é simplesmente uma gramática sem contexto que gera apenas sua entrada, mas com exatamente as mesmas árvores de análise que a gramática DSL. Isso torna muito fácil entender e processar. Para mais detalhes, sugiro que você analise esta resposta que dei no site linguístico. Entendo que você não está interessado em obter uma floresta de análise, mas uma representação adequada da floresta de análise pode ajudá-lo a fornecer mensagens melhores sobre qual é o problema da ambiguidade. Também pode ajudá-lo a decidir que a ambiguidade não importa em alguns casos (associatividade) se você quiser fazer isso.

Você mencionou as restrições de tempo de processamento de sua gramática DSL, mas não deu nenhuma dica sobre seu tamanho (o que não significa que eu poderia responder com números que você fez).

Algum processamento de erro pode ser integrado nesses algoritmos gerais de CF de maneiras simples. Mas eu precisaria entender que tipo de processamento de erro você espera ser mais afirmativo. Você tem alguns exemplos?

Estou um pouco à vontade para falar mais, porque não entendo quais são realmente suas motivações e restrições. Com base no que você diz, eu continuaria com o CYK (e conheço os outros algoritmos e algumas de suas propriedades).

babou
fonte