Здравствуйте, VladD2, Вы писали:
VD>Про левую рекурсию не забыл? Она тут не стрельнет?
Не вижу в каком месте она может стрельнуть.
VD>Про NewLine не понял. Наверно ты имеешь в виду требование начала новой вложенности.
Нет. NewLine это перевод строки.
IndentInc начало новой вложенности.
Indent текущий отступ.
IndentDec конец.
VD>Там еще вопросы есть. Например, в некоторых языках можно искусственно игнорировать конец строки и рассматривать следующую строку как продолжение предыдущей. Например, в Васике это "_" в конце строки. А в Питоне, вроде бы, "\". Причем она даже в строках действует.
Пробельное правило просто не должно содержать перевод строки.
Но должно содержать:
"_" NewLine
И всё.
VD>Так что твоя грамматика не верна. В прочем, это детали. Может и прокатить.
А так?
Здравствуйте, WolfHound, Вы писали:
EP>>Или ты имеешь в виду что у парсера больше информации чем у итератора, и из-за этого ему требуется меньше проверок? WH>Если между парсером и текстом будет стоять итератор то обращение к таблице будет на каждый символ. WH>Ибо парсер работает с символами. WH>А если записать данные непосредственно в таблицу мемоизации парсера, то обращения к ней будут только в тех местах, где есть вызов этих правил.
Понятно, то есть у парсера больше необходимой информации.
А нельзя ли использовать нужный тип итератора в зависимости от того какие правила заданны? Или там всё равно будет недостаточно информации?
WH>Как фильтр точно не вариант. Ибо тормоза. WH>Отдельным проходом можно. Но тут тоже не всё хорошо.
Без существенной модификации парсера — тут либо то, либо то.
Причём отдельный проход — это ведь тоже тормоза. Правда если весь файл помещается в кэш (и не вымывается из него) — то от второго прохода не так много тормозов.
Кстати, если проход отдельный, и не хочется залезать в charset, то можно просто расширить кодировку — это избавит от необходимости смотреть в таблицу при парсинге.
Re[11]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Indent тут избыточен (препроцессор будет его просто съедать), можно без него — только с IndentInc+IndentDec.
Это если текст менять. А если закладывать данные в таблицу мемоизации или протаскивать контекст, то необходим.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Без существенной модификации парсера — тут либо то, либо то.
Если будет понятно, как сделать парсер существенно лучше то я вообще всё перепишу. Не первый раз.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[10]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, WolfHound, Вы писали:
WH>Ну и задача максимум сделать так чтобы всё происходило за один проход.
В этом нет особого смысла. Практика показала, что простые препроцессоры обычно работают дико быстро. Препроцессор Шарпа на составляет и пол процента от общего времени парсинга, например.
В прочем, иметь все в одной грамматике, конечно же, проще и удобнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[13]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Ещё раз, ты же сам сказал выше что парсер будет лезть в таблицу. EP>Или ты имеешь в виду что у парсера больше информации чем у итератора, и из-за этого ему требуется меньше проверок?
Он имел в виду, что некий перпоцессор читает исходный файл и не создавая новый файл записывает информацию о виртуальных скобках во внутренние структуры парсера.
Когда будет работать парсер он будет думать, что в некоторых местах успешно спарсились правила скобок. На скорость парсинга это не повлияет, так как парсер и так проверят эти внутренние структуры данных.
В общем, идея здравая. Ее нужно использовать, если не будет противопоказаний.
EP>Ок, вот в этом варианте: EP>
WH>>Препроцессор должен не менять строку, а записать в таблицу мемоизации виртуальные скобки.
Он когда должен работать? Отдельным проходом или как фильтр?
Да, отдельным. Но строку не менять и новой не создавать. Таблицы пересчетов тоже при этом не нужны. Препроцессорт только читает файл и говорит парсеру, что в таких то местах спарсились такие-то правила.
Это реально решает одну из проблема.
Остается вторая проблема — сделать так, чтобы препроцессор не приходилось писать на ЯВУ. Оптимально описать на некотором ДСЛ-е правила извлечения информации о скобках/блоках и т.п.
Уж реализовать то мы это точно сумеем.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[14]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, WolfHound, Вы писали:
WH>Идеально было бы протаскивание некоторого контекста через парсер. И разбор соответствующих правил с его учётом. Но тут появляются осложнения с восстановление после ошибок.
Думаю, что совмещать разбор отступов и прсинг не реально. Проще препроцессировать всю разбираемую строку. Это будет дико быстро. Стас уже проверил это на препроцессоре шарпа.
Этот препроцессор можно сделать и инкрементальным. Он ведь линейны. Если отступ на предыдущей строке совпал и на сроке идущей за имененной, то можно менять только отступ для текущей строки (и т.п.).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Понятно, то есть у парсера больше необходимой информации. EP>А нельзя ли использовать нужный тип итератора в зависимости от того какие правила заданны? Или там всё равно будет недостаточно информации?
Просто нужно сделать АПИ, чтобы прероцессор тупо дергал функции вроде:
BeginBlock(pos : int);
EndBlock(pos : int);
Эти функции говорят парсеру где начинаются и кончаются блоки. Он преоразует их в предопределенные правила. В грамматике тупо помещаются ссылки на эти правила. Вуаля! Имеем парсер для скобочного языка, но вместо скобок выступают виртуальные правила.
EP>Без существенной модификации парсера — тут либо то, либо то. EP>Причём отдельный проход — это ведь тоже тормоза. Правда если весь файл помещается в кэш (и не вымывается из него) — то от второго прохода не так много тормозов.
Простой препроцессор (а подсчет отступов это очень простой препроцессор) будет отрабатывать в микросекунды даже на мегабайтных файлах. Так что это не проблема.
EP>Кстати, если проход отдельный, и не хочется залезать в charset, то можно просто расширить кодировку — это избавит от необходимости смотреть в таблицу при парсинге.
Ты просто не понимаешь внутреннего устройства парсера. В нем есть массив интов с числом элементов равным числу символов в разбираемой строке. Парсер прежде чем парсить правило проверяет нет ли в этом массиве ссылки на это правило. Если она есть, то парсинг не просходит, а берется мемоизированное значение. Это позволяет устранить экспоненту при парсинге (гарантировать, что одно правило не будет разобрано с одного места более одного раза).
Так вот в этот массив и можно подсунуть информацию о правиле парсящем скобки. Только сделает это не парсер лично, а препроцессор, через некоторое АПИ. В общем, это детали.
Нужно придумать как описать логику перевода текста в блоки и проблема будет решаться автоматически.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
Парсер сам разрулит неоднозначность на основании этих самых IndentInc/IndentDec. Точнее ее, для парсера, просто не будет. Он увидит IndentInc и пойдев путем блока, а не увидев его пойдет путем выражения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
EP>>Indent тут избыточен (препроцессор будет его просто съедать), можно без него — только с IndentInc+IndentDec. WH>Это если текст менять. А если закладывать данные в таблицу мемоизации или протаскивать контекст, то необходим.
Почему? Текст съедать не нужно. Просто основной парсер должен игнорировать концы строк. Вместо этого он может опираться на концы стейтментов и иных конструкций о которых ему расскажет препроцессор.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: [Nitra] Парсинг языков базирующихся на отсупах
Здравствуйте, VladD2, Вы писали:
VD>Думаю, что совмещать разбор отступов и прсинг не реально.
С основным парсером вообще не проблема. С восстанавливающим есть над чем подумать. Но думаю тоже можно.
Преимущество совмещённого режима в том что мы сможем внутри одного исходника свободно переключаться между режимами.
Более того протягивание контекста нам нужно для реализации изменения грамматики во время разбора.
Задачи близкородственные. Думаю, можно будет решить их одним механизмом.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: [Nitra] Парсинг языков базирующихся на отсупах
Вольфхаунд подкинул интересную мысль.
Я читал, но у меня пока нет понимания внутреннего устройства нитры, чтобы оценить.
VD>Препроцессор там должен быть примитивнийший. Думаю, его не составит труда написать и вручную. Предоставим АПИ позволяющее регистрировать эти виртуальные токены и вперед... VD>Что касается декларативного варианта, то нужно придумать это самое декларативное описание, так чтобы с его помощью можно было покрыть имеющиеся юзкейсы.
В прошлое обсуждение сошлись на том, что надо придумать некий генерик-механизм и декларативное описание для него. Время прошло, а механизма, чтобы синтаксис на отступах был его частным случаем, никто не предоставил. И Вольфхаунд, как я понял, пишет про то, как безболезненно захардкодить отступы в парсер.
STD>>>>как дружить все это дело со студийной интеграцией STD>>Вопрос открытый. Потому что нет идей, как, допустим, параметризовать SourceSnapshot кастомным препроцессором во время работы интеграции. Или, допустим, имея наследника SourceSnapshot с зашитой логикой препроцессинга и пересчета, указать интеграции, что надо использовать именно его? VD>Ну, дернуть функцию перед работай парсера не сложно.
Я не понимаю. Я про Adding new language suppor (http://confluence.jetbrains.com/display/Nitra/VsExtension). И как для своего язычка с отступами заставить все работать через свой препроцессор, понять пока не могу.
VD>Лучше, конечно, придумать декларативный вариант. Тогда и дергать ничего не пришлось бы.
Конечно лучше. Я это изначально обозвал как "Способ описания отступов в самой грамматике"
VD>Как вставить виртуальные скобки уже понятно. Это упрощает проблему. Осталось придумать как описывать принцип преобразования отступов в эти виртуальные скобки.
Полагаю, что надо начать с варианта "отступ больше текущего" = индент, и "отступ меньше текущего, равный вершине стека" = дедент, иначе — ошибка.
Я пытался как-то добрасывать дедентов и бэддедентов ради парсера, но это всё "эвристика".
Просто смотрел, в каком случае парсер больше всего разбирает и пришел к такому решению.
Не думаю, что парсер должен таким страдать.
Re[13]: [Nitra] Парсинг языков базирующихся на отсупах
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] Парсинг языков базирующихся на отсупах
В данном случае у нас первый IndentDec должен закрыть два IndentInc. А второй 3.
Это в нашу таблицу не записать никак.
Соответственно нужно либо делать полноценный препроцессинг вставляя скобки физически.
Либо протаскивать через парсер контекст. Чтобы можно было сделать так