Реализация "*?" (ленивый "*") шаблон регулярных выражений в комбинаторных парсерах GLR

Question

Я реализовал комбинаторные парсеры GLR. Среди них:

• char(·) синтаксический анализатор, который потребляет указанный символ или диапазон символов.
• many(·) комбинатор, который повторяет указанный синтаксический анализатор от нуля до бесконечного времени.

Пример: "char('a').many()" будет соответствовать строке с любым числом "a" -s.

Но комбинатор many(·) является жадным, поэтому, например, char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}') (где ">>" - последовательная цепочка синтаксических анализаторов) будет успешно использовать всю строку "{{foo}}some{{bar}}".

Я хочу реализовать ленивую версию many(·), которая при использовании в предыдущем примере будет потреблять только "{{foo}}". Как я могу это сделать?

Edit:

Может быть, я вас всех запутал. В моей программе парсер - это функция (или «функтор» в терминах C ++), которая принимает «шаг» и возвращает лес «шагов». «Шаг» может иметь тип OK (это означает, что синтаксический анализатор успешно использовал часть ввода) и тип FAIL (это означает, что синтаксический анализатор обнаружил ошибку). Есть несколько типов шагов, но они вспомогательные.

Parser = f(Step) -> Collection of TreeNodes of Steps.

Поэтому, когда я анализирую ввод, я:

• Составьте простые предопределенные функции Parser для получения сложной функции Parser, представляющей требуемую грамматику.

• Форма начального шага со входа.

• Дайте начальный шаг для комплексной функции Parser.

• Фильтрация узлов дерева с шагами, оставляя только OK (или с минимальными ошибками, если были ошибки при вводе).

• Соберите информацию из оставшихся шагов.

Answer 1

Я реализовал и использую парсеры GLR в течение 15 лет в качестве внешнего интерфейса для системы преобразования программ.

Я не знаю, что такое "комбинаторный парсер GLR", и я незнакомс вашей записью, так что я не совсем уверен, как это интерпретировать.Я предполагаю, что это какая-то запись функции с карри?Я представляю, что ваши правила комбинатора эквивалентны определению грамматики в терминах терминальных символов, где "char ('a'). Many" соответствует правилам грамматики:

 char = "a" ;
 char = char "a" ;

парсеры GLR, действительно, производятвсе возможные разборы.Ключевым моментом анализа GLR является его псевдопараллельная обработка всех возможных синтаксических анализов.Если ваши «комбинаторы» могут предлагать несколько разборов (то есть они вырабатывают правила грамматики, своего рода эквивалентные вышеприведенным), и вы действительно подключаете их к анализатору GLR, все они будут испытаны, и только те последовательности произведений, которые выкладываютсятекст выживет (то есть все действительные разборы, например, неоднозначные разборы) сохранятся.

Если вы действительно внедрили синтаксический анализатор GLR, этот набор всех возможных разборов должен был быть для вас предельно понятен.Тот факт, что это не говорит о том, что вы реализовали, не является синтаксическим анализатором GLR.

Восстановление ошибок с помощью синтаксического анализатора GLR возможно, как и с любой другой технологией синтаксического анализа.То, что мы делаем, - это сохраняем множество живых разборов до точки ошибки;когда обнаружена ошибка, мы пытаемся (в psuedo-параллельном механизме синтаксического анализа GLR это легко сделать, если она правильно согнута) все следующее: а) удаление токена-нарушителя, б) вставка всех токенов, которые по существу являются следующими (x)где х это живой анализ.По сути, удалите токен или вставьте тот, который ожидается при живом разборе.Затем мы снова отключаем анализатор GLR.Только действительные разборы (например, ремонт) выживут.Если текущий токен не может быть обработан, анализатор, обрабатывающий поток с удаленным токеном, остается в живых.В худшем случае восстановление парсера GLR приводит к сбросу всех токенов в EOF.Серьезным недостатком этого является то, что время работы анализатора GLR довольно радикально увеличивается при анализе ошибок;если их много в одном месте, время восстановления после ошибки может пройти через крышу.

Answer 2

Разве анализатор GLR не произведет все возможные синтаксические анализ входных данных?Тогда для устранения неоднозначности нужно выбрать тот синтаксический анализ, который вы предпочитаете.Я полагаю, что для этого элементы леса разбора должны быть помечены в зависимости от того, какой комбинатор их создал, нетерпеливый или ленивый.(Вы не можете разрешить неоднозначность постепенно, пока не увидите все входные данные, в общем.)

(Этот ответ основан на моей слабой памяти и смутном возможном недопонимании анализа GLR. Надеюсь, кто-нибудь из экспертов придет.)

Answer 3

Нежадная функциональность - не что иное, как механизм устранения неоднозначности.Если у вас действительно есть обобщенный синтаксический анализатор (который не требует устранения неоднозначности для получения результатов), тогда «нежадность» не имеет смысла;те же результаты будут возвращены независимо от того, является ли оператор «не жадным».

Нежадное поведение устранения неоднозначности можно применить ко всему набору результатов, предоставленному обобщенным анализатором.Работая слева направо, отфильтруйте неоднозначные подгруппы, соответствующие не жадному оператору, чтобы использовать самое короткое совпадение, которое все же привело к успешному анализу оставшегося ввода.

Answer 4

Рассмотрим регулярное выражение <.*?> и ввод <a>bc<d>ef.Это должно найти <a>, и никаких других совпадений, верно?

Теперь рассмотрим регулярное выражение <.*?>e с тем же вводом.Это должно найти <a>bc<d>e, верно?

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

Один ответ для каждого синтаксического анализатора - последовательность всех парсетов, упорядоченных по предпочтениюа не неупорядоченный набор всех парсеров.Жадное совпадение вернет совпадения, отсортированные от самого длинного до самого короткого;не жадный, самый короткий до самого длинного.