Re[8]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 03.10.14 14:38
Оценка:
Здравствуйте, WolfHound, Вы писали:

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

WH>Это в нашу таблицу не записать никак.

А там не одинарные IndentDec'и, а несколько идущих подряд — как в примере выше:
while(level < levels.top())
{
    yield('}');
    levels.pop();
    if(level > levels.top()) indentation_error();
}

Или ты имеешь в виду, что в твоём подходе можно поставить только одинарные?
Re[8]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 06.10.14 18:03
Оценка:
Здравствуйте, WolfHound, Вы писали:

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

WH>Это в нашу таблицу не записать никак.

Я же тебе говорил, что левая рекурсия получается.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 06.10.14 18:19
Оценка:
Здравствуйте, VladD2, Вы писали:

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

Не левая. И не рекурсия.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[10]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 06.10.14 23:17
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


Результат тот же. Ты не можешь записать инфу о парсеинге одного и того же правила с одной позиции.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 07.10.14 14:34
Оценка:
Здравствуйте, VladD2, Вы писали:

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

VD>Результат тот же. Ты не можешь записать инфу о парсеинге одного и того же правила с одной позиции.
Не тот же. В данном случае даже в структуры Эрли парсера нельзя записать эту информацию.
При этом если добавить отдельный лексер или изменить строку, то и основной парсер справится с этой задачей.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[14]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 07.10.14 15:14
Оценка: 7 (1)
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, надо будет проверить.
Отредактировано 14.06.2015 7:34 Evgeny.Panasyuk . Предыдущая версия . Еще …
Отредактировано 07.10.2014 15:17 Evgeny.Panasyuk . Предыдущая версия .
Отредактировано 07.10.2014 15:16 Evgeny.Panasyuk . Предыдущая версия .
Re[11]: [Nitra] Парсинг языков базирующихся на отсупах
От: damir  
Дата: 18.04.18 14:19
Оценка:
VladD2, есть ли новости по теме ?
Re[12]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.04.18 15:06
Оценка:
Здравствуйте, damir, Вы писали:

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


По поводу поддержки отступных грамматик ничего не делалось, к сожалению. Единственное, что можно попробовать самому в режиме препроцессора парсить. Первым проходом вставить символы заменяющие скобки, а далее уже парсить результат. Потом, правда придется скорректировать позиции сообщений локейшонов.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.04.18 15:30
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

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


Все с точностью до наоборот. Чем мощнее алгоритмы, тем они хуже могут передавать состояние. Этот отступ нужно при каждом откате восстанавливать. Если у нас чистый LL(k) с этим проблем нет. Если обобщенный алгоритм, то это становится серьезной проблемой.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[17]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.04.18 15:44
Оценка:
Здравствуйте, 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.

http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[17]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.04.18 15:46
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

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


Проблема в том, что у нас нет лексера. Точнее каждое правило имеет свой лексер, а отдельного лексического шага (где бы выделялись токены) нет вообще.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.04.18 15:52
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

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

EP>В терминах C++ STL просто нужен адаптер для итератора, и никаких изменений в коде парсера

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

Еще Нитра использует алгоритм которому нежен индексированный доступ. Причем максимально эффективный. Так что "виртуальный вью" здесь не подойдет. Придется материализовать его в строку. А вот локейшоны можно преобразовывать туда-сюда с помощью таблицы соответствий.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.