» Синтаксический анализатор (на Delphi)

Пишу интерпретатор языков программирования. Текст переводится в лексемы. Потом из лексем строятся синтаксические конструкции основываясь на правилах вывода из нетерминалов. Так вот проблема - не могу придумать, как в Delphi замутить эффективную по скорости и памяти структуру данных для обработки рекурсивного спуска. Рекурсию не предлагать, это убожество.
Была идея очереди, в конец которой добавляетются все правые части правил вывода текущего раскрываемого нетерминала, а отработанное и не подошедшее из очереди удалять простым смещением указателя на начало очереди вправо. Но вложенность нетерминалов может быть большой (до 10) и правил вывода для каждого тоже может быть дофига, так что даже не знаю, как быть...

p.s. наверняка не все знакомы с тем, о чём я тут говорю. при надобности могу разъяснить.

sdmaster

Цитата:

Рекурсию не предлагать, это убожество.

Это как раз оптимальное решение. Главное с ней дружить. Многие задачи так легко решаются

Цитата:

p.s. наверняка не все знакомы с тем, о чём я тут говорю. при надобности могу разъяснить.

Сами на досуге компиляторами/интерпретаторами балуемся

OdesitVadim

Цитата:

Это как раз оптимальное решение. Главное с ней дружить. Многие задачи так легко решаются

Мне главное, чтобы работало быстро и памяти не требовало много. Мне нравятся красивые решения. Для этого собственно мне и надо придумаль, как получше всё закодить. А с рекурсией всё будет "дёшево и сердито" и неинтересно

Цитата:

Мне нравятся красивые решения.

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

Lex & Yacc http://dinosaur.compilertools.net/

Если это слишком сложно, можно использовать уже существующие встраиваемые движки - embedded perl, python или m$ java/vb script

dmka

Цитата:

тогда нужно отложить Delphi в сторонку

Цитата:

можно использовать уже существующие встраиваемые движки - embedded perl, python или m$ java/vb script

Это ты дельфи в сторонку отложить предлагаешь и на vb script'е писать?? Кхем...
За ссылку спасибо. Однако там предлагается уже готовый продукт, типа скачай и построй свой компилятор. Это очень даже неплохо, но в данном случае мне нужен именно свой.
А красивое решение можно и на дельфе написать, если уметь писать

sdmaster

Цитата:

Мне главное, чтобы работало быстро

Поверь, достаточно быстро рекурсия работает.

Цитата:

памяти не требовало много.

А много это сколько?
Когда я начинал програмить у меня было 48 килобайт памяти. 16 - операционка, ещё 16 интерпретатор. остальное - мне. по современным меркам - это ничто, а мне удавалось на пару тисяч строк прогу запихнуть. (интерпретатор бейсика был с компилятором, как бы теперь сказали "в байт код" или "для виртуальной машины", поэтому память нада была для откомпилированой части)
А теперь, при использовании .НЕТ'а 100 мегабайт памяти - это ничто, это норма, это особенность компилятора.
Раньше прога поиска простых чисел до 1000 работала несколько минут (частота проца - 700 килогерц, да, да, килогерц!) и тратиш время на то, чтобы выжать пару сек. Сейчас до милиона быстрей справляется и без особой оптимизации.

Отсюдова вывод, sdmaster: подумай, мож ты не в ту сторону оптимизацию делаеш? Обычно прога либо имеет малый размер либо быстро работает.

Цитата:

Это ты дельфи в сторонку отложить предлагаешь и на vb script'е писать??

сама прога может быть на чем угодно (в т.ч. на дельфях), а некоторая логика внутри (которая может гибко настраиваться пользователем) управляться скриптом (в т.ч. vb script) . В этом нет ничего плохого.



Цитата:

А красивое решение можно и на дельфе написать, если уметь писать

не хочу начинать очередной holy war, но если ты в будущем планируешь зарабатывать деньги этим ремеслом, забудь про delphi как можно скорее. У нас при преме на работу delphi в резюме засчитывается как минус

OdesitVadim
принято. подумаю.

Цитата:

У нас при преме на работу delphi в резюме засчитывается как минус

!! ГЫ !!

dmka

Цитата:

У нас при преме на работу delphi в резюме засчитывается как минус

а у нас VB и FoxPro во всех проявлениях :))

Цитата:

У нас при преме на работу delphi в резюме засчитывается как минус

У нас, людей, утверждающих что Си крут просят доказать это. Мне ещё не попадались те, кто это сумел доказать (аргументировано, без общих фраз типа "плох тот язык, в котором нельзя одной строкой объявить указатель на массив массивов указателей" или что то в этом роде. Спрашиваеш, "а зачем?" - моментально ступор. "А сам понял, что сказал, сам сможеш?" - тоже)
Да простит меня ShIvADeSt за флуд.

Цитата:

а у нас VB и FoxPro во всех проявлениях

ну VB сам по себе безусловно не катит, но будучи упомянут в конце резюме is a plus. С FoxPro к нам не приходють

OdesitVadim

Цитата:

У нас, людей, утверждающих что Си крут просят доказать это.

Я не хотел обидеть профессионалов-дельфистов. Тут дело не в языках, а в деньгах. Денежные проекты это в основной массе java & oracle, .net & mssql (поровну c# и vb) и c/c++

все, no more flame

все уже давно придумано за нас - yacc/lex, генерящие код для Delphi:
http://www.grendelproject.nl/dyacclex/