LINUX.ORG.RU

Синтаксический и лексический анализ.


0

1

Нужно реализовать вычисление арифметических выражений, заданных в строковом виде, никакого подобия языка программирования. Ввиду того, что разобранное выражение должно будет много раз применяться, нужно генерировать в упрощенное промежуточное представление.
Знает ли кто-нибудь готовое решение задачи? Желательно на С и лицензия LGPL.
P.S.Я знаю про Книгу Дракона, но читать её времени нет пока.

★★★★

Во всех мануалах yacc/bison/etc в качестве примера реализуется калькулятор.

anonymous ()

Если выражение не будет преобразовываться, то всунуть его в виде текста в С-шный код и собрать gcc в виде отдельного модуля.

Если выражение будет преобразовываться - преобразовать его какой нить CAS, выгрузить результат в C-шный код и собрать gcc в виде отдельного модуля.

Или Вы хотите сказать, что выражение задается в формате не похожем ни на какой ЯП? А привести его к формату похожему на ЯП не проще будет?

AIv ★★★★★ ()
Последнее исправление: AIv (всего исправлений: 1 )
Ответ на: комментарий от AIv

В обычном формате будет - «1+2*a+sqrt(b)».
Собирание в виде отдельного модуля имхо слишком затратно.
muParser кажется реалистичней.

aptyp ★★★★ ()

antlr - на жабе, но зато грамматику можно просто нарисовать и получить парсер

EugeneBas ★★ ()

Я знаю про Книгу Дракона

Если нужно просто пособие по генерации AST, то в http://pragprog.com/book/tpdsl/language-implementation-patterns есть нужный материал. Там изложение на основе ANTLR и Java, но вполне доступно. Всю книгу читать не обязательно.

А если нужен просто калькулятор, то самый лучший пример калькулятора, который я видел - у Страуструпа. Recursive descent, без всяких внешних утилит. В ранних редакциях калькулятор был почти на Си :)

tailgunner ★★★★★ ()
Последнее исправление: tailgunner (всего исправлений: 1 )
Ответ на: комментарий от aptyp

Понятия не имею. Использовал год назад, всё работало.

imtw ()
Ответ на: комментарий от aptyp

Тогда начни с примера Страуструпа. Если тебе всё-таки не нужно внуртрннее представление - это то, что доктор прописал. Если нужно - думаю, генерацию польского кода туда добавить нетрудно.

tailgunner ★★★★★ ()

1. Парсишь на лексемы (это у нас число, это сложение)
2. Конвертишь в RPN
3. Реализуешь простенькую стековую машину
Можно уложиться в пару десятков строк.

mix_mix ★★★★★ ()
Ответ на: комментарий от tailgunner

O_o

http://www.math.bas.bg/bantchev/place/rpn/rpn.c.html
Ну и парсер столько же примерно будет. Ну хотя да, побольше, чем пару десятков. А вообще (аналог сишного кода по ссылке):

calc :: String -> [Float]
calc = foldl f [] . words
  where 
    f (x:y:zs) "+" = (y + x):zs
    f (x:y:zs) "-" = (y - x):zs
    f (x:y:zs) "*" = (y * x):zs
    f (x:y:zs) "/" = (y / x):zs
    f xs y         = read y : xs

mix_mix ★★★★★ ()
Ответ на: комментарий от mix_mix

1. Парсишь на лексемы (это у нас число, это сложение)
2. Конвертишь в RPN
3. Реализуешь простенькую стековую машину
Можно уложиться в пару десятков строк.

Ну так я написал, что парсер столько же примерно будет.

Не вижу про «не считая парсера».

tailgunner ★★★★★ ()
Ответ на: комментарий от tailgunner

Не вижу про «не считая парсера».

1 и 2 пункты очень мило объединяются при реализации однопроходного алгоритма.
http://ru.wikipedia.org/wiki/Обратная_польская_запись#Преобразование_из_инфик...

mix_mix ★★★★★ ()
Последнее исправление: mix_mix (всего исправлений: 2 )
Ответ на: комментарий от mix_mix

1 и 2 пункты очень мило объединяются при реализации однопроходного алгоритма.

И? В 20 строк не уложишься ни при каком раскладе.

tailgunner ★★★★★ ()
Ответ на: комментарий от aptyp

Собирание в виде отдельного модуля имхо слишком затратно.

А что потом планируется с ним делать?

AIv ★★★★★ ()
Ответ на: комментарий от AIv

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

aptyp ★★★★ ()
Ответ на: комментарий от aptyp

Ну другой, самый дешевый (по трудозатратам) путь, это взять ЯП где есть eval;-)

AIv ★★★★★ ()
Ответ на: комментарий от anonymous

Анонимус, ты лично выкопал руду, из которой смастерил свой компьютер и лично написал ОС, из-под которой написал это очень полезное сообщение? Я всё таки homo sapiens, а не человек повторяющий.

aptyp ★★★★ ()

Не надо книг дракона и прочей давно устаревшей дребедени. PEG на Си пишется за пять минут. А в твоем случае и вообще тупейший рекурсивный LL(n) сойдет.

Программист, не умеющий писать парсеры и простые компиляторы - это вообще не программист, а отстой, так что ссылаться на «нет времени» просто гнило. На все задачи готовых решений не напасешься, а эта задача - одна из наиболее часто встречающихся, и умение это - одно из самых мощных (позволяет писать DSL, а это многократно повышает производительность труда).

anonymous ()
Ответ на: комментарий от aptyp

Ты и арифметику в школе не учил под тем же предлогом, лошара?

anonymous ()
Ответ на: комментарий от aptyp

В Squeeze mathgl требует 7 пакетов, muParser - 2.

Это вопросы к маинтайнеру. Собрать можно вообще без внешних зависимостей.

abalakin ★★ ()
Ответ на: комментарий от imtw

Косяк с #include <muParserDLL.h> в нескольких файлах. Странно.

aptyp ★★★★ ()

Плюсую. Нафига тебе готовое решение задачи, если парсер по методу рекурсивного спуска пишется на раз-два, руками? Да ещё и обратная польская нотация элементарно генерируется?

Учебные примеры лучше всего делать своими руками, так чётче в голове отложится. Конечно, потом можно и «готовое решение» присобачить — и сравнить ощущения. Например, взять bison/ANTLR/PEG в качестве «готовой» библиотеки, разобрать типичный элементарный пример — калькулятор на этих примерах, почувствовать разницу.

Но только потом.

Иначе ты ничему не научишься.

anonymous ()

В качестве простого LALR-парсера, можно взять например, GOLD parser. Там из коробки много языков и примеров ( например ). ЕМНИП, и калькулятор есть.

Заодно, если повторить пример раза 4: «ручной» RDP парсер, PEG, LALR (gold/yacc/bison) , LL(k) парсер (ANTLR), GLR(bison,...) лучше поймёшь разницу.

Но опять таки, пример у тебя элементарный, сделай всё руками, лучше научишься.

anonymous ()
Ответ на: комментарий от tailgunner

А если нужен просто калькулятор, то самый лучший пример калькулятора, который я видел - у Страуструпа.

ещё Креншоу в «Давайте напишем компилятор» пишет компилятор какого-то паскаля на RDP парсере, написанном вручную

Хотя это довольно устаревшая книжка.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.