парсеры, сгенеренные lex & yacc
Мне тоже интересно.
По-моему, освобождать память в таком софте просто не принято.
По-моему, освобождать память в таком софте просто не принято.
класс union-а ты сам определяешь?
Для языков без GC эти тулзы не использовал, но по логике за все отвечать должен ты. Для С реализация может отличаться, но что касается того, что использовал я, то строки связанные с лексемами и тем более объекты парсера были полностью в моей власти. Хоть там и была сборка мусора, но было четко видно, что они живут столько, сколько я им позволю.
При наличии GC проблема как бы и не стоит.
А с бизоном проблема в том, что он вырезает куски из входного текста и отдаёт их твоему коду в виде char *, и непонятно, когда их освобождать.
А с бизоном проблема в том, что он вырезает куски из входного текста и отдаёт их твоему коду в виде char *, и непонятно, когда их освобождать.
Так если строится дерево, то проблем не видно.
При удалении дерева ты сам и должен почистить все ссылки.
При удалении дерева ты сам и должен почистить все ссылки.
Чего непонятного то? Тут всего 2 варианта: либо их надо скопировать, если нужно, либо освободить, если они в дальнейшем не нужны. Я просто не знаю, что именно Бизон делает. Мой лексер давал мне самому возможность решать, нужен ли мне данный кусок текста. То есть у меня был вариант 1, который, на мой взгляд, наиболее правильный.
А если из кода непонятно, какой вариант правильный, можно провести экперимент.
А если из кода непонятно, какой вариант правильный, можно провести экперимент.
Так в том вся и проблема, что оно не однозначно строится. То есть нашли букву "A", а с этой буквы может начинаться сразу 2 лексемы, попробовали один вариант - натолкнулись на лажу. Потом попробовали другой вариант успешно - вернули юзеру. А лексер в тоже время каждый раз делает strdup на куски исходной строки. Поэтому на каждый shift/reduce конфликт течет память, что неприятно. Одно дело, когда прога работает разово, типа компилятора - там еще такое можно стерпеть (хотя все равно не хорошо). Но мне нужно чтобы прога обрабатывала массу запросов и висела долго, утечки памяти там непозволительны.
>> каждый shift/reduce конфликт течет память
Ты уверен? Да и делать strdup даже на каждый правильный кусок это идиотизм, зачем мне, например, строки с названиями ключевых слов или коментариями. Если он действительно так работает, стоит наверно подумать об rm * в его каталоге.
Ты уверен? Да и делать strdup даже на каждый правильный кусок это идиотизм, зачем мне, например, строки с названиями ключевых слов или коментариями. Если он действительно так работает, стоит наверно подумать об rm * в его каталоге.
Чтение man-ов, сырцов сгенеренных парсеров, mailinglist-ов в инете и другой документации привели к тому что мои самые худшие опасения оправдались. Для flex и bison это глобальная проблема.
Если кому интересно, рассказываю, как я выкрутился:
1) написал свой простенький аллокатор, который запоминает кто сколько выделил
2) в сканнере, сгенеренном flex, вся память выделяется через него
3) когда парсится текст, строится дерево. Все узлы дерева - объекты, наследуются от одного общего предка. В нем переопределены операторы new, delete так что они используют этот аллокатор (+ виртуальный деструктор)
4) парсер в конструкторе создает экземпляр аллокатора и запускает парсер сделанный bison
5) по окончании парсинга аллокатор уничтожается, освобождая всю память
PS. Дебагные printf вставленные в аллокаторе в функции alloc/free и в деструкторе аллокатора наглядно демонстрируют, что память действительно течет
Если кому интересно, рассказываю, как я выкрутился:
1) написал свой простенький аллокатор, который запоминает кто сколько выделил
2) в сканнере, сгенеренном flex, вся память выделяется через него
3) когда парсится текст, строится дерево. Все узлы дерева - объекты, наследуются от одного общего предка. В нем переопределены операторы new, delete так что они используют этот аллокатор (+ виртуальный деструктор)
4) парсер в конструкторе создает экземпляр аллокатора и запускает парсер сделанный bison
5) по окончании парсинга аллокатор уничтожается, освобождая всю память
PS. Дебагные printf вставленные в аллокаторе в функции alloc/free и в деструкторе аллокатора наглядно демонстрируют, что память действительно течет
Немного не в тему, но если ты так серьёзно разбирался, то наверное знаешь:
правда ли, что с бизоном практически невозможно включить в одну программу несколько парсеров, из-за конфликта имён?
Если и это верно, тогда точно фтопку его.
правда ли, что с бизоном практически невозможно включить в одну программу несколько парсеров, из-за конфликта имён?
Если и это верно, тогда точно фтопку его.
bison генерирует все имена с префиксом. Дефолтный префикс - yy, то есть функции называются типа yy_parse итп. С помощью ключа -p можно указать другой префикс. Например bison -p zz приведет к функциям типа zz_parse. Насколько я понимаю, если указывать разные префиксы то конфликта имен не будет. Или ты имел ввиду что-то другое?
то самое
а как заставил своим аллокатором пользоваться?
а как заставил своим аллокатором пользоваться?
Просто заменил strdup на вызов своей allocator->alloc(size) 
А вообще есть всякие там yyalloc, которые можно переопределить, и тогда внутренние буфера парсера тоже будут выделяться там же.
Кстати, если интересно, то есть всякие более продвинутые генераторы, например LEMON. Он написан с учетом этих граблей. Авторы обещают, что:
1) он генерит парсеры, более быстрые чем bison
2) может работать много парсеров одновременно, thread-safe итп
3) там есть понятие деструктора, поэтому вся память вовремя освобождается и никаких подобных проблем не возникает
Подробности тут http://www.hwaci.com/sw/lemon/
Я на него забил, т.к. мне хотелось решить задачу стандартными средствами.
А вообще есть всякие там yyalloc, которые можно переопределить, и тогда внутренние буфера парсера тоже будут выделяться там же.
Кстати, если интересно, то есть всякие более продвинутые генераторы, например LEMON. Он написан с учетом этих граблей. Авторы обещают, что:
1) он генерит парсеры, более быстрые чем bison
2) может работать много парсеров одновременно, thread-safe итп
3) там есть понятие деструктора, поэтому вся память вовремя освобождается и никаких подобных проблем не возникает
Подробности тут http://www.hwaci.com/sw/lemon/
Я на него забил, т.к. мне хотелось решить задачу стандартными средствами.
> Просто заменил strdup на вызов своей allocator->alloc(size)
В уже сгенерированном коде?
В уже сгенерированном коде?
Нет. На вход flex-у дается файл где описаны действия при обработкем различных лексем. Подавляющее большинство использований при встрече лексемы типа "идентификатор" делает на него strdup. Flex из этого файла уже генерит код, вставляя эти куски в нужные места. Как раз во входном файле нужно поменять все strdup на специальные alloc. В самом сгенеренном файле ничего менять не надо.
Вся проблема, в том что сгенеренный сканер затирает эти указатели, их потом никак не освободить. То есть примерно что-то такое:
union {
char* m_string;
int m_integer;
} YYSTYPE;
YYSTYPE yylval;
<встретили лексему>: yylval.m_string = strdup(yytext);
<встретили следующую>: yylval.m_interger = atoi(yytext); <- указатель затерли
Flex генерит массу присваиваний между объектами типа YYSTYPE внутри себя, что и не дает нормально освобождать память.
Вся проблема, в том что сгенеренный сканер затирает эти указатели, их потом никак не освободить. То есть примерно что-то такое:
union {
char* m_string;
int m_integer;
} YYSTYPE;
YYSTYPE yylval;
<встретили лексему>: yylval.m_string = strdup(yytext);
<встретили следующую>: yylval.m_interger = atoi(yytext); <- указатель затерли
Flex генерит массу присваиваний между объектами типа YYSTYPE внутри себя, что и не дает нормально освобождать память.
> Подавляющее большинство использований при встрече лексемы типа "идентификатор" делает на него strdup.
В твоём коде или в сгенерированном?
И flex меня не очень интересует, больше bison
Спасибо за ссылку, кстати.
В твоём коде или в сгенерированном?
И flex меня не очень интересует, больше bison
Спасибо за ссылку, кстати.
> В твоём коде или в сгенерированном?
В коде, входном для flex. В сгенерированный это переносится без проблем.
> И flex меня не очень интересует, больше bison
В bison похожая байда. Обычно пишут правила типа:
expr:
NUMBER { $$ = new Number($1); }
| expr '+' expr { $$ = new Sum($1, $3); }
| expr '*' expr { $$ = new Mult($1, $3); }
где Number, Sum, Mult - классы от общего предка, узлы дерева.
Проблема в том, что если все спарсилось хорошо и конфликтов не было, то в принципе, делая delete на корень дерева, можно все освободить, но вот если произошла синтаксическая ошибка, то тебе вернут NULL, и непонятно что и кого освобождать.
В коде, входном для flex. В сгенерированный это переносится без проблем.
> И flex меня не очень интересует, больше bison
В bison похожая байда. Обычно пишут правила типа:
expr:
NUMBER { $$ = new Number($1); }
| expr '+' expr { $$ = new Sum($1, $3); }
| expr '*' expr { $$ = new Mult($1, $3); }
где Number, Sum, Mult - классы от общего предка, узлы дерева.
Проблема в том, что если все спарсилось хорошо и конфликтов не было, то в принципе, делая delete на корень дерева, можно все освободить, но вот если произошла синтаксическая ошибка, то тебе вернут NULL, и непонятно что и кого освобождать.
ну тогда генератор и не виноват в общем, если сам не делает выделений памяти
и твоё решение самое верное (кроме как фтопку bison и С/C++)
и твоё решение самое верное (кроме как фтопку bison и С/C++)
Оставить комментарий
Landstreicher
Есть вопрос про сабж. Если реализовывать калькулятор с переменными через сабж, то когда определяются лексемы, делается union в числе которых есть char *Например,
%union {
double m_double; /* For returning numbers. */
char *m_string; /* For variables */
}
Если делать что-то более сложное, например чтобы парсер строил дерево, а не только возвращал конечный результат, то могут быть еще более сложные типы, какой-нибудь NodeType *.
Соотвественно, сканнер создает такие объекты, например:
yylval.m_string = strdup(yytext);
Парсер тоже свободно кидается такими объектами, например:
mathexpr:
expr + expr { $$ = new CBinaryOperator('+', $1, $3); }
| expr - expr { $$ = new CBinaryOperator('-', $1, $3); }
В общем, это все круто работает, но меня интересует, как при этом происходит работа с памятью? Кто освобождает все эти char *, выделенные в сканерах и парсерах? Какое у них время жизни?
В документации по flex и bison эти вопросы почему-то не рассмотрены