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

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Про парсер и лексер.
« : Сентябрь 09, 2012, 06:22:23 pm »
Я не поленился и нашел этот шедевр:
...
Я как-то писал здесь http://forum.oberoncore.ru/viewtopic.php?p=69811#p69811 про смесь из лексического и синтаксического разбора
Цитировать
Мне многократно приходилось писать "наколеночные" решения для разбора каких-нибудь данных. Почти всегда возникал соблазн схалтурить, не делать отдельный лексический разбор. В 100% случаев это приводило к тому, что в итоге получалась какая-то дрянь.

"Шестиветочный цикл" Info21 - прекрасная иллюстрация.

Я тоже думал об этом. Ну и немного шишек понабивал самостоятельно, так что подтверждаю.

Galkov, помнится очень хорошо объяснял почему требуется разделять парсер и лексер (за что был неоднократно гнобим на оборонкоре) - они банально работают по разным принципам. Обычный LL(с)-парсер не сможет разбить входной поток на лексемы. Какой-нибудь LALR - тоже. Я подозреваю что с задачей сможет справиться GLR и/или GLL парсер, но это будет не эффективно (ну и не факт что получится - я еще не прорабатывал эту тему).

PS. Справится/не справится - имеется ввиду, что это честный парсер, работающий по полностью формализованной грамматике и ничего кроме нее не знающий. А не так как работает например виртовский парсер Оберона.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #1 : Сентябрь 10, 2012, 06:09:52 pm »
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.

А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #2 : Сентябрь 10, 2012, 06:17:13 pm »
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.

Звучит страшно. Это что-то типа жабаскриптового "use strict"? https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Functions_and_function_scope/Strict_mode?redirectlocale=en-US&redirectslug=JavaScript%2FStrict_mode
Или есть более приличные применения такому?

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #3 : Сентябрь 10, 2012, 06:31:20 pm »
Конечно, есть. Можно, например новые конструкции не хардкодить в язык, а складывать в библиотеки.
И тогда люди могут добавлять расширения в язык, не дожидаясь пока автор языка его сделает.
Более того если расширяется основной язык то расширение появляется сразу у всех, а в случае библиотечных расширений языка пользователи могут выбирать какие расширения использовать.
Грамотное языковое расширение может уменьшить код в разы. А в особо запущенных случаях в десятки, а иногда и сотни раз.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #4 : Сентябрь 10, 2012, 07:03:25 pm »
Конечно, есть. Можно, например новые конструкции не хардкодить в язык, а складывать в библиотеки.
И тогда люди могут добавлять расширения в язык, не дожидаясь пока автор языка его сделает.
Более того если расширяется основной язык то расширение появляется сразу у всех, а в случае библиотечных расширений языка пользователи могут выбирать какие расширения использовать.
Грамотное языковое расширение может уменьшить код в разы. А в особо запущенных случаях в десятки, а иногда и сотни раз.

В топике запахло немерлёй :-)
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #5 : Сентябрь 10, 2012, 07:54:10 pm »
В топике запахло немерлёй :-)

Или это лисп? :)

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #6 : Сентябрь 10, 2012, 08:30:09 pm »
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.

А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А где можно прочитать про эту самую массу способов? Какие-то книжки/статейки имеются? А то в АхУльмане вроде бы ничего нет (собственно там даже про glr/gll нет).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #7 : Сентябрь 10, 2012, 08:31:10 pm »
Ну вот куда Пётр Алмазов делся? Он же скептически относится к макросам, вот было бы ему с кем их обсудить, а то больше тут никто их не умеет готовить ))
to iterate is human, to recurse, divine

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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #8 : Сентябрь 11, 2012, 09:48:14 am »
Цитировать
А где можно прочитать про эту самую массу способов? Какие-то книжки/статейки имеются? А то в АхУльмане вроде бы ничего нет (собственно там даже про glr/gll нет).
Найти такие статьи довольно проблематично. Они мне периодически попадаются на глаза, но их очень трудно гуглить и ссылку я так сразу не вспомню.
Из-за того что в безлексерных парсерах слишком мало матана на них трудно защищать диссеры. Вот про них учёные и забыли.
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Еще советую держаться подальше от слов BNF/EBNF ибо они задают способ генерации текста. А нам нужен разбор. Теоритически из генератора можно сделать парсер на практике это работает очень плохо.
Нужно копать в сторону аналитических грамматик.
http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #9 : Сентябрь 11, 2012, 10:02:37 am »
Из-за того что в безлексерных парсерах слишком мало матана на них трудно защищать диссеры. Вот про них учёные и забыли.
Стоп. Если там нет "матана" (хотя ясно что матан к грамматикам не имеет отношения), значит ли это, что безлексерный разбор не формализован?

А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).

Еще советую держаться подальше от слов BNF/EBNF ибо они задают способ генерации текста. А нам нужен разбор. Теоритически из генератора можно сделать парсер на практике это работает очень плохо.
То есть yacc/bison это таки генераторы текстов? ;-) Потому как формализм которым задается грамматика для разбора yacc'ом по сути является диалектом BNF.

Нужно копать в сторону аналитических грамматик.
http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars
Спасибо. Посмотрю еще раз.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #10 : Сентябрь 11, 2012, 10:09:44 am »
Нужно копать в сторону аналитических грамматик.
http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars

Да, и вопрос в догонку: если у меня уже есть грамматика заданная в (E)BNF, всегда ли возможно её переформулировать "без потерь" в терминах скажем PEG?

То есть какие из переходов возможны:
a) (E)BNF => PEG
b) PEG => (E)BNF
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Fktrc

  • Newbie
  • *
  • Сообщений: 9
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #11 : Сентябрь 11, 2012, 10:10:36 am »
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Речь о другом драконе ( http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы) ), видимо :)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #12 : Сентябрь 11, 2012, 10:11:59 am »
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Он имел в виду вот эту "книгу дракона":
to iterate is human, to recurse, divine

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

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #13 : Сентябрь 11, 2012, 10:14:13 am »
А от секты дракона нужно держаться подальше. Они не умеют писать компиляторы. Ради развлечения попробуйте найти промышленный компилятор, написанный по книге дракона... Не найдете.
Драконоиды вообще к компиляторам никакого отношения вроде бы не имеют :-) Да и не нужен мне дракон для моих задач (а потому и не интересен).
Речь о другом драконе ( http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы) ), видимо :)
Спасибо что обозначил правильный контекст, а то я до сих пор под впечатлением от секты другого Дракона :-)

А по тему - в АхУльмане многого (из по крайней мере актуального-современного) нет. Но и многое есть. Как справочник он хорош. Только не надо им ограничиваться.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #14 : Сентябрь 11, 2012, 11:43:20 am »
Ну вот куда Пётр Алмазов делся? Он же скептически относится к макросам, вот было бы ему с кем их обсудить, а то больше тут никто их не умеет готовить ))
Он может мне рассказать о макросах что-то, что я не знаю? Если нет, то разговор с ним не имеет смысла.
Ибо я уже знаю всё, что говорят скептики. Весь их скептицизм основан на мифах, не имеющих ничего общего с реальностью.