Re[4]: [Nitra] Парсинг языков базирующихся на отсупах
От: STDray http://stdray.livejournal.com
Дата: 02.10.14 11:59
Оценка: 50 (1)
VD>Часть из этих языков уже довольно старые. Ну, и не сложно найти еще большую тучу скобочных языков.
Согласен, не сложно. С другой стороны, я просматривал различные генераторы парсеров и практически нигде проблема разбора языков с синтаксисом на отступах из коробки не решена. Хотя устойчивый интерес есть.

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


Я делал что-то вроде
#pragma indent
using Nemerle
using Nemerle.Imperative
using System
using System.IO
using System.Text
using SCG = System.Collections.Generic

namespace SampleParserApplication2

    [Record] class IndentPreprocessor
        public Indent    : char
        public Dedent    : char 
        public BadDedent : char
    
        public Preprocess(input : string) : string 
            input |> StringReader |> Preprocess
        
        public Preprocess(reader : TextReader) : string 
            def builder     = StringBuilder()
            def indentSizes = SCG.Stack()
            mutable prevIndentSize : int? = null
            for(mutable line  = reader.ReadLine(); line != null; line = reader.ReadLine())
                def currentIndentSize = GetIndentSize(line)
                when(currentIndentSize == line.Length && line.Length >= 0)
                    continue;
                when(!prevIndentSize.HasValue) 
                    prevIndentSize = currentIndentSize
                if(prevIndentSize.Value < currentIndentSize)
                    indentSizes.Push(prevIndentSize.Value)
                    _ = builder.Append(Indent)
                else when(prevIndentSize.Value > currentIndentSize) 
                    _ = builder.Append <| 
                        if(indentSizes.Count > 0) 
                            match(indentSizes.Peek())
                                | x when x == currentIndentSize => _ = indentSizes.Pop(); Dedent
                                | x when x >  currentIndentSize => _ = indentSizes.Pop(); BadDedent
                                | _                             =>                        BadDedent
                        else BadDedent
                prevIndentSize = currentIndentSize
                _ = builder.Append(Environment.NewLine).Append(line)
            foreach(currentIndentSize in indentSizes)
                _ = builder.Append <| 
                    if(currentIndentSize < prevIndentSize.Value) Dedent
                    else                                         BadDedent
            builder.ToString();
    
        static GetIndentSize(line : string) : int
            mutable size = 0
            while(size < line.Length && line[size] == ' ')
                size++
            size


и использование
        def preprocessor = IndentPreprocessor('\uE001', '\uE002', '\uE003');
        def result = preprocessor.Preprocess(str);
        def source = SourceSnapshot(result);

  token INDENT  = '\uE001';
  token BADDENT = '\uE003';
  token DEDENT  = BADDENT? '\uE002';


То есть была какая-то идея, чтобы
— использовать символы из приватного диапазона юникода для расстановки виртуальных скобок.
— использовать некий BadDedent для разметки кривых отступов, чтобы парсер мог сгенерировать ошибку вида "Dedent expected", восстановиться и разбирать дальше.
— использовать конструктор SourceSnapshot this(originalText : string, text : string, fileIndex : int, fileName : string, lineIndexes : array[int], textOffset : int); для корректного позиционирования ошибок после расстановки виртуальных скобок.

Но потом я от этой идеи отказался, потому что непонятно, как дружить все это дело со студийной интеграцией. Да и то, что надо в двух местах указывать символы для виртуальных скобок мне не понравилось. Так что я считаю, пусть какое-то простенькое решение, но должно быть в коробке.
Отредактировано 02.10.2014 12:01 STDray . Предыдущая версия .
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, то можно просто расширить кодировку — это избавит от необходимости смотреть в таблицу при парсинге.


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

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

Нужно придумать как описать логику перевода текста в блоки и проблема будет решаться автоматически.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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] Парсинг языков базирующихся на отсупах
От: 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 . Предыдущая версия .
[Nitra] Парсинг языков базирующихся на отсупах
От: STDray http://stdray.livejournal.com
Дата: 29.09.14 10:45
Оценка:
Здравствуйте, WolfHound.

Способ описания отступов в самой грамматике придумать удалось? Стоит вообще этого ожидать, а то, судя по всему, в 2014 уже никто не хочет делать языки со скобками.

03.10.14 00:48: Ветка выделена из темы Nemerle через 5 лет &mdash; выстрелит или скончается?
Автор: AndrewVK
Дата: 30.09.09
— VladD2
Re: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 29.09.14 14:25
Оценка:
Здравствуйте, STDray, Вы писали:

STD>Способ описания отступов в самой грамматике придумать удалось? Стоит вообще этого ожидать,

В смысле поддержку языков на отступах типа питона?
В планах есть. Непреодолимых проблем не вижу. Но в данный момент это не приоритет.

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

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

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


Что-то не заметил этой тенденции. Можно примеры привести?

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

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

Для реализации своего языка — это подойдет. Но для воспроизведения того же Питона — нет. Для этого требуется препроцессирование и двухпроходный парсинг.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 30.09.14 18:02
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Для реализации своего языка — это подойдет. Но для воспроизведения того же Питона — нет. Для этого требуется препроцессирование и двухпроходный парсинг.

Ты уверен что он не сводится к расстановке виртуальных скобок?
  syntax Block = ":" NewLine IndentInc (Indent Statement)+ IndentDec;

  syntax Statement
  {
    | If      = "if" Expression Block else Block;
    | While   = "while" Expression Block;
    | Return  = "return " Expression NewLine;
  }
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Отредактировано 03.10.2014 3:59 VladD2 . Предыдущая версия .
Re[2]: [Nitra] Парсинг языков базирующихся на отсупах
От: STDray http://stdray.livejournal.com
Дата: 01.10.14 13:42
Оценка:
Здравствуйте, VladD2, Вы писали:

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

VD>Что-то не заметил этой тенденции. Можно примеры привести?
f#, coffescript, haml, scss, dg, ela, nimrod, purescript, moonscript, livescript, snowscript, sugarcpp
вот такое вспомнилось

VD>С другой стороны можно, относительно легко, сделать поддержку отсупного синтаксиса как это было сделано в Немерле. Ну, то есть набор правил интерпретации отступов как виртуальных скобок.

Я думаю, это был бы отличный вариант. По крайней мере у меня сложилось впечатление, что рассматривая генераторы парсеров, люди часто интересуются как делать отступный синтаксис.
Re[3]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.10.14 23:59
Оценка:
Здравствуйте, STDray, Вы писали:

STD>f#, coffescript, haml, scss, dg, ela, nimrod, purescript, moonscript, livescript, snowscript, sugarcpp

STD>вот такое вспомнилось

Часть из этих языков уже довольно старые. Ну, и не сложно найти еще большую тучу скобочных языков.

STD>Я думаю, это был бы отличный вариант. По крайней мере у меня сложилось впечатление, что рассматривая генераторы парсеров, люди часто интересуются как делать отступный синтаксис.


Как я уже говорил, можно относительно не сложно, и полностью автоматически сделать аналог немерлововго решения, когда некий препроцессор расставляет вымышлинные скобки на базе некоторого алгоритма, а далее парсинг происходит по обычным принципам.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Отредактировано 02.10.2014 0:01 VladD2 . Предыдущая версия .
Re[5]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 13:27
Оценка:
Здравствуйте, STDray, Вы писали:

STD>Я делал что-то вроде...


STD>
STD>  token INDENT  = '\uE001';
STD>  token BADDENT = '\uE003';
STD>  token DEDENT  = BADDENT? '\uE002';
STD>


STD>То есть была какая-то идея, чтобы

STD>- использовать символы из приватного диапазона юникода для расстановки виртуальных скобок.

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

То что ты предлагаешь сделать можно. Хотя и не так просто, так как токенов, как таковых, у нас нет. Мы парсим непосредственно текст.

STD>- использовать конструктор SourceSnapshot this(originalText : string, text : string, fileIndex : int, fileName : string, lineIndexes : array[int], textOffset : int); для корректного позиционирования ошибок после расстановки виртуальных скобок.


Ну, да. У нас там уже базовая инфраструктура для ремапинга есть. Так что в теории это возможно.

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


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

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

Можно сделать половинчатое решение. Препроцессор пишется вручную, но использует механизм пересчета (relocation) встроенный в SourceSnapshot (его доведем до нужного уровня).

Вставлять, кстати, можно обычные скобки, а не какие-то страшные символы. Но можно и страшные, если язык не позволяет.

Собственно, если есть желание, можешь сам это дело реализовать. Мы же теперь опен-сорс.

Мы поможем разобраться в деталях. Допилим что надо...
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: [Nitra] Парсинг языков базирующихся на отсупах
От: STDray http://stdray.livejournal.com
Дата: 02.10.14 14:28
Оценка:
Здравствуйте, VladD2, Вы писали:

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

В Питоне, емнип, можно в одном файле для идентации и пробелы и табы использовать, что само по себе мрак.

VD>То что ты предлагаешь сделать можно. Хотя и не так просто, так как токенов, как таковых, у нас нет. Мы парсим непосредственно текст.

VD>Вставлять, кстати, можно обычные скобки, а не какие-то страшные символы. Но можно и страшные, если язык не позволяет.
В идеале, пользователь вообще не должен задумываться о том, какие символы скобок ему можно вбрасывать, а какие — нет. Поэтому решил, что раз виртуальные скобки вполне реальны, надо минимизировать шанс коллизий с пользовательской грамматикой. По идее http://en.wikipedia.org/wiki/Private_Use_Areas как раз для этого и существует.

VD>Я давно не занимался проблемой, но вроде бы были какие-то грабли в разных языках. Так что там нельзя вот так универсально расставить виртуальные скобки.

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

VD>SourceSnapshot должен осуществлять все пересчеты. Он должен храрить две строки. Одну препроцессированную, а другую исходную. Перед выдачей информации пользователю позиции должны пересчитывается по таблице пересчета. Хардекс использовал эту штуку для подержи препроцессора в парсере Шарпа еще на ПЕГ-е.

VD>Можно сделать половинчатое решение. Препроцессор пишется вручную, но использует механизм пересчета (relocation) встроенный в SourceSnapshot (его доведем до нужного уровня).
Как делается ограниченное решение на базе препроцессинга и механизма пересчета координат вроде понятно.

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

Вопрос открытый. Потому что нет идей, как, допустим, параметризовать SourceSnapshot кастомным препроцессором во время работы интеграции. Или, допустим, имея наследника SourceSnapshot с зашитой логикой препроцессинга и пересчета, указать интеграции, что надо использовать именно его?
Re[6]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 14:58
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Вставлять, кстати, можно обычные скобки, а не какие-то страшные символы. Но можно и страшные, если язык не позволяет.

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

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

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

Мысль интересная.
Но, на этом же месте ведь и другие конструкции могут начинаться. Это не приведет к конфликту?
Ведь будет два правила с одного места спарсиваться.
Виртуальным скобкам, конечно, можно задавать пустые локейшоны. Теоретически это может срастись.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: [Nitra] Парсинг языков базирующихся на отсупах
От: Evgeny.Panasyuk Россия  
Дата: 02.10.14 18:43
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Мысль интересная.

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

Виртуальные скобки это просто виртуальный view оригинального текста, и через призму этого view видно текст со вставленными скобками (которые вообще не входят в оригинальный набор символов), хотя никаких inplace изменений не было.
В терминах C++ STL просто нужен адаптер для итератора, и никаких изменений в коде парсера
Отредактировано 02.10.2014 18:57 Evgeny.Panasyuk . Предыдущая версия .
Re[8]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 19:01
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Мысль интересная.

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

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

Должно всё работать. Если пройтись по тексту и сказать где у нас NewLine, IndentInc, Indent и IndentDec то с помощью этой грамматики можно будет спокойно парсить питон.
  syntax Block = ":" NewLine IndentInc (Indent Statement)+ IndentDec;

  syntax Statement
  {
    | If      = "if" Expression Block else Block;
    | While   = "while" Expression Block;
    | Return  = "return " Expression NewLine;
  }
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Отредактировано 03.10.2014 4:00 VladD2 . Предыдущая версия .
Re[9]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 19:06
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

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

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

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

WH>И получить многократное замедление парсера... Не вариант.

И чем это отличается от "Когда он будет пытаться парсить нашу виртуальную скобку, он будет смотреть в таблицу мемоизации."?
Какая разница кто будет смотреть в таблицу — код парсера или итератор?

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


С учётом препроцессора или без?
Re[11]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 19:19
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

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

EP>Какая разница кто будет смотреть в таблицу — код парсера или итератор?
Очень большая. Нитра парсер безлексерный. И работает непосредственно с символами.
И если ты на каждую букву будешь что-то проверять, у тебя всё будет тормозить.

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

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

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

EP>>Какая разница кто будет смотреть в таблицу — код парсера или итератор?
WH>Очень большая. Нитра парсер безлексерный. И работает непосредственно с символами.
WH>И если ты на каждую букву будешь что-то проверять, у тебя всё будет тормозить.

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

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

EP>>С учётом препроцессора или без?
WH>Желательно чтобы его вообще не было.

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

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

Он когда должен работать? Отдельным проходом или как фильтр?
Re[7]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 19:42
Оценка:
Здравствуйте, STDray, Вы писали:

STD>В идеале, пользователь вообще не должен задумываться о том, какие символы скобок ему можно вбрасывать, а какие — нет. Поэтому решил, что раз виртуальные скобки вполне реальны, надо минимизировать шанс коллизий с пользовательской грамматикой. По идее http://en.wikipedia.org/wiki/Private_Use_Areas как раз для этого и существует.


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

STD>Понятно, что особенности рукописных лексеры с парсерами создают проблемы. Надо либо думать, как дать возможность пользователю прикрутить всю эту императивную логику к Нитре, либо признать, что подобные контекстно-зависимые штуки Нитра разбирать не может.


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

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

Но если есть мысли, то озвучивайте. Реализуем, если будет годная модель.

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

STD>Вопрос открытый. Потому что нет идей, как, допустим, параметризовать SourceSnapshot кастомным препроцессором во время работы интеграции. Или, допустим, имея наследника SourceSnapshot с зашитой логикой препроцессинга и пересчета, указать интеграции, что надо использовать именно его?

Ну, дернуть функцию перед работай парсера не сложно.

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

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

Как вставить виртуальные скобки уже понятно. Это упрощает проблему. Осталось придумать как описывать принцип преобразования отступов в эти виртуальные скобки.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 19:56
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Проблем не будет. Ибо в почти любой грамматике множество правил с одного места начинаются.


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

WH>Должно всё работать. Если пройтись по тексту и сказать где у нас NewLine, IndentInc, Indent и IndentDec то с помощью этой грамматики можно будет спокойно парсить питон.


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

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

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

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

WH>  syntax Statement
WH>  {
WH>    | If      = "if" Expression Block else Block;
WH>    | While   = "while" Expression Block;
WH>    | Return  = "return " Expression NewLine;
WH>  }
WH>


Там прикол в том, что код может быть написан так:
if (a):
  foo()

а можно так:
if (a): foo()


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

Нужно кого-то секущего в Питоне, или самим учить правила их переноса строк. Для чего нужна хотя бы внятная ссылка.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Отредактировано 03.10.2014 4:00 VladD2 . Предыдущая версия .
Re[13]: [Nitra] Парсинг языков базирующихся на отсупах
От: WolfHound  
Дата: 02.10.14 20:02
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

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

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

EP>

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

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

Как фильтр точно не вариант. Ибо тормоза.
Отдельным проходом можно. Но тут тоже не всё хорошо.
Идеально было бы протаскивание некоторого контекста через парсер. И разбор соответствующих правил с его учётом. Но тут появляются осложнения с восстановление после ошибок.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
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[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>Ну и задача максимум сделать так чтобы всё происходило за один проход.


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

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

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

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

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

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

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

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

EP>

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

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


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

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

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

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

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


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

Этот препроцессор можно сделать и инкрементальным. Он ведь линейны. Если отступ на предыдущей строке совпал и на сроке идущей за имененной, то можно менять только отступ для текущей строки (и т.п.).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [Nitra] Парсинг языков базирующихся на отсупах
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 02.10.14 21:00
Оценка:
Здравствуйте, WolfHound, Вы писали:

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

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

Причем ужасная. Почему мне диктуют, как форматировать мои исходники? Потому и не пользуюсь питоном
Маньяк Робокряк колесит по городу
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 21:12
Оценка:
Где можно почитать правила распознавания блоков в Питоне и других языках где применяются отступы?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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 и пойдев путем блока, а не увидев его пойдет путем выражения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Отредактировано 03.10.2014 4:01 VladD2 . Предыдущая версия .
Re[13]: [Nitra] Парсинг языков базирующихся на отсупах
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.10.14 21:20
Оценка:
Здравствуйте, WolfHound, Вы писали:

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

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

Почему? Текст съедать не нужно. Просто основной парсер должен игнорировать концы строк. Вместо этого он может опираться на концы стейтментов и иных конструкций о которых ему расскажет препроцессор.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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 . Предыдущая версия .
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>Это в нашу таблицу не записать никак.

Я же тебе говорил, что левая рекурсия получается.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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> Не левая. И не рекурсия.


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

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

VD>Результат тот же. Ты не можешь записать инфу о парсеинге одного и того же правила с одной позиции.
Не тот же. В данном случае даже в структуры Эрли парсера нельзя записать эту информацию.
При этом если добавить отдельный лексер или изменить строку, то и основной парсер справится с этой задачей.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
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, есть ли новости по теме ?


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

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


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

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

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


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

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

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

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

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