Я недавно читал о парсере Earley и думаю, что это один из самых элегантных алгоритмов, которые я когда-либо видел. Однако алгоритм в его традиционном смысле является распознавателем, а не анализатором, то есть он может определять, соответствует ли строка определенному CFG, но не генерировать для...
Когда я возился с неканоническим анализом LR, я придумал метод синтаксического анализа (с таблицами бесконечного размера, что делает его несколько непрактичным ), способный анализировать ровно однозначные грамматики за времени, и мне было интересно, возможно ли это сделать лучше:O(n2)O(n2)O(n^2)...
Метод производных Бжозовского - очень симпатичная техника для построения детерминированных автоматов из регулярных выражений хорошо алгебраическим способом. Я разработал несколько симпатичных обобщений этого метода для обработки некоторых более крупных классов грамматик, но алгоритмы достаточно...
Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...
Допустим, у меня есть большой блок кода, который я уже проанализировал и проанализировал. Предположим, что меняется только один символ; Я хотел бы обновить мой синтаксический анализ, но поскольку модификация очень мала по сравнению со всем этим, я хотел бы знать, возможно ли не анализировать все...
Кто-нибудь формализовал связь между методами синтаксического анализа с уменьшением сдвига и продолжением с разделителями? При построении снизу вверх анализатора (например, LR парсеры), мы возьмем грамматику , а затем представляют синтаксический анализ состояние как совокупности элементов :...
Поскольку мне интересны парсеры (в основном грамматики выражений парсеров), мне интересно, есть ли какая-то работа, которая дает категорический подход к анализу. Любая ссылка на приложения теории категорий к синтаксическому анализу высоко ценится....
Когда я смотрю на разбор Эрли, он выглядит очень элегантно, и мне интересно, почему методы GLR становятся популярными? Кто-нибудь знает, что не так с парсингом Эрли, который Томита создал GLR? Представление? Любые публикации по этой дискуссии высоко...
Парсеры диаграмм могут быть реализованы на основе нормальной формы Хомского или непосредственно на основе правил производства. Предположим на данный момент, что у нас есть анализатор диаграмм CYK, который использует нормальную форму Хомского. Бинаризация не определяется однозначно. Влияет ли это на...
Один из моих проектов Java является ответвлением пропаренного , и в отличие от, скажем, Antlr или JavaCC, парсеры генерируются во время выполнения. Генерируемые грамматики - это грамматики синтаксического анализа или PEG (я слышал, что для них используется другой термин - «packrat»). Хотя генерация...