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

Тема в разделе "WASM.A&O", создана пользователем volodya, 12 ноя 2004.

  1. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    Ничего не имею против.



    Если решение принято, то написано ли уже правило лексера, которое выбирает строку в скобках с пробелами без изменений?...



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



    Также страшненько выглядят hardcoded имена хендлеров и их независимая отдельная обработка. Нельзя ли что-нибудь обобщить и чтобы похожие действия выполняла только одна функция?
     
  2. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Основная потенциальная проблема лишь в том, что одинаковую работу выполняют два разных куска кода.



    Э-э-э... Что-то в этом есть... Но не слишком много. Рассматривай хендлер как функцию, которая принимает на вход один параметр - строку. А уж передать ей эту строку -работа движка парсера.



    Также страшненько выглядят hardcoded имена хендлеров и их независимая отдельная обработка.



    Хм... Ты во многом прав.

    Вообще-то имена хендлеров подключаются reflection и от этого мне не убежать. Не убежать от хардкорных имен... Но, возможно, имеет смысл кое-что переписать...



    Если решение принято, то написано ли уже правило лексера, которое выбирает строку в скобках с пробелами без изменений?...





    Я все никак не разберусь с правилами регулярок в лексе...

    Примерно так:


    Код (Text):
    1.  
    2. HANDLER_DATA=       ([^\f\t\b\r\n]+)
    3.  
     
  3. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    Ничего больше не буду навязывать...



    Когда "истина где то рядом", лучше почитать что-нибудь теоретическое, с целью поиска подходящих идей. Читать можно dragon book, или, например, это:



    _http://offline.computerra.ru/2001/402/10900/print.html



    (не совсем по теме, но описан один из подходов, как подобные задачи могут решаться "по-научному")
     
  4. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    captain cobalt



    Ты ничего не навязываешь. Моя беда в том, что у меня никогда не было классического образования по программированию. А на данный момент темп жизни настолько высок, что я просто не могу позволить себе вдумчиво читать книжки о дизайне паттернов и т.п. Так что подобные разговоры для меня очень важны. Поэтому еще раз спасибо. Я очень ценю твою помощь.
     
  5. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Если решение принято, то написано ли уже правило лексера, которое выбирает строку в скобках с пробелами без изменений?...



    Oops. My bad :)



    Вот так вот должно выглядеть: скобку тоже надо эскейпить.



    Дополнительно говорю.. Может, понадобится кому... Java на этом форуме не обсуждается (разве что в целях поломать :)), но jlex и lex - это почти одно и то же, а lex - это генератор лексических анализаторов для С, стало быть...



    Для Jlex надо определить свой класс Yytoken. Вот простой файл спецификации, на основе которого я и буду делать движок:


    Код (Text):
    1.  
    2. /**
    3.  * Lexical specification for jimporter.
    4.  *
    5.  *
    6.  **/
    7. import java.lang.System;
    8. import java.io.FileReader;
    9. import java.io.BufferedReader;
    10.  
    11. class ClassCodes
    12. {
    13.     public static final int ERROR =         0;
    14.     public static final int OPEN_CURL_BRACKET = 1;
    15.     public static final int CLOSE_CURL_BRACKET =    2;
    16.     public static final int HANDLER_NAME =      3;
    17.     public static final int HANDLER_DATA =      4;
    18.     public static final int SECTION_HEADER =    5;
    19. }
    20.  
    21. class Yytoken
    22. {
    23.     private int classCode;
    24.     String p_data;
    25.    
    26.     Yytoken(int class_code, String data)
    27.     {
    28.         classCode = class_code;
    29.         p_data = data;
    30.     }
    31.  
    32.     Yytoken(int class_code)
    33.     {
    34.         classCode = class_code;
    35.     }
    36.  
    37.     int getClassCode()
    38.     {
    39.         return classCode;
    40.     }
    41.    
    42.     String getText()
    43.     {
    44.         return p_data;
    45.     }
    46. }
    47.  
    48. class jimporter {
    49.     public static void main(String argv[]) throws java.io.IOException {
    50.     BufferedReader rdr = new BufferedReader(new FileReader("test.txt"));
    51.     Yylex yy = new Yylex(rdr);
    52.     Yytoken t;
    53.     while ((t = yy.yylex()) != null)
    54.     {
    55.         switch(t.getClassCode())
    56.         {
    57.             case ClassCodes.ERROR:
    58.                 System.out.println("Error");
    59.                 break;
    60.             case ClassCodes.OPEN_CURL_BRACKET:
    61.                 System.out.println("Bracket: {");
    62.                 break;
    63.             case ClassCodes.CLOSE_CURL_BRACKET:
    64.                 System.out.println("Bracket: }");
    65.                 break;
    66.             case ClassCodes.HANDLER_NAME:
    67.                 System.out.println("Handler name is: " + t.getText());
    68.                 break;
    69.             case ClassCodes.HANDLER_DATA:
    70.                 System.out.println("Handler data is: " + t.getText());
    71.                 break;
    72.             case ClassCodes.SECTION_HEADER:
    73.                 System.out.println("Section header is: " + t.getText());
    74.                 break;
    75.             default:
    76.                 System.out.println("Fatal error");
    77.                 break;
    78.         }
    79.     }
    80.     }
    81. }
    82.  
    83. %%
    84. SPACE=          [\ \f\t\b\r\n]+
    85. OPEN_CURL_BRACKET=  \{
    86. CLOSE_CURL_BRACKET= \}
    87. SECTION_HEADER=     [%a-zA-Z]+
    88. HANDLER_NAME=       [a-zA-Z_]+
    89. HANDLER_DATA=       \([^\f\t\b\r\n]+\)
    90. %line
    91.  
    92. %%
    93. {OPEN_CURL_BRACKET} { return (new Yytoken(ClassCodes.OPEN_CURL_BRACKET)); }
    94. {CLOSE_CURL_BRACKET}    { return (new Yytoken(ClassCodes.CLOSE_CURL_BRACKET)); }
    95. {HANDLER_NAME}      { return (new Yytoken(ClassCodes.HANDLER_NAME, yytext())); }
    96. {HANDLER_DATA}      { return (new Yytoken(ClassCodes.HANDLER_DATA, yytext())); }
    97. {SECTION_HEADER}    { return (new Yytoken(ClassCodes.SECTION_HEADER, yytext())); }
    98. {SPACE}         { }
    99. .           { return (new Yytoken(ClassCodes.ERROR)); }
    100.  
     
  6. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Работает корректно, шустро. Парсит файл как мне и надо. Понимает и случаи вот такие вот:


    Код (Text):
    1.  
    2. %keywords{
    3.  
    4. %сommon {
    5.  
    6. BIND_Interaction_division(BIND fungi)}
    7.  




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

    P.S. Статьи по конечным автоматам можно найти на RSDN.
     
  7. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    А что насчёт подхода, описанного в вышеупомянутой статье?



    Там рассматривается преобразование из XML в HTML. Похожая задача? Довольно-таки.



    Суть метода в том, чтобы разделить преобразование на две последовательные фазы. Сначала входной файл преобразуется во внутреннее представление (R-выражение), а затем из полученного генерируется выходной файл. Каждый из этих алгоритмов реализуется парой десятков строк кода. По сути это очень похоже, и почти так же просто, как сначала построение дерева, а потом его обход... Синтаксический анализатор при этом может существенно упроститься...



    Поэтому, если есть время, можно взглянуть на задачу и с этой чочки зрения.

    Возможно, работы менее чем на сотню строк кода...
     
  8. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Похожая задача?



    Нет. Моя задача совсем другого рода. Долго объяснять. Парс файла и вывод XML - это 10% общей работы. Самое сложное в другом месте :)
     
  9. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    captain cobalt



    У меня появились еще вопросы. По конечным автоматам.

    Почитал я то, что мне n0p прислал + то, что на RSDN и, все равно, не доволен...

    Словом, вот чего я надумал.

    Как уже говорилось - есть три секции (%common, %objects, %keywords). Лексический анализатор выдает токены. Анализ токенов подвешивается на три функции - три КА, по одному на секцию. Как я себе этот КА смутно представляю...

    Вот так:



    ---> SECTION_HEADER ----> OPEN_CURL_BRACKET ------>



    HANDLER_NAME/HANDLER_DATA ----> CLOSE_CURL_BRACKET



    Состояние HANDLER_NAME/HANDLER_DATA замыкается само на себя...

    Как реализовать - пока не знаю. Точнее, есть идеи касательно switch как предложено в статье на RSDN, но в той же самой статье предложена и таблица переходов, но я ее уже не вполне понимаю...
     
  10. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    В принципе, кое-что потихоньку проясняется...



    1. Имеем набор правил.

    2. На их основе строим НКА

    3. НКА в ДКА

    4. ДКА на основе таблицы



    Ключевые слова в гугле: "DFA table-driven implementation tutorial transition table"
     
  11. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    > Как уже говорилось - есть три секции

    > Анализ токенов подвешивается на три функции - три КА



    Обыкновенно лексер - это один КА.

    По лексическим правилам генератор лексеров строит готовую процедуру лексера, что ещё надо?



    > 1. Имеем набор правил.

    > 2. На их основе строим НКА

    > 3. НКА в ДКА

    > 4. ДКА на основе таблицы



    Вручную что ли делать КА?

    Если так, то для простой лексики (зарезервированные ключевые слова + числа + строки) можно сразу рисовать ДКА (я вообще никогда не делаю НКА). Обычно основная задача здесь - это сделать, чтобы быстро отличать ключевые слова друг от друга...
     
  12. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Обыкновенно лексер - это один КА.



    Вот, блин. Или я плохо объясняю, или ты плохо понимаешь мои объяснения... Наверное, все таки, я :dntknw:



    Логика какая.



    Лексер выдает токены --> мне надо анализировать эти токены (для этого нужна логика более высокого уровня, которая, например, знает, что после открывающей скобки должна быть закрывающая и, если ее нет, надо громко вопить и требовать консула)

    Да, КА делать вручную. Но не для лексики, а для контроля правильности синтаксиса! Вот мне и надо нарисовать ДКА, а потом построить его на основе таблицы. Пока думаю. Знаний мало. :dntknw:
     
  13. n0p

    n0p 10010000b

    Публикаций:
    0
    Регистрация:
    7 май 2003
    Сообщения:
    256
    Адрес:
    Новосиbeerск
    Насколько я понял из туманных объяснений препода, КА занимается разбором входного потока на лексемы, а синтаксическим анализом заведует формальная грамматика. КА я делал, там все достаточно просто - надо только вьехать в суть таблицы переходов и суметь ее правильно построить. А ФГ я еще не делал, хотя представляю более-менее. По заверениям более расторопных сослуживцев, ФГ тоже просто, но надо понять.



    ЗЫ: Это я так, для поддержания боевого духа. :)
     
  14. captain cobalt

    captain cobalt New Member

    Публикаций:
    0
    Регистрация:
    21 дек 2003
    Сообщения:
    222
    Адрес:
    /ru/perm
    volodya

    > Лексер выдает токены --> мне надо анализировать эти токены

    > (для этого нужна логика более высокого уровня,

    > которая, например, знает, что

    > после открывающей скобки должна быть закрывающая и,

    > если ее нет, надо громко вопить и требовать консула)



    Значит ли это, что лексер будет отдавать каждую скобку на уровень выше, в синтаксис?



    > Да, КА делать вручную. Но не для лексики, а для контроля правильности синтаксиса!



    То есть, для синтаксического анализатора. Это правильно.



    n0p> Насколько я понял из туманных объяснений препода,

    n0p> КА занимается разбором входного потока на лексемы,

    n0p> а синтаксическим анализом заведует формальная грамматика.



    КА используется и для синтаксических анализаторов.



    n0p> КА я делал, там все достаточно просто -

    n0p> надо только вьехать в суть таблицы переходов...



    Угу...
     
  15. n0p

    n0p 10010000b

    Публикаций:
    0
    Регистрация:
    7 май 2003
    Сообщения:
    256
    Адрес:
    Новосиbeerск


    Значит наш курс эту проблему обходит стороной и останавливается на ФГ для синтаксического анализа. :dntknw:

    Плохо. Что тут еще можно добавить?
     
  16. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Да я, в принципе, уже все и сделал. Выдались свободные пол-часа - почитал драконовскую книжку + еще час посидел схемы порисовал.

    Примерно это выглядит так:


    Код (Text):
    1. SECTION_HEADER -> обозначим как A
    2. OPEN_CURL_BRACKET -> B
    3. HANDLER_NAME -> C
    4. HANDLER_DATA -> D
    5. CLOSE_CURL_BRACKET -> E




    Правила таковы. Обязан быть А, после него обязана идти B, C и D опциональны, и D может отсутствовать вообще и останется только C, ну и, под конец, обязана быть E.

    Тогда регулярное выражение выглядит так:



    AB(C|CD)*E



    На основании этого я нарисовал ДКА и составил таблицу. Осталось только накодить двумерный массив на жабе и дело, в принципе, сделано...