Re[10]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 20:12
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Про левую рекурсию не забыл? Она тут не стрельнет?

Не вижу в каком месте она может стрельнуть.

VD>Про NewLine не понял. Наверно ты имеешь в виду требование начала новой вложенности.

Нет. NewLine это перевод строки.
IndentInc начало новой вложенности.
Indent текущий отступ.
IndentDec конец.

VD>Там еще вопросы есть. Например, в некоторых языках можно искусственно игнорировать конец строки и рассматривать следующую строку как продолжение предыдущей. Например, в Васике это "_" в конце строки. А в Питоне, вроде бы, "\". Причем она даже в строках действует.

Пробельное правило просто не должно содержать перевод строки.
Но должно содержать:
"_" NewLine

И всё.

VD>Так что твоя грамматика не верна. В прочем, это детали. Может и прокатить.

А так?
syntax Block
{
  | MultyLine = ":" NewLine IndentInc (Indent Statement)+ IndentDec;
  | OneLine   = ":" OneLineStatement NewLine;
}

syntax Statement
{
  | If               = "if" Expression Block else Block;
  | While            = "while" Expression Block;
  | OneLineStatement = OneLineStatement NewLine;
}

syntax OneLineStatement
{
  | Return  = "return " Expression;
}
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Отредактировано 02.10.2014 21:16 VladD2 . Предыдущая версия .
Re[14]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 02.10.14 20:24
Оценка:
Здравствуйте, WolfHound, Вы писали:

EP>>Или ты имеешь в виду что у парсера больше информации чем у итератора, и из-за этого ему требуется меньше проверок?

WH>Если между парсером и текстом будет стоять итератор то обращение к таблице будет на каждый символ.
WH>Ибо парсер работает с символами.
WH>А если записать данные непосредственно в таблицу мемоизации парсера, то обращения к ней будут только в тех местах, где есть вызов этих правил.

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

WH>Как фильтр точно не вариант. Ибо тормоза.

WH>Отдельным проходом можно. Но тут тоже не всё хорошо.

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

Кстати, если проход отдельный, и не хочется залезать в charset, то можно просто расширить кодировку — это избавит от необходимости смотреть в таблицу при парсинге.
Re[11]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 02.10.14 20:27
Оценка: +1
Здравствуйте, WolfHound, Вы писали:

WH>IndentInc начало новой вложенности.

WH>Indent текущий отступ.
WH>IndentDec конец.

Indent тут избыточен (препроцессор будет его просто съедать), можно без него — только с IndentInc+IndentDec.
Отредактировано 02.10.2014 20:30 Evgeny.Panasyuk . Предыдущая версия .
Re[12]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 20:44
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Indent тут избыточен (препроцессор будет его просто съедать), можно без него — только с IndentInc+IndentDec.

Это если текст менять. А если закладывать данные в таблицу мемоизации или протаскивать контекст, то необходим.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 20:48
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Без существенной модификации парсера — тут либо то, либо то.

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

WH>Ну и задача максимум сделать так чтобы всё происходило за один проход.


В этом нет особого смысла. Практика показала, что простые препроцессоры обычно работают дико быстро. Препроцессор Шарпа на составляет и пол процента от общего времени парсинга, например.

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

EP>Ещё раз, ты же сам сказал выше что парсер будет лезть в таблицу.

EP>Или ты имеешь в виду что у парсера больше информации чем у итератора, и из-за этого ему требуется меньше проверок?

Он имел в виду, что некий перпоцессор читает исходный файл и не создавая новый файл записывает информацию о виртуальных скобках во внутренние структуры парсера.

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

В общем, идея здравая. Ее нужно использовать, если не будет противопоказаний.

EP>Ок, вот в этом варианте:

EP>

WH>>Препроцессор должен не менять строку, а записать в таблицу мемоизации виртуальные скобки.

Он когда должен работать? Отдельным проходом или как фильтр?


Да, отдельным. Но строку не менять и новой не создавать. Таблицы пересчетов тоже при этом не нужны. Препроцессорт только читает файл и говорит парсеру, что в таких то местах спарсились такие-то правила.

Это реально решает одну из проблема.

Остается вторая проблема — сделать так, чтобы препроцессор не приходилось писать на ЯВУ. Оптимально описать на некотором ДСЛ-е правила извлечения информации о скобках/блоках и т.п.

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

WH>Идеально было бы протаскивание некоторого контекста через парсер. И разбор соответствующих правил с его учётом. Но тут появляются осложнения с восстановление после ошибок.


Думаю, что совмещать разбор отступов и прсинг не реально. Проще препроцессировать всю разбираемую строку. Это будет дико быстро. Стас уже проверил это на препроцессоре шарпа.

Этот препроцессор можно сделать и инкрементальным. Он ведь линейны. Если отступ на предыдущей строке совпал и на сроке идущей за имененной, то можно менять только отступ для текущей строки (и т.п.).
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [Nitra] Парсинг языков базирующихся на отсупах
От: Marty Пират  
Дата: 02.10.14 21:00
Оценка:
Здравствуйте, WolfHound, Вы писали:

STD>>а то, судя по всему, в 2014 уже никто не хочет делать языки со скобками.

WH>Это мода. Пройдёт.

Причем ужасная. Почему мне диктуют, как форматировать мои исходники? Потому и не пользуюсь питоном
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 21:11
Оценка: 8 (1)
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Понятно, то есть у парсера больше необходимой информации.

EP>А нельзя ли использовать нужный тип итератора в зависимости от того какие правила заданны? Или там всё равно будет недостаточно информации?

Просто нужно сделать АПИ, чтобы прероцессор тупо дергал функции вроде:
BeginBlock(pos : int);
EndBlock(pos : int);

Эти функции говорят парсеру где начинаются и кончаются блоки. Он преоразует их в предопределенные правила. В грамматике тупо помещаются ссылки на эти правила. Вуаля! Имеем парсер для скобочного языка, но вместо скобок выступают виртуальные правила.

EP>Без существенной модификации парсера — тут либо то, либо то.

EP>Причём отдельный проход — это ведь тоже тормоза. Правда если весь файл помещается в кэш (и не вымывается из него) — то от второго прохода не так много тормозов.

Простой препроцессор (а подсчет отступов это очень простой препроцессор) будет отрабатывать в микросекунды даже на мегабайтных файлах. Так что это не проблема.

EP>Кстати, если проход отдельный, и не хочется залезать в charset, то можно просто расширить кодировку — это избавит от необходимости смотреть в таблицу при парсинге.


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

Так вот в этот массив и можно подсунуть информацию о правиле парсящем скобки. Только сделает это не парсер лично, а препроцессор, через некоторое АПИ. В общем, это детали.

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

WH>А так?

WH>
WH>syntax Block
WH>{
WH>  | MultyLine = ":" NewLine IndentInc (Indent Statement)+ IndentDec;
WH>  | OneLine   = ":" OneLineStatement NewLine;
WH>}
WH>


Сдается мне этот NewLine просто лишний. Если будет информация о блоках, то накаких приседаний просто ненужно.

Будет именно что
syntax Block
{
  | MultyLine = ":" IndentInc (Indent Statement)+ IndentDec;
  | OneLine   = ":" OneLineStatement NewLine;
}

Парсер сам разрулит неоднозначность на основании этих самых IndentInc/IndentDec. Точнее ее, для парсера, просто не будет. Он увидит IndentInc и пойдев путем блока, а не увидев его пойдет путем выражения.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Отредактировано 03.10.2014 4:01 VladD2 . Предыдущая версия .
Re[13]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 21:20
Оценка:
Здравствуйте, WolfHound, Вы писали:

EP>>Indent тут избыточен (препроцессор будет его просто съедать), можно без него — только с IndentInc+IndentDec.

WH>Это если текст менять. А если закладывать данные в таблицу мемоизации или протаскивать контекст, то необходим.

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

VD>Думаю, что совмещать разбор отступов и прсинг не реально.

С основным парсером вообще не проблема. С восстанавливающим есть над чем подумать. Но думаю тоже можно.
Преимущество совмещённого режима в том что мы сможем внутри одного исходника свободно переключаться между режимами.
Более того протягивание контекста нам нужно для реализации изменения грамматики во время разбора.
Задачи близкородственные. Думаю, можно будет решить их одним механизмом.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: [Nitra] Парсинг языков базирующихся на отсупах
От: STDray http://stdray.livejournal.com
Дата: 02.10.14 23:35
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Тут
Автор: WolfHound
Дата: 02.10.14
Вольфхаунд подкинул интересную мысль.

Я читал, но у меня пока нет понимания внутреннего устройства нитры, чтобы оценить.

VD>Препроцессор там должен быть примитивнийший. Думаю, его не составит труда написать и вручную. Предоставим АПИ позволяющее регистрировать эти виртуальные токены и вперед...

VD>Что касается декларативного варианта, то нужно придумать это самое декларативное описание, так чтобы с его помощью можно было покрыть имеющиеся юзкейсы.
В прошлое обсуждение сошлись на том, что надо придумать некий генерик-механизм и декларативное описание для него. Время прошло, а механизма, чтобы синтаксис на отступах был его частным случаем, никто не предоставил. И Вольфхаунд, как я понял, пишет про то, как безболезненно захардкодить отступы в парсер.

STD>>>>как дружить все это дело со студийной интеграцией

STD>>Вопрос открытый. Потому что нет идей, как, допустим, параметризовать SourceSnapshot кастомным препроцессором во время работы интеграции. Или, допустим, имея наследника SourceSnapshot с зашитой логикой препроцессинга и пересчета, указать интеграции, что надо использовать именно его?
VD>Ну, дернуть функцию перед работай парсера не сложно.
Я не понимаю. Я про Adding new language suppor (http://confluence.jetbrains.com/display/Nitra/VsExtension). И как для своего язычка с отступами заставить все работать через свой препроцессор, понять пока не могу.

VD>Лучше, конечно, придумать декларативный вариант. Тогда и дергать ничего не пришлось бы.

Конечно лучше. Я это изначально обозвал как "Способ описания отступов в самой грамматике"

VD>Как вставить виртуальные скобки уже понятно. Это упрощает проблему. Осталось придумать как описывать принцип преобразования отступов в эти виртуальные скобки.

Полагаю, что надо начать с варианта "отступ больше текущего" = индент, и "отступ меньше текущего, равный вершине стека" = дедент, иначе — ошибка.
Я пытался как-то добрасывать дедентов и бэддедентов ради парсера, но это всё "эвристика".
Просто смотрел, в каком случае парсер больше всего разбирает и пришел к такому решению.
Не думаю, что парсер должен таким страдать.
Re[13]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 03.10.14 03:04
Оценка:
Пример фильтра-препроцессора:
// Grammar:
function   = string("def")   >> +space >> expression >> '(' >> expression >> ')' >> block;
while_     = string("while") >> +space >> expression >> block;
if_        = string("if")    >> +space >> expression >> block >> string("else") >> block;

block      = ':' >> ((eol >> '{' >> statements >> '}') | (+space >> statement));
statement  = (expression >> eol) | while_ | if_ | function;
expression = *alnum;
statements = *statement;
/***************************************************************************************/
auto identation_preprocessor = [](auto it, auto &yield)
{
    std::stack<unsigned> levels({0u});
    while(*it)
    {
        auto level = 0u;
        while(*it == ' ')
        {
            ++level;
            ++it;
        }

        if(level > levels.top())
        {
            yield('{');
            levels.push(level);
        }
        else while(level < levels.top())
        {
            yield('}');
            levels.pop();
            if(level > levels.top())
                for_each("<$indentation error$>", std::ref(yield));
        }

        while(*it)
        {
            auto x = *it++;
            yield(x);
            if(x == '\n') break;
        }
    }

    auto n = levels.size();
    while(--n) yield('}');
};

Тесты:

def foo():
    a1
    if 1:
        b2
        b3
    else:
        b4
    a2
    while 2: c1
    a3

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


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

Failed at: <$indentation error$>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/range/algorithm.hpp>
#include <boost/coroutine/all.hpp>

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

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

/***************************************************************************************/
template <typename Iterator>
struct PythonGrammar : grammar<Iterator, utree()>
{
    template<typename Result>
    using Rule = rule<Iterator, Result()>;

    // Some of following fields can be replaced by auto deduction
    Rule<utree> statements, function, while_, if_;
    Rule<utree::list_type> statement, block;
    Rule<std::string> expression;

    PythonGrammar()
        : PythonGrammar::base_type(statements)
    {
        auto space = qi::ascii::space;
        /*******************************************************************************************/
        function   = string("def")   >> +space >> expression >> '(' >> expression >> ')' >> block;
        while_     = string("while") >> +space >> expression >> block;
        if_        = string("if")    >> +space >> expression >> block >> string("else") >> block;

        block      = ':' >> ((eol >> '{' >> statements >> '}') | (+space >> statement));
        statement  = (expression >> eol) | while_ | if_ | function;
        expression = *alnum;
        statements = *statement;
        /*******************************************************************************************/
    }
};
/***************************************************************************************/
auto identation_preprocessor = [](auto it, auto &yield)
{
    std::stack<unsigned> levels({0u});
    while(*it)
    {
        auto level = 0u;
        while(*it == ' ')
        {
            ++level;
            ++it;
        }

        if(level > levels.top())
        {
            yield('{');
            levels.push(level);
        }
        else while(level < levels.top())
        {
            yield('}');
            levels.pop();
            if(level > levels.top())
                for_each("<$indentation error$>", std::ref(yield));
        }

        while(*it)
        {
            auto x = *it++;
            yield(x);
            if(x == '\n') break;
        }
    }

    auto n = levels.size();
    while(--n) yield('}');
};
/***************************************************************************************/
auto test_parse_python = [](const auto &code)
{
    coroutine<char>::pull_type coro([&](auto &yield)
    {
        identation_preprocessor(begin(code), yield);
    });
    auto first = make_default_multi_pass(begin(coro)),
         last = make_default_multi_pass(end(coro));

    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 << "Failed at: " << std::string(first, last) << endl;
    cout << std::string(80, '_') << endl;
};
/***************************************************************************************/
constexpr auto &good_python_code = R"python(
def foo():
    a1
    if 1:
        b2
        b3
    else:
        b4
    a2
    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);
}
Re[16]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 03.10.14 11:16
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Где можно почитать правила распознавания блоков в Питоне и других языках где применяются отступы?


Вот The Python Language Reference — там и граматика, и лексер.
А вот конкретно раздел про индентацию:

...
The indentation levels of consecutive lines are used to generate INDENT and DEDENT tokens, using a stack, as follows.
...

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

VD>Где можно почитать правила распознавания блоков в Питоне и других языках где применяются отступы?


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

This paper presents a grammatical formalism for indentation-sensitive languages. It is both expressive and easy to use. We derive provably correct GLR and LR(k) parsers for this formalism. Though not shown here, CYK, SLR, LALR, GLL and LL(k) parsers can also be constructed by appropriately using the key technique of factoring item sets. 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. Improvements in the handling of indentation sets may reduce this overhead. Using these techniques, the layout rules of a wide variety of languages can be expressed easily and parsed effectively.

Re[7]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 03.10.14 13:50
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Тут на самом деле всё намного проще можно сделать.

Я тут ещё подумал. Не получится совсем так просто.
class Asd:
    def sdf(qwe):
        for a in b:
            c
    def sdf(qwe):
        for a in b:
            c

syntax Block = ":" NewLine IndentInc (Indent Statement)+ IndentDec;

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

Соответственно нужно либо делать полноценный препроцессинг вставляя скобки физически.
Либо протаскивать через парсер контекст. Чтобы можно было сделать так
syntax Block = ":" NewLine IndentInc[level] (Indent[level] Statement)+ IndentDec[_ < level];
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[16]: [Nitra] Парсинг языков базирующихся на отсупах
От: novitk США  
Дата: 03.10.14 14:26
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Где можно почитать правила распознавания блоков в Питоне и других языках где применяются отступы?


https://docs.python.org/2/reference/lexical_analysis.html
Отредактировано 03.10.2014 14:27 novitk . Предыдущая версия .
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.