Oberon space
General Category => Общий раздел => Тема начата: valexey от Сентябрь 09, 2012, 06:22:23 pm
-
Я не поленился и нашел этот шедевр:
...
Я как-то писал здесь http://forum.oberoncore.ru/viewtopic.php?p=69811#p69811 про смесь из лексического и синтаксического разбора
Мне многократно приходилось писать "наколеночные" решения для разбора каких-нибудь данных. Почти всегда возникал соблазн схалтурить, не делать отдельный лексический разбор. В 100% случаев это приводило к тому, что в итоге получалась какая-то дрянь.
"Шестиветочный цикл" Info21 - прекрасная иллюстрация.
Я тоже думал об этом. Ну и немного шишек понабивал самостоятельно, так что подтверждаю.
Galkov, помнится очень хорошо объяснял почему требуется разделять парсер и лексер (за что был неоднократно гнобим на оборонкоре) - они банально работают по разным принципам. Обычный LL(с)-парсер не сможет разбить входной поток на лексемы. Какой-нибудь LALR - тоже. Я подозреваю что с задачей сможет справиться GLR и/или GLL парсер, но это будет не эффективно (ну и не факт что получится - я еще не прорабатывал эту тему).
PS. Справится/не справится - имеется ввиду, что это честный парсер, работающий по полностью формализованной грамматике и ничего кроме нее не знающий. А не так как работает например виртовский парсер Оберона.
-
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
-
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
Звучит страшно. Это что-то типа жабаскриптового "use strict"? https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Functions_and_function_scope/Strict_mode?redirectlocale=en-US&redirectslug=JavaScript%2FStrict_mode
Или есть более приличные применения такому?
-
Конечно, есть. Можно, например новые конструкции не хардкодить в язык, а складывать в библиотеки.
И тогда люди могут добавлять расширения в язык, не дожидаясь пока автор языка его сделает.
Более того если расширяется основной язык то расширение появляется сразу у всех, а в случае библиотечных расширений языка пользователи могут выбирать какие расширения использовать.
Грамотное языковое расширение может уменьшить код в разы. А в особо запущенных случаях в десятки, а иногда и сотни раз.
-
Конечно, есть. Можно, например новые конструкции не хардкодить в язык, а складывать в библиотеки.
И тогда люди могут добавлять расширения в язык, не дожидаясь пока автор языка его сделает.
Более того если расширяется основной язык то расширение появляется сразу у всех, а в случае библиотечных расширений языка пользователи могут выбирать какие расширения использовать.
Грамотное языковое расширение может уменьшить код в разы. А в особо запущенных случаях в десятки, а иногда и сотни раз.
В топике запахло немерлёй :-)
-
В топике запахло немерлёй :-)
Или это лисп? :)
-
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А где можно прочитать про эту самую массу способов? Какие-то книжки/статейки имеются? А то в АхУльмане вроде бы ничего нет (собственно там даже про glr/gll нет).
-
Ну вот куда Пётр Алмазов делся? Он же скептически относится к макросам, вот было бы ему с кем их обсудить, а то больше тут никто их не умеет готовить ))
-
А где можно прочитать про эту самую массу способов? Какие-то книжки/статейки имеются? А то в АхУльмане вроде бы ничего нет (собственно там даже про glr/gll нет).
Найти такие статьи довольно проблематично. Они мне периодически попадаются на глаза, но их очень трудно гуглить и ссылку я так сразу не вспомню.
Из-за того что в безлексерных парсерах слишком мало матана на них трудно защищать диссеры. Вот про них учёные и забыли.
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Еще советую держаться подальше от слов BNF/EBNF ибо они задают способ генерации текста. А нам нужен разбор. Теоритически из генератора можно сделать парсер на практике это работает очень плохо.
Нужно копать в сторону аналитических грамматик.
http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars
-
Из-за того что в безлексерных парсерах слишком мало матана на них трудно защищать диссеры. Вот про них учёные и забыли.
Стоп. Если там нет "матана" (хотя ясно что матан к грамматикам не имеет отношения), значит ли это, что безлексерный разбор не формализован?
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Еще советую держаться подальше от слов BNF/EBNF ибо они задают способ генерации текста. А нам нужен разбор. Теоритически из генератора можно сделать парсер на практике это работает очень плохо.
То есть yacc/bison это таки генераторы текстов? ;-) Потому как формализм которым задается грамматика для разбора yacc'ом по сути является диалектом BNF.
Нужно копать в сторону аналитических грамматик.
http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars
Спасибо. Посмотрю еще раз.
-
Нужно копать в сторону аналитических грамматик.
http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars
Да, и вопрос в догонку: если у меня уже есть грамматика заданная в (E)BNF, всегда ли возможно её переформулировать "без потерь" в терминах скажем PEG?
То есть какие из переходов возможны:
a) (E)BNF => PEG
b) PEG => (E)BNF
-
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Речь о другом драконе ( http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы) (http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы)) ), видимо :)
-
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Он имел в виду вот эту "книгу дракона":
(http://www.cs.washington.edu/education/courses/cse401/99au/admin/book.jpg)
-
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Речь о другом драконе ( http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы) (http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы)) ), видимо :)
Спасибо что обозначил правильный контекст, а то я до сих пор под впечатлением от секты другого Дракона :-)
А по тему - в АхУльмане многого (из по крайней мере актуального-современного) нет. Но и многое есть. Как справочник он хорош. Только не надо им ограничиваться.
-
Ну вот куда Пётр Алмазов делся? Он же скептически относится к макросам, вот было бы ему с кем их обсудить, а то больше тут никто их не умеет готовить ))
Он может мне рассказать о макросах что-то, что я не знаю? Если нет, то разговор с ним не имеет смысла.
Ибо я уже знаю всё, что говорят скептики. Весь их скептицизм основан на мифах, не имеющих ничего общего с реальностью.
-
Стоп. Если там нет "матана" (хотя ясно что матан к грамматикам не имеет отношения), значит ли это, что безлексерный разбор не формализован?
Не значит. И я не сказал что нет. Я сказал что его там не достаточно чтобы написать миллионы статей на тему как на основе языка кроторый описывает генерацию сделать парсерсер.
То есть yacc/bison это таки генераторы текстов? ;-) Потому как формализм которым задается грамматика для разбора yacc'ом по сути является диалектом BNF.
Читай что написано.
Теоритически из генератора можно сделать парсер на практике это работает очень плохо.
Так вот yacc/bison работают очень плохо.
-
А по тему - в АхУльмане многого (из по крайней мере актуального-современного) нет. Но и многое есть. Как справочник он хорош. Только не надо им ограничиваться.
На весь толмуд там полезного десяток страниц про регулярные выражения и трансформации ДКА. Больше ничего полезного там нет.
-
А по тему - в АхУльмане многого (из по крайней мере актуального-современного) нет. Но и многое есть. Как справочник он хорош. Только не надо им ограничиваться.
На весь толмуд там полезного десяток страниц про регулярные выражения и трансформации ДКА. Больше ничего полезного там нет.
Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.
-
Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.
Это вредный алгоритм. Алгоритм парсера должен поддерживать левую рекурсию. Мой поддерживает.
-
Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.
Это вредный алгоритм.
Иногда полезный.
Алгоритм парсера должен поддерживать левую рекурсию. Мой поддерживает.
Где можно прочитать/посмотреть/пощупать?
-
Иногда полезный.
Только если занимаешься онанизмом (более мягкое слово подобрать не могу) с алгоритмами, которые пытаются делать парсер, по языку который описывает генератор.
Где можно прочитать/посмотреть/пощупать?
https://github.com/rampelstinskin/ParserGenerator
Это устаревшая версия. Сейчас, в пока закрытом режиме, идут работы по доведению её до промышленного качества.
-
Иногда полезный.
Только если занимаешься онанизмом (более мягкое слово подобрать не могу) с алгоритмами, которые пытаются делать парсер, по языку который описывает генератор.
Если нужно разобрать что-то простое, причем пишешь ты на чем-то вроде Си и работать должно оно на сильно ограниченных ресурсах (реально ограниченных, то есть мегабайт в распоряжении скорее всего не будет), ужель вместо рекурсивного спуска будешь использовать что-то более брутальное?
Где можно прочитать/посмотреть/пощупать?
https://github.com/rampelstinskin/ParserGenerator
Это устаревшая версия. Сейчас, в пока закрытом режиме, идут работы по доведению её до промышленного качества.
Это тот самый парсер про который говорил VladD2 на Application Developer Days-3 (в своем долгом спиче про Nemerle-2)?
-
Если нужно разобрать что-то простое, причем пишешь ты на чем-то вроде Си и работать должно оно на сильно ограниченных ресурсах (реально ограниченных, то есть мегабайт в распоряжении скорее всего не будет), ужель вместо рекурсивного спуска будешь использовать что-то более брутальное?
Так мой алгоритм и есть строго рекурсивный спуск.
Причем рекурсивных вызовов там получается меньше чем в убогом LL(1)... Те мой алгоритм еще и эффективнее.
А всё по тому, что мне не нужен онанизм типа такого:
Expr := Term Expr'
Expr' := "+" Term Expr' | ""
Term := Factor Term'
Term' := "*" Factor Term' | ""
Factor := "(" Expr ")" | Int
И дерево разбора получается сразу таким, каким нужно без всякого мусора и нужной формы. С нужной ассоциативностью.
Можно сразу использовать.
И это очень круто я считаю.
Это тот самый парсер про который говорил VladD2 на Application Developer Days-3 (в своем долгом спиче про Nemerle-2)?
Не помню о чем он говорил.
-
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А можно какой-нибудь примерчик, а то не понятно.
-
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А можно какой-нибудь примерчик, а то не понятно.
А что тут не понятного? Написал using syntax Xml; и у тебя в языке появились XML литаралы.
-
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А можно какой-нибудь примерчик, а то не понятно.
А что тут не понятного? Написал using syntax Xml; и у тебя в языке появились XML литаралы.
А если они конфликтуют с другими литералами?
-
А если они конфликтуют с другими литералами?
А что им конфликтовать если они разные?
-
Так мой алгоритм и есть строго рекурсивный спуск.
Причем рекурсивных вызовов там получается меньше чем в убогом LL(1)... Те мой алгоритм еще и эффективнее.
А всё по тому, что мне не нужен онанизм типа такого:
А можно подробнее если не про алгоритм, то хотя бы про альтернативу EBNF? Кроме ссылок в википедию и на исходники.
-
А можно подробнее если не про алгоритм, то хотя бы про альтернативу EBNF? Кроме ссылок в википедию и на исходники.
EBNF задает правила генерации всех текстов на данном языке. Она так и называется пораждающая грамматика. Те она пораждает тексты. С теоритической точки зрения она просто создает всё множество текстов, которое принадлежит языку.
Аналитические грамматики разбирают текст. С теоритической точки зрения им дают все множество текстов, и они для каждого текста говорят, принадлежит ли он языку.
Таким образом, идя с двух разных сторон, мы получаем одно и то же множество текстов.
Но когда мы пишем парсер, у нас нет задачи, сгенерировать все тексты на языке.
У нас есть задача взять строку и сказать принадлежит ли она языку.
Те аналитические грамматики просто по построению подходят для парсеров лучше.
-
Те аналитические грамматики просто по построению подходят для парсеров лучше.
В общем виде я понял. Можно где-то почитать про формы записи таких "аналитических грамматик"?
-
В общем виде я понял. Можно где-то почитать про формы записи таких "аналитических грамматик"?
Вот одна из аналитических грамматик написанная сама на себе.
https://github.com/rampelstinskin/ParserGenerator/blob/master/N2/N2.Grammar/GrammarParser2.n2
-
2 chucheloid
Сразу оговорюсь, что не шарю, но в википедии начертано:
...В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью...
Речь об распознающих автоматах?
-
Я это к тому, что автомат строится по порождающей грамматике вроде как...
Поправьте если ошибаюсь.
-
Вот одна из аналитических грамматик написанная сама на себе.
https://github.com/rampelstinskin/ParserGenerator/blob/master/N2/N2.Grammar/GrammarParser2.n2
Че-то не работает линка.
-
Я это к тому, что автомат строится по порождающей грамматике вроде как...
Я уже отвечал на этот вопрос.
Но отвечу еще раз. Да строится. Но результат получается ну очень хреновым. Использовать его для реальной работы нельзя.
-
Еще вот такое нашел:
Категориальная грамматика (http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
Оно?
-
Че-то не работает линка.
Гитхаб похоже лежит. Попробуй позже.
-
Но когда мы пишем парсер, у нас нет задачи, сгенерировать все тексты на языке.
У нас есть задача взять строку и сказать принадлежит ли она языку.
Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.
К сожалению обычно в книжках по методам трансляции и формальным грамматикам это все опускают либо говорят вскользь (как в АхУльмане), как о чем-то совершенно второстепенном.
-
Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.
Здравствуй капитан очевидность.
Вот только научить всему этому парсер на аналитической грамматике намного проще.
Вон посмотри на тот ужОс в который превращается разбор простейших арифметических выражений.
Там ты не получишь ни нормального АСТ. Ни нормального восстановления после ошибок. Ни нормальных сообщений об ошибках.
Ибо ни один пользователь языка не поймет что term'ы м factor'ами.
К сожалению обычно в книжках по методам трансляции и формальным грамматикам это все опускают либо говорят вскользь (как в АхУльмане), как о чем-то совершенно второстепенном.
Ессно опускают. Ибо сделать это качественно для порождающих грамматик задача не реальная. Вот и не хотят позориться.
-
Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.
Здравствуй капитан очевидность.
Превед!
Вот только научить всему этому парсер на аналитической грамматике намного проще.
Вон посмотри на тот ужОс в который превращается разбор простейших арифметических выражений.
Там ты не получишь ни нормального АСТ. Ни нормального восстановления после ошибок. Ни нормальных сообщений об ошибках.
Ибо ни один пользователь языка не поймет что term'ы м factor'ами.
Дык уже (не понял):
[00:16:51] <vlad2> А вот как расшифровывается "term" применительно к примерам всяких грамматик?
[00:38:11] <valexеy> vlad2: terminal ?
[00:38:25] <valexеy> там есть терминалы и нетерминалы
[00:38:31] <valexеy> а еще бывают лексемы
[00:38:39] <valexеy> ну и правила вывода
[00:38:41] <valexеy> вроде бы все.
[00:38:46] <valexеy> больше ничего там нет
[00:38:54] <valexеy> а, ну еще аксиома грамматики.
[00:38:57] <valexеy> теперь точно все :-)
[00:39:14] <vlad2> Не, не терминал.
[00:39:43] <vlad2> Пытаюсь сочинить EBNF. Пока глухо.
[00:41:10] <valexеy> Э? А чо там сочинять то?
[00:41:58] <valexеy> откуда ты вообще этот терм выкопал?
[00:42:01] <valexеy> давай контекст
[00:44:30] <valexеy> Терм — кормовая единица, выражаемая в количестве «чистой», или физиологически полезной животному, энергии. В США один терм приравнен к 1 Мкал.
[00:44:38] <valexеy> :-)
[00:47:38] <vlad2> Терм во всяких примерах. Вобщем избавился я от него :)
[00:47:49] <vlad2> Сочиняю грамматику для выражений.
[00:47:55] <vlad2> Вроде получилось.
[00:48:40] <valexеy> В каких это примерах?
[00:49:07] <vlad2> Например, в Compiler Construction ;)
[00:49:23] <valexеy> В переводном или в исходном?
[00:49:50] <vlad2> syntax = {production}.
production = identifier "=" expression "." .
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
[00:49:56] <vlad2> В исходном, конечно.
[00:50:00] <vlad2> Вот что тут term?
[00:50:05] <valexеy> а, ну это ж тупо так один из нетерминалов назван
[00:50:12] <valexеy> term = factor {factor}.
[00:50:17] <vlad2> _Почему_ так?
[00:50:19] <valexеy> очевидно же :-)
[00:50:22] <vlad2> Как переводится то? :)
[00:50:26] <valexеy> Потому что так захотелось создателю :-)
[00:50:36] <valexеy> У меня сестра их вообще называет навроде A12
[00:50:38] <valexеy> :-)
[00:50:45] <vlad2> просто оно реально confusing с терминалами нетерминалами.
[00:51:02] <valexеy> ну, блин. это ж Вирт! :-)
[00:51:26] <vlad2> Кстати, если попробуешь представить себе этот синтаксис - тоже фигня какая-то поулучается.
[00:52:40] <valexеy> нихачу представлять!
[00:52:52] <vlad2> factor {factor} превращается в последовательность всякой херни (без операторов). К чему такой пример?
[00:54:00] <valexеy> К тому, что Вирт там избавлялся от левой рекурсии (на которой рекурсивный спуск, да и вообще почти любой парсер который идет сверху-вниз, кроме GLL, сдохнет).
[00:55:05] <valexеy> Это стандартный прием ухода от левой рекурсии, в ахульмане он описан.
[00:55:36] <valexеy> А у Вирта, НЕ описан. Ибо грамматикам он не учит. А учит по готовой Им даденой грамматике строить компилятор одного вида :-)
Ессно опускают. Ибо сделать это качественно для порождающих грамматик задача не реальная. Вот и не хотят позориться.
Но собственно ты пока так и не ответил на вопрос - если у меня есть произвольная порождающая грамматика (в EBNF) всегда ли существует эквивалентная ей (в плане языка) аналитическая грамматика?
PS. Если ты так высказываешься в сторону АхУльмана, то что же ты скажешь про "Построение Компиляторов" Вирта? ;-)
-
Но собственно ты пока так и не ответил на вопрос - если у меня есть произвольная порождающая грамматика (в EBNF) всегда ли существует эквивалентная ей (в плане языка) аналитическая грамматика?
Аналитические грамматики бывают разными.
Можно создать и такую что будет полность покрывать языки задаваемые EBNF.
Но на практике всем на это пофиг. Так что обычно аналитические грамматики разбирают свой весьма специфический класс языков.
Например мой парсер может полностью покрывает регулярные грамматики, частично КЗ грамматики и скорей всего все однозначные КС грамматики. А скоро возможно и неоднозначные кушать будет.
Строго математически я это не доказывал. Но разбор реальных языков на нем делать проще, чем на БНФ парсерах.
PS. Если ты так высказываешься в сторону АхУльмана, то что же ты скажешь про "Построение Компиляторов" Вирта? ;-)
Не читал. И судя по его языкам, не думаю, что Вирт может написать что-то интересное.
Да ты и сам пишешь что:
А у Вирта, НЕ описан. Ибо грамматикам он не учит. А учит по готовой Им даденой грамматике строить компилятор одного вида :-)
-
chucheloid, вы можешь привести пример на пальцах? Мне вот совсем ума не хватает понять чем это будет отличаться от обычных распознающих автоматов.
ps Реально интересно. :)
-
Еще вот такое нашел:
Категориальная грамматика (http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
Оно?
Я так понимаю, что нихрена не оно...
Ибо: (http://isdwiki.rsuh.ru/index.php/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B3%D0%B2%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0#.D0.9F.D1.80.D0.BE.D1.81.D1.82.D1.8B.D0.B5_.D0.BA.D0.B0.D1.82.D0.B5.D0.B3.D0.BE.D1.80.D0.B8.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B0.D1.82.D0.B8.D0.BA.D0.B8_.D0.9B.D0.B0.D0.BC.D0.B1.D0.B5.D0.BA.D0.B0)
Теорема о том, что каждый язык, определяемый К-грамматикой является контекстно-свободным (с доказательством)
противоречит:
Например мой парсер может полностью покрывает регулярные грамматики, частично КЗ грамматики и скорей всего все однозначные КС грамматики
-
Гитхаб похоже лежит. Попробуй позже.
Посмотрел. DSL такой DSL. Все классно. Но непонятно :) Можно на маленьком примерчике а-ля "парсинг выражений +,-,*,/" разобрать преимущества аналитической грамматики?
-
Ещё хотелось бы понять какая вообще задача решается?
-
Можно на маленьком примерчике а-ля "парсинг выражений +,-,*,/" разобрать преимущества аналитической грамматики?
Обычно на маленьких примерчиках преимущества не раскрываются, увидеть их можно в объёмных/сложных случаях. По-крайней мере преимущества ООП, ФП и т.д...
-
Некий товарищ в одной из дискуссий сказал:
"Ты даже не представляешь, какой объем работы по изучению технологий прасинга я проделал.
Я проанализировал кучу научных и практических работ за последние несколько десятилетий.
В результате я взял за основу два разработанных и забытых в середине семидесятых алгоритма.
Я разобрал их по косточкам. После чего соединил их части. Добавил кое-что от себя. И получил очень выразительный ДСЛ для описания парсеров."
Вот указал бы он в открытую, на что он опирается в своей разработке?
Сильно сомневаюсь, но нисколечко не осуждаю.
А ведь это знание многое могло бы прояснить.
:)
-
Некий товарищ в одной из дискуссий сказал:
"Ты даже не представляешь, какой объем работы по изучению технологий прасинга я проделал.
Я проанализировал кучу научных и практических работ за последние несколько десятилетий.
В результате я взял за основу два разработанных и забытых в середине семидесятых алгоритма.
Я разобрал их по косточкам. После чего соединил их части. Добавил кое-что от себя. И получил очень выразительный ДСЛ для описания парсеров."
Это отсюда: http://eao197.blogspot.com/2012/03/progflame-nemerle2.html?showComment=1333198653688#c4149065481751166467
-
Посмотрел. DSL такой DSL. Все классно. Но непонятно :) Можно на маленьком примерчике а-ля "парсинг выражений +,-,*,/" разобрать преимущества аналитической грамматики?
Так было уже.
Вот как разбор арифметики выглядит на БНФ в виде понятном LL парсеру.
http://oberspace.dyndns.org/index.php/topic,333.msg8854.html#msg8854
А вот так с использование аналитической грамматики.
syntax add is expr = expr '+'s expr { precedence 10; }
syntax sub is expr = expr '-'s expr { precedence 10; }
syntax mul is expr = expr '*'s expr { precedence 20; }
syntax div is expr = expr '/'s expr { precedence 20; }
syntax mod is expr = expr '%'s expr { precedence 20; }
syntax pow is expr = expr '^'s expr { precedence 30 right-associative; }
Операторы описаны как они есть. Приоритеты и ассоциативность заданы явно, а не через хитрую рекурсию.
АСТ получается сразу, такой как надо, а не та жуть, которую выдаст BNF парсер по той страшной грамматике.
Ну и сам факт того что никто не использует БНФ парсеры для промышленных применений, а только для побаловаться (максимум для внутренних проектов) наводит на мысли.
-
Обычно на маленьких примерчиках преимущества не раскрываются, увидеть их можно в объёмных/сложных случаях. По-крайней мере преимущества ООП, ФП и т.д...
В данном случае раскрывается даже на маленьких примерчиках...
-
Вот указал бы он в открытую, на что он опирается в своей разработке?
Сильно сомневаюсь, но нисколечко не осуждаю.
А ведь это знание многое могло бы прояснить.
:)
TDPL/PEG и TDOP
Много тебе это сказало?
Вижу как побежал в гугл выяснять что это такое. :)
-
Ещё хотелось бы понять какая вообще задача решается?
Тотальное уничтожение "синтаксического оверхеда (С)".
-
Много тебе это сказало?
Вижу как побежал в гугл выяснять что это такое. :)
[/quote]
Вот это - достаточно :)
-
Некий товарищ в одной из дискуссий сказал:
"Ты даже не представляешь, какой объем работы по изучению технологий прасинга я проделал.
Я проанализировал кучу научных и практических работ за последние несколько десятилетий.
В результате я взял за основу два разработанных и забытых в середине семидесятых алгоритма.
Я разобрал их по косточкам. После чего соединил их части. Добавил кое-что от себя. И получил очень выразительный ДСЛ для описания парсеров."
Брайен Форд, в русских блогах тусит? ;)
-
Собсна вот:
Относительно недавно появилась работа некоего Брайена Форда (Bryan Ford), посвященная его алгоритму, названному "packrat parsing". Он вытащил на свет формализм, разработанный около 30 лет назад, и описывавший парсер, использующий алгоритм нисходящего спуска с откатами (Top-Down Parsing Language, TDPL).
http://www.k-press.ru/cs/2010/2/Editorial/Editorial.asp (http://www.k-press.ru/cs/2010/2/Editorial/Editorial.asp)
-
Ну и сама работа до кучи:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.1175 (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.1175)
ps Индекс цитирования забавно выглядит :)
-
TDOP тоже нашел:
http://cat.hansa-flex.com/ru/pdf/906451 (http://cat.hansa-flex.com/ru/pdf/906451)
надеть прорезиненной стороной на выступ
поршневого штока и зафиксировать с
помощью шайбы и гайки
Так просто!?!? ;D ;D ;D
-
http://www.k-press.ru/cs/2010/2/Editorial/Editorial.asp (http://www.k-press.ru/cs/2010/2/Editorial/Editorial.asp)
1)На чистом ПЕГ писать грамматики довольно сложно.
2)Пакрат жуткий тормоз.
-
Тогда меня только один вопрос интересует. Оно живет вне немерли? И если живет, то где сие чудо можно лицезреть?
ps Ну не шарю я в немерлях, и не расшарюсь в ближайшее время.
-
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.
По-моему, Вы под лексером что-то слишком частное. Может, просто в вашей команде переосмыслили трансляцию и придумали лексер нового поколения?
-
Посмотрел. DSL такой DSL. Все классно. Но непонятно :) Можно на маленьком примерчике а-ля "парсинг выражений +,-,*,/" разобрать преимущества аналитической грамматики?
Так было уже.
Вот как разбор арифметики выглядит на БНФ в виде понятном LL парсеру.
http://oberspace.dyndns.org/index.php/topic,333.msg8854.html#msg8854
А вот так с использование аналитической грамматики.
syntax add is expr = expr '+'s expr { precedence 10; }
syntax sub is expr = expr '-'s expr { precedence 10; }
syntax mul is expr = expr '*'s expr { precedence 20; }
syntax div is expr = expr '/'s expr { precedence 20; }
syntax mod is expr = expr '%'s expr { precedence 20; }
syntax pow is expr = expr '^'s expr { precedence 30 right-associative; }
Операторы описаны как они есть. Приоритеты и ассоциативность заданы явно, а не через хитрую рекурсию.
АСТ получается сразу, такой как надо, а не та жуть, которую выдаст BNF парсер по той страшной грамматике.
Ну и сам факт того что никто не использует БНФ парсеры для промышленных применений, а только для побаловаться (максимум для внутренних проектов) наводит на мысли.
По-моему, вы там у себя просто реализовали аналог BNF-а, что позволило более точно управлять областью значения. А грамматика как была порождающей, так и осталась.
-
Тогда меня только один вопрос интересует. Оно живет вне немерли? И если живет, то где сие чудо можно лицезреть?
Пока нет. Но будет.
ps Ну не шарю я в немерлях, и не расшарюсь в ближайшее время.
Там шарить нечего.
-
По-моему, Вы под лексером что-то слишком частное. Может, просто в вашей команде переосмыслили трансляцию и придумали лексер нового поколения?
По PEG есть много документации в сети.
Покажи мне там лексер.
-
Зачем так оверквотить?
По-моему, вы там у себя просто реализовали аналог BNF-а,
Если оно, похоже, выглядит, то это еще ничего не значит.
Семантика там совершенно другая.
что позволило более точно управлять областью значения.
Чего?
А грамматика как была порождающей, так и осталась.
Извини, но мне виднее какая у меня грамматика.
-
По PEG есть много документации в сети.
Покажи мне там лексер.
Дело вот в чём: пока программы пишут в обычных текстовых редакторах, которые сохраняют файлы на диск, для трансляции необходимо произвести следующие манипуляции.
1. поток байт (например, из файла) преобразовать в поток букв (грубо говоря).
2. поток букв преобразовать в поток лексем. (лексический анализатор)
3. поток лексем преобразовать в дерево разбора. (синтаксический анализатор)
4. ...
То есть, для работы синтаксического анализатора нужны лексемы. И совсем не важно, запихан ли весь его функционал в файл lexer.src или равномерно размазано по транслятору.
-
Если оно, похоже, выглядит, то это еще ничего не значит.
Семантика там совершенно другая.
Но документации-то, которая понятно всё разъясняет, пока нет, поэтому приходится гадать.
syntax add is expr = expr '+'s expr { precedence 10; }Смысл BNF основан на подстановке. Сами правила с помощью BNF записываются так: Понятие = Определение.
Когда при разборе кода встретилось понятие, то происходит его замена на определение. На этом основан синтаксический разбор. Как пишут в книгах по компиляторам, разбор - это порождение наоборот.
Вы же утверждаете, что Ваш метод имеет отношение к разбору, но не имеет отношение к порождающим грамматикам.
Статей на эту тему от Вас нет, глядя на исходный код, мне не очевидно, что так и есть.
Кстати
{ precedence 10; }Не лучше ли задание конкретных значений переложить на плечи компилятора? Список списков.
[
[{add,"expr '+'s expr"},
{sub,"expr '-+'s expr"}],
[{mul,"expr '*'s expr"},
{div,"expr '/'s expr"},
{mod,"expr '%'s expr"}],
[{pow,"expr '^'s expr"}]
]
-
1. поток байт (например, из файла) преобразовать в поток букв (грубо говоря).
2. поток букв преобразовать в поток лексем. (лексический анализатор)
3. поток лексем преобразовать в дерево разбора. (синтаксический анализатор)
Так бы сразу и сказал что из секты дракона.
То, что было до букв к синтаксическому анализу вообще не относится.
А для безлексерных парсеров лексемами являются отдельные буквы.
Лексеры вообще говоря нужны только из-за того что быстрые БНФ'ные анализаторы физически не способны разрешать конфликты которые разрешает лексер.
А те, которые способны тормозят, как чёрт знает что.
-
Ахо и Ульмана не читал, поэтому не знаю, как они обосновали наличие лексера. А вот в другом источнике его потребовалось ввести потому, что именно парсер не мог разрешить некоторые проблемы.
sum=a1+b3
su m = a 1+ b3
Если работать напрямую с буквами простым способом, то две вышеприведённые строки для парсера окажутся одинаковыми. А если с буквами работать сложным способом, чтобы он различал варианты, то код станет страшным. Правда, здесь стоит учитывать, что весь код парсера должен был по-старинке находиться в одном файле (точнее, в одной компилируемой единице, если принимать во внимание includ-ы).
-
Если работать напрямую с буквами простым способом, то две вышеприведённые строки для парсера окажутся одинаковыми. А если с буквами работать сложным способом, чтобы он различал варианты, то код станет страшным. Правда, здесь стоит учитывать, что весь код парсера должен был по-старинке находиться в одном файле (точнее, в одной компилируемой единице, если принимать во внимание includ-ы).
Это даже не секта дракона. Это что-то неизмеримо более страшное.
Неадекват полнейший.
-
Valery Solovey, не тратьте время:
В тырнетах море информации по безлексерным парсерам... (http://www.google.ru/#hl=ru&newwindow=1&sclient=psy-ab&q=%D0%B1%D0%B5%D0%B7%D0%BB%D0%B5%D0%BA%D1%81%D0%B5%D1%80%D0%BD%D1%8B%D0%B9&oq=%D0%B1%D0%B5%D0%B7%D0%BB%D0%B5%D0%BA%D1%81%D0%B5%D1%80%D0%BD%D1%8B%D0%B9&gs_l=hp.3...4163.4163.4.4463.1.1.0.0.0.0.48.48.1.1.0...0.0...1c.1.zE8BpE6r6xs&bav=on.2,or.r_gc.r_pw.r_qf.&fp=6d5370b65c4540e2&biw=1092&bih=514) ;)
-
А вот и определение безлексерности:
PEGs do not require tokenization to be a separate step, and tokenization rules can be written in the same way as any other grammar rule.
т.е. в PEG не требуется отдельный лексер в том же смысле, что и в регулярках.
ОК, с этим понятно. Но преимуществ перед лексерным подходом не вижу.
chucheloid, вы можете сказать в чем конкретно превосходство? Хде профит?
-
ОК, с этим понятно. Но преимуществ перед лексерным подходом не вижу.
На сколько я понял, они хотят язык в котором лексемы зависят от контекста. Простой лексер с этим не справится, вот и извращаются.
---------
Добавляю свой вопрос: А зачем вам язык с лексемами зависящими от контекста?
-
Добавляю свой вопрос: А зачем вам язык с лексемами зависящими от контекста?
Чтобе легко лепить eDSL'и, очевидно.
Другое дело, что практика показывает, чта-а средний программист не умеет думать еще и о конструировании DSL, даже eDSL не умеет. У него голова занята совсем другим - предметной областью.
Поэтому, после общения с Владиславом Чистяковов (ака VladD2) по поводу Nemerle/N2 и Андреем Бреславом, по поводу Kotlin'a, у меня сложилось четкое мнение, что Kotlin при попутном ветре вполне может взлететь, а вот Nemerle и, тем более, Nemerle-2 - нет.
Хотя мне конечно N2 намного интересней Котлина. Точнее так: N1/N2 мне интересней на поковыряться в алгоритмах, dsl'и понаделать, теорию там с практикой в плане синтаксического разбора почесать (единственное что активно мешает ковырянию - мертвая привязка немерлей к .net'у. Мне довольно сложно найти винды в округе чтобы там немерлю поковырять).
Kotlin интересен с сугубо практической точки зрения (но нужно дождаться стабилизации языка и средств разработки для него). Особенно он мне интересен тем, что у него два бекенда - jvm и js.
-
У Вирта короче вполне себе безлексерный парсер ;D :P
from valexey: Сори. Вместо того чтобы нажать на цитирование твоего сообщения, нажал на редактирование, и затер нафиг (что мог - восстановил) :-/ Повтори свою мысль пожалуйста.
-
Собсна вот тут есть некоторая информация:
Анализаторы для языков, представленных КС-грамматиками, такие как LR-анализаторы, требуют особого шага лексического анализа, который разбивает входные данные в соответствии с пробелами, пунктуацией и так далее. Это необходимо, так как эти анализаторы используют предварительный анализ для обработки некоторых КС-грамматик в линейное время. РВ-грамматики не требуют отдельного шага лексического анализа, а правила для него могут быть заложены вместе с другими правилами грамматики.
Многие КС-грамматики содержат существенные неоднозначности, даже когда они должны описывать однозначные языки. Проблема «висячего else» языков C, C++ и Java является одним из примеров этого явления. Эти проблемы часто разрешаются применением внешнего по отношению к грамматике правила. В РВ-грамматике эти неоднозначности никогда не возникают вследствие приоритезации.
-
Сори. Вместо того чтобы нажать на цитирование твоего сообщения, нажал на редактирование, и затер нафиг
Opera наше всё.
-
Анализаторы для языков, представленных КС-грамматиками, такие как LR-анализаторы, требуют особого шага лексического анализа, который разбивает входные данные в соответствии с пробелами, пунктуацией и так далее.
Вот, кстати, я сначала не подумал о том, что есть шаг. Может, в википедии под шагом понимают проход по тексту только с целью разбиения на лексемы?..
А с началом шага синтаксического анализа о продолжении работы лексического говорить уже не приходится...
-
У Вирта короче вполне себе безлексерный парсер ;D :P
from valexey: Сори. Вместо того чтобы нажать на цитирование твоего сообщения, нажал на редактирование, и затер нафиг (что мог - восстановил) :-/ Повтори свою мысль пожалуйста.
Мою мысль повторяет следующий же пост:
http://oberspace.dyndns.org/index.php/topic,333.msg8917.html#msg8917 (http://oberspace.dyndns.org/index.php/topic,333.msg8917.html#msg8917)
Для PEG не нужен предпросмотр токенов и потому нет необходимости в отдельном лексере.
Т.е. получается что безлексерный парсер - это парсер в котором отдельный лексер не обязателен.
-
Другое дело, что практика показывает, чта-а средний программист не умеет думать еще и о конструировании DSL, даже eDSL не умеет. У него голова занята совсем другим - предметной областью.
Поэтому, после общения с Владиславом Чистяковов (ака VladD2) по поводу Nemerle/N2 и Андреем Бреславом, по поводу Kotlin'a, у меня сложилось четкое мнение, что Kotlin при попутном ветре вполне может взлететь, а вот Nemerle и, тем более, Nemerle-2 - нет.
Хотя мне конечно N2 намного интересней Котлина. Точнее так: N1/N2 мне интересней на поковыряться в алгоритмах, dsl'и понаделать, теорию там с практикой в плане синтаксического разбора почесать (единственное что активно мешает ковырянию - мертвая привязка немерлей к .net'у. Мне довольно сложно найти винды в округе чтобы там немерлю поковырять).
Kotlin интересен с сугубо практической точки зрения (но нужно дождаться стабилизации языка и средств разработки для него). Особенно он мне интересен тем, что у него два бекенда - jvm и js.
1. да и не только средний.. любой, которому есть чем заняться.
2. в явке уже есть дополняющие языки (как доп язык javafx1.0, например , не прошел), впрочем они есть и под .net. По первому впечатлению НИМЕРЛЕЙ спроектирован лучше.. Что касается вторых версий (Немерлея и FX) - то разработчики (наверное понимая, что в разработанную нишу одним только сахаром не влезешь ) пытаются найти свое собственное место.. - как результат.. и там и там "FRAMEWORKS"
-
2. в явке уже есть дополняющие языки (как доп язык javafx1.0, например , не прошел), впрочем они есть и под .net. По первому впечатлению НИМЕРЛЕЙ спроектирован лучше.. Что касается вторых версий (Немерлея и FX) - то разработчики (наверное понимая, что в разработанную нишу одним только сахаром не влезешь ) пытаются найти свое собственное место.. - как результат.. и там и там "FRAMEWORKS"
JavaFX 2.0 это не язык. Это просто либа для java.
Кроме того, я не вижу смысла даже сравнивать javafx с nemerle, ибо первый по сути является DSL'ем, а второй является языком общего назначения с богатыми возможностями создания eDSL'ей.
-
JavaFX 2.0 это не язык. Это просто либа для java.
Кроме того, я не вижу смысла даже сравнивать javafx с nemerle, ибо первый по сути является DSL'ем, а второй является языком общего назначения с богатыми возможностями создания eDSL'ей.
1 Так я про это и сказал.. в конце
2. Думаю что есть.. 1 версии были яп.. общего назначения с небольшими уклонами в предметные области... а вот вторые - фреймворки(это по словам САМИХ РАЗРАБОТЧИКОВ)
-
то есть мне лично интересно это вот с какой позиции куда процесс языкосоздания заносит в нашей реальности , где конкуренция достаточно высока и почему это так...
-
Другое дело, что практика показывает, чта-а средний программист не умеет думать еще и о конструировании DSL, даже eDSL не умеет. У него голова занята совсем другим - предметной областью.
Нет. Она у него занята головоломкой, на тему как впихнуть предметную область в узкие рамки языка программирования так, чтобы код не скатился в говно.
А если не занята, то проект проваливается с вероятностью близкой к 100%.
Просто люди настолько привыкли к данной совершенно бесполезной активности, что не замечают её.
С ДСЛ все намного проще. Написал логику как она есть. И скомпилировал.
Сделать компилятор намного проще, чем архитектуру архитектурить, ибо компилятор может генерировать любой говнокод и ни каких проблем это не создает.
Кстати немерле тоже умеет компилироваться в яваскрипт. http://user1663.netfx45lab.discountasp.net/
Можете сравнить данный способ создания веб интерфейсов с любым другим...
-
1. да и не только средний.. любой, которому есть чем заняться.
И чем же он занимается?
Ломает голову, как протащить через 100500 методов контекст, который в начале проекта был не нужен, а когда понаписали десятки метров кода понадобился?
Или продирается через тонны костылей, которые протаскивают что-то куда-то?
А может он долбит реализацию INotifyPropertyChanged, которая у всех классов настолько одинаковая, что даже не смешно?
...
2. в явке уже есть дополняющие языки (как доп язык javafx1.0, например , не прошел), впрочем они есть и под .net. По первому впечатлению НИМЕРЛЕЙ спроектирован лучше.. Что касается вторых версий (Немерлея и FX) - то разработчики (наверное понимая, что в разработанную нишу одним только сахаром не влезешь ) пытаются найти свое собственное место.. - как результат.. и там и там "FRAMEWORKS"
Я совершенно не понял что общего у JavaFX и Н2?
-
Другое дело, что практика показывает, чта-а средний программист не умеет думать еще и о конструировании DSL, даже eDSL не умеет. У него голова занята совсем другим - предметной областью.
Нет. Она у него занята головоломкой, на тему как впихнуть предметную область в узкие рамки языка программирования так, чтобы код не скатился в говно.
А если не занята, то проект проваливается с вероятностью близкой к 100%.
Типичный программист не знает полностью своего основного языка программирования даже если это просто java. Не знает как работает скажем jvm, не знат как работает сборщик мусора (а это уже .net'чик), и, в частности, не знает соберет ли сборщик мусора два объекта которые ссылаются друг на друга но извне на них больше ссылок нет. И что под капотом библиотек тоже не знает. Но при этом этот самый типичный разработчик, каким-то образом добивается поставленных перед проектом целей. Это факт подтверждаемый экспериментально.
Про то как устроены компиляторы, про какие-то грамматики и про то как сделать простейший язык (да даже тупо калькулятор который умеет + и -) они не знают и не ведают. И не умеют.
-
Типичный программист не знает полностью своего основного языка программирования даже если это просто java. Не знает как работает скажем jvm, не знат как работает сборщик мусора (а это уже .net'чик), и, в частности, не знает соберет ли сборщик мусора два объекта которые ссылаются друг на друга но извне на них больше ссылок нет. И что под капотом библиотек тоже не знает. Но при этом этот самый типичный разработчик, каким-то образом добивается поставленных перед проектом целей. Это факт подтверждаемый экспериментально.
Как меня утомила эта сказка.
Такое случается только если над ними стоят надсмотрщики, которые создают архитектуру. А такие люди без труда смогут сделать ДСЛ.
Либо проект маленький как хелловорлд. Тогда просто он не успевает загнуться до того как его доделают.
-
Как меня утомила эта сказка.
Такое случается только если над ними стоят надсмотрщики, которые создают архитектуру. А такие люди без труда смогут сделать ДСЛ.
Либо проект маленький как хелловорлд. Тогда просто он не успевает загнуться до того как его доделают.
Да нет не сказка, просто каждый занимается своим делом.. а насчет остального не вижу противоречия с тем о чем говорит Алексей - каждому свое. Понятие "маленький" относительно.. вон айфон - тоже маленький да отдельных "частей" в нем немного - но высокотехнологичный продукт однако..
-
Да нет не сказка, просто каждый занимается своим делом..
Именно что сказка. Ну не могут люди с низкой квалификацией сделать что-то большое.
Физически не могут.
Обязательно нужен надсмотрщик, который ходит и бьёт по рукам.
ДСЛ с этим справится гораздо лучше.
1)Банально в разы меньше писать. Те работа будет сделана быстрее и там будет меньше багов.
2)ДСЛ очень эффективно бьёт по рукам. Причем со 100% вероятностью и сразу.
Понятие "маленький" относительно.. вон айфон - тоже маленький да отдельных "частей" в нем немного - но высокотехнологичный продукт однако..
Абсолютно неадекватная аналогия. Я даже не могу понять, как она могла в голову прийти.
-
ДСЛ с этим справится гораздо лучше.
Поправочка: удачный DSL.
-
Я совершенно не понял что общего у JavaFX и Н2?
Я уже сказал - ребрэндинг -стали называться фреймворками... разумеется каждый разошелся по "своим понятиям"... но тем не менее...
-
Коль разговор скатывается к DSL (я правда так и не понял при чём тут контекстно зависимые лексемы), расскажу как я (этим летом) сделал некий аналог DSL без написания каких-либо парсеров вовсе.
Стоит задача автоматического тестирования программной системы (телефонной станции). Написан Симулятор внешнего мира. Программная система стартует, коннектится к Симулятору внешнего мира и думает, что она в настоящем "боевом режиме". Симулятор симулирует регистрацию телефонов, звонков, отправку всяких факсов и т. п.
Возникает вопрос как запрограммировать Симулятор. Сначала сделал это "в лоб". Написал пяток тестов. Каждый под 700 строчек C# кода. А тестов-то нужно несколько десятков если не сотен. Причём в будущем чего-то обязательно поменяется и надо будет править всё это хозяйство. Пришлось напрячь извилины и родить некий аналог DSL. Мозгом Симулятора сделал некую виртуальную машину, которая программируется на специальном языке DSL-ассемблера. Написание теста свелось к написанию эмиттера DSL-ассемблерного кода для той виртуальной машины.
Вот пара примеров:
public abstract class BasicCallEmitter: BasicTestEmitter
{
public Assembler.Procedure Emit ()
{
MACROS_Init();
CONNECT_Logic(L1, subscriberLogicId);
REGISTER_Phone(T1, proto1, L1);
REGISTER_Phone(T2, proto2, L1);
SEND_CallBegin(C1, T1, T2, codecs1);
WAIT_CallAck(C1);
MACROS_AfterReceiveCallAck1();
WAIT_CreateCall(C2);
WAIT_SetMedia(C2);
WAIT_Setup(C2);
MACROS_AfterReceiveSetup2();
SEND_SetMediaAck(C2, codecs2);
MACROS_AfterSendSetMediaAck2();
MACROS_Connect();
MACROS_AfterReceiveConnect1();
SLEEP(this.secondsDuration);
SEND_Terminate(C1, SIPBye);
WAIT_Terminate(C2);
WAIT_TerminatedAck(C1);
WAIT_TerminatedAck(C2);
ASSERT_StreamCount(0);
ASSERT_RecordingCount(0);
ASSERT_CallCount(0);
ASSERT_PromptCount(0);
SLEEP(1);
CONNECT_CentrexCDR(this.centrexCDR);
CHECK_CDR(T1, C1, T2, C2, SIPBye);
PASSED();
return this.GetProcedure();
}
protected virtual void MACROS_Connect ()
{
SEND_Connect(C2);
WAIT_Connect(C1);
}
protected virtual void MACROS_AfterReceiveCallAck1 ()
{
}
protected virtual void MACROS_AfterReceiveConnect1 ()
{
}
protected virtual void MACROS_AfterReceiveSetup2 ()
{
}
protected virtual void MACROS_AfterSendSetMediaAck2 ()
{
}
}
public abstract class Web_Fax: BasicTestEmitter
{
public Assembler.Procedure Emit ()
{
MACROS_Init();
CONNECT_Logic(L1, subscriberLogicId);
CONNECT_Logic(L2, servicePlatformId);
REGISTER_Phone(T1, proto1, L1);
REGISTER_Phone(T2, proto2, L1);
EXECUTE(MakeFaxTask);
WAIT_CreateCall(C1, desc);
WAIT_SetMedia(C1);
WAIT_Setup(C1);
NEW_Call(C2, L1);
COPY_ConfId(C2, C1);
COPY_Codecs(C2, C1);
COPY_Proto(C2, C1);
SEND_CallBegin(C2, desc);
WAIT_CallAck(C2);
SEND_SetMedia(C2);
SEND_CallAckProceded(C2);
WAIT_CreateCall(C3);
WAIT_SetMedia(C3);
WAIT_Setup(C3);
SEND_Progress(C3, true, true);
WAIT_SetMediaAck(C2);
COPY_Codecs(C1, C2);
SEND_SetMediaAck(C1);
WAIT_Progress(C2);
SEND_Progress(C1, true, true);
SEND_SetMediaAck(C3, defaultCodecs);
SEND_Connect(C3);
WAIT_Connect(C2);
SEND_Connect(C1);
MACROS_FaxSetMedia();
WAIT_SendFax();
WAIT_Terminate(C1);
WAIT_TerminatedAck(C1);
SEND_Terminate(C2, SIPBye);
WAIT_Terminate(C3);
WAIT_TerminatedAck(C2);
WAIT_TerminatedAck(C3);
ASSERT_StreamCount(0);
ASSERT_RecordingCount(0);
ASSERT_CallCount(0);
ASSERT_PromptCount(0);
SLEEP(1);
CONNECT_CentrexCDR(this.centrexCDR);
CHECK_CDR(T1, C1, T2, C2, SIPBye);
PASSED();
return this.GetProcedure();
}
public abstract void MACROS_FaxSetMedia ();
}
Эмиттеры DSL-ассемблерного кода конкретных тестов просто наследуются от этих абстрактных классов и переопределяются нужные виртуальные процедуры MACROS_***.
Вот, например, эмиттер кода теста базового звонка SIP-SIP (при написании "в лоб" было 728 строчек на C#, а теперь всего пять DSL-ассемблерных инструкций):
public class SIP_SIP_Emitter: BasicCallEmitter
{
public SIP_SIP_Emitter ()
{
reference = "SIP-SIP";
description = "Basic call test SIP-SIP";
}
protected override void MACROS_AfterReceiveCallAck1 ()
{
SEND_SetMedia(C1);
SEND_CallAckProceded(C1);
}
protected override void MACROS_AfterReceiveSetup2 ()
{
SEND_Progress(C2, true, true);
WAIT_SetMediaAck(C1);
WAIT_Progress(C1);
}
}
Как видите всё на чистом C#, между тем DSL есть и сильно помогает. А своего парсера-транслятора-компилятора из DSL в чего-то там писать не пришлось. :) :) :)
-
Ну не могут люди с низкой квалификацией сделать что-то большое.
Физически не могут.
Обязательно нужен надсмотрщик, который ходит и бьёт по рукам.
....
Абсолютно неадекватная аналогия. Я даже не могу понять, как она могла в голову прийти.
ммм. есть некоторая вероятность , что мы друг друга не понимаем.. я говорю про то, что есть различные уровни "восприятия" сложности.. скажем так специалист по теоретической механике или еще лучше , по термодинамике может решать вполне СЛОЖНЫЕ задачи , без понимания внутренней структуры обьектов с которыми он работает (скажем воспользовавшись эмпирическими законами, математикам ,так вообще хватает аксиоматики)- и глупостью было бы предположить что некоторый "фундаментальщик" разберется с пол -тычка с их заморочками... более того, ИМХО человеку который утверждает обратное стоило бы провериться в психдиспансере ;).
-
Коль разговор скатывается к DSL (я правда так и не понял при чём тут контекстно зависимые лексемы), расскажу как я (этим летом) сделал некий аналог DSL без
....
И что, если завернуть это дело , нормальным образом в библиотеку код так уж сильно распухнет?
-
Коль разговор скатывается к DSL (я правда так и не понял при чём тут контекстно зависимые лексемы), расскажу как я (этим летом) сделал некий аналог DSL без написания каких-либо парсеров вовсе.
...
Как видите всё на чистом C#, между тем DSL есть и сильно помогает. А своего парсера-транслятора-компилятора из DSL в чего-то там писать не пришлось. :) :) :)
Так это не DSL, а просто набор процедур...
-
Коль разговор скатывается к DSL (я правда так и не понял при чём тут контекстно зависимые лексемы), расскажу как я (этим летом) сделал некий аналог DSL без написания каких-либо парсеров вовсе.
...
Как видите всё на чистом C#, между тем DSL есть и сильно помогает. А своего парсера-транслятора-компилятора из DSL в чего-то там писать не пришлось. :) :) :)
Так это не DSL, а просто набор процедур...
Это eDSL :-) По сути такой же какой в Haskell'e бейсик ;-)
-
И что, если завернуть это дело , нормальным образом в библиотеку код так уж сильно распухнет?
Я не понял вопроса.
Я сравнивал количество DSL-ассемлерных инструкций с количеством C# кода, который требовался для каждого теста до тех пор пока я не изобрёл для этой задачи DSL-ассемблер.
Сама виртуальная машина обрабатывающая DSL-ассемблерные инструкции сейчас занимает 2651 строчек C#.
Если нужно написать 100 тестов, то выбор очевиден: написание "в лоб" отнимет по 700 строчек C# на тест; написание на DSL-ассемблере -- примерно по 5-10 DSL-ассемблерных инструкций на тест.
-
Так это не DSL, а просто набор процедур...
Именно! Сам DSL мне оказался нафиг не нужным, хватило его ассемблера. Набором процедур на C# эмичу DSL-ассеблерный код.
-
Кстати, для того, чтобы в языке общего назначения (например C#, C++) можно было полноценно делать eDSL нужна возможность не только добавлять возможности (в виде тех же процедур как у Сергея в примере), но и возможность запрещать/удалять что-то, грубо говоря, чтобы в блоке кода на этом eDSL гарантированно не было тех или иных вещей которые есть в родительском языке.
-
Так это не DSL, а просто набор процедур...
Именно! Сам DSL мне оказался нафиг не нужным, хватило его ассемблера. Набором процедур на C# эмичу DSL-ассеблерный код.
Да, но тут есть серьёзная проблема -- нет защиты от ошибок в порядке вызова этих процедур, от ошибок в логике получающейся программы.
DSL же подразумевает более защищённый от ошибок язык, более высокоуровневый...
-
Да, но тут есть серьёзная проблема -- нет защиты от ошибок в порядке вызова этих процедур, от ошибок в логике получающейся программы.
DSL же подразумевает более защищённый от ошибок язык, более высокоуровневый...
Вызов процедур - эмичение инструкций. Например, вызов процедуры PASSED:
public void PASSED ()
{
this.Emit(new Halt(true, null));
}
Процедура Emit:
public void Emit (Instruction inst)
{
if (this.program == null)
{
this.program = new Procedure();
}
this.program.Emit(inst);
}
Instruction - это:
public abstract class Instruction
{
public abstract bool Execute (Service x);
}
Procedure - это тоже инструкция:
public sealed class Procedure: Instruction
{
public readonly System.Collections.Generic.List<Instruction> instructions = new System.Collections.Generic.List<Instruction>();
public void Emit (Instruction inst)
{
this.instructions.Add(inst);
}
public override bool Execute (Service service)
{
return false;
}
}
Разный порядок ассемблерных инструкций - разные программы. Откуда DSL-компилятору знать какую именно программу мне нужно сейчас, чтобы подсказать мне, что я располагаю ассемблерные команды в неправильном порядке? Тут почти любой порядок будет давать в каком-то смысле правильную программу.
-
Коль разговор скатывается к DSL (я правда так и не понял при чём тут контекстно зависимые лексемы), расскажу как я (этим летом) сделал некий аналог DSL без написания каких-либо парсеров вовсе.
Это тебе просто с задачей повезло.
А могло и не повезти.
http://user1663.netfx45lab.discountasp.net/
Что бы делал?
-
Что бы делал?
Не знаю. Я с Гуём не очень. Там надо динамически генерить html код? Ну, первое что приходит в голову, наверное я натворил бы композицию объектов, которые умеют сериализовываться в html. Это неплохо бы сработало когда надо генерировать типовой-однообразный html.
-
Не знаю. Я с Гуём не очень. Там надо динамически генерить html код? Ну, первое что приходит в голову, наверное я натворил бы композицию объектов, которые умеют сериализовываться в html. Это неплохо бы сработало когда надо генерировать типовой-однообразный html.
Там все намного сложнее, чем кажется. Открой демку Introduction и посмотри на код. Потом поменяй то, что написано в полях ввода. Нажми на кнопку и подумай, может ли этот код так себя вести... ;D
-
Открой демку Introduction и посмотри на код.
Я там ещё у странички запросил исходный код и получил 2312 строчечный html вот с такими названиями функций: MVCTest_SamplesViewModel__N_closureOf__N_lambda__8064_8256.
Веб для меня -- тёмный лес...
-
Открой демку Introduction и посмотри на код.
Я там ещё у странички запросил исходный код и получил 2312 строчечный html вот с такими названиями функций: MVCTest_SamplesViewModel__N_closureOf__N_lambda__8064_8256.
Веб для меня -- тёмный лес...
Это не веб, это выхлоп компилятора немерли (если не ошибаюсь).
И да, для данных примеров оно выглядит как суровый оверкил. (мало того что для такой простой задачи там порядка 2к строк, так еще и пачка либ подключено:
<script src="/Scripts/jquery-1.8.0.min.js" type="text/javascript"></script>
<script src="/Scripts/knockout-2.1.0.debug.js" type="text/javascript"></script>
<script src="/Scripts/jquery.signalR-0.5.3.min.js" type="text/javascript"></script>
<script src="/Scripts/sammy.js" type="text/javascript"></script>
<script src="/Scripts/prettify.js" type="text/javascript"></script>
<script src="/Scripts/lang-n.js" type="text/javascript"></script>
<script src="/Scripts/linq.js" type="text/javascript"></script>
<script src="/signalr/hubs" type="text/javascript"></script>
хотя, возможно как минимум часть этих либ нужна лишь для подсветки синтаксиса исходника странички и так далее.
)
-
Я там ещё у странички запросил исходный код и получил 2312 строчечный html вот с такими названиями функций: MVCTest_SamplesViewModel__N_closureOf__N_lambda__8064_8256.
Веб для меня -- тёмный лес...
Ты пытаешься понять язык высокого уровня глядя на машинный код, полученный после оптимизирующего компилятора.
Это очень не правильный подход.
-
Это не веб, это выхлоп компилятора немерли (если не ошибаюсь).
И да, для данных примеров оно выглядит как суровый оверкил.
Смотреть нужно не машинный код. А тот код, из которого это все получается.
(мало того что для такой простой задачи там порядка 2к строк, так еще и пачка либ подключено:
Если почитать этот код, то станет ясно, что это код _всех_ демок и обвязки.
Ну и проект еще только начали писать. Объем генерируемого кода там можно очень жестоко оптимизировать. Просто это пока никто не делал.
хотя, возможно как минимум часть этих либ нужна лишь для подсветки синтаксиса исходника странички и так далее.
Именно.
-
chucheloid, а что в твоем понимание "лексер"?
-
Ссылочка в тему.
[PEG] Очень хорошо забытое старое (http://ko.com.ua/ochen_horosho_zabytoe_staroe_35025)
Вообще PEG довольно интересен как замена регулярок.
-
Ух ты. А добровольцы одинэснеги уже прикрутили Lua к 1С и тамошний LPeg юзают.
-
http://www.inf.puc-rio.br/~roberto/docs/peg.pdf
Current text pattern-matching tools are based on regular expressions. However, pure regular
expressions have proven too weak a formalism for the task: many interesting patterns either are
difficult to describe or cannot be described by regular expressions. Moreover, the inherent nondeterminism of regular expressions does not fit the need to capture specific parts of a match.
Motivated by these reasons, most scripting languages nowadays use pattern-matching tools that
extend the original regular-expression formalism with a set of ad-hoc features, such as greedy
repetitions, lazy repetitions, possessive repetitions, “longest match rule”, lookahead, etc. These
ad-hoc extensions bring their own set of problems, such as lack of a formal foundation and complex
implementations.
In this paper, we propose the use of Parsing Expression Grammars (PEGs) as a basis for pattern
matching. Following this proposal, we present LPEG, a pattern-matching tool based on PEGs for
the Lua scripting language. LPEG unifies the ease of use of pattern-matching tools with the full
expressive power of PEGs. Because of this expressive power, it can avoid the myriad of ad-hoc
constructions present in several current pattern-matching tools. We also present a Parsing Machine
that allows a small and efficient implementation of PEGs for pattern matching.
-
Ух ты. А добровольцы одинэснеги уже прикрутили Lua к 1С и тамошний LPeg юзают.
http://code.google.com/p/v7lua/
-
Parser Generator for JavaScript (http://pegjs.majda.cz/)
-
The Parsing Expression Grammar Template Library (PEGTL) is a C++0x library for creating parsers according to a Parsing Expression Grammar (PEG). Grammars are embedded as regular C++ code, created with template programming (not template meta programming). These hierarchies naturally correspond to the inductive definition of PEGs. The library extends on the subject of PEGs with new expression types, actions that can be attached to grammar rules, and mechanisms to ensure helpful diagnostics in case of parsing errors. PEGs are superficially similar to Context-Free Grammars (CFGs); for a description see Wikipedia page on PEGs or this paper on PEGs by Bryan Ford.
https://code.google.com/p/pegtl/