Вырезать html-форматирование из документа

[NickLion]

а может, грамотные товарищи объяснят, в чём разница между абстрактным конечным автоматом, про который упоминает уважаемый NickLion, и конечными автоматами, используемыми, например, в sed/perl (недетерминированные к.а.) и awk (детерминированный к.а.)?

Разница в синтаксисе. Описании. Как разница между C++ и Лиспом. К тому же самописный КА проще нагрузить дополнительными фичами. Тот же магазинный автомат не реализуется на регекспах нормально, с дополнительными затратами на время.

[sash-kan]

Разница в синтаксисе. Описании. Как разница между C++ и Лиспом. К тому же самописный КА проще нагрузить дополнительными фичами. Тот же магазинный автомат не реализуется на регекспах нормально, с дополнительными затратами на время.

надеюсь, здесь присутствующие математики вас поняли.

[drBatty]

И написание транслятора займёт намного меньше сил, времени, будет работать не хуже придуманных регекспов, и работать быстрее.

это только если вы регэкспы знаете намного хуже Qt.

Чтобы обработать так, как самому хочется, а не так, как автор готового парсера решил. drBatty, поправьте, если неверно Вас понял.

именно так. к тому-же, что-бы выдрать ссылки из HTML вместе с md5 суммами (которые под тегом <code>) мне сегодня понадобилось 15 минут (какой-то движок странный, теги рвал неудачно по разным строкам, одним egrep'ом не отделаться было), то вот писать на Qt... Сначала надо вспомнить где у мну kDevelop, потом выяснится что там нет нужных либ и/или шаблонов, потом выяснится, что они есть, но не те (старые), потом надо искать/качать, потом... короче пол-дня... а потом это всё будет за собой тянуть чуть менее чем всё KDE?! увольте-с... Я понимаю - браузер делать, или хотя-бы файлокачалку... Но на такую разовую задачку?...

А konqueror разве не браузер?

а... точно... у самого такой есть :)

Регекспы - не лучшее решение. В данном случае. ИМХО, тут лучше всё же КА.

вроде как в sed и реализован КА. а самих регэкспов в sed как раз и нет - она юзает те, что в glibc зашиты. хотя да, там что-то с детерминированным.. ну короче sed это один из самых ЯП, который ещё и полный к тому-же. Имеется как раз минимум:

1)команда перехода
2)команда условного перехода
3)одна переменная (а куда больше?)
4)ну и на всякий случай - команда прерывания.

Кстати, на рекурсивный разбор HTML тегов мне этого хватило, но код приводить не буду - тут sed конечно не слишком красиво выглядит (:

А регекспов в sed нету... Можете сами исходники глянуть...

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

и на sed не реализуется - она на очередь заточена, которая FIFO. просто команд таких нет - есть "оторвать голову", и есть "добавить в хвост" (:

[t.t]

Разница в синтаксисе. Описании. Как разница между C++ и Лиспом. К тому же самописный КА проще нагрузить дополнительными фичами. Тот же магазинный автомат не реализуется на регекспах нормально, с дополнительными затратами на время.

надеюсь, здесь присутствующие математики вас поняли.

Нет, не поняли. (:

Как можно всерьёз обсуждать разницу в синтаксисе, говоря об _абстрактном_ КА? Откуда вообще понятие "синтаксис" в этом контексте?

Что такое "магазинный автомат"?

Что Вы имеете ввиду под регэкспами? Строго говоря, даже s-выражения -- это уже не регэкспы. А уж тем более непонятна подразумеваемая прямая связь между регэкспами и языками sed или awk в целом.

[drBatty]

Как можно всерьёз обсуждать разницу в синтаксисе, говоря об _абстрактном_ КА? Откуда вообще понятие "синтаксис" в этом контексте?

ну это к математикам, я тоже не понял (:

Что такое "магазинный автомат"?

LIFO видимо...

Что Вы имеете ввиду под регэкспами? Строго говоря, даже s-выражения -- это уже не регэкспы. А уж тем более непонятна подразумеваемая прямая связь между регэкспами и языками sed или awk в целом.

согласен.

[t.t]

Как можно всерьёз обсуждать разницу в синтаксисе, говоря об _абстрактном_ КА? Откуда вообще понятие "синтаксис" в этом контексте?

ну это к математикам, я тоже не понял (:

Вот я, как математик по образованию, автора и переспрашиваю.

Что такое "магазинный автомат"?

LIFO видимо...

Это терминология под влиянием старой шутки? "Автомат Калашникова -- это преобразователь стека в очередь"? Других ассоциаций между LIFO (стеком) и магазином у меня не возникает. (:

[drBatty]

Это терминология под влиянием старой шутки? "Автомат Калашникова -- это преобразователь стека в очередь"? Других ссоциаций между LIFO (стеком) и магазином у меня не возникает. (:

игра слов - "автоматный магазин". В АКМ'е он именно LIFO, это даже такой дембель из стройбата как я знает (:

[t.t]

Это терминология под влиянием старой шутки? "Автомат Калашникова -- это преобразователь стека в очередь"? Других ссоциаций между LIFO (стеком) и магазином у меня не возникает. (:

игра слов - "автоматный магазин". В АКМ'е он именно LIFO, это даже такой дембель из стройбата как я знает (:

Ну да, я примерно о том и говорю. Это и я знаю, хотя в армии не служил по состоянию здоровья.

[NickLion]

И написание транслятора займёт намного меньше сил, времени, будет работать не хуже придуманных регекспов, и работать быстрее.

это только если вы регэкспы знаете намного хуже Qt.

Я просто не думаю, что сразу получится предусмотреть все случаи. Конечно, если практика регекспов велика, то да...

Регекспы - не лучшее решение. В данном случае. ИМХО, тут лучше всё же КА.

вроде как в sed и реализован КА. а самих регэкспов в sed как раз и нет - она юзает те, что в glibc зашиты. хотя да, там что-то с детерминированным.. ну короче sed это один из самых ЯП, который ещё и полный к тому-же. Имеется как раз минимум:
...

Ну, так речь шла о регекспах. Я с sed не очень много работал. Мне проще perl -e '...' Да и pcre привык юзать.

Как можно всерьёз обсуждать разницу в синтаксисе, говоря об _абстрактном_ КА? Откуда вообще понятие "синтаксис" в этом контексте?

Самый простой. Вход - сама строка. Выход - текст без разметки. Состояния свитчем, дуги тоже свитчем. Что-то типа (это псевдо-код):

Код: Выделить всё

enum states { text, tagname, tagspace, attr, attris, attrvalue, attrquote... };
std::stack< char > st;
std::string tagName;
states state = text;
for( char c = next_char(); c; c = next_char() ) {
  switch( state ) {
  case text:
    switch( c ) {
    case '<':
      state = tagname;
      tagName = "";
      break;
    default:
      printf( "%c", c );
      break;
    }
    break;
  case tagname:
    switch( c ) {
    case ' ': case '\t':
      state = tagspace;
      break;
    default:
      tagName += c;
      break;
    }
    break;
...
  case attris:
    switch( c ) {
    case '\'': case '"':
      stack.push( c );
      state = attrquote;
      break;
    case ' ': case '\t':
      break;
    default:
      state=attrvalue;
      break;
    }
    break;
  case attrquote:
    if( c == stack.top() ) {
    ....
    }
    break;
...
  }
}

Что такое "магазинный автомат"?

drBatty правильно ответил:

LIFO видимо...

Это терминология под влиянием старой шутки? "Автомат Калашникова -- это преобразователь стека в очередь"? Других ассоциаций между LIFO (стеком) и магазином у меня не возникает. (:

Не знаю под чьим влиянием, но она общепризнанная. И на дискретке мы их учили именно под таким названием.
http://ru.wikipedia.org/wiki/Автомат_с_магазинной_памятью

Что Вы имеете ввиду под регэкспами? Строго говоря, даже s-выражения -- это уже не регэкспы. А уж тем более непонятна подразумеваемая прямая связь между регэкспами и языками sed или awk в целом.

Не очень знаком с sed, вообще не знаком с awk. Сужу о регекспах по perl в основном. На одних регекспах в такой задаче сидеть неудобно. О катастрофическом падении скорости в некоторых случаях знаком не по наслышке.

PS я не спорю, что регекспы великая вещь. Сам их частенько использую. Но считаю, что в данной задаче вот такие вот свитчи проще, прозрачнее и надёжнее (не будет провалов по скорости).

[t.t]

Как можно всерьёз обсуждать разницу в синтаксисе, говоря об _абстрактном_ КА? Откуда вообще понятие "синтаксис" в этом контексте?

Самый простой. Вход - сама строка. Выход - текст без разметки. Состояния свитчем, дуги тоже свитчем. Что-то типа (это псевдо-код):

И какое это имеет отношение к моему вопросу о синтаксисе? Эти "свитчи" -- КА? Отлично, но sed -- тоже КА; и awk. Разница в "синтаксисе" между всеми тремя весьма велика.

Это терминология под влиянием старой шутки? "Автомат Калашникова -- это преобразователь стека в очередь"? Других ассоциаций между LIFO (стеком) и магазином у меня не возникает. (:

Не знаю под чьим влиянием, но она общепризнанная. И на дискретке мы их учили именно под таким названием.
http://ru.wikipedia.org/wiki/Автомат_с_магазинной_памятью

А, так и надо было сказать: "с магазинной памятью". Всё было бы понятно. А сокращение "магазинный автомат" я слышу впервые.

Что Вы имеете ввиду под регэкспами? Строго говоря, даже s-выражения -- это уже не регэкспы. А уж тем более непонятна подразумеваемая прямая связь между регэкспами и языками sed или awk в целом.

Не очень знаком с sed, вообще не знаком с awk.

Видимо, в этом всё дело. (: У меня и сложилось впечатление, что Вы не совсем понимаете, о чём говорите. Извините за прямоту.

Сужу о регекспах по perl в основном. На одних регекспах в такой задаче сидеть неудобно. О катастрофическом падении скорости в некоторых случаях знаком не по наслышке.

На одних регэкспах в такой задаче "сидеть" не то что неудобно, а невозможно. Как я уже говорил, s-выражение -- это уже не регэксп. С натяжкой "одними регэкспами" можно назвать, скажем, голый pcregrep; но он с задачей справится лишь в одном случае: если html не только написан без особых нарушений структуры разметки (незакрытых тегов, например), но и хоть как-то отформатирован.

PS я не спорю, что регекспы великая вещь. Сам их частенько использую. Но считаю, что в данной задаче вот такие вот свитчи проще, прозрачнее и надёжнее (не будет провалов по скорости).

В такой задаче проще и прозрачнее "такие свитчи" базировать не на посимвольном разборе, а как раз на регэкспах, и даже чуть более -- на s-выражениях. Что, собственно, приведенный drBatty пример на sed и демонстрирует. (: Провалы по скорости (и памяти) будут, если пытаться загонять в s-выражения слишком сложные конструкции; говоря о pcre, если использовать "нежадные" квантификаторы; и т.п. Если же s-выражения грамотно комбинировать с управляющими конструкциями, то как раз по скорости может выйти даже эффективнее, чем посимвольный разбор.

[NickLion]

И какое это имеет отношение к моему вопросу о синтаксисе? Эти "свитчи" -- КА? Отлично, но sed -- тоже КА; и awk. Разница в "синтаксисе" между всеми тремя весьма велика.

Ну, я к тому, что данный код больше походит на КА в классическом понимании. Вход, множество состояний, и переходов между ними. Синтаксис регекспов всего этого не содержит. Разве не ответ на вопрос о синтаксисе?

А, так и надо было сказать: "с магазинной памятью". Всё было бы понятно. А сокращение "магазинный автомат" я слышу впервые.

Извиняюсь, строгость терминологии у меня бывает страдает.

Не очень знаком с sed, вообще не знаком с awk.

Видимо, в этом всё дело. (: У меня и сложилось впечатление, что Вы не совсем понимаете, о чём говорите. Извините за прямоту.

Можете не извиняться Ну не знаком, что поделать... учить надо Просто речь изначально шла именно о регекспах. И даже была фраза, что PCRE не нужны, достаточно просто RE.

На одних регэкспах в такой задаче "сидеть" не то что неудобно, а невозможно. Как я уже говорил, s-выражение -- это уже не регэксп. С натяжкой "одними регэкспами" можно назвать, скажем, голый pcregrep; но он с задачей справится лишь в одном случае: если html не только написан без особых нарушений структуры разметки (незакрытых тегов, например), но и хоть как-то отформатирован.

Вот, видимо всё от непонимания. Я подразумевал применение s/.../.../[ig] последовательно несколько раз. Без применения дополнительных средств.

s-выражение -- это уже не регэксп

Для уверенности - имеется в виду s/.../.../ ? Или http://ru.wikipedia.org/wiki/S-выражение ?

В такой задаче проще и прозрачнее "такие свитчи" базировать не на посимвольном разборе, а как раз на регэкспах, и даже чуть более -- на s-выражениях. Что, собственно, приведенный drBatty пример на sed и демонстрирует. (: Провалы по скорости (и памяти) будут, если пытаться загонять в s-выражения слишком сложные конструкции; говоря о pcre, если использовать "нежадные" квантификаторы; и т.п. Если же s-выражения грамотно комбинировать с управляющими конструкциями, то как раз по скорости может выйти даже эффективнее, чем посимвольный разбор.

Согласен, что может выйти эффективнее. Я просто хотел максимально сохранить близость с "классическим" описание КА.

[t.t]

И какое это имеет отношение к моему вопросу о синтаксисе? Эти "свитчи" -- КА? Отлично, но sed -- тоже КА; и awk. Разница в "синтаксисе" между всеми тремя весьма велика.

Ну, я к тому, что данный код больше походит на КА в классическом понимании. Вход, множество состояний, и переходов между ними. Синтаксис регекспов всего этого не содержит. Разве не ответ на вопрос о синтаксисе?

Синтаксис последовательных s-выражений (в терминологии perl/sed, а не ФП, это Вы правильно уточнили) именно это и содержит. Только под входом здесь нужно понимать весь текст в целом.

Не очень знаком с sed, вообще не знаком с awk.

Видимо, в этом всё дело. (: У меня и сложилось впечатление, что Вы не совсем понимаете, о чём говорите. Извините за прямоту.

Можете не извиняться Ну не знаком, что поделать... учить надо Просто речь изначально шла именно о регекспах. И даже была фраза, что PCRE не нужны, достаточно просто RE.

Пропустил, видимо. Да, если именно чистые регэкспы упоминались как инструмент обработки разметки (а не как лишь один из элементов такого инструмента), то это инструмент очень ограниченный.

На одних регэкспах в такой задаче "сидеть" не то что неудобно, а невозможно. Как я уже говорил, s-выражение -- это уже не регэксп. С натяжкой "одними регэкспами" можно назвать, скажем, голый pcregrep; но он с задачей справится лишь в одном случае: если html не только написан без особых нарушений структуры разметки (незакрытых тегов, например), но и хоть как-то отформатирован.

Вот, видимо всё от непонимания. Я подразумевал применение s/.../.../[ig] последовательно несколько раз. Без применения дополнительных средств.

s-выражение -- это уже не регэксп

Для уверенности - имеется в виду s/.../.../ ? Или http://ru.wikipedia.org/wiki/S-выражение ?

Имеется ввиду первое, я пояснил немного выше. Это действительно больше, чем регэксп.

В такой задаче проще и прозрачнее "такие свитчи" базировать не на посимвольном разборе, а как раз на регэкспах, и даже чуть более -- на s-выражениях. Что, собственно, приведенный drBatty пример на sed и демонстрирует. (: Провалы по скорости (и памяти) будут, если пытаться загонять в s-выражения слишком сложные конструкции; говоря о pcre, если использовать "нежадные" квантификаторы; и т.п. Если же s-выражения грамотно комбинировать с управляющими конструкциями, то как раз по скорости может выйти даже эффективнее, чем посимвольный разбор.

Согласен, что может выйти эффективнее. Я просто хотел максимально сохранить близость с "классическим" описание КА.

А обработка на sed тоже подходит под это описание, как я уже сказа выше: под входом только нужно понимать не символ, а весь текст или как минимум строку. В классическом примере ведь тоже не символы, а биты используются, для простоты. Так что строка или текстовый поток в целом -- всего лишь следующий уровень "расширения" в цепочке бит-символ. (;

[NickLion]

Так что строка или текстовый поток в целом -- всего лишь следующий уровень "расширения" в цепочке бит-символ. (;

Ладно, уболтали, сдаюсь Потому что в целом согласен с доводами, да.

[drBatty]

Самый простой. Вход - сама строка. Выход - текст без разметки. Состояния свитчем, дуги тоже свитчем. Что-то типа (это псевдо-код):

всё это прелестно ложится на sed-скрипт. единственная сложность - это то, что sed обрабатывает файл построчно, а в HTML понятие "строка" не имеет смысла. В C++ с этим тоже будет сложности (в STL). Обычно в память грузят весь текст целиком, а потом выкидывают код на помойку, и юзают чужой парсер, потому-что он "быстрее". (:

Не очень знаком с sed, вообще не знаком с awk. Сужу о регекспах по perl в основном. На одних регекспах в такой задаче сидеть неудобно. О катастрофическом падении скорости в некоторых случаях знаком не по наслышке.

падение скорости связано с двумя причинами:
1) из-за слишком сложных перловых RE. В sed такой проблемы нет - там нет PCRE. в awk тоже - там их вообще нет. (:
2) неправильной работой с памятью. Загрузить огромный файл целиком в память, а потом ковырять его потоковым редактором - плохая идея. В sed есть эффектные методы работы с такими потоками (команды P, N, D). А вот про perl - не знаю...

PS я не спорю, что регекспы великая вещь. Сам их частенько использую. Но считаю, что в данной задаче вот такие вот свитчи проще, прозрачнее и надёжнее (не будет провалов по скорости).

ага.

Код: Выделить всё

#!/bin/sed
/</{
# обработка тегов
}
/<!--/{
# обработка комментов
}
... и т.д.

и где тут регекспы?
тут как раз C++ не пойдёт, там нельзя case '<!--':

Просто речь изначально шла именно о регекспах. И даже была фраза, что PCRE не нужны, достаточно просто RE.

ага. только тут RE нужны несколько для другого - например для поиска "<!--". Не, вы конечно можете написать свою реализацию метода SHIFT-AND, только какой в этом смысл, если в нашей glibc УЖЕ это есть? Причём вовсе не обязательно использовать STL обёртку, и городить свой код, есть уже готовая обёртка - sed.
Падение скорости будет только если вы зачем-то применили например скобки (вроде того, что-бы найти то, что три раза уже было), в данной задаче это не нужно, а нужен простой поиск. И реализация из glibc будет намного быстрее, чем посимвольный разбор. К тому-же она места не занимает, и всегда есть.

Вот, видимо всё от непонимания. Я подразумевал применение s/.../.../[ig] последовательно несколько раз. Без применения дополнительных средств.

в sed(и в perl) это не просто RE. Просто RE просто ищет некоторое выражение в некотором тексте, и выдаёт результат: позиции начала и конца совпадений. команда s делает намного больше, она не только ищет, но и заменяет(или НЕ заменяет) совпадения. А иногда даже преобразует текст для замены (может сменить регистр, или отправить текст оболочке).

Согласен, что может выйти эффективнее. Я просто хотел максимально сохранить близость с "классическим" описание КА.

а в sed оно и будет ближе. C++ не умеет выбирать строчки, а только целые числа (switc-case). Потому ваш КА в C++ ляжет очень криво, на кучу if-ов. В отличие от sed.

А обработка на sed тоже подходит под это описание, как я уже сказа выше: под входом только нужно понимать не символ, а весь текст или как минимум строку. В классическом примере ведь тоже не символы, а биты используются, для простоты. Так что строка или текстовый поток в целом -- всего лишь следующий уровень "расширения" в цепочке бит-символ. (;

в исходной задаче у нас есть "подстроки". биты, байты и даже символы нам не подходят по условию. Причём подстроки ещё и не имеют жёсткого формата, даже самый простой тег <br> может быть записан например как <br
/>
потому в этой задаче RE понадобятся в любом случае, без них всё будет слишком сложно, медленно и криво.

[drBatty]

ЗЫЖ уточнение:

А регекспов в sed нету... Можете сами исходники глянуть...

не, есть там RE. они нужны в том случае, если нет libc. Например если мы собираем sed для Windows (странная ось - там даже регекспов нет...)

и на sed не реализуется - она на очередь заточена, которая FIFO. просто команд таких нет - есть "оторвать голову", и есть "добавить в хвост" (:

LIFO тоже можно сделать конечно... вот только это жутко долго. Т.е. если сравнить FIFO из sed с другой реализацией - то в sed не хуже, а вот LIFO на sed - намного хуже...