Recentemente, eu estava lendo o analisador Earley e acho que é um dos algoritmos mais elegantes que já vi até hoje. No entanto, o algoritmo em seu sentido tradicional é um reconhecedor e não um analisador, o que significa que ele pode detectar se uma sequência corresponde a um CFG …
25 fl.formal-languages parsing
1
Todas as gramáticas inequívocas podem ser analisadas em tempo linear?
Ao mexer na análise de LR não-canônica, pensei em um método de análise (com tabelas de tamanho infinito, o que o torna um tanto impraticável ) capaz de analisar exatamente as gramáticas inequívocas no tempo , e me perguntei se é possível fazer melhor. :O ( n2)O(n2)O(n^2) Todas as gramáticas …
22 reference-request fl.formal-languages time-complexity parsing context-free
3
CFG análise utilizando espaço
Existem vários algoritmos que podem analisar uma gramática livre de contexto em . Usando a multiplicação de matrizes, pode-se até assintoticamente mais rápido que isso.O ( n3)O(n3)O(n^3) No entanto, todos os algoritmos para analisar CFGs arbitrários que eu conheço têm um uso de espaço no pior dos casos de (embora, …
18 ds.algorithms fl.formal-languages space-bounded parsing context-free
3
Generalizações do método de Brzozowski de derivadas de expressões regulares para gramáticas?
O método de derivadas de Brzozowski é uma técnica muito bonita para construir autômatos determinísticos a partir de expressões regulares de uma maneira bastante algébrica. Eu elaborei algumas generalizações engraçadas dessa técnica para lidar com algumas classes maiores de gramática, mas os algoritmos são simples o suficiente para que pareça …
18 reference-request fl.formal-languages parsing
2
Frases de permutação com análise de LR
Uma frase de permutação é uma extensão das definições gramaticais livres de contexto (E) BNF: uma frase de permutação contém produções (ou equivalentes, não terminais) a . Na posição da frase de permutação, gostaríamos de ver cada uma dessas produções exatamente uma vez, mas não estamos interessados ​​em ordenar essas …
16 ds.algorithms fl.formal-languages parsing context-free
2
Algoritmo eficiente para atualizar uma árvore de análise
Digamos que eu tenho um grande bloco de código que já lexei e analisei. Suponha que apenas um caractere mude; Gostaria de atualizar minha análise, mas como a modificação é muito pequena em comparação com a coisa toda, gostaria de saber se é possível não analisar a coisa toda novamente, …
14 fl.formal-languages parsing
2
Categoria teoria e analisadores - referências desejadas
Como estou interessado em analisadores (principalmente em gramáticas de expressão do analisador), estou me perguntando se há algum trabalho que forneça um tratamento categórico para a análise. Qualquer referência sobre aplicações da teoria de categorias à análise é altamente apreciada. melhor,
13 reference-request functional-programming ct.category-theory parsing
1
Relação entre análise de redução por turno e continuações delimitadas?
Alguém formalizou a relação entre técnicas de análise de redução de turnos e continuações delimitadas? Ao construir um analisador de baixo para cima (por exemplo, analisadores LR), pegamos uma gramática e, em seguida, representamos estados de análise como conjuntos de itens : produções aumentadas da forma , onde α e …
13 pl.programming-languages parsing
1
Por que Tomita criou o GLR e não usou Earley?
Quando olho para a análise de Earley, ela parece muito elegante e me pergunto por que as técnicas de GLR se tornam populares? Alguém sabe o que havia de errado com Earley analisando que Tomita criou o GLR? Atuação? Todas as publicações sobre essa discussão são muito apreciadas.
11 parsing
4
Bons livros sobre a teoria do analisador?
Um dos meus projetos Java é uma bifurcação de analisadores parboilizados e, diferentemente do Antlr ou JavaCC, os geradores são gerados em tempo de execução. Gramáticas geradas são Gramáticas de Expressão de Análise ou PEGs (ouço outro termo para elas é "packrat"). Enquanto a geração de tempo de execução adiciona …
9 research-practice books parsing
2
Método de forma normal de Chomsky: implicações no desempenho do analisador CYK?
Os analisadores de gráficos podem ser implementados com base na forma normal de Chomsky ou diretamente com base nas regras de produção. Vamos, por enquanto, supor que temos um analisador de gráfico CYK que usa a forma normal de Chomsky. A binarização não está definida exclusivamente. Isso afeta o desempenho …
9 fl.formal-languages parsing
1
Correspondência de expressão regular de tempo totalmente linear
Existe um algoritmo para verificar se uma expressão regular de tamanho corresponde a uma string de tamanho , assumindo um alfabeto de tamanho fixo, se isso importa?O ( n + m )O(n+m)O(n+m)nnnmmm O algoritmo NFA padrão é pior caso de . Groz et al. obtenha tempo linear para uma variedade …
8 regular-expressions parsing
Ao utilizar nosso site, você reconhece que leu e compreendeu nossa Política de Cookies e nossa Política de Privacidade.