PEG + TDOP альфа
От: WolfHound  
Дата: 23.10.11 17:08
Оценка: 251 (7)
Наконец дошли руки до парсера.
https://github.com/rampelstinskin/ParserGenerator
В данный момент это все еще дремучая альфа, но она уже работает.
В продакшене пока использовать не стоит, ибо будут ломающие изменения.

Реализовано:
Разбор выражений с учетом приоритетов операторов.
Эвристика разрешения конфликтов "кто длиннее тот и прав". Отход от правил PEG но это необходимое условие для того чтобы расширение во время разбора не было мучительно больным. Да и вообще приоритетный выбор considered harmful.
Внутренняя реализация заточена под динамическое расширение.

Еще не сделано:
Динамическое расширение.
Относительные приоритеты и силы связывания. Сейчас приоритеты не задаются вообще. А сила связывания задается циферками.
Разрешение конфликта в случае если два правила съели одно и тоже количество текста (приоритеты нужны именно для этого). Сейчас молча будет выбрано одно из них. Какое зависит от фазы луны.
Куча оптимизаций. Я их уже придумал, но делать буду потом.

Нужно: Придумать название алгоритму.
Ибо штука получилась очень мощная.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: PEG + TDOP альфа
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 23.10.11 19:16
Оценка: 13 (1) :)))
Здравствуйте, WolfHound, Вы писали:

WH>Убийство приоритетного выбора от ПЕГа рожки да ножки оставило.


А, ну тогда HLoP (horns and legs of PEG)

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 12:06
Оценка: 48 (1)
Здравствуйте, WolfHound, Вы писали:

Сделал поддержку нескольких стартовых правил.
Сейчас поддерживаются точки расширения и простые правила.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 15:02
Оценка: +1
Здравствуйте, WolfHound, Вы писали:

WH>Нету. Ща пофикшу.

Хотя если подумать, то может она и не нужна.
Ибо люди могут захотеть сделать исключительно расширяющую грамматику не рассчитанную на самостоятельный разбор.
Например так:
[ParserGrammar(Options = EmitDebugSources,
  grammar
  {
    using CalcParser;

    prefixInc is expr = "++"s expr : 200;
    postfixInc is expr = expr : 200 "++"s;
  }
)]
class IncParser : IGrammar
{
  prefixInc(op : NToken, v : Ast) : Ast { Ast.UOp(GetText(op), v) }
  postfixInc(v : Ast, op : NToken) : Ast { Ast.UOp(GetText(op), v) }
}

Тут даже атрибут повесить некуда.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: PEG + TDOP альфа
От: catbert  
Дата: 23.10.11 17:19
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Наконец дошли руки до парсера.

WH>https://github.com/rampelstinskin/ParserGenerator
WH>В данный момент это все еще дремучая альфа, но она уже работает.

Как это соотносится с TDOP-ом Влада?

WH>В продакшене пока использовать не стоит, ибо будут ломающие изменения.


Макросы к нему есть?

WH> Да и вообще приоритетный выбор considered harmful.


Это ж главная фича ПЕГа, не?

WH>Относительные приоритеты и силы связывания. Сейчас приоритеты не задаются вообще. А сила связывания задается циферками.


Планируются другие стратегии поведения при конфликте между двумя динамическими правилами?

WH>Нужно: Придумать название алгоритму.

WH>Ибо штука получилась очень мощная.

OPEG (operator peg). Надо paper писать!
Re[2]: PEG + TDOP альфа
От: WolfHound  
Дата: 23.10.11 17:40
Оценка:
Здравствуйте, catbert, Вы писали:

C>Как это соотносится с TDOP-ом Влада?

Я честно говоря его даже не смотрел.
Насколько я понял он реализовал тот же алгоритм (ибо я ему его объяснил) но без заточки под расширение что бесполено.

WH>>В продакшене пока использовать не стоит, ибо будут ломающие изменения.

C>Макросы к нему есть?
Это и есть макрос.
Там макрос более чем в 15 раз больше рантайма и сложен что писец.

WH>> Да и вообще приоритетный выбор considered harmful.

C>Это ж главная фича ПЕГа, не?
Это его главная бага.

C>Планируются другие стратегии поведения при конфликте между двумя динамическими правилами?

Нет. Ибо не нужно.

C>OPEG (operator peg). Надо paper писать!

Убийство приоритетного выбора от ПЕГа рожки да ножки оставило.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: PEG + TDOP альфа
От: catbert  
Дата: 23.10.11 18:05
Оценка:
Здравствуйте, WolfHound, Вы писали:

C>>Планируются другие стратегии поведения при конфликте между двумя динамическими правилами?

WH>Нет. Ибо не нужно.

Тут подетальнее, если можно

WH>Убийство приоритетного выбора от ПЕГа рожки да ножки оставило.


То есть остался TDOP?
Re[4]: PEG + TDOP альфа
От: WolfHound  
Дата: 23.10.11 18:21
Оценка:
Здравствуйте, catbert, Вы писали:

C>Тут подетальнее, если можно

Так правило "кто длиннее тот и прав" разрешает чуть менее чем все конфликты. На практике я так думаю этим дело и ограничится.
На случай если два правила съедают одинаковое количество символов можно будет задать какому из них нужно отдать предпочтение.
Это делает разбор полностью детерминированным.
Зачем нужно что-то еще не ясно.

WH>>Убийство приоритетного выбора от ПЕГа рожки да ножки оставило.

C>То есть остался TDOP?
В нем нет ни предикатов, ни бектрекинга и вообще он лексерный.

Фактически это получился новый алгоритм хоть и идеи взяты из существующих.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: PEG + TDOP альфа
От: WolfHound  
Дата: 23.10.11 19:31
Оценка:
Здравствуйте, kochetkov.vladimir, Вы писали:

KV>А, ну тогда HLoP (horns and legs of PEG)

А в этом что-то есть.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: PEG + TDOP альфа
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 23.10.11 19:42
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>А в этом что-то есть.


Блин. Я ведь зарекался больше не шутить на этом форуме, после http://www.rsdn.ru/forum/prj.nemerle/1925845.aspx
Автор: Vladimir V Kochetkov
Дата: 30.05.06



[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re[4]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.10.11 21:11
Оценка:
Здравствуйте, catbert, Вы писали:

C>То есть остался TDOP?


Не совсем. TDOP рассчитан на работу с операторами. Причем, в основном на бинарные и унарные (префиксные и постфиксные).

Здесь же получилась эдакая смесь между TDOP и модернизированным Packrat (что использовался до этого в PegGrammar). TDOP вообще не рассчитан на разбор неоднозначных грамматик. В Пакрате неоднозначности устранялись приоритетным выбором. В данном алгоритме разрешение неоднозначностей производится по принципу "кто длиннее тот и прав". При одинаковой длине разбора победитель определяется приоритетом (который можно будет задать при описании правила расширяющего другое правило).

В общем, это смесь алгоритмов, по сути, дающая новый алгоритм.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.10.11 21:15
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Это делает разбор полностью детерминированным.


Я пока не пол как задавать приоритеты при условии, что два правила расширяющие одно правило пишутся параллельно (независимо).

WH>Зачем нужно что-то еще не ясно.


Еще не ясно что будет на практике. Ведь люди могут захотеть отменить имеющееся правило и заменить его своим. При этом новое правило может разбирать строку меньшей длинны. Для расширяемого языка — это более чем актуально.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.10.11 21:20
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Еще не сделано:

WH>Динамическое расширение.
WH>Относительные приоритеты и силы связывания. Сейчас приоритеты не задаются вообще. А сила связывания задается циферками.
WH>Разрешение конфликта в случае если два правила съели одно и тоже количество текста (приоритеты нужны именно для этого). Сейчас молча будет выбрано одно из них. Какое зависит от фазы луны.
WH>Куча оптимизаций. Я их уже придумал, но делать буду потом.

Здорово! Теперь, главное, чтобы это еще на год не затянулось.

WH>Нужно: Придумать название алгоритму.


YaTDP — Yet another top-down parser
или даже
YaTD — Yet another top-down

Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG + TDOP альфа
От: Ka3a4oK  
Дата: 24.10.11 04:47
Оценка:
WH>Еще не сделано:
WH>Динамическое расширение.

А статическое расширение есть? Я могу комбинировать грамматики на этапе компиляции? А то сейчас приходится заниматься непотребством с помощью m4.
Re[2]: PEG + TDOP альфа
От: Аноним  
Дата: 24.10.11 04:52
Оценка:
синтаксис для разруливания

1.
alias for=my.for // будет всегда for разбираться из библиотеки my

for()


2. my.for() // явно указываю из какой библиотеки будет браться for
Re[2]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 05:11
Оценка:
Здравствуйте, Ka3a4oK, Вы писали:

KK>А статическое расширение есть? Я могу комбинировать грамматики на этапе компиляции? А то сейчас приходится заниматься непотребством с помощью m4.

А оно от динамического ничем не отличается.
Так что оно неизбежно.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: PEG + TDOP альфа
От: para  
Дата: 24.10.11 05:23
Оценка:
Здравствуйте, Аноним, Вы писали:
А>1.
А>alias for=my.for // будет всегда for разбираться из библиотеки my
А>for()

А>2. my.for() // явно указываю из какой библиотеки будет браться for


+1
Re[3]: PEG + TDOP альфа
От: Ka3a4oK  
Дата: 24.10.11 10:34
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


KK>>А статическое расширение есть? Я могу комбинировать грамматики на этапе компиляции? А то сейчас приходится заниматься непотребством с помощью m4.

WH>А оно от динамического ничем не отличается.
WH>Так что оно неизбежно.

Т.е. оно тоже пока не работает?
Re[4]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 11:11
Оценка:
Здравствуйте, Ka3a4oK, Вы писали:

KK>>>А статическое расширение есть? Я могу комбинировать грамматики на этапе компиляции? А то сейчас приходится заниматься непотребством с помощью m4.

WH>>А оно от динамического ничем не отличается.
WH>>Так что оно неизбежно.

KK>Т.е. оно тоже пока не работает?


Сейчас — нет. Он просто так своеобразно выражает мысль — если будет динамическая расширяемость, то статическая будет особо и не нужна (это будет частный случай).

Кстати, расширяемости на уровне литеральных правил не будет. Так что полностью модульность можно будет обеспечить разве что инклюдами. Но, на мой взгляд, это не особо нужно. Литеральные правила и по месту описываются на раз.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG + TDOP альфа
От: Аноним  
Дата: 24.10.11 12:15
Оценка:
Здравствуйте, VladD2, Вы писали:

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


KK>>>>А статическое расширение есть? Я могу комбинировать грамматики на этапе компиляции? А то сейчас приходится заниматься непотребством с помощью m4.

WH>>>А оно от динамического ничем не отличается.
WH>>>Так что оно неизбежно.

KK>>Т.е. оно тоже пока не работает?


VD>Сейчас — нет. Он просто так своеобразно выражает мысль — если будет динамическая расширяемость, то статическая будет особо и не нужна (это будет частный случай).


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


можно пример литеральных и не литеральных правил.
Re[6]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 13:03
Оценка:
Здравствуйте, Аноним, Вы писали:

А>можно пример литеральных и не литеральных правил.

d = ['0'..'9'];
num : Num = d+;

Вот d — это литеральное правило. Точнее не знаю как его назвать, так что называю так.

В общем, расширять грамматику можно будет только для правил которые помечены как расширяемые. А помечать так литеральные правила слишком не эффективно. Так что если кто-то решит добиться модульности на уровне латеральных правил, то он сделает это только ценой снижения эффективности.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 13:21
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Сделал поддержку нескольких стартовых правил.

WH>Сейчас поддерживаются точки расширения и простые правила.

С первым понятно. Можно подробностей про "простые правила"? Их как-то надо помечать? Или все правила могут быть стартовыми (это сколько же тогда будет публичных методов?)?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 13:22
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Сделал поддержку нескольких стартовых правил.

WH>Сейчас поддерживаются точки расширения и простые правила.

Осталось сделать динамическую расширяемость и можно начинать эксперименты по созданию немерле на новом парсере!
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 13:29
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>С первым понятно. Можно подробностей про "простые правила"? Их как-то надо помечать? Или все правила могут быть стартовыми (это сколько же тогда будет публичных методов?)?

Надо помечать.
    [StartRule]
    start : Ast = s expr !any;

    [StartRule]
    expr : Ast;

    rounds is expr = '('s expr ')'s;//(*)

(*)Это правило стартовым делать нельзя. Пока по крайней мере. Но я сомневаюсь что оно вообще нужно.
вот код: https://github.com/rampelstinskin/ParserGenerator/blob/5222985d4585a34c920fcf024c9c47c6ccb88793/Test/Main.n
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 13:29
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Осталось сделать динамическую расширяемость и можно начинать эксперименты по созданию немерле на новом парсере!

Это я сейчас ковыряю.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 13:49
Оценка:
Здравствуйте, WolfHound, Вы писали:


WH>
WH>    rounds is expr = '('s expr ')'s;//(*)
WH>

WH>(*)Это правило стартовым делать нельзя. Пока по крайней мере. Но я сомневаюсь что оно вообще нужно.

Не нужно.

А можно делать расширяемым стартовое правило (в смысле, проблем не будет, там же предикат)?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 14:11
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>А можно делать расширяемым стартовое правило (в смысле, проблем не будет,

Вроде можно. Никаких проблем быть не должно.

VD>там же предикат)?

И что?
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 14:40
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


VD>>А можно делать расширяемым стартовое правило (в смысле, проблем не будет,

WH>Вроде можно. Никаких проблем быть не должно.

А проверка на то что есть хотя бы одно стартовое правило есть? А то я что-то гляжу код и не вижу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 14:54
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>А проверка на то что есть хотя бы одно стартовое правило есть? А то я что-то гляжу код и не вижу.

Нету. Ща пофикшу.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 15:39
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>
WH>class IncParser : IGrammar
WH>


Чёто мне это ручное задание IGrammar совсем не нравится. Вешай как ты лучше его сам, в макросе. Зачем людей лишними знаниями обременять?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 15:45
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Чёто мне это ручное задание IGrammar совсем не нравится. Вешай как ты лучше его сам, в макросе. Зачем людей лишними знаниями обременять?

Это все временно.
В теме же написано что это альфа.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 15:47
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>
WH>[ParserGrammar(Options = EmitDebugSources,
WH>  grammar
WH>  {
WH>    using CalcParser;

WH>    prefixInc is expr = "++"s expr : 200;
WH>    postfixInc is expr = expr : 200 "++"s;
WH>  }
WH>)]
WH>class IncParser : IGrammar
WH>{
WH>  prefixInc(op : NToken, v : Ast) : Ast { Ast.UOp(GetText(op), v) }
WH>  postfixInc(v : Ast, op : NToken) : Ast { Ast.UOp(GetText(op), v) }
WH>}
WH>


Кстати, этот пример отчетливо демонстрирует, что s нужно как-то стандартизировать. Или здесь подразумевается, что новой грамматике доступны правила расширяемой? В общем, откуда s?

А так же становится очевидным, что имеет смысл уже сейчас реализовать идею с умолчальными s и S для правил:

Подразумевается, что после каждой синтаксической конструкции могут идти пробельные символы (т.е. как бы каждое подправило дополняется правилом s разбирающим ноль или более незначащих символов вроде пробелов и концов строк). Если подправило заканчивается на букву, подчеркивание или цифру (в понятии Unicode-категорий), то подразумевается, что такое подправило дополняется правилом S (которое содержит предикат не допускающих наличия в следующем символе цифр и букв и идущие за ним правило s). Таким образом, синтаксис, описываемый в макросах, не содержит специальных конструкций для разбора пробельных символов, но при этом автоматических их вставляет. Кроме того можно будет отключить эту функциональность (добавив к декларации макроса атрибут ExplicitSpaces) и разбираться с пробельными символами вручную. При этом для описания пробельных символов нужно будет использовать предопределенные макросы s и S (описывающие правила разбора пробельных символов).


А то в 99% правил будет один и тот же шаблон с пробельными символами. Зачем заставлять пользователей долбить его из раза в раз?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.10.11 15:52
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Или здесь подразумевается, что новой грамматике доступны правила расширяемой?


Подумал... доступность правил из внешней грамматики нужна. Например, при описании своего типа хотелось иметь возможность использовать правила модификаторов и атрибутов описанных в исходной грамматике.

Можно, конечно, заложиться на ручную пометку таких правил, но боюсь, что это ненужный геморрой для писателей грамматик.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG + TDOP альфа
От: Rival Таиланд
Дата: 24.10.11 22:45
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Нужно: Придумать название алгоритму.

WH>Ибо штука получилась очень мощная.

Можно попробовать придумать какое-то производное от lupus (волк) или canis(собака).
Почему так? Ну во-первых, раз ты это написал тут есть неявный отсыл к твоему нику, а во-вторых парсинг, ведение носом по строке, похож на действия собаки-ищейки.
«История жизни – это, по существу, развитие сознания, которое завуалировано морфологией.» Пьер Тейяр де Шарден
Re: PEG + TDOP альфа
От: VladD2 Российская Империя www.nemerle.org
Дата: 26.10.11 16:46
Оценка:
Здравствуйте, WolfHound, Вы писали:

Предлагаю назвать ETD — Extendeble Top-Down (как вариант Excellent). Запоминается хорошо. Произносится легко. А суть алгоритма в названии один хрен не отразить. Слишком там много всего.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.