Приветствую!

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

Для тех, кто не помнит что такое лексический анализ, напомню: лексический анализ занимается тем, что берет поток байт и "нарезет" его на токены. Токены задаются с помощью регулярных выражений. Например возьмем строку: "float square(float x) { return  x*x; /* calculate square */ }", то один из возможных результатов лексического анализа будут лексемы: "float", " ", "square", "(", "float", " ", "x", ")", " ", "{", " ", "return", " ", "x", "*", "x", ";", " ", "/* calculate square */", " ' "}"

Можно например считать файл по частям и каждую часть анализировать отдельно. Проблема распараллеливания заключается в том, что я не могу знать где закончится лексема, пока она полностью не будет прочитана. Скажем такой токен как КОММЕНТАРИЙ может начинаться в одном куске и заканчиваться в другом, таким образом я не могу знать откуда начинать анализ второго куска, ведь если я начну с неправильного места, то либо получу ошибку (что еще хорошо, хотя иди знай ошибка была из-за неправильного начала или действительно ошибка в данных), либо получу неправильный результат анализа.

Буду благодарен любым идеям (мои уже все исчерпал).

Можно навстречу идти с начала и с конца файла))
В целом действительно задача не тривиальная, т.к. что бы разделить данные на части для параллельных задач их нужно сначала обработать...
У вас такие большие файлы? Может разбивать на отдельные модули и их парсить параллельно?

neutrino, дело в том, что существуют разные уровни распараллеливания. На примере задачи парсинга это можно описать следующим образом.

Допустим, у тебя есть 5 пакетов документов. В каждом из пакетов 10 документов. В каждом документе по 100 блоков в каждом из которых 1000 лексем. Так вот параллельная обработка возможна как на уровне пакетов, так и на уровне лексем (о чём ты здесь, собственно, и спрашиваешь). Сказать заранее какой уровень даст оптимальный коэффициент прироста производительности -- сложно. It depends. 

По теме такой к тебе вопрос. Насколько я понял, не существует возможности уточнить границы лексемы которой заканчивается/начинается некий блок? Например у тебя есть:
"float square(float x) { return  x*x; /* calculate square */ }"

Ты делишь на два блока:
float square(float x) { ret
urn  x*x; /* calculate square */ }

Т.е. мы "отрезали" данные неудачно. Можно ли без парсинга двух блоков целиком уточнить границы сочленяющей их лексемы, чтобы получить вот это:
float square(float x) { 
return  x*x; /* calculate square */ }

Sartorius, 

Интересная идея!  Но:
1) не масштабируемо
2) нужно строить для всех регекспов обратные автоматы

Однако я не догадался до этого 

W4FhLF, 

Думаю детерминизма тут не будет. Может какой-нибудь рандомальный алгоритм можно смастрячить, который с большой вероятностью может так нарезать как надо.

Например:
0) допустим граница буфера проходит в позиции Х
1) попробовать пропарсить с Х 
2) попробовать пропарсить с первого символа после Х (Х + 1)
...
Как только получилось что-то пропарсить, можно предположить, что лексема найдена и поделить в этом месте.

Сложность? В худшем случае - длина буфера. В среднем - средняя длина токена. Вроде ничего, но если например есть три токена: аа, ааа и пробел? Допустим наш файл содержит:
аа ааа аааа аа аа  (т.е. лексемы 1 3 2 3 1 1 3 1 3 1, 1=аа, 2=ааа, 3=пробел)
Допустим поделили так:
аа ааа а
ааа аа аа
Правильно, что в первом буфере есть неправильная лексема - а, но мы об этом узнаем только после того, как пропарсим оба буфера (мы ведь делаем это параллельно).
Значит при "нарезке" файла на куски надо смотреть на лексемы в обе стороны.
Вот с комментами это будет работать очень плохо, т.к. комменты очень длинные и придется далеко ходить, чтобы искать конец.

Для простоты допустим, что мы делим на два куска наш мега файл. Делим мы его по принципу "как хочется", допустим на куски размером по 4 МБ.
Далее нам нужно сделать fine tuning для нашей границы, т.е. определить в правиьлном ли месте мы провели черту. Делаем это следующим образом:

Допустим мы поделили в месте i:


Черт только сейчас увидел, что и это решение не подходит - тот пример в предыдущем посте с аа и ааа не пройдет. 

neutrino, готовое решение нельзя найти?

я видел на регулярных выражениях экспериментально PlusPlus - [Delphi|VB|Java]-like Perl preprocessor
README
PlusPlus.pm


Это сообщение отредактировал(а) gcc - 24.11.2010, 23:54

не знаю, насколько это можно распространить на что-то кроме поиска комментариев, но возникла такая идея:

делим файл на две половины
на первой половине всё просто - запускаем парсер в обычном режиме
на второй половине есть непонятность - является ли первый символ комментарием или нет?
запускаем два парсера: один будет думать, что начинает с комментария, второй - что с кода
когда первый парсер закончит, мы будет знать, результаты какого анализа второй половины нам нужны

естественно, не в два раза быстрее, а в полтора, ну и памяти больше, но хоть что-то 

кстати, если делить на более мелкие куски, могут стать возможны дополнительные отсечения, но тут уже сложнее...

Есть не очень красивая идея, но всё же:
вначале удаляем комментарии без регулярок, чтобы избавится от неограниченно длинных кусков за хорошее время
ε - самая длинная лексема
затем хотим провести границе на символе X, берем ε окрестность X и ищем первую лескему регулярками, получаем правильное разделение за не очень плохое время.

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

Некоторые комментарии начинаются с начала строки и оканчиваются переводом строки. 
так что парсить с конца файла может оказаться сложнее.

Добавлено через 2 минуты и 52 секунды
если предварительно выкидывать комментарии, то можно просто выкидывать первый токен как подозрительный и нчинать реальны парсинг со следующего токена. 

при выкидывании комментариев выкидывается также и информация о расположении лексем в файле. Что сильно будет мешать при выводе сообщений об ошибке.

Спасибо всем ответевшим!

gcc, Huh? o_O


maxim1000, 

Дело в том, что я пишу генератор парсеров и посему я понятия не имею какие имено токены будут. Мне нужно решение для общего случая. Вот и долбаюсь :(


theworldcreator, 

Это невозможно, т.к. могут быть лексемы (например тринговые константы), которые как-бы неограничены в длине.


ksnk, 

Опять же, мне не известны сами токены. Пример с кодом С++ я привел только для "понюхать" 

Когда-то я натыкался на статью по реализации КА на GPU. Т.е. как-то их распараллеливают. Могу поискать, но насколько я понял проблема не в этом? 

Я не зря в прошлом своём сообщения упомянул про уровни распараллеливания, может следует подняться на уровень выше. 

Тащи 



Если парсятся несколько файлов, то можно конечно каждый файл лексить отдельно. Но:
1) не всегда есть несколько файлов
2) может быть такое, что пропарсить второй файл нельзя, т.к. у него есть какие-то зависимости с первым файлом. Тогда куда складывать лексемы второго файла? Держать в памяти? 

Короче пока что единственный способ:
1) запросить у пользователя все токены для которых существуют другие токены в которых они являются под-токенами (т.е. если есть токен "абвгде" и есть токены: "а", "в", "где"; то их нужно передать).
2) определить предположительную границу разделения (например 4 МБ)
3) Выполнить этот fine tuning, описанный выше, НО ТОЛЬКО НЕ ДЛЯ ТОКЕНОВ ИЗ 1)

Добавлено через 1 минуту

Хмм... Вполне можно это автоматизировать, ведь у меня есть автомат...

Апдейт.

Ничего у меня не получилось. Выходит так, что если я напорюсь на такой случай с комментом:



то разрезав этот код где-нибудь в комменте получу неправильный парсинг. Единственное решение, которое я вижу - совет Максима. Начать парсить как в комменте и как не в комменте и когда предыдущий кусок найдет "//", то выбрать тот, что с комментом. Теперь интересно как эту идею обобщить для любого набора токенов заданных регекспами...

neutrino, а зачем тебе нужна скорость? 
если файл исходников будет большой 4М, это будет долго компилироватся в любом случае...

почему бы не написать демон который распарсит один раз файлик и будет выполнять это много раз?

большие Си библиотеки могут очень медленно инициализироваться, можно их поставить в apache (есть API) или в HTTP::Daemon, где парсить и компилировать файл будет только при старте демона



Это сообщение отредактировал(а) gcc - 12.12.2010, 22:50

Я пишу генератор разного рода парсеров (LL(k), LR(1), LALR, GLR),  а не компилятор.