Парсинг исходников

[madskull]

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

Интересует информация по разбору исходных файлов (напр. сишных): теория, алгоритмы, простые примеры.
А может даже в linux есть библиотеки или тулзы для разбора текста программ в какие-то примитивы?

Спасибо.

[d_Sun]

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

Интересует информация по разбору исходных файлов (напр. сишных): теория, алгоритмы, простые примеры.
А может даже в linux есть библиотеки или тулзы для разбора текста программ в какие-то примитивы?

Спасибо.

↑

По-подробней можно? "Какие-то примитивы" - как-то раcплывчато...

[flook]

Э, батентка! Это вам в теорию и реализацию языков программирования надо
Есть классический одноименный учебник Ахо и Ульмана... Книжечка небольшая. Но скажу сразу - парсить С - забодаетесь из-за препроцессора.

[madskull]

Вот. Убегал с работы и забыл написать, что "слышал о существовании книжицы, ни авторов, ни названия не помню..."
В общем, это именно она. Спасибо, flook .

А под примитивами я имел в виду примерно следующее.
Есть C-образное выражение :

Код: Выделить всё

x+=somefunc(15)*(y-z);

И некоторая тулза должна из него слепить нечто такое, что мне потом проще разбирать, не отвлекаясь на проверку синтаксиса, директивы препроцессора, подстановку констант и тому подобное.
Например, я хочу получить из предыдущего выражения что-то Форто-образное:

Код: Выделить всё

15 somefunc y @ z @ - * x +!

Это обрабатывать, на мой взгляд, на порядки проще.
( Форт я взял для примера, поскольку, сколько не думаю, у меня всё сводится к нему )

[flook]

Погугли на предмет обратной польской нотации. Где-то есть тул, который такие конструкции в нее переводит. А уж ее прасить - одно удовольствие.

[madskull]

Погугли на предмет обратной польской нотации. Где-то есть тул, который такие конструкции в нее переводит. А уж ее прасить - одно удовольствие.

↑

Спасибо! (Как же я сразу не догадался по "обратную польскую"?!!)

[t.t]

Погугли на предмет обратной польской нотации. Где-то есть тул, который такие конструкции в нее переводит. А уж ее прасить - одно удовольствие.

↑

По идее это двойная работа: сначала тулза будет парсить прямую запись и переводить её в обратную, а потом уже самому руцями писать парсер обратной.

Я, кстати, когда-то синтаксический анализатор на тех же сях и писал (правда, только формулы, т.е. операторы и несколько функций типа exp(), log(), sqrt() и т.п.) -- ничего сложного там нет. Исходники, правда, утеряны в веках, но алгоритм могу на пальцах набросать, если надо. Правда, у меня сейчас со временем тяжко, так что срочности не обещаю.

[XPhoenix]

Есть такая "наука" - теория построения компиляторов
В общем случае копай в сторону: конечный автоматы, синтаксические деревья и.т.д
Обратная польская нотация, если я ничего не путаю - давно дело было, не очень применима для сложных грамматик. Например в Shell используются конечные автоматы, для деления исходного кода на лексемы...В более соложных грамматиках (С, С++ и.тд) используются деревья разбора....

Если неплохо в сторону Lisp'а глянуть, Refal'а...Ну и вообще функциональных языков программирования. - говорят что гуру данных языков пишут компиляторы буквально за пару-тройку дней..... )

Вот тебе ссылка на книгу по написанию компиляторов - считается "классическим"( по-моему ) учебником по данной теме - даже исходники интерпритаторов есть насколько я помню ....

Как прочтешь - пороешься в Инете на предмет более свежих разработок....Однако принципы, на которых стоят парсеры компиляторов не сильно-то поменялись за последние годы (ИМХО) )

Вот тут книга

PS: Вот блин, слепая тетеря я
Это и есть "Книга Дракона" - то бишь Ахо и Ульмана книженция....Вообщем если понадобиться мой сорс на книжку, то свисни когда скачаешь я его потру... )

[Ananas]

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

Интересует информация по разбору исходных файлов (напр. сишных): теория, алгоритмы, простые примеры.
А может даже в linux есть библиотеки или тулзы для разбора текста программ в какие-то примитивы?

Спасибо.

↑

тулзы - смотрите в сторону bison и flex

[madskull]

Всем спасибо, будем думать.

[oav]

Всем спасибо, будем думать.

↑

После вычитывания из красного дракона (эта как раз та "книжечка" Ахо и Ульмана - http://www.ozon.ru/context/detail/id/146264/ ) что такое граматика принципы ее построения и EBNF форма, можно сразу обращаться к мануалу на bison. Но лучше почитать Ахо поглубже Вообщем, все зависит от синтаксической сложности того что надо программе парсить, мож и вообще bison не понадобиться

[flook]

Про парсинг С могу сказать, что самый удачный проект (отличный от компилятора) выглядел как спайка перпроцессора (!) и собсно парсера, поскольку как я уже сказал парсить опрепроцессоренные исходники С, а особенно (готовьте камни) ПЛЮСОВЫЕ (даже неопрепроцесоренные)... В лучшем случае проще научиться на потолке спать и штаны через голову надевать

[madskull]

Да, в общем, у меня все проще. Это (может быть) будут С-образные скрипты. Которые будут переводиться, все-таки, в что-то Forth-подобное, а кроме Форта мне не известно ничего проще.

Так что ни о каких препроцессорах и, тем более, С++ наворотов речи нет.

А книжечку в электронном варианте полистал - интересно. Вероятно куплю бумажную.

Нашел и алгоритм разбора арифметических выражений (главный мой затык). Как оказалось, я с ним уже был знаком тыщу лет назад, но... склероз...

[oav]

Нашел и алгоритм разбора арифметических выражений (главный мой затык). Как оказалось, я с ним уже был знаком тыщу лет назад, но... склероз...

↑

офтопик
калькулятор на С++ :devil_2:

Код: Выделить всё

struct calc_closure : boost::spirit::closure<calc_closure, double>
{
    member1 val;
};

struct calculator : public grammar<calculator, calc_closure::context_t>
{
    template <typename ScannerT>
    struct definition
    {
        definition(calculator const& self)
        {
            top = expression[self.val = arg1];

            expression
                =   term[expression.val = arg1]
                    >> *(   ('+' >> term[expression.val += arg1])
                        |   ('-' >> term[expression.val -= arg1])
                        )
               ;

            term
                =   factor[term.val = arg1]
                    >> *(   ('*' >> factor[term.val *= arg1])
                        |   ('/' >> factor[term.val /= arg1])
                        )
               ;

            factor
                =   ureal_p[factor.val = arg1]
                |   '(' >> expression[factor.val = arg1] >> ')'
                |   ('-' >> factor[factor.val = -arg1])
                |   ('+' >> factor[factor.val = arg1])
               ;
        }

        typedef rule<ScannerT, calc_closure::context_t> rule_t;
        rule_t expression, term, factor;
        rule<ScannerT> top;

        rule<ScannerT> const&
        start() const { return top; }
    };
};

////////////////////////////////////////////////////////////////////////////
//
//  Main program
//
////////////////////////////////////////////////////////////////////////////
int
main()
{
    cout << "/////////////////////////////////////////////////////////\n\n";
    cout << "\t\tExpression parser using Phoenix...\n\n";
    cout << "/////////////////////////////////////////////////////////\n\n";
    cout << "Type an expression...or [q or Q] to quit\n\n";

    calculator calc;    //  Our parser

    string str;
    while (getline(cin, str))
    {
        if (str[0] == 'q' || str[0] == 'Q')
            break;

        double n = 0;
        parse_info<> info = parse(str.c_str(), calc[var(n) = arg1], space_p);

        //  calc[var(n) = arg1] invokes the calculator and extracts
        //  the result of the computation. See calculator grammar
        //  note above.

        if (info.full)
        {
            cout << "-------------------------\n";
            cout << "Parsing succeeded\n";
            cout << "result = " << n << endl;
            cout << "-------------------------\n";
        }
        else
        {
            cout << "-------------------------\n";
            cout << "Parsing failed\n";
            cout << "stopped at: \": " << info.stop << "\"\n";
            cout << "-------------------------\n";
        }
    }

    cout << "Bye... :-) \n\n";
    return 0;
}

[flook]

Doesn't even compile

[oav]

Doesn't even compile 

↑

это почему-то? :megalol:
в легкую! я пропустил инклуды и requirements

[sash-kan]

[offtopic]

Форт я взял для примера, поскольку, сколько не думаю, у меня всё сводится к нему

↑

да-а, хорошая штука была. я его даже на palm ставил :P (естественно, не как систему, а просто как интерпретатор).
кстати, не так давно где-то тут дискуссия была по поводу системных языков программирования, а про forth и не упомянули ни разу, хотя встроенные системы вполне себе на нем работали. помнится, даже у какого-то телескопа управление на forth-е было реализовано.
[offtopic]

[flook]

Doesn't even compile 

↑

это почему-то? :megalol:
в легкую! я пропустил инклуды и requirements

↑

Ага Вот возмет Линус, пропустит в очередном ядре инклуды... Все оценят.

[oav]

Doesn't even compile 

↑

это почему-то? :megalol:
в легкую! я пропустил инклуды и requirements

↑

Ага Вот возмет Линус, пропустит в очередном ядре инклуды... Все оценят.

↑

вставь в начало файла:

Код: Выделить всё

#include <boost/spirit/core.hpp>
#include <boost/spirit/attribute.hpp>
#include <iostream>
#include <string>

////////////////////////////////////////////////////////////////////////////
using namespace std;
using namespace boost::spirit;
using namespace phoenix;

и g++ на него (не забыв вначале apt-get install libboost-spirit* )

[demongloom]

у меня давно назревает план о создании своего языка программирования. типа более сишнутого пхп. даже препроцессор хочу встроить. но пока только в мыслях.