я видел как по регулярным выражениям создают конечный автомат вручную
а как автоматизировать этот процесс ? — выглядит как контекстно свободная грамматика ...
неужели для не Бизон или Yacc применяют?
Здравствуйте, VVVa, Вы писали:
VVV>я видел как по регулярным выражениям создают конечный автомат вручную VVV>а как автоматизировать этот процесс ? — выглядит как контекстно свободная грамматика ... VVV>неужели для не Бизон или Yacc применяют?
Там очень простая грамматика, и она не контекстно-свободная. Парсят парсером, напусанным руками, я полагаю.
Здравствуйте, VVVa, Вы писали:
VVV>я видел как по регулярным выражениям создают конечный автомат вручную VVV>а как автоматизировать этот процесс ? — выглядит как контекстно свободная грамматика ...
Теоретически регулярные выражения начинались с регулярной грамматики, это даже жёстче, чем контекстно-свободная.
Но как только в них появились backreferences, она стала по сути как минимум контекстно-зависимой. Наличие всяких \b или (?!pattern) (так называемый lookbehind) превращает это совсем во что-то своё, не соответствующее ни одному стандартному определению.
Вообще, классификация Хомского это нечто, пригодное только для учебных целей — получения начального представления о некоем каноне, который дальше ломается под тяжестью реальности, но всё равно остаётся полезной умозрительной концепцией. Точно так же, например, с моделью сетей OSI со всеми этими L1...L7 — банальное туннелирование её расщепляет, но чтобы понять, надо вс равно начать думать в её концепциях. Возможно, ещё есть примеры.
VVV>неужели для не Бизон или Yacc применяют?
А всякие штатные regcomp() чем не то?
Как раз внутри и создаётся структура данных для работы конечного автомата.
Или, например, re2c — отличается тем, что вместо таблиц генерирует выходной код c толстыми группами case — соответственно скорость выше за счёт прямой интерпретации.
Здравствуйте, netch80, Вы писали:
N>А всякие штатные regcomp() чем не то? N>Как раз внутри и создаётся структура данных для работы конечного автомата.
N>Или, например, re2c — отличается тем, что вместо таблиц генерирует выходной код c толстыми группами case — соответственно скорость выше за счёт прямой интерпретации.
а как они написаны? они случайно не по готовых таблицах работают ? (которые сгенерированы заранее лексером и парсером)...
Здравствуйте, VjcheslavV, Вы писали:
VV>а как они написаны? они случайно не по готовых таблицах работают ? (которые сгенерированы заранее лексером и парсером)...
Маловероятно. Скорее всего, рекурсивным спуском все разбирается. Например, Java java.util.regex.Pattern. Смотреть на compile() и далее из него. Сама по себе грамматика регулярных выражений для рекурсивного спуска удачная. А еще в результате разбора получаются более-менее вменяемые сообщения об ошибках, которые можно показать пользователю или разработчику. В автоматически сгенерированных LR-парсерах с диагностикой ошибок (в виде, понятном обычному автору исходного текста) дела обстоят не очень хорошо.
Здравствуйте, VjcheslavV, Вы писали:
VV>Здравствуйте, netch80, Вы писали:
N>>А всякие штатные regcomp() чем не то? N>>Как раз внутри и создаётся структура данных для работы конечного автомата.
N>>Или, например, re2c — отличается тем, что вместо таблиц генерирует выходной код c толстыми группами case — соответственно скорость выше за счёт прямой интерпретации.
VV>а как они написаны? они случайно не по готовых таблицах работают ? (которые сгенерированы заранее лексером и парсером)...
Это как раз генераторы, если ты не заметил. Первое, да, создаёт таблицы. Второе — код вместо таблиц.
Здравствуйте, maxkar, Вы писали:
M>Маловероятно. Скорее всего, рекурсивным спуском все разбирается. Например, Java java.util.regex.Pattern. Смотреть на compile() и далее из него. Сама по себе грамматика регулярных выражений для рекурсивного спуска удачная. А еще в результате разбора получаются более-менее вменяемые сообщения об ошибках, которые можно показать пользователю или разработчику. В автоматически сгенерированных LR-парсерах с диагностикой ошибок (в виде, понятном обычному автору исходного текста) дела обстоят не очень хорошо.
Как я заметил там рекурсивный спуск сразу без какой либо токенизации (без применения какого-либо лексера).
Не лучше сначала какни-будь разбить на токены ? и как лучше?
Здравствуйте, VVVa, Вы писали:
M>>Маловероятно. Скорее всего, рекурсивным спуском все разбирается. Например, Java java.util.regex.Pattern. Смотреть на compile() и далее из него. Сама по себе грамматика регулярных выражений для рекурсивного спуска удачная. А еще в результате разбора получаются более-менее вменяемые сообщения об ошибках, которые можно показать пользователю или разработчику. В автоматически сгенерированных LR-парсерах с диагностикой ошибок (в виде, понятном обычному автору исходного текста) дела обстоят не очень хорошо.
VVV>Как я заметил там рекурсивный спуск сразу без какой либо токенизации (без применения какого-либо лексера). VVV>Не лучше сначала какни-будь разбить на токены ? и как лучше?
Что именно в движке регэкспов ты собрался разбивать на токены?
Здравствуйте, netch80, Вы писали:
N>Что именно в движке регэкспов ты собрался разбивать на токены?
Ну большинство токенов по 2 симвала, экранирование и всё такое (например \Q \E вообще как литерал в языках программирования)
Ну например в private static String normalize(String pattern) в этих исходниках везде по 2 символа проверяют...
Здравствуйте, VjcheslavV, Вы писали:
N>>Что именно в движке регэкспов ты собрался разбивать на токены?
VV>Ну большинство токенов по 2 симвала, экранирование и всё такое (например \Q \E вообще как литерал в языках программирования) VV>Ну например в private static String normalize(String pattern) в этих исходниках везде по 2 символа проверяют...
Здравствуйте, VVVa, Вы писали:
VVV>я видел как по регулярным выражениям создают конечный автомат вручную VVV>а как автоматизировать этот процесс ? — выглядит как контекстно свободная грамматика ... VVV>неужели для не Бизон или Yacc применяют?
Перечитав ветку, я, кажется, понял, что тут не так. Коллега, вы не заметили проблему курицы и яйца, а она тут основная.
Чтобы сделать парсер чего-то, нужен синтаксический анализ и, если выделен, лексический анализ. А для лексического анализа обычно строятся регулярные выражения, что именно ловить. Получается, чтобы сделать движок регэкспов, надо сделать движок регэкспов? А начало где? В другом движке? То есть надо иметь для этого готовый скомпилированный?
Ну да, для компилятора C так делают, чтобы не слишком мучаться (и то, варианты "для новой платформы собрали тупой, с ужасным кодом, но надёжный (условный) FooCC, а затем он собрал GCC — вполне нормальны). А вот для регэкспов проще сделать "рукопашный" рекурсивный спуск.
Ну или нужен готовый движок синтаксического анализатора, которому лексический анализатор не включен и он по буквам это разбирает. Причём движок, скорее всего, типа PEG. Ну да, есть такие. Но опять же — зачем, если >99% тонкостей в "бизнес-логике" всех этих матчингов с генерацией таблиц, и внешнее средство для 1% будет гирей на ноге?
Здравствуйте, VVVa, Вы писали:
VVV>я видел как по регулярным выражениям создают конечный автомат вручную VVV>а как автоматизировать этот процесс ? — выглядит как контекстно свободная грамматика ... VVV>неужели для не Бизон или Yacc применяют?
По разному, грамматика там простая. Я пару раз делал парсер на обычной операторной грамматике с приоритетами. Там только одна трудность — оператора конкатенации нет, но чуть подумать и решается. Сам парсер строк на 50.
