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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #15 : Сентябрь 11, 2012, 11:49:18 am »
Стоп. Если там нет "матана" (хотя ясно что матан к грамматикам не имеет отношения), значит ли это, что безлексерный разбор не формализован?
Не значит. И я не сказал что нет. Я сказал что его там не достаточно чтобы написать миллионы статей на тему как на основе языка кроторый описывает генерацию сделать парсерсер.

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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #16 : Сентябрь 11, 2012, 11:56:07 am »
А по тему - в АхУльмане многого (из по крайней мере актуального-современного) нет. Но и многое есть. Как справочник он хорош. Только не надо им ограничиваться.
На весь толмуд там полезного десяток страниц про регулярные выражения и трансформации ДКА. Больше ничего полезного там нет.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #17 : Сентябрь 11, 2012, 11:57:06 am »
А по тему - в АхУльмане многого (из по крайней мере актуального-современного) нет. Но и многое есть. Как справочник он хорош. Только не надо им ограничиваться.
На весь толмуд там полезного десяток страниц про регулярные выражения и трансформации ДКА. Больше ничего полезного там нет.
Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #18 : Сентябрь 11, 2012, 12:16:11 pm »
Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.
Это вредный алгоритм. Алгоритм парсера должен поддерживать левую рекурсию. Мой поддерживает.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #19 : Сентябрь 11, 2012, 12:18:20 pm »
Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.
Это вредный алгоритм.

Иногда полезный.

Алгоритм парсера должен поддерживать левую рекурсию. Мой поддерживает.
Где можно прочитать/посмотреть/пощупать?
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #20 : Сентябрь 11, 2012, 12:25:33 pm »
Иногда полезный.
Только если занимаешься онанизмом (более мягкое слово подобрать не могу) с алгоритмами, которые пытаются делать парсер, по языку который описывает генератор.

Где можно прочитать/посмотреть/пощупать?
https://github.com/rampelstinskin/ParserGenerator
Это устаревшая версия. Сейчас, в пока закрытом режиме, идут работы по доведению её до промышленного качества.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #21 : Сентябрь 11, 2012, 12:40:46 pm »
Иногда полезный.
Только если занимаешься онанизмом (более мягкое слово подобрать не могу) с алгоритмами, которые пытаются делать парсер, по языку который описывает генератор.
Если нужно разобрать что-то простое, причем пишешь ты на чем-то вроде Си и работать должно оно на сильно ограниченных ресурсах (реально ограниченных, то есть мегабайт в распоряжении скорее всего не будет), ужель вместо рекурсивного спуска будешь использовать что-то более брутальное?

Где можно прочитать/посмотреть/пощупать?
https://github.com/rampelstinskin/ParserGenerator
Это устаревшая версия. Сейчас, в пока закрытом режиме, идут работы по доведению её до промышленного качества.
Это тот самый парсер про который говорил VladD2 на Application Developer Days-3 (в своем долгом спиче про Nemerle-2)?
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #22 : Сентябрь 11, 2012, 01:53:23 pm »
Если нужно разобрать что-то простое, причем пишешь ты на чем-то вроде Си и работать должно оно на сильно ограниченных ресурсах (реально ограниченных, то есть мегабайт в распоряжении скорее всего не будет), ужель вместо рекурсивного спуска будешь использовать что-то более брутальное?
Так мой алгоритм и есть строго рекурсивный спуск.
Причем рекурсивных вызовов там получается меньше чем в убогом LL(1)... Те мой алгоритм еще и эффективнее.

А всё по тому, что мне не нужен онанизм типа такого:
Expr := Term Expr'
Expr' := "+" Term Expr' | ""
Term := Factor Term'
Term' := "*" Factor Term' | ""
Factor := "(" Expr ")" | Int

И дерево разбора получается сразу таким, каким нужно без всякого мусора и нужной формы. С нужной ассоциативностью.
Можно сразу использовать.
И это очень круто я считаю.

Это тот самый парсер про который говорил VladD2 на Application Developer Days-3 (в своем долгом спиче про Nemerle-2)?
Не помню о чем он говорил.

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

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Про парсер и лексер.
« Ответ #23 : Сентябрь 11, 2012, 03:02:02 pm »
Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.

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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #24 : Сентябрь 11, 2012, 03:14:55 pm »
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А можно какой-нибудь примерчик, а то не понятно.
А что тут не понятного? Написал using syntax Xml; и у тебя в языке появились XML литаралы.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #25 : Сентябрь 11, 2012, 03:18:13 pm »
А если делать парсер который может изменять свою грамматику во время разбора текста (чем я и занимаюсь) то он может быть только безлексерным.
А можно какой-нибудь примерчик, а то не понятно.
А что тут не понятного? Написал using syntax Xml; и у тебя в языке появились XML литаралы.
А если они конфликтуют с другими литералами?
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #26 : Сентябрь 11, 2012, 03:46:48 pm »
А если они конфликтуют с другими литералами?
А что им конфликтовать если они разные?

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #27 : Сентябрь 11, 2012, 03:49:26 pm »
Так мой алгоритм и есть строго рекурсивный спуск.
Причем рекурсивных вызовов там получается меньше чем в убогом LL(1)... Те мой алгоритм еще и эффективнее.

А всё по тому, что мне не нужен онанизм типа такого:

А можно подробнее если не про алгоритм, то хотя бы про альтернативу EBNF? Кроме ссылок в википедию и на исходники.

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #28 : Сентябрь 11, 2012, 04:00:48 pm »
А можно подробнее если не про алгоритм, то хотя бы про альтернативу EBNF? Кроме ссылок в википедию и на исходники.
EBNF задает правила генерации всех текстов на данном языке. Она так и называется пораждающая грамматика. Те она пораждает тексты. С теоритической точки зрения она просто создает всё множество текстов, которое принадлежит языку.

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

Таким образом, идя с двух разных сторон, мы получаем одно и то же множество текстов.

Но когда мы пишем парсер, у нас нет задачи, сгенерировать все тексты на языке.
У нас есть задача взять строку и сказать принадлежит ли она языку.
Те аналитические грамматики просто по построению подходят для парсеров лучше.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #29 : Сентябрь 11, 2012, 04:07:08 pm »
Те аналитические грамматики просто по построению подходят для парсеров лучше.

В общем виде я понял. Можно где-то почитать про формы записи таких "аналитических грамматик"?