Учитывая строку и CFG, какие символы могут следовать за строкой (в предложениях форм CFG)?

10

Пусть множество терминального и N множества нетерминальных символов некоторой контекстно-свободная грамматика G .ΣNG

Скажем , у меня есть строка такое , что х у S ( G ) , где х , у ( Е N ) * и S ( G ) являются сентенциальные формы G .a(ΣN)+ИксaYS(г)Икс,Y(ΣN)*S(г)г

Учитывая , я бы хотел определить множество C = { b w a b z S ( G ) , b Σ N } .гСзнак равно{б|весaбZS(г),бΣN}

Чтобы уточнить, в этом случае являются строками терминалов и нетерминалов, а b имеет длину один.вес,Икс,Y,Z,a,бб

Я могу видеть, как это сделать, если также имеет длину один; каждый b является членом следующего набора a (включая нетерминалы).aбa

Тем не менее, мне любопытно, если это возможно для последовательности символов. Для моего приложения, строка не намного больше , чем с правой стороны производств , в G .aг

Различие между терминалами и нетерминалами в моем приложении несколько немое, потому что я использую генеративную грамматику; и я считаю, что это не приведет к большим проблемам, так как имеет длину один.б

Томас
источник
1
Какова ваша заявка? Вы создаете парсер?
Рафаэль
Можем ли мы предположить, что грамматика в любой нормальной форме или она должна работать для произвольных?
Рафаэль
@AlextenBrink - и y - произвольные строки. Я просто смотрю на фрагмент / подстроку. ИксY
Томас
@Raphael - я пытаюсь автоматизировать преобразования грамматик L-System ... так что это не в нормальной форме. На самом деле я снова отредактирую этот вопрос, чтобы сделать его более точным.
Томас
Я надеюсь, что я не слишком изменил вопрос - сейчас он немного другой.
Томас

Ответы:

6

Я опишу алгоритм, который работает. Это время не должно быть слишком плохо. Вы можете заранее вычислить и это.

Я предполагаю, что не содержит нетерминалов (хотя, вероятно, его легко адаптировать к этому случаю) и что вы не знаете x , y или производную от a . Я также предполагаю, что ваша грамматика не содержит произведений, которые никогда не используются ни при каких производных (например, A A ).aИксYaAA

Основная проблема на самом деле заключается в том, чтобы проанализировать , так как вы хотите знать, в каких состояниях вы оказались, чтобы вы знали, что может последовать за a . Это не так просто, как вы не знаете х .aaИкс

Мы используем адаптацию алгоритма Эрли . Сначала вы захотите понять этот алгоритм. Наш алгоритм работает почти так же, за исключением того, что наши шаги инициализации и завершения отличаются.

Для инициализации, мы семена нашего первого набора с элементом Эрел для каждого вхождения (первом символе в ) в любом производстве вашей грамматики. Мы устанавливаем обратный указатель этого элемента на -1, недопустимое значение. Это важно в нашем измененном завершении. По сути, -1 означает «Я понятия не имею, где это производство было начато».a1a

Теперь мы выполняем алгоритм Эрли отдельно для каждого возможного такого начального элемента Эрли. Мы не можем просто сделать их все одновременно, так как парсинги могут мешать друг другу. Я не могу легко увидеть более быстрый метод, чем возврат назад здесь.

Для шага завершения нам нужно только сделать модификацию для обработки -1 обратного указателя. Поскольку мы завершили производство, происхождение которого мы не знаем, у нас проблемы. Тем не менее, метод , используемый для вычисления Наборы касательноLALр(1) последующего по Pennello и DeRemer спасает нас: то , что нам здесь нужно в точности Наборы касательно последующего . Каждому предмету в этих наборах прогнозирования соответствует положение в грамматике, что, в свою очередь, соответствует возможному продолжению законченного производства.LALр(1)

К сожалению, я не вижу другого выбора, кроме как вернуться сюда еще раз. Для каждой позиции в наборе указателей вы выполняете шаг завершения с этой позицией и продолжаете анализ оттуда. Вы делаете это отдельно для каждого разбора. Обратите внимание, что если ваша грамматика , ваш взгляд вперед будет однозначно определять, в какую позицию вы должны пойти, поэтому вам не нужно возвращаться назад.LALр(1)

a

Изменить: я думаю, что я нашел метод, который устраняет большую часть накладных расходов, введенных при возврате. Мы связываем с каждым элементом Earley набор идентификаторов, которые являются строками, так как нам нужно будет использовать префиксы этих идентификаторов. При инициализации мы добавляем все начальные элементы в набор Earley и связываем уникальный идентификатор с каждым набором.

На этапах сканера и предиктора идентификаторы переносятся на новые элементы. Предметы Earley в том же наборе Earley, которые отличаются только по своим идентификаторам, объединяются путем объединения их идентификаторов. Обратите внимание, что мы можем выполнить шаги сканера и предиктора для этих новых элементов с идентификаторами, не выполняя этот шаг для каждого идентификатора отдельно.

LALр(1)

По сути, мы выполняем возврат с использованием этих идентификаторов, чтобы не выполнять двойную работу на этапах сканера и предиктора.

Алекс тен Бринк
источник
aa
@Thomas Это не так уж сложно: вы просто рассматриваете нетерминал как терминал для этой конкретной позиции в разборе: вы все еще предсказываете и выполняете ее как обычно, но вы также учитываете это при сканировании.
Алекс тен Бринк
Да, действительно - теперь, когда я понимаю ваше решение, это не должно иметь никакого значения.
Томас