Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Распараллеливание лексического анализатора.

Автор: neutrino 24.11.2010, 14:08

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

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

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

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

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

Автор: Sartorius 24.11.2010, 15:43

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

Автор: W4FhLF 24.11.2010, 16:20

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 */ }

Автор: neutrino 24.11.2010, 18:34

Sartorius,

Цитата(Sartorius @ 24.11.2010, 14:43

)

Можно навстречу идти с начала и с конца файла))

Интересная идея! smile

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

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

W4FhLF,

Цитата(W4FhLF @ 24.11.2010, 15:20

)

Можно ли без парсинга двух блоков целиком уточнить границы сочленяющей их лексемы

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

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

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

Автор: neutrino 24.11.2010, 19:30

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

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

Код


int pos;
for (pos = i; pos < chunk.length; pos++)
{
    if (tryParseToken(buffer1, pos)) break;
}

// We found that there is some token starting at pos
// Now, we should ensure it is not a part of some other longer token (for example, assume there are two legal tokens: abcd, cd and we found cd)

int negpos;
for (negpos = i; negpos > 0; negpos--)
{
    if (tryParseToken(buffer0, negpos)) break;
}

// Now there are several possible cases:
// 1) Token from negpos to pos and token from pos to whatever are two distinct tokens having nothing in common
// 2) the second token (from pos to whatever) is suffix of first token (like in case I've described above)

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

Автор: gcc 24.11.2010, 20:02

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

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

Автор: maxim1000 24.11.2010, 20:15

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

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

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

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

Автор: theworldcreator 24.11.2010, 23:35

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

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

Автор: ksnk 25.11.2010, 00:03

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

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

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

Автор: neutrino 25.11.2010, 10:23

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

gcc, Huh? o_O

maxim1000,

Цитата(maxim1000 @ 24.11.2010, 19:15

)

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

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

theworldcreator,

Цитата(theworldcreator @ 24.11.2010, 22:35

)

необходим анализ регулярных выражение на самую длинную лексему

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

ksnk,

Цитата(ksnk @ 24.11.2010, 23:03

)

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

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

Автор: W4FhLF 25.11.2010, 13:45

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

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

Автор: neutrino 25.11.2010, 15:14

Цитата(W4FhLF @ 25.11.2010, 12:45

)

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

Тащи

Цитата(W4FhLF @ 25.11.2010, 12:45

)

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

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

Автор: neutrino 29.11.2010, 12:41

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

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

Цитата(neutrino @ 29.11.2010, 11:41

)

1) запросить у пользователя все токены для которых существуют другие токены в которых они являются под-токенами (т.е. если есть токен "абвгде" и есть токены: "а", "в", "где"; то их нужно передать).

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

Автор: neutrino 12.12.2010, 18:45

Апдейт.

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

Код


void main()
{
    int a = 5;
    int b = 15; // int b = 8; b+=a; b--;
    int c = 0;

    for (int i = a; i < b; i++)
    {
        c += i * a/b;
    }
}

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

Автор: gcc 12.12.2010, 22:38

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

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

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

Автор: neutrino 13.12.2010, 10:13

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