массив регексов вместо парсеров-комбинаторов

[juan_gandhi]

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

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

Сегодня смотрю на код на работе, батюшки, массив регексов. Для парсинга документов. А, знакомая картина!!! Автора зовут Нараян, он уже у нас не работает. Образование - пиэчди по компьютерным наукам из University of Texas at Austin. 

Я однажды интервьюировал в Гугле кандидатку оттуда. У нее пиэчди по компьютерным наукам, и я не стал ее спрашивать, может ли она написать регекс для проверки скобок в выражениях, но у нее было "implemented binary search on the internet", и я ее спросил, как это (делит интернет пополам, как физики при ловле льва в пустыне?). Оказывается, она искала в интернете двоичные файлы.

Вот такая херня, коллеги.

Comments

[dijifi]

Честно признаюсь — сам парсил андроилские логи массивом регексов на Питоне. Для прикола программа была одним массивным выражением, так что вопрос о подсчете пробелов не стоял.
Но логи это не язык.

[chaource]

PhD is today's high school diploma.

[sassa_nf]

I would have an array of parsers instead :)

Fast and efficient for conformant HTML, slow and perfect for those that failed the fast and efficient.

[euthanasepam]

Ужасы какие!

[juan_gandhi]

What would you do with <div> inside <div>?

[juan_gandhi]

Логи разве не на регулярном языке пишутся?

[dijifi]

Логи в Андроиде — большая помойка строк. Каждый таракан так и норовит что-нибудь наложить, иногда даже нечто непечатное. Единственное что общее — таймстамп и имя хулиганского процесса в начале строки.

[mikerrr]

И я парсил почтовые сообщения, путем составления массива регэкспов.
Мне надо было из почты доставать одно единственное слово, а форматов сообщений (автоматических) было несколько. Ну для каждого формата получался свой регэксп. А как надо было? Где почитать?

[http://users.livejournal.com/sorcerer-/]

Парсил "логи" не просто массивом регексов, а они туда добавлялись сами с помощью "ML". И все это в 2007 году. Внутри базы данных. Других вариантов не было.

[juan_gandhi]

Все зависит от сложности языка.

[mikerrr]

Английский язык, иногда русский (зависит от офиса)

[juan_gandhi]

Я о сложности языка выражений. Вы ж не парсите структуру фраз, а просто проверяете наличие одного из слов, так? Это регулярный язык.

[mikerrr]

Ну я сделал так: для каждого из типов писем описывал структуру фразы, которая мне нужна. На определенном месте в этой фразе было нужное мне слово (я определял уволили ли человека или он уволился сам). Ну сама фраза была почти произвольной, но в рамках одного офиса, естественно, повторялась (письма писали вручную, но копировали из шаблона)
Получалось как-то так:
"Please note that the following employee has left[^\n]+([^()]+)[^)]+\) Manager"
Но это не суть важно, не думаю что есть смысл вникать в конкретную задачу, просто укажите куда идти и что почитать по этому поводу, если не сложно.

[soid]

Зачем парсить HTML самому когда есть готовые решения? Или он написал универсальный HTML парсер на основе регулярных выражений?

[juan_gandhi]

Ну вот мои слайды (там и линки есть в конце) Регулярные языки КС языки и прочее

[juan_gandhi]

Готовые решения не годятся для malformed HTML. В нашем случае полезная информация вполне могла сидеть в meta. Кроме того, у нас парсер был специализированный. Нам нужна была сущность, а не форма. Например, таблицу можно разными способами нарисовать. А нам нужно было понять, что это таблица и превратить в плоские проперти. Ну и т.д.

Короче, готовых решений нестандартных задач не существует.

[mikerrr]

Спасибо! Изучу

[sassa_nf]

well, it looks like we need to define what the output of a parser is. I was thinking a stream of tokens (which you consume with a stack machine to model tree-like structure), but it looks like you want it to do more.

[soid]

У вас задача обработки естественного языка (NLP), там совсем другие подходы. Вам нужен классификатор какой-нибудь для NLP.

[sassa_nf]

nice!

[mikerrr]

Конечно же нет)

[soid]

Это не готовое решение, это более высокоуровневый инструмент. Есть парсеры которые и с malformed HTML работают, как браузеры это делают (meta это тег?). Делают дерево, а дальше уже с этим деревом можно нестандартную задачу решать.

[soid]

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

[juan_gandhi]

Кстати да.

Я когда-то сначала переводил на doggy English, а потом уже...