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: 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[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[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: PEG + TDOP альфа
От: WolfHound  
Дата: 24.10.11 12:06
Оценка: 48 (1)
Здравствуйте, WolfHound, Вы писали:

Сделал поддержку нескольких стартовых правил.
Сейчас поддерживаются точки расширения и простые правила.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
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 — это литеральное правило. Точнее не знаю как его назвать, так что называю так.

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