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

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #60 : Сентябрь 12, 2012, 02:20:28 pm »
Посмотрел. 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-а, что позволило более точно управлять областью значения. А грамматика как была порождающей, так и осталась.

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #61 : Сентябрь 12, 2012, 02:21:37 pm »
Тогда меня только один вопрос интересует. Оно живет вне немерли? И если живет, то где сие чудо можно лицезреть?
Пока нет. Но будет.

ps Ну не шарю я в немерлях, и не расшарюсь в ближайшее время.
Там шарить нечего.

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #62 : Сентябрь 12, 2012, 02:24:29 pm »
По-моему, Вы под лексером что-то слишком частное. Может, просто в вашей команде переосмыслили трансляцию и придумали лексер нового поколения?
По PEG есть много документации в сети.
Покажи мне там лексер.

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #63 : Сентябрь 12, 2012, 02:28:52 pm »
Зачем так оверквотить?
По-моему, вы там у себя просто реализовали аналог BNF-а,
Если оно, похоже, выглядит, то это еще ничего не значит.
Семантика там совершенно другая.

что позволило более точно управлять областью значения.
Чего?

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

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #64 : Сентябрь 12, 2012, 04:55:35 pm »
По PEG есть много документации в сети.
Покажи мне там лексер.
Дело вот в чём: пока программы пишут в обычных текстовых редакторах, которые сохраняют файлы на диск, для трансляции необходимо произвести следующие манипуляции.

1. поток байт (например, из файла) преобразовать в поток букв (грубо говоря).
2. поток букв преобразовать в поток лексем. (лексический анализатор)
3. поток лексем преобразовать в дерево разбора. (синтаксический анализатор)
4. ...

То есть, для работы синтаксического анализатора нужны лексемы. И совсем не важно, запихан ли весь его функционал в файл lexer.src или равномерно размазано по транслятору.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #65 : Сентябрь 12, 2012, 05:37:04 pm »
Если оно, похоже, выглядит, то это еще ничего не значит.
Семантика там совершенно другая.
Но документации-то, которая понятно всё разъясняет, пока нет, поэтому приходится гадать.
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"}]
]

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #66 : Сентябрь 12, 2012, 06:22:53 pm »
1. поток байт (например, из файла) преобразовать в поток букв (грубо говоря).
2. поток букв преобразовать в поток лексем. (лексический анализатор)
3. поток лексем преобразовать в дерево разбора. (синтаксический анализатор)
Так бы сразу и сказал что из секты дракона.
То, что было до букв к синтаксическому анализу вообще не относится.
А для безлексерных парсеров лексемами являются отдельные буквы.

Лексеры вообще говоря нужны только из-за того что быстрые БНФ'ные анализаторы физически не способны разрешать конфликты которые разрешает лексер.
А те, которые способны тормозят, как чёрт знает что.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #67 : Сентябрь 12, 2012, 06:54:02 pm »
Ахо и Ульмана не читал, поэтому не знаю, как они обосновали наличие лексера. А вот в другом источнике его потребовалось ввести потому, что именно парсер не мог разрешить некоторые проблемы.

sum=a1+b3
su m = a 1+ b3
Если работать напрямую с буквами простым способом, то две вышеприведённые строки для парсера окажутся одинаковыми. А если с буквами работать сложным способом, чтобы он различал варианты, то код станет страшным. Правда, здесь стоит учитывать, что весь код парсера должен был по-старинке находиться в одном файле (точнее, в одной компилируемой единице, если принимать во внимание includ-ы).

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #68 : Сентябрь 12, 2012, 07:48:03 pm »
Если работать напрямую с буквами простым способом, то две вышеприведённые строки для парсера окажутся одинаковыми. А если с буквами работать сложным способом, чтобы он различал варианты, то код станет страшным. Правда, здесь стоит учитывать, что весь код парсера должен был по-старинке находиться в одном файле (точнее, в одной компилируемой единице, если принимать во внимание includ-ы).
Это даже не секта дракона. Это что-то неизмеримо более страшное.
Неадекват полнейший.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #69 : Сентябрь 12, 2012, 08:00:30 pm »

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #70 : Сентябрь 12, 2012, 08:35:27 pm »
А вот и определение безлексерности:
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, вы можете сказать в чем конкретно превосходство? Хде профит?

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Про парсер и лексер.
« Ответ #71 : Сентябрь 12, 2012, 09:10:42 pm »
ОК, с этим понятно. Но преимуществ перед лексерным подходом не вижу.
На сколько я понял, они хотят язык в котором лексемы зависят от контекста. Простой лексер с этим не справится, вот и извращаются.

---------

Добавляю свой вопрос: А зачем вам язык с лексемами зависящими от контекста?

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #72 : Сентябрь 12, 2012, 09:47:08 pm »
Добавляю свой вопрос: А зачем вам язык с лексемами зависящими от контекста?
Чтобе легко лепить eDSL'и, очевидно.

Другое дело, что практика показывает, чта-а средний программист не умеет думать еще и о конструировании DSL, даже eDSL не умеет. У него голова занята совсем другим - предметной областью.

Поэтому, после общения с Владиславом Чистяковов (ака VladD2) по поводу Nemerle/N2 и Андреем Бреславом, по поводу Kotlin'a, у меня сложилось четкое мнение, что Kotlin при попутном ветре вполне может взлететь, а вот Nemerle и, тем более, Nemerle-2 - нет.

Хотя мне конечно N2 намного интересней Котлина. Точнее так: N1/N2 мне интересней на поковыряться в алгоритмах, dsl'и понаделать, теорию там с практикой в плане синтаксического разбора почесать (единственное что активно мешает ковырянию - мертвая привязка немерлей к .net'у. Мне довольно сложно найти винды в округе чтобы там немерлю поковырять).

Kotlin интересен с сугубо практической точки зрения (но нужно дождаться стабилизации языка и средств разработки для него). Особенно он мне интересен тем, что у него два бекенда - jvm и js.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #73 : Сентябрь 12, 2012, 09:54:18 pm »
У Вирта короче вполне себе безлексерный парсер  ;D  :P

from valexey: Сори. Вместо того чтобы нажать на цитирование твоего сообщения, нажал на редактирование, и затер нафиг (что мог - восстановил) :-/ Повтори свою мысль пожалуйста.
« Последнее редактирование: Сентябрь 12, 2012, 10:50:21 pm от valexey »

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #74 : Сентябрь 12, 2012, 10:13:15 pm »
Собсна вот тут есть некоторая информация:
Анализаторы для языков, представленных КС-грамматиками, такие как LR-анализаторы, требуют особого шага лексического анализа, который разбивает входные данные в соответствии с пробелами, пунктуацией и так далее. Это необходимо, так как эти анализаторы используют предварительный анализ для обработки некоторых КС-грамматик в линейное время. РВ-грамматики не требуют отдельного шага лексического анализа, а правила для него могут быть заложены вместе с другими правилами грамматики.
Многие КС-грамматики содержат существенные неоднозначности, даже когда они должны описывать однозначные языки. Проблема «висячего else» языков C, C++ и Java является одним из примеров этого явления. Эти проблемы часто разрешаются применением внешнего по отношению к грамматике правила. В РВ-грамматике эти неоднозначности никогда не возникают вследствие приоритезации.