Синтаксический анализ CFG с использованием пространства

18

Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)

Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в худшем случае (хотя, по общему признанию, я понятия не имею, каково использование пространства этого алгоритма умножения матриц). Мне было интересно, есть ли какие-либо алгоритмы, которые улучшают это использование пространства (так, не обращая внимания на временные рамки).Ω(n2)

Вопрос возник у меня в голове после того, как мы мысленно связали с пространством Ω ( n 2 ), ограниченным всеми алгоритмами синтаксического анализа CFG Я знал. Это, вероятно, не представляет практического интереса, а просто то, что мне было бы интересно узнать.CSG=NDSPACE(n)DSPACE(n2)Ω(n2)

Алекс тен Бринк
источник
5
Не знаю обо всех других алгоритмах синтаксического анализа, но алгоритмы, основанные на умножении матриц, занимают места; см .: cstheory.stackexchange.com/questions/1313/…Θ(n2)
Райан Уильямс

Ответы:

14

Первая половина этого ответа - не более чем эффективная ( - log 2 ( n ) ) перефразировка ответа Дэвида в терминах теории сложности.log4(n)log2(n)

Контекст свободных языков живут в классе сложности Этот класс эквивалентно характеризуется полунезависимой схемой глубины каротажа . Это схемы полиномиального размера, в которых вентили ИЛИ имеют неограниченную веерность, а вентили И имеют ограниченную веерность (скажем, 2). Увеличивая глубину на логарифмический коэффициент, мы можем заменить каждый неограниченный вентиль OR с ограниченным вентилем OR. Это ставит проблему в N C 2 . Нетрудно увидеть, как N CLOGCFL.NC2. можно оценить с помощью D S P A C E ( log 2 (NC2 скажем, поиск в глубину, который поддерживает последовательность левых / правых детей у изученных до сих пор ворот. Результат восходит к статье Льюиса-Хартманиса. И хотя это улучшает ограничение пространства Дэвида, это может занять n log n времени. Мы не знаем лучше.DSPACE(log2(n))nlogn

Традиционный способ понять компромисс между временем и пространством - это использовать игры с галькой. Там было несколько работ на CYK; более поздняя попытка находится в первой части этой презентации . Здесь показано, что (а) линейное пространство может быть достигнуто за экспоненциальное время и (б) если время ограничено , то CYK будет использовать по крайней мере n 2 пространства.O(n2)n2

Конечно, очень интересная проблема, достойная внимания.

V Vinay
источник
Это была довольно интересная презентация, спасибо за ссылку.
Алекс тен Бринк
13

Любой контекстно-свободный язык может быть описан грамматикой в ​​нормальной форме Хомского, а затем распознан недетерминированным алгоритмом, который использует битов памяти: достаточно угадать производственный ( O ( 1 ) биты) верхнего уровня и точка останова во входной строке между двумя подстроками, совпадающими с двумя сторонами производства ( O ( logO(log2n)O(1)O(logn)

O(log4n)

Дэвид Эппштейн
источник
3
Я только что наткнулся на аналогичный результат Льюиса и соавт. здесь: ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5397245 . Тем не менее, остается вопрос, можем ли мы добиться большего успеха, чем квадратичное пространство, используя только полиномиальное время.
Алекс тен Бринк
8

O(log2n)SC2

Эмиль Йержабек поддерживает Монику
источник