Про парсер и лексер.

[chucheloid]

Стоп. Если там нет "матана" (хотя ясно что матан к грамматикам не имеет отношения), значит ли это, что безлексерный разбор не формализован?

Не значит. И я не сказал что нет. Я сказал что его там не достаточно чтобы написать миллионы статей на тему как на основе языка кроторый описывает генерацию сделать парсерсер.

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

Читай что написано.

Теоритически из генератора можно сделать парсер на практике это работает очень плохо.

Так вот yacc/bison работают очень плохо.

[chucheloid]

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

На весь толмуд там полезного десяток страниц про регулярные выражения и трансформации ДКА. Больше ничего полезного там нет.

[valexey]

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

На весь толмуд там полезного десяток страниц про регулярные выражения и трансформации ДКА. Больше ничего полезного там нет.

Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.

[chucheloid]

Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.

Это вредный алгоритм. Алгоритм парсера должен поддерживать левую рекурсию. Мой поддерживает.

[valexey]

Ну, например из полезного там еще есть алгоритм избавления от левой рекурсии в грамматике.

Это вредный алгоритм.

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

Алгоритм парсера должен поддерживать левую рекурсию. Мой поддерживает.

Где можно прочитать/посмотреть/пощупать?

[chucheloid]

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

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

Где можно прочитать/посмотреть/пощупать?

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

[valexey]

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

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

Если нужно разобрать что-то простое, причем пишешь ты на чем-то вроде Си и работать должно оно на сильно ограниченных ресурсах (реально ограниченных, то есть мегабайт в распоряжении скорее всего не будет), ужель вместо рекурсивного спуска будешь использовать что-то более брутальное?

Где можно прочитать/посмотреть/пощупать?

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

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

[chucheloid]

Если нужно разобрать что-то простое, причем пишешь ты на чем-то вроде Си и работать должно оно на сильно ограниченных ресурсах (реально ограниченных, то есть мегабайт в распоряжении скорее всего не будет), ужель вместо рекурсивного спуска будешь использовать что-то более брутальное?

Так мой алгоритм и есть строго рекурсивный спуск.
Причем рекурсивных вызовов там получается меньше чем в убогом LL(1)... Те мой алгоритм еще и эффективнее.

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

Код: [Выделить]

Expr := Term Expr'
Expr' := "+" Term Expr' | ""
Term := Factor Term'
Term' := "*" Factor Term' | ""
Factor := "(" Expr ")" | Int

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

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

Не помню о чем он говорил.

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

Есть масса способов сделать безлексерные парсеры.
И они работают лучше лексерных.

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

А можно какой-нибудь примерчик, а то не понятно.

[chucheloid]

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

А можно какой-нибудь примерчик, а то не понятно.

А что тут не понятного? Написал using syntax Xml; и у тебя в языке появились XML литаралы.

[valexey]

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

А можно какой-нибудь примерчик, а то не понятно.

А что тут не понятного? Написал using syntax Xml; и у тебя в языке появились XML литаралы.

А если они конфликтуют с другими литералами?

[chucheloid]

А если они конфликтуют с другими литералами?

А что им конфликтовать если они разные?

[vlad]

Так мой алгоритм и есть строго рекурсивный спуск.
Причем рекурсивных вызовов там получается меньше чем в убогом LL(1)... Те мой алгоритм еще и эффективнее.

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

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

[chucheloid]

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

EBNF задает правила генерации всех текстов на данном языке. Она так и называется пораждающая грамматика. Те она пораждает тексты. С теоритической точки зрения она просто создает всё множество текстов, которое принадлежит языку.

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

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

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

[vlad]

Те аналитические грамматики просто по построению подходят для парсеров лучше.

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