Автор Тема: Про парсер и лексер.  (Прочитано 50751 раз)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #45 : Сентябрь 12, 2012, 08:14:47 am »
Можно на маленьком примерчике а-ля "парсинг выражений +,-,*,/" разобрать преимущества аналитической грамматики?
Обычно на маленьких примерчиках преимущества не раскрываются, увидеть их можно в объёмных/сложных случаях. По-крайней мере преимущества ООП, ФП и т.д...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

albobin

  • Full Member
  • ***
  • Сообщений: 198
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #46 : Сентябрь 12, 2012, 09:46:27 am »
Некий товарищ в одной из дискуссий сказал:
"Ты даже не представляешь, какой объем работы по изучению технологий прасинга я проделал.
Я проанализировал кучу научных и практических работ за последние несколько десятилетий.
В результате я взял за основу два разработанных и забытых в середине семидесятых алгоритма.
Я разобрал их по косточкам. После чего соединил их части. Добавил кое-что от себя. И получил очень выразительный ДСЛ для описания парсеров."
Вот указал бы он в открытую, на что он опирается в своей разработке?
Сильно сомневаюсь, но нисколечко не осуждаю.
А ведь это знание многое могло бы прояснить.
:)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #47 : Сентябрь 12, 2012, 10:39:26 am »
Некий товарищ в одной из дискуссий сказал:
"Ты даже не представляешь, какой объем работы по изучению технологий прасинга я проделал.
Я проанализировал кучу научных и практических работ за последние несколько десятилетий.
В результате я взял за основу два разработанных и забытых в середине семидесятых алгоритма.
Я разобрал их по косточкам. После чего соединил их части. Добавил кое-что от себя. И получил очень выразительный ДСЛ для описания парсеров."
Это отсюда: http://eao197.blogspot.com/2012/03/progflame-nemerle2.html?showComment=1333198653688#c4149065481751166467
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #48 : Сентябрь 12, 2012, 11:09:30 am »
Посмотрел. 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 парсер по той страшной грамматике.
Ну и сам факт того что никто не использует БНФ парсеры для промышленных применений, а только для побаловаться (максимум для внутренних проектов) наводит на мысли.

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #49 : Сентябрь 12, 2012, 11:11:12 am »
Обычно на маленьких примерчиках преимущества не раскрываются, увидеть их можно в объёмных/сложных случаях. По-крайней мере преимущества ООП, ФП и т.д...
В данном случае раскрывается даже на маленьких примерчиках...

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #50 : Сентябрь 12, 2012, 11:19:46 am »
Вот указал бы он в открытую, на что он опирается в своей разработке?
Сильно сомневаюсь, но нисколечко не осуждаю.
А ведь это знание многое могло бы прояснить.
:)
TDPL/PEG и TDOP
Много тебе это сказало?
Вижу как побежал в гугл выяснять что это такое. :)

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #51 : Сентябрь 12, 2012, 11:20:52 am »
Ещё хотелось бы понять какая вообще задача решается?
Тотальное уничтожение "синтаксического оверхеда (С)".

albobin

  • Full Member
  • ***
  • Сообщений: 198
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #52 : Сентябрь 12, 2012, 11:40:41 am »
Много тебе это сказало?
Вижу как побежал в гугл выяснять что это такое. :)
[/quote]
Вот это - достаточно :)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #53 : Сентябрь 12, 2012, 11:44:38 am »
Некий товарищ в одной из дискуссий сказал:
"Ты даже не представляешь, какой объем работы по изучению технологий прасинга я проделал.
Я проанализировал кучу научных и практических работ за последние несколько десятилетий.
В результате я взял за основу два разработанных и забытых в середине семидесятых алгоритма.
Я разобрал их по косточкам. После чего соединил их части. Добавил кое-что от себя. И получил очень выразительный ДСЛ для описания парсеров."

Брайен Форд, в русских блогах тусит?  ;)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #54 : Сентябрь 12, 2012, 11:46:23 am »
Собсна вот:
Цитировать
Относительно недавно появилась работа некоего Брайена Форда (Bryan Ford), посвященная его алгоритму, названному "packrat parsing". Он вытащил на свет формализм, разработанный около 30 лет назад, и описывавший парсер, использующий алгоритм нисходящего спуска с откатами (Top-Down Parsing Language, TDPL).
http://www.k-press.ru/cs/2010/2/Editorial/Editorial.asp

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #55 : Сентябрь 12, 2012, 11:51:00 am »
Ну и сама работа до кучи:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.1175

ps Индекс цитирования забавно выглядит :)
« Последнее редактирование: Сентябрь 12, 2012, 11:52:59 am от ilovb »

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #56 : Сентябрь 12, 2012, 11:57:43 am »
TDOP тоже нашел:
http://cat.hansa-flex.com/ru/pdf/906451
Цитировать
надеть прорезиненной стороной на выступ
поршневого штока и зафиксировать с
помощью шайбы и гайки

Так просто!?!?  ;D ;D ;D

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #57 : Сентябрь 12, 2012, 11:59:12 am »
http://www.k-press.ru/cs/2010/2/Editorial/Editorial.asp
1)На чистом ПЕГ писать грамматики довольно сложно.
2)Пакрат жуткий тормоз.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #58 : Сентябрь 12, 2012, 12:03:56 pm »
Тогда меня только один вопрос интересует. Оно живет вне немерли? И если живет, то где сие чудо можно лицезреть?

ps Ну не шарю я в немерлях, и не расшарюсь в ближайшее время.
« Последнее редактирование: Сентябрь 12, 2012, 12:05:57 pm от ilovb »

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #59 : Сентябрь 12, 2012, 12:31:42 pm »
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.
По-моему, Вы под лексером что-то слишком частное. Может, просто в вашей команде переосмыслили трансляцию и придумали лексер нового поколения?