Всім привіт!
Я нещодавно почав займатись парсингом тексту з файлів і розробив власний алгоритм. Як для початківця, це було цікавим досвідом, але з часом я задумався: чи існують вже стандартні методи, підходи, готові алгоритми та інструменти для парсингу тексту?
Можливо, хтось з вас має досвід у цій сфері та зможе поділитися корисною інформацією або порадами. Буду вдячний за будь-яку допомогу!
Мова: Java
Для мов програмування дивитися в сторону граматик , синтаксичного аналізу.
Для «людських» мов — natural language processing.
Скажу чесно, не можу зрозуміти, що ви хотіли сказати своїм коментарем...
Дивлячись що та як парсити. Тим не менше головних підхода до API парсера 3.
Підхід перший — сканер розбирає вхідний поток символів в проміжну деревину структуру — DOM, AST, JSON Objects і т.п.
Підхід другий — парсер приймає колбеки/медіатори які будуть викликатись коли він розпізнає певні елементи у вихідному потоці символів — типовий приклад XML SAX API.
Третій підхід — pull, парсер виглядає як iterator який послідовно видає, що в тексті трапляється далі та видає проміжну структуру — event в якому характеристики наступного елементу. Типові приклади XML StAX API, майже усі парсери CSV (coma separated files) і частина Wave front/OBJ, property файли і т.п.
Щодо безпосередньо розбору текстів. Тут теж два головних підхода, перший це регулярні вирази та детерміновані і не детерміновані кінцеві автомати DKA, NKA які на них базуються, другий метод — рекурсивний спуск (токенайзер) пишеться в ручну з використанням бібліотечних функцій стандартної бібліотеки якоїсь мови. Ще є метод монадичного парсингу цікавтесь в пошувикові, в цілому це такий варіант рекурсивного спуску.
Є генератори парсерів типу Lex/Flex, Yacc — в комплекті Bison, ANTLR — та фактично вони усі під підхід отримання дерева розбору позаяк для розробки компіляторів із мов програмування. Boost Spirit — також для розробки мов програмування. Регулярних виразів бібліотек та засобів різних дуже багато.
Коротше тема для великої статті, може навіть книги. Насправді справа навіть не просто в тексті, це характерно для читання файлів будь якого формату в яких треба по пізнавати вхід ASN1, Bjson, Protocol Buffers і т.д.
Як відомо алгоритми читання вхідних данних тобто де серіалізації, значно складніші за алгоритми запису вихідних серіалізації.
Є дві спеціалізована мова для розробки парсерів тексту — AWK, і друга формально універсальна мова Perl, що по суті є специфічною саме для обробки текстів.
Де почерпнути інформацію — з першого підходу напевно найкращій матеріал це Книга Дракона. Також дуже не погану класифікацію парсерів написав Arseny Kapaukilne — автор Puigi XML, та Mesh Optimizer в деяких свої статтях. Щодо табличних парсерів в кінцевих автоматів, тобто базису регулярних виразів так і про самі регулярні вирази інформації повний інтернет, як і про алгоритми пошуку підстилки в строці пошуку ствола та спану в строці і т.д. що використовуються в рекурсивних та монадичних парсерах (які через це зазвичай швидші в декілька разів, але писати їх аналогічно складніше в десятку разів ніж регулярні вирази чи BNF подібні структури для компіляторів-компіляторів).
Проблема в тому, що поки ви не підкажете, який саме текст, ніхто не зможе навіть приблизно відповісти.
Яка мова? Для англійської проблеми флексій (як tie — tying, catch — caught) значно простіші ніж для української чи російської. Для китайської ще простіші. Але для всіх розбір вимагає розуміння семантики. Стандартів нема, або вони порушуються: хто каже про фіксований порядок у англійській, не впорається з «right you are» чи «so did I». А діалектні варіації? А описки і одруківки?
Які обмеження на кодування? Чи треба вираховувати випадки типу коли вci oднaкoві бyкви зaмiнeнi нa лaтинcькi? А коли не всі?
Це, можна вважати, ще не початок шляху, це тільки підготовка до початку ;)
парсинг буде не стандартного тексту а тексту в особливому форматі напису на англ мові
Ну... якщо ефективно це швидкодія, то Bison. Так в принципі для невеличкого можна самому писати рекурсивний спуск. Якщо ефективно це швидко та надійно писати код, то напевно монадічні комбінаторні парсери, але на Java вони будуть виглядати трохи не дуже, як на мене.
Volodymyr Rudyi
Volodymyr Rudyi
Vic
Valentin Nechayev
Andrii Sevastianov
8 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів