Парсер/лексический анализатор...

Есть у мя проект на жабе...

(Quantum, кстати, спасибо за идею с архитектурой!)



Дык вот, есть текстовый файл примерно такого вида:

Код (Text):

1.  
2. %objects
3. {
4.     BIND-Condition(1)
5.     BIND-loc-siteA(1)
6.     BIND-loc-siteB(1)
7. }
8.  
9. %common=5
10. {
11.     Author  (vasya, pupkin, organization|ATP|Toronto|zzz|Canada|some street|me@here.com|123-456-789|321-654-987|M2Z 45F)
12.     Author  (fedya, NULL, NULL)
13.     BIND_pub_object (1, 12457)
14.     BIND_pub_object (2, 4576)
15.     BIND_Interaction_division(metazoa)
16.  
17. }
18.  
19. %keywords = 23
20. {
21.     BINDObjectTypeId
22.     Org_ref
23.     BINDObject_short_label
24.     BINDObject_other_names
25.     BINDObject_descr
26.     BIND_other_db
27.     BIND_loc_site
28.     BIND_loc_site_source
29.     BIND_id_Geninfo_id
30.     BINDObjectTypeId
31.     BINDObject_short_label
32.     BINDObject_other_names
33.     BINDObject_descr
34.     BIND_other_db
35.     BIND_loc_site
36.     BIND_loc_site_source
37.     BIND_id_Geninfo_id
38.     BIND_condition_system
39.     BIND_condition_general
40.     BIND_condition_descr
41.     BINDdescr_simple_descr
42.     BIND_condition_bait_condition
43.     BIND_condition_source
44. }
45.  
46. (A)protein  (A)280|Xanthobacter autotrophicus   (A)short_label  (A)aaa|bbb  (A)some shit    (A)EntrezGeneID|5089|NULL   (A)(0)58-169|NULL   (A)(0)2|12457   (A)4545 6787    (B)protein  (B)short_label  (B)aaa|bbb  (B)some  shit   (B)EntrezGeneID|5089|NULL   (B)(0)58-169|NULL   (B)(0)2|12457   (B)4545 6787    (0)1    (0)0    (0)some  desc   some description of the interaction (0)0    (0)2|4576  
47.  

Задача.

Пропарсить такой файл. После последней закрывающей фигурной скобки идут данные - таких строк может быть от 1 до нескольких десятков тысяч.

Парсер обрабатывает txt файл и, юзая чудовищно огромную API, выдает XML-файл согласно некоторой спецификации.

На данный момент я парсаю файл в лоб. При помощи регулярок, построчной обработкой и т.п. Основной минус такого подхода - это то, что какая-нибудь чукча просто постоянно вставит где-нибудь лишний пробельчик, символ табуляции, левую запятую и все грохается к херам. И мне приходится то регулярки править, то еще чего-нибудь в этом же роде. Надоело!

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

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

 

Тьфу, не синтаксические, а лексические. Мне нужно что-то вроде лексического анализатора... Типа какой-нибудь такой парсер + внутренняя таблица символов... Наверное... Мнения?

 

volodya

Привет!



Неужели регулярные выражения не могут отсеить лишний пробельчик, символ табуляции, левую запятую?

 

Могут, но ты представляешь с какой тщательностью их приходится выбирать? Я уже очумел их переделывать!

 

душа чего-то такого эдакого просит

 

volodya imho, гну-шный flex создан специально для твоего случая. ) А если скрестить его с bison для грамматического анализа тогда у-у.. будет сообще супер.



P.S. упс. Проглядел что проект на жабе. Тогда не знаю, быть может написать парзер все-таки на C (flex+bison)?

 

Да нет, вот это уже будет чересчур Парсер на жабе, а не на С. Пардон

Что-то свое написать с нуля...

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

 

volodya

Драконовская книжка помогает понять принцип работы старых компилеров, но на базе голой теории разродиться чем-нибудь своим... эт будет очень сложно, IMHO. Кстати, про С vs. Java, не забывай что жаба имеет JNI, т.е. интерфейс для нативного кода.

 

угу. на что-то похожее наткнулся недавно. представь себе файл из неск тыс ПОЛУвыровненных (по шаблону) сиквенсов. Парсятся без проблем. И вдруг огромный кусок файла совсем битый - не только выравнивание полностью поехало но и разделители нестандартные. Т.е. не то что бы битый - просто первый кусок сгенерил такой же идиот, но это был ДРУГОЙ идиот с другими условностями. Я офигел и перетащил этот кусок в sql, запросами разобрал 100 случаев совсем офигел и тогда скормил все сям - просто уничтожил нафиг все полувыравнивание (шаблонное) и ровнял уже заново все.

 

До сих пор непонятно, что нужно?

-- игнорировать мусор

-- обнаруживать и тыкать юзера носом в мусор

-- преобразовывать кавычку в &quote; и т. п.

 

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



Если заинтересовал, могу выслать. Или можно в онлайне увидеть тут: ermak.cs.nstu.ru/trans/

 

captain cobalt

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

 

Есть куча или несколько книг(лекций ввиде книг) по написанию компиляторов, там рассматривается теория разработки лексических анализаторов.

 

n0p> Это семантика, а интересует в первую очередь лексика, ведь так?



В том то и дело, что проблема как следует не поставлена.

Возможно, лексическим анализатором тут не отделаться.

 

captain cobalt



Я не пытаюсь ставить проблему. И не выдаю ТЗ. Это мой проект, который я делаю сам. Просто, читая посты, я пытаюсь собрать мысли в кучу. Вот и все



Теперь немножко более детально.

Секции "%keywords" и "%common" содержат имена хендлеров, которые подключаются через reflection. Порядок расположения хендлеров в "%keywords" определяет расположение элементов собственно тела файла (строк с данными, которых может быть от 1 до десятков тысяч). Т.о. от анализатора файла мне требуется следующее:



1) Получить имя хендлера без пробелов и любого другого мусора.

2) В случае секций "%common" и "%objects" получить имя хендлера + данные, несмотря на возможные лишние пробелы и т.п.

3) При парсе собственно тела файла (не заголовка) лишние табы должны игнорироваться.

4) Секции "%common", "%objects", "%keywords" могут следовать в произвольном порядке

5) Если файл где-то сформирован неверно - надо уведомить юзверя об ошибках



Примерно так



n0p

Хорошо. Давай. Мыло знаешь. Спасибо.

 

Таким образом, пробелы, табуляторы и переводы строки (aka whitespace) вообще не имеют никакого значения? Весь файл можно записывать в одну строку? Тогда какие проблемы? Каждый байт может быть либо нужным, либо "ненужным". И это можно запросто проверить. Обычно, составить множество "нужных" байтов проще; например: буквы, цифры, подчёркивания, скобки... А всё остальное отбрасывать...



Или не так?

 

Весь файл действительно можно записать в одну строку. Но табы... Пробелы... Как мне отличать данные друг от друга? Но, в принципе, общая идея в чем-то правильная...

 

volodya

Отправил на mail.ru. Там 300к.

 

Все получил. Спасибо.

 

volodya> Пробелы... Как мне отличать данные друг от друга?



ОК. Тогда займёмся буквоедством.



Задача лексического анализатора - собирать из букв слова (лексемы). Пробелы иногда необходимы, чтобы отделять друг от друга лексемы.



Например, в языке программрования Си, во фрагменте "void main" между словами "void" и "main" может быть любое количество пробелов, табуляторов и переводов строки. Но хотя бы что-нибудь одно из этого должно быть. Однако, на уровне синтаксиса это не имеет значения. Синтакисический анализатор получает от лексического два слова (на самом деле, некоторых условных кода aka токена): "void" (зарезервированное ключевое слово) и "main" (идентификатор). А то, что между ними есть пробел с точки зрения синтаксиса вообще "не видно". Пробел нужен только для того, чтобы лексический анализатор мог отделить их друг от друга.



Поэтому лексический анализатор обыкновенно работает так:

-- проскипать whitespace

-- начать собирать лексему

-- как только попадается байт, недопустимый для данной лексемы (например, скобка - это отдельная лексема), или попадается whitespace, то это означает, что лексема закончилась и её следует передать синтаксическому анализатору...



Вот.