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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #30 : Сентябрь 11, 2012, 04:14:28 pm »
В общем виде я понял. Можно где-то почитать про формы записи таких "аналитических грамматик"?
Вот одна из аналитических грамматик написанная сама на себе.
https://github.com/rampelstinskin/ParserGenerator/blob/master/N2/N2.Grammar/GrammarParser2.n2

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #31 : Сентябрь 11, 2012, 04:43:59 pm »
2 chucheloid
Сразу оговорюсь, что не шарю, но в википедии начертано:
Цитировать
...В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью...

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

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #32 : Сентябрь 11, 2012, 04:50:44 pm »
Я это к тому, что автомат строится по порождающей грамматике вроде как...

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

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #33 : Сентябрь 11, 2012, 05:04:10 pm »
Вот одна из аналитических грамматик написанная сама на себе.
https://github.com/rampelstinskin/ParserGenerator/blob/master/N2/N2.Grammar/GrammarParser2.n2

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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #34 : Сентябрь 11, 2012, 05:06:20 pm »
Я это к тому, что автомат строится по порождающей грамматике вроде как...
Я уже отвечал на этот вопрос.
Но отвечу еще раз. Да строится. Но результат получается ну очень хреновым. Использовать его для реальной работы нельзя.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #35 : Сентябрь 11, 2012, 05:07:26 pm »
Еще вот такое нашел:
Категориальная грамматика

Оно?

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #36 : Сентябрь 11, 2012, 05:07:56 pm »
Че-то не работает линка.
Гитхаб похоже лежит. Попробуй позже.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #37 : Сентябрь 11, 2012, 05:13:45 pm »
Но когда мы пишем парсер, у нас нет задачи, сгенерировать все тексты на языке.
У нас есть задача взять строку и сказать принадлежит ли она языку.
Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.

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

chucheloid

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #38 : Сентябрь 11, 2012, 05:28:04 pm »
Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.
Здравствуй капитан очевидность.
Вот только научить всему этому парсер на аналитической грамматике намного проще.
Вон посмотри на тот ужОс в который превращается разбор простейших арифметических выражений.
Там ты не получишь ни нормального АСТ. Ни нормального восстановления после ошибок. Ни нормальных сообщений об ошибках.
Ибо ни один пользователь языка не поймет что term'ы м factor'ами.

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

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #39 : Сентябрь 11, 2012, 06:04:39 pm »
Ну, вообще говоря, обычно от парсера мы хотим несколько бОльшего. Если это часть компилятора - то нам нужно распозновать отдельные конструкции языка, нам нужно восстановление после ошибок, нам нужна точная и внятная диагностика ошибок для прикладного программиста.
Здравствуй капитан очевидность.
Превед!

Вот только научить всему этому парсер на аналитической грамматике намного проще.
Вон посмотри на тот ужОс в который превращается разбор простейших арифметических выражений.
Там ты не получишь ни нормального АСТ. Ни нормального восстановления после ошибок. Ни нормальных сообщений об ошибках.
Ибо ни один пользователь языка не поймет что 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

  • Newbie
  • *
  • Сообщений: 35
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #40 : Сентябрь 11, 2012, 06:19:52 pm »
Но собственно ты пока так и не ответил на вопрос - если у меня есть произвольная порождающая грамматика (в EBNF) всегда ли существует эквивалентная ей (в плане языка) аналитическая грамматика?
Аналитические грамматики бывают разными.
Можно создать и такую что будет полность покрывать языки задаваемые EBNF.
Но на практике всем на это пофиг. Так что обычно аналитические грамматики разбирают свой весьма специфический класс языков.
Например мой парсер может полностью покрывает регулярные грамматики, частично КЗ грамматики и скорей всего все однозначные КС грамматики. А скоро возможно и неоднозначные кушать будет.
Строго математически я это не доказывал. Но разбор реальных языков на нем делать проще, чем на БНФ парсерах.
 
PS. Если ты так высказываешься в сторону АхУльмана, то что же ты скажешь про "Построение Компиляторов" Вирта? ;-)
Не читал. И судя по его языкам, не думаю, что Вирт может написать что-то интересное.

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

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #41 : Сентябрь 11, 2012, 07:03:45 pm »
chucheloid, вы можешь привести пример на пальцах? Мне вот совсем ума не хватает понять чем это будет отличаться от обычных распознающих автоматов.

ps Реально интересно. :)
« Последнее редактирование: Сентябрь 11, 2012, 07:05:37 pm от ilovb »

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Про парсер и лексер.
« Ответ #42 : Сентябрь 11, 2012, 10:03:09 pm »
Еще вот такое нашел:
Категориальная грамматика

Оно?

Я так понимаю, что нихрена не оно...
Ибо:
Цитировать
Теорема о том, что каждый язык, определяемый К-грамматикой является контекстно-свободным (с доказательством)
противоречит:
Например мой парсер может полностью покрывает регулярные грамматики, частично КЗ грамматики и скорей всего все однозначные КС грамматики

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Про парсер и лексер.
« Ответ #43 : Сентябрь 12, 2012, 03:09:21 am »
Гитхаб похоже лежит. Попробуй позже.

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

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

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Про парсер и лексер.
« Ответ #44 : Сентябрь 12, 2012, 08:08:55 am »
Ещё хотелось бы понять какая вообще задача решается?