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

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

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

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

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

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

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

Здравствуйте, 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>>

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

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

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

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

STD>f#, coffescript, haml, scss, dg, ela, nimrod, purescript, moonscript, livescript, snowscript, sugarcpp
STD>вот такое вспомнилось

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

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

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

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); для корректного позиционирования ошибок после расстановки виртуальных скобок.

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

Здравствуйте, 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 (его доведем до нужного уровня).

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

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

Мы поможем разобраться в деталях. Допилим что надо...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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>>

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

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

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

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

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

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

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

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

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

С учётом препроцессора или без?

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

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

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

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

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

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

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

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

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

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

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

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

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

Тут Вольфхаунд подкинул интересную мысль.

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

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

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

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

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

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

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

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

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

Здравствуйте, 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()

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

Нужно кого-то секущего в Питоне, или самим учить правила их переноса строк. Для чего нужна хотя бы внятная ссылка.

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

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

EP>

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

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

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

От:	STDray	http://stdray.livejournal.com
Дата:	29.09.14 10:45
Оценка:

	От:	WolfHound
	Дата:	29.09.14 14:25
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	30.09.14 17:01
Оценка:

	От:	WolfHound
	Дата:	30.09.14 18:02
	Оценка:

От:	STDray	http://stdray.livejournal.com
Дата:	01.10.14 13:42
Оценка:

	От:	Evgeny.Panasyuk
	Дата:	02.10.14 18:43
	Оценка: