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

[chucheloid]

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

Вот одна из аналитических грамматик написанная сама на себе.
https://github.com/rampelstinskin/ParserGenerator/blob/master/N2/N2.Grammar/GrammarParser2.n2

[ilovb]

2 chucheloid
Сразу оговорюсь, что не шарю, но в википедии начертано:

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

Речь об распознающих автоматах?

[ilovb]

Я это к тому, что автомат строится по порождающей грамматике вроде как...

Поправьте если ошибаюсь.

[vlad]

Вот одна из аналитических грамматик написанная сама на себе.
https://github.com/rampelstinskin/ParserGenerator/blob/master/N2/N2.Grammar/GrammarParser2.n2

Че-то не работает линка.

[chucheloid]

Я это к тому, что автомат строится по порождающей грамматике вроде как...

Я уже отвечал на этот вопрос.
Но отвечу еще раз. Да строится. Но результат получается ну очень хреновым. Использовать его для реальной работы нельзя.

[ilovb]

Еще вот такое нашел:
Категориальная грамматика

Оно?

[chucheloid]

Че-то не работает линка.

Гитхаб похоже лежит. Попробуй позже.

[valexey]

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

Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.

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

[chucheloid]

Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.

Здравствуй капитан очевидность.
Вот только научить всему этому парсер на аналитической грамматике намного проще.
Вон посмотри на тот ужОс в который превращается разбор простейших арифметических выражений.
Там ты не получишь ни нормального АСТ. Ни нормального восстановления после ошибок. Ни нормальных сообщений об ошибках.
Ибо ни один пользователь языка не поймет что term'ы м factor'ами.

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

Ессно опускают. Ибо сделать это качественно для порождающих грамматик задача не реальная. Вот и не хотят позориться.

[valexey]

Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.

Здравствуй капитан очевидность.

Превед!

Вот только научить всему этому парсер на аналитической грамматике намного проще.
Вон посмотри на тот ужОс в который превращается разбор простейших арифметических выражений.
Там ты не получишь ни нормального АСТ. Ни нормального восстановления после ошибок. Ни нормальных сообщений об ошибках.
Ибо ни один пользователь языка не поймет что term'ы м factor'ами.

Дык уже (не понял):

[00:16:51] <vlad2> А вот как расшифровывается "term" применительно к примерам всяких грамматик?
[00:38:11] <valexеy> vlad2: terminal ?
[00:38:25] <valexеy> там есть терминалы и нетерминалы
[00:38:31] <valexеy> а еще бывают лексемы
[00:38:39] <valexеy> ну и правила вывода
[00:38:41] <valexеy> вроде бы все.
[00:38:46] <valexеy> больше ничего там нет
[00:38:54] <valexеy> а, ну еще аксиома грамматики.
[00:38:57] <valexеy> теперь точно все :-)
[00:39:14] <vlad2> Не, не терминал.
[00:39:43] <vlad2> Пытаюсь сочинить EBNF. Пока глухо.
[00:41:10] <valexеy> Э? А чо там сочинять то?
[00:41:58] <valexеy> откуда ты вообще этот терм выкопал?
[00:42:01] <valexеy> давай контекст
[00:44:30] <valexеy> Терм — кормовая единица, выражаемая в количестве «чистой», или физиологически полезной животному, энергии. В США один терм приравнен к 1 Мкал.
[00:44:38] <valexеy> :-)
[00:47:38] <vlad2> Терм во всяких примерах. Вобщем избавился я от него
[00:47:49] <vlad2> Сочиняю грамматику для выражений.
[00:47:55] <vlad2> Вроде получилось.
[00:48:40] <valexеy> В каких это примерах?
[00:49:07] <vlad2> Например, в Compiler Construction
[00:49:23] <valexеy> В переводном или в исходном?
[00:49:50] <vlad2> syntax = {production}.
production = identifier "=" expression "." .
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
[00:49:56] <vlad2> В исходном, конечно.
[00:50:00] <vlad2> Вот что тут term?
[00:50:05] <valexеy> а, ну это ж тупо так один из нетерминалов назван
[00:50:12] <valexеy> term = factor {factor}.
[00:50:17] <vlad2> _Почему_ так?
[00:50:19] <valexеy> очевидно же :-)
[00:50:22] <vlad2> Как переводится то?
[00:50:26] <valexеy> Потому что так захотелось создателю :-)
[00:50:36] <valexеy> У меня сестра их вообще называет навроде A12
[00:50:38] <valexеy> :-)
[00:50:45] <vlad2> просто оно реально confusing с терминалами нетерминалами.
[00:51:02] <valexеy> ну, блин. это ж Вирт! :-)
[00:51:26] <vlad2> Кстати, если попробуешь представить себе этот синтаксис - тоже фигня какая-то поулучается.
[00:52:40] <valexеy> нихачу представлять!
[00:52:52] <vlad2> factor {factor} превращается в последовательность всякой херни (без операторов). К чему такой пример?
[00:54:00] <valexеy> К тому, что Вирт там избавлялся от левой рекурсии (на которой рекурсивный спуск, да и вообще почти любой парсер который идет сверху-вниз, кроме GLL, сдохнет).
[00:55:05] <valexеy> Это стандартный прием ухода от левой рекурсии, в ахульмане он описан.
[00:55:36] <valexеy> А у Вирта, НЕ описан. Ибо грамматикам он не учит. А учит по готовой Им даденой грамматике строить компилятор одного вида :-)

Ессно опускают. Ибо сделать это качественно для порождающих грамматик задача не реальная. Вот и не хотят позориться.

Но собственно ты пока так и не ответил на вопрос - если у меня есть произвольная порождающая грамматика (в EBNF) всегда ли существует эквивалентная ей (в плане языка) аналитическая грамматика?

PS. Если ты так высказываешься в сторону АхУльмана, то что же ты скажешь про "Построение Компиляторов" Вирта? ;-)

[chucheloid]

Но собственно ты пока так и не ответил на вопрос - если у меня есть произвольная порождающая грамматика (в EBNF) всегда ли существует эквивалентная ей (в плане языка) аналитическая грамматика?

Аналитические грамматики бывают разными.
Можно создать и такую что будет полность покрывать языки задаваемые EBNF.
Но на практике всем на это пофиг. Так что обычно аналитические грамматики разбирают свой весьма специфический класс языков.
Например мой парсер может полностью покрывает регулярные грамматики, частично КЗ грамматики и скорей всего все однозначные КС грамматики. А скоро возможно и неоднозначные кушать будет.
Строго математически я это не доказывал. Но разбор реальных языков на нем делать проще, чем на БНФ парсерах.
 

PS. Если ты так высказываешься в сторону АхУльмана, то что же ты скажешь про "Построение Компиляторов" Вирта? ;-)

Не читал. И судя по его языкам, не думаю, что Вирт может написать что-то интересное.

Да ты и сам пишешь что:

А у Вирта, НЕ описан. Ибо грамматикам он не учит. А учит по готовой Им даденой грамматике строить компилятор одного вида :-)

[ilovb]

chucheloid, вы можешь привести пример на пальцах? Мне вот совсем ума не хватает понять чем это будет отличаться от обычных распознающих автоматов.

ps Реально интересно.

[ilovb]

Еще вот такое нашел:
Категориальная грамматика

Оно?

Я так понимаю, что нихрена не оно...
Ибо:

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

противоречит:

Например мой парсер может полностью покрывает регулярные грамматики, частично КЗ грамматики и скорей всего все однозначные КС грамматики

[vlad]

Гитхаб похоже лежит. Попробуй позже.

Посмотрел. DSL такой DSL. Все классно. Но непонятно Можно на маленьком примерчике а-ля "парсинг выражений +,-,*,/" разобрать преимущества аналитической грамматики?

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

Ещё хотелось бы понять какая вообще задача решается?