Xpoint
   [напомнить пароль]

Найти строку по Регулярному Выражению

Метки: [без меток]
2005-01-18 20:31:09 [обр] Пётр Фомин(0/48)[досье]
Пытаюсь сделать подсветку синтаксиса для различных языков программирования на Javascript.
Сначала сделал её на встроеных регулярных выражениях, но результат меня разочаровал своей скоростью.
Поэтому я решил пойти другим путём и вручную написал ДКА (детерминированный конечный автомат)
 для распознавания лексем языка дельфи. Полученный парсер работал гораздо быстрее предыдущего, однако у него есть один существенный недостаток — трудность редактирования правил по которым распознаются лексемы, так как для этого нужно вручную заново строить матрицу переходов (из одного состояния в другое).
Выходом из положения я видел автоматизацию построение матрицы переходов а также всех остальных частей ДКА по регулярному выражению.
Однако мне удалось реализовать только скрипт который решает задачу принадлежности строки (от начала до конца) регуляному множеству. Но мне нужно решить задачу поиска регВыра в строке. (т.е. узнать начало и конец совпывшего с регвыром текста)
Кое-где я прочел, что задача поиска сводиться к задаче установления принадлежности
строки множеству .*РегВыр.*
Но мне в таком случае непонятно как определить начало и конец найденого регВыра?
спустя 14 часов [обр] Алексей Севрюков(0/1292)[досье]

Пётр Фомин[досье] В Perl есть всякие хитрые переменные которые хранят строку до совпадения и после (насчет точной позиции не вспомню). И все сводится к тому, что мы берем часть строки до совпадения и вычесляем его длину. Длина совпадения нам известна.

Так что надо поискать или в сторону таких переменных, или в сторону переменных, которые содержат позицию начала совпадения в регуле.

спустя 3 часа 51 минуту [обр] Пётр Фомин(0/48)[досье]
Алексей Севрюков[досье]
Обратите внимание, я задал этот вопрос в разделе Теория и алгоритмы а не в регулярных выражениях.
К томуже я занимаюсь реализацией механизма регулярных выражений на языке JavaScript а не на Perl.
(т.к. в JS регЭкспы основаны на медленном НКА (и в перле кстати тоже ))
спустя 1 час 45 минут [обр] Алексей Севрюков(0/1292)[досье]

Пётр Фомин[досье] Я обратил внимание. И Perl взял как пример. И последнее предолжение как раз и есть рекомендация.

Кстати, кто Вам мешает сделать

(.*)(РегВыр)

Тогда Вы получите длину первого куска (начало выражения) и по длине выражения высчислите конец. Сразу я что-то не сообразил.

спустя 9 минут [обр] Владимир Палант(27/4445)[досье]
Алексей Севрюков[досье]
Пётр Фомин[досье] работает с регулярными выражениями формальных языков, а не с регулярными выражениями Perl (которые, строго говоря, регулярными выражениями и не являются) :)
спустя 1 час 5 минут [обр] Александр Самойлов(6/342)[досье]

Пётр Фомин[досье]
правильно ли я понял, что надо просто найти позицию найденного регулярного выражения в строке поиска?

если так

var s = "         regular        "
var re = new RegExp(/regular/)

alert(re.exec(s).index)
спустя 1 час 24 минуты [обр] Пётр Фомин(0/48)[досье]
работает с регулярными выражениями формальных языков, а не с регулярными выражениями Perl (которые, строго говоря, регулярными выражениями и не являются) :)
Кстати Джефри Фридл в своей книге "Регулярные выражения" пишет по этому поводу, что нам следует перейти на термин "нерегулярные выражения" :)
спустя 10 минут [обр] Пётр Фомин(0/48)[досье]
правильно ли я понял, что надо просто найти позицию найденного регулярного выражения в строке поиска?

Да.

если так
var s = " regular "
var re = new RegExp(/regular/)

alert(re.exec(s).index)

Я так Уже делал (я умею обращаться со "встроеными" в JS интерпритатор регулярными выражениями, с этим у меня проблем нет), получилось медленно, так как регЭкспов много.
Речь идёт о реализации собственного механизма регулярных выражений на языке JS.

Вот как это я себе представляю

  1. На входе строка с регулярным вырадением и строку с текстом
  2. Пользуясь этой строкой строю ДКА
  3. Проходясь про тексту один раз и пользуясь при этом ДКА обнаруживаю начало и конец

подстроки.

Проблемма в пункте 3, а стало быть и ставиться под сомнение правильно ли я реализовал пункты 1 и 2.

спустя 11 минут [обр] Пётр Фомин(0/48)[досье]
Чтобы было понятнее уточняю, что
я реализовывал построение ДКА по регулярному выражению пользуясь алгоритмом
который описан тут:
http://www.citforum.ru/programming/theory/serebryakov/3.shtml
Ctrl+F,
3.3.3 Построение детерминированного конечного автомата по регулярному выражению ,
Enter
спустя 15 часов [обр] Александр Самойлов(6/342)[досье]
Пётр Фомин[досье]
Сомнительно, что собственная реализация регулярных выражений на Javascript обойдет встроенную. Разве, что реализация некоторого подмножества регулярных выражений. А методом compile пользовались? Он вроде как ускоряет выполнение.
Можно узнать какая платформа? IE? Mozilla? Или это отдельное приложение?
спустя 9 часов [обр] Пётр Фомин(0/48)[досье]
что реализация некоторого подмножества регулярных выражений.

Об этом и идёт речь. К томуже реги в JS работают на НКА, а я хочу реализовать поиск по ДКА

А методом compile пользовались? Он вроде как ускоряет выполнение.

Пользовалься, не помогло.

Можно узнать какая платформа? IE? Mozilla? Или это отдельное приложение?

IE, Mozilla, Opera
А зачем себя ограничивать заранее, ограничения если они и будут — появяться по ходу работы.

спустя 41 минуту [обр] Пётр Фомин(0/48)[досье]

Кстати, кто Вам мешает сделать
(.*)(РегВыр)

Тогда Вы получите длину первого куска (начало выражения) и по длине выражения высчислите конец. Сразу я что-то не сообразил.

У меня скобки только для групировки, а для сохранения, я бы конечно хакрепил бы ними и функцию сохранения, если бы только знал как.
спустя 10 дней [обр] Дмитрий Котеров(15/912)[досье]
Пётр Фомин[досье], позвольте, а зачем для распознавания Дельфи вообще регулярные выражения? По-моему, там лексемы выделяются и прямо "в лоб" довольно прозрачно (это же касается и многих других языков - C++, Java и т.д.). В данном случае у Вас, мне кажется, из кукушки по воробьям.
спустя 13 часов [обр] Пётр Фомин(0/48)[досье]

Дмитрий Котеров[досье]
Речь идет о создании универсального средства создания автоматов, которые будут подсвечивать подсвечивать исходники на различных языках. Дельфи я привёл в качестве примера.

По-моему, там лексемы выделяются и прямо "в лоб"

Мне бы хотелось добиться однопроходности (каждый символ строки обрабатываеться только один раз) парсера, поэтому этот вариант не катит.

спустя 9 часов [обр] Сергей Чернышев(5/589)[досье]
http://colorer.sourceforge.net/ - вот этот продукт уже видели?
спустя 6 часов [обр] Александр Самойлов(6/342)[досье]
Кстати, у колорера своя, относительно простая, библиотека разбора регвыров, можно попробовать портировать ее на js.
Powered by POEM™ Engine Copyright © 2002-2005