[Nitra] Парсинг языков базирующихся на отсупах - Nemerle

Здравствуйте, WolfHound, Вы писали:

WH>В данном случае у нас первый IndentDec должен закрыть два IndentInc. А второй 3.
WH>Это в нашу таблицу не записать никак.

А там не одинарные IndentDec'и, а несколько идущих подряд — как в примере выше:

while(level < levels.top())
{
    yield('}');
    levels.pop();
    if(level > levels.top()) indentation_error();
}

Или ты имеешь в виду, что в твоём подходе можно поставить только одинарные?

Здравствуйте, WolfHound, Вы писали:

WH>В данном случае у нас первый IndentDec должен закрыть два IndentInc. А второй 3.
WH>Это в нашу таблицу не записать никак.

Я же тебе говорил, что левая рекурсия получается.

Здравствуйте, VladD2, Вы писали:

VD>Я же тебе говорил, что левая рекурсия получается.

Не левая. И не рекурсия.

... << RSDN@Home 1.2.0 alpha 5 rev. 62>>

Здравствуйте, WolfHound, Вы писали:

WH>

Не левая. И не рекурсия.

Результат тот же. Ты не можешь записать инфу о парсеинге одного и того же правила с одной позиции.

Здравствуйте, VladD2, Вы писали:

WH>>

Не левая. И не рекурсия.
VD>Результат тот же. Ты не можешь записать инфу о парсеинге одного и того же правила с одной позиции.
Не тот же. В данном случае даже в структуры Эрли парсера нельзя записать эту информацию.
При этом если добавить отдельный лексер или изменить строку, то и основной парсер справится с этой задачей.

... << RSDN@Home 1.2.0 alpha 5 rev. 62>>

EP>Пример фильтра-препроцессора:

Пример без корутины-препроцессора, используя только возможности Boost.Spirit — через inherited attributes передаётся текущий уровень индентации:

/*******************************************************************************************/        
root = statements(0u);

statements     = *line_statement(lvl);
line_statement = indent(lvl) >> statement(lvl);
statement      = (expression >> newline) | while_(lvl) | if_(lvl) | function(lvl);
expression     = *alnum;

if_        = "if"_k    >> +space >> expression >> block(lvl) >> indent(lvl) >> "else"_k >> block(lvl);
while_     = "while"_k >> +space >> expression >> block(lvl);
function   = "def"_k   >> +space >> expression >> '(' >> expression >> ')' >> block(lvl);

block      = ':' >> ((newline >> compound(lvl)) | (+space >> statement(lvl)));
compound   = omit[ indent_inc(lvl)[_a = _1] ] >> +line_statement(_a) >> indent_dec(lvl);

indent_inc = & repeat(lvl + 1, inf)[space][_val = phoenix::size(_1)];
indent_dec = & repeat(0u     , lvl)[space];
indent     =   repeat(lvl         )[space];
/*******************************************************************************************/

Кстати, как видно, при таком подходе помимо indent_inc, indent_dec понадобился ещё и indent.

Как я понимаю, если парсеры Nemerle/Nitra настолько же мощны — то тоже должно получиться.

Тесты


def foo():
    a1

    a2
    if 1:
        b2
        b3
    else:
        b4
        while 4:
            e1
    a2
    a3
    while 2: c1
    a3

(
    ((("")))
    (
        (
            (
                "d" "e" "f" " " "foo" ""
                (
                    (
                        (
                            (
                                ((("a1")))
                                ((("a2")))
                                (
                                    (
                                        (
                                            "i" "f" " " "1"
                                            (
                                                (((((("b2")))
                                                ((("b3"))))))
                                            )
                                            "e" "l" "s" "e"
                                            (
                                                (
                                                    (
                                                        (
                                                            ((("b4")))
                                                            (
                                                                (
                                                                    (
                                                                        "w" "h" "i" "l" "e" " " "4"
                                                                        ((((((("e1")))))))
                                                                    )
                                                                )
                                                            )
                                                        )
                                                    )
                                                )
                                            )
                                        )
                                    )
                                )
                                ((("a2")))
                                ((("a3")))
                                (
                                    (
                                        (
                                            "w" "h" "i" "l" "e" " " "2" 
                                            ((" " (("c1"))))
                                        )
                                    )
                                ) 
                                ((("a3")))
                            )
                        )
                    )
                )
            )
        )
    )
)


a1
while 2:
    b2
    b3
    while 3:
        c3
  while 1: b4

Tail={  while 1: b4
}

LIVE DEMO

full code

#include <boost/spirit/include/support_multi_pass.hpp>
#include <boost/spirit/include/support_utree.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/phoenix.hpp>
#include <boost/coroutine/all.hpp>

#include <functional>
#include <iterator>
#include <iostream>
#include <cstddef>
#include <string>

using namespace boost;
using namespace spirit;
using namespace coroutines;
using namespace qi;

/***************************************************************************************/
auto operator "" _k(const char *keyword, size_t)
{
    return string(keyword);
}

template <typename Iterator>
struct PythonGrammar : grammar<Iterator, utree()>
{
    template<typename ...Ts>
    using Rule = rule<Iterator, Ts...>;
    
    template<typename Result, typename ...Ts>
    using LevelRule = Rule<Result(unsigned), Ts...>;

    template<typename Result>
    using SimpleRule = Rule<Result()>;

    // Some of following fields can be replaced by auto deduction
    Rule<utree()> root;

    SimpleRule<std::string> expression;

    LevelRule<utree> statements, function, while_, if_;
    LevelRule<utree::list_type> statement, line_statement, block;
    LevelRule<utree::list_type, locals<unsigned>> compound;

    LevelRule<unsigned> indent_inc;
    LevelRule<void> indent_dec, indent;

    PythonGrammar()
        : PythonGrammar::base_type(root)
    {
        auto lvl = _r1;
        auto space    = char_(' ');
        auto newline = +eol;
        /*******************************************************************************************/        
        root = statements(0u);

        statements     = *line_statement(lvl);
        line_statement = indent(lvl) >> statement(lvl);
        statement      = (expression >> newline) | while_(lvl) | if_(lvl) | function(lvl);
        expression     = *alnum;

        if_        = "if"_k    >> +space >> expression >> block(lvl) >> indent(lvl) >> "else"_k >> block(lvl);
        while_     = "while"_k >> +space >> expression >> block(lvl);
        function   = "def"_k   >> +space >> expression >> '(' >> expression >> ')' >> block(lvl);

        block      = ':' >> ((newline >> compound(lvl)) | (+space >> statement(lvl)));
        compound   = omit[ indent_inc(lvl)[_a = _1] ] >> +line_statement(_a) >> indent_dec(lvl);

        indent_inc = & repeat(lvl + 1, inf)[space][_val = phoenix::size(_1)];
        indent_dec = & repeat(0u     , lvl)[space];
        indent     =   repeat(lvl         )[space];
        /*******************************************************************************************/
    }
};
/***************************************************************************************/
auto test_parse_python = [](const auto &code)
{
    auto first = begin(code),
         last  = end(code) - 1;

    PythonGrammar< decltype(first) > py;
    utree tree;
    bool done = parse(first, last, py, tree);

    using namespace std;
    cout << "Code:" << endl << code << endl;
    if (done && first == last)
        cout << "Succeeded: " << tree << endl;
    else
        cout << "Tail={" << std::string(first, last) << "}" << endl;
    cout << std::string(80, '_') << endl;
};
/***************************************************************************************/
constexpr auto &good_python_code = R"python(
def foo():
    a1

    a2
    if 1:
        b2
        b3
    else:
        b4
        while 4:
            e1
    a2
    a3
    while 2: c1
    a3
)python";
/***************************************************************************************/
constexpr auto &bad_python_code = R"python(
a1
while 2:
    b2
    b3
    while 3:
        c3
  while 1: b4
)python";
/***************************************************************************************/
int main()
{
    test_parse_python(good_python_code);
    test_parse_python(bad_python_code);
}

UPD: Походу здесь indent_dec вообще не нужен — достаточно indent_inc и indent, надо будет проверить.

VladD2, есть ли новости по теме ?

Здравствуйте, damir, Вы писали:

D>VladD2, есть ли новости по теме ?

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

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Как я понимаю, если парсеры Nemerle/Nitra настолько же мощны — то тоже должно получиться.

Все с точностью до наоборот. Чем мощнее алгоритмы, тем они хуже могут передавать состояние. Этот отступ нужно при каждом откате восстанавливать. Если у нас чистый LL(k) с этим проблем нет. Если обобщенный алгоритм, то это становится серьезной проблемой.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Наткнулся на вот такую статью: Principled Parsing for Indentation-Sensitive Languages

Что-то как-то совсем "матанисто"

И совсем не радует вот это:

Experiments on a Haskell parser using this formalism show that the parser runs between one and three times slower than a parser using traditional ad hoc techniques for handling indentation sensitivity.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Вот The Python Language Reference — там и граматика, и лексер.

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

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Виртуальные скобки это просто виртуальный view оригинального текста, и через призму этого view видно текст со вставленными скобками (которые вообще не входят в оригинальный набор символов), хотя никаких inplace изменений не было.
EP>В терминах C++ STL просто нужен адаптер для итератора, и никаких изменений в коде парсера

Согласен. Но не все так просто. Сквозь эту "призму" нужно пропускать много чего. Причем в обе стороны. Нужно сделать преобразование локейшонов по некой таблице виртуальных скобок.

Еще Нитра использует алгоритм которому нежен индексированный доступ. Причем максимально эффективный. Так что "виртуальный вью" здесь не подойдет. Придется материализовать его в строку. А вот локейшоны можно преобразовывать туда-сюда с помощью таблицы соответствий.

	От:	Evgeny.Panasyuk
	Дата:	03.10.14 14:38
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	06.10.14 18:03
Оценка:

	От:	WolfHound
	Дата:	06.10.14 18:19
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	06.10.14 23:17
Оценка:

	От:	WolfHound
	Дата:	07.10.14 14:34
	Оценка:

	От:	damir
	Дата:	18.04.18 14:19
	Оценка: