OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 00:30

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 9  След.
Автор Сообщение
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 16:11 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Здесь слово сканер - это моя отсебятина, классик (Galkov) говорил "лексика".
Я этим словом обозначил, что речь идет о синтаксисе для сканера, а не для парсера.
Так что речь идет именно о теории, а не о конкретном сканере.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 16:25 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Peter Almazov писал(а):
Здесь слово сканер - это моя отсебятина, классик (Galkov) говорил "лексика".
Я этим словом обозначил, что речь идет о синтаксисе для сканера, а не для парсера.
Так что речь идет именно о теории, а не о конкретном сканере.
Хм... Интересно.

Тогда можно говорить о двух эквивалентных лексиках языка. Одна - это та, которая описана в "Сообщении о языке". А другая - та, по которой "шпарит" конкретный сканер.

Относительно лексики, которая в сканере, похоже разногласий нет, и все согласны, что она там детерминированная.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 19:19 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Сергей Оборотов писал(а):
В общем случае - нет. Где он об этом сказал?
Если я еще не потерял мысль в этом тасовании колоды постов, то речь идет о том, что Вирт не сказал, что регулярные языки являются обязательно детерминированными.
Правильно ???
Да, не сказал. Но мне представляется более значительным, что он не сказал и обратного (что в общем случае - нет). Тут, правда, я могу говорить лишь о русском варианте, но который читал очень внимательно.
Поставьте себя на место студизо, который первый раз, и именно здесь, прочитал определение регулярного синтаксиса.
Будет ли у него правильное понимание после прочтения ???
Мне кажется - не факт. Про себя скажу: по первому разу запутался. Азы читал давно, а по жизни меня больше интересует генерация кода из графической схемы, чем из текста. Не, ну вспомнил, конечно же. Но у меня таки была первичная подготовка, а каково бедному студиозо ??? :)


Сергей Оборотов писал(а):
Вообще-то понятно что имелось в виду, но сказано коряво.
Ну вот, уже более конкретно.
Сергей, мне непонятно, в чем заключается корявость. Поясните пожалуйста. Или как это должно сказать не коряво...
Пока мне кажется все нормальным. Если, конечно у нас одинаковое понимание термина "лексика"
Но именно это и есть предмет обсуждение в топике. Как мне кажется... Несмотря на его сегодняшнее название


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 19:42 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
igor писал(а):
Относительно лексики, которая в сканере, похоже разногласий нет, и все согласны, что она там детерминированная
Ну если все согласны, тогда у меня ко всем абсолютно конкретное предложение - проверить правила Вирта для следующего синтаксиса (это из упражнения 4.2, с исправлением опечаток)
Код:
   syntax   = {production}.
   production   = id "=" expression ".".
   expression   = term {"|" term}.
   term      = factor {factor}.
   factor   = id | string | "(" expression ")" | "[" expression "]"
                          | "{" expression "}".
   id      = letter {letter | digit}.
   string   = """ {character} """.
- в конце концов, почему я один должен бодаться за правду.

Здесь лексика не выделена, а включена в синтаксис. Если она детерминирована, значит правила Вирта для этого синтаксиса выполняются.
Вопрос даже не в моем мнении: выполняются или нет - это просто медицинский факт. Для установления которого надо просто уметь считать.
Я умею (настаиваю на этом) - не выполняются.

Поскольку я уже немного устал, то деликатничать не буду: у кого не выполнится, тот не умеет считать.
Скажу даже еще менее деликатно: я могу допустить такие пенки в упражнении - типа пусть студиозо помучается, умнее станет. Но ведь те же пенки в Приложениях А1 и А2.
И считаю это не совсем допустимым. Точнее - совсем недопустимым

Вот Вам и весь сказ :evil:


Последний раз редактировалось Galkov Воскресенье, 31 Январь, 2010 21:56, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 20:52 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Galkov писал(а):
Код:
expression   = term {" " term}.
Что-то я не понял про опечатки, а книги нет под рукой. Может все-таки как в оригинале:
expression = term {"|" term}.
?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 21:55 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Спасибо коллега, в книге эта строчка правильно нарисована.
Там в строке factor аналогичные "пропуски палок"
А я скопировал (и поправил factor) из Упражнения.txt на диске. И попался :)
((выше поправил))


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 23:14 

Зарегистрирован: Вторник, 29 Ноябрь, 2005 21:41
Сообщения: 1030
Galkov писал(а):
Правильно ???
Да, не сказал. Но мне представляется более значительным, что он не сказал и обратного (что в общем случае - нет). Тут, правда, я могу говорить лишь о русском варианте, но который читал очень внимательно.
Поставьте себя на место студизо, который первый раз, и именно здесь, прочитал определение регулярного синтаксиса.
Будет ли у него правильное понимание после прочтения ???

Да, правильно. Если это написано в "Конструировании компиляторов" и получилось сделать у Вирта то может получиться и у студента, который будет это пособие читать. Как-то так.
Galkov писал(а):
Сергей, мне непонятно, в чем заключается корявость. Поясните пожалуйста. Или как это должно сказать не коряво...
Пока мне кажется все нормальным. Если, конечно у нас одинаковое понимание термина "лексика"
Но именно это и есть предмет обсуждение в топике. Как мне кажется... Несмотря на его сегодняшнее название
Нет, не одинаковое. Лексика - следствие определения, а недетерминированность - конструирования.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 07:21 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Galkov писал(а):
igor писал(а):
Относительно лексики, которая в сканере, похоже разногласий нет, и все согласны, что она там детерминированная
Ну если все согласны, тогда у меня ко всем абсолютно конкретное предложение - проверить правила Вирта для следующего синтаксиса (это из упражнения 4.2, с исправлением опечаток)
В сканере такой лексики нет! Откройте в Блэкбокс модуль DevCPS, найдите в нём процедуру Get, и по ней и проверяйте правила Вирта для "лексики, которая в сканере".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 08:17 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
И причем здесь за рыбу деньги :?:
Есть упражнение, в котором написано:
Цитата:
Определить множества символов FIRST и FOLLOW для конструкций РБНФ production, expression, term и factor. Используя эти множества, проверить, что РБНФ является детерминированной.

Проверить-то можно, или нельзя :?:
В конце концов, упражнения даются, чтобы их делать. Вот я - сделал, А Вы - нет. Но при этом Вы мне говорите, что это я говорю ерунду про недетерминированность.
А по моему, так - наоборот.

Кто-то разве говорит, что некие коды сделаны неправильно :?:
Чего Вы так распереживались, непойму. Как будто, сказавши НКА, отобрали тем самым веру в Деда Мороза.
Нормальные коды. Просто сделаны они не совсем из тех правил, которые даны Виртом для детерминированного синтаксиса.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 10:01 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Galkov писал(а):
В конце концов, упражнения даются, чтобы их делать. Вот я - сделал, А Вы - нет.
Всё! Иду выполнять Ваше предписание. :)
Вечерком отпишусь (постараюсь).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 13:36 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Не нашел там никакой недетерминированности. Причем, все упрощается тем, что ни одна конструкция (кроме самой верхней) не может породить пустую последовательность.
Надо "сверить часы" - где там недерминированность?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 14:04 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Ну давайте, попробуем.
С igor вот не получилось (хотя я еще не теряю надежды), потому что у нас разное понимание основы по фамилии patern matching. Вот он вроде говорит "что-то в этом есть" - но это же не может быть базой для дальнейшего продвижения... А он молчит :)

Щаз. С пол-часика уйдет наверное...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 14:06 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Цитата:
Определить множества символов FIRST и FOLLOW для конструкций РБНФ production, expression, term и factor. Используя эти множества, проверить, что РБНФ является детерминированной.


FIRST(id) = char, FOLLOW(id) = char | digit.
FIRST(string) = <">, FOLLOW(string) = char | <">.

У нетерминалов, естественно, FIRST() нет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 14:29 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
1) Нетерминал id. Проверяем правило 3 для "повторения". Для этого необходимо, чтобы FIRST(letter|digit) непересекался с FOLLOW(id)

2) Ищем вхождения id в синтаксис - это только нетерминал factor. Из чего делаем заключение, что FOLLOW(id)=FOLLOW(factor).

3) Ищем вхождение factor в синтаксис - это нетерминал term. Первое вхождение factor в term говорит о том, что FOLLOW(factor)=FIRST(factor)+FOLLOW(term). Второе слагаемое возникло от применения правила 2, ибо FIRST({factor}) содержит в себе пустышку.

4) Можно не анализировать далее второе вхождение factor в term, и FOLLOW(term) - они только расширят множество FOLLOW(factor). Вполне достаточно уже того, что FIRST(factor)=FIRST(ident)+"""+"("+"["+"{" и FIRST(letter|digit) - пересекаются
Ну и все, типа - кердык

Просьба критиковать. Желательно не все сразу, а по отдельным утверждениям. А я буду сопротивляться :)
Да, вот: плюсик я тут употреблял как обединение множеств...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 15:12 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
А разве id - нетерминал? Чёрт, забыл.
Galkov писал(а):
2) Ищем вхождения id в синтаксис - это только нетерминал factor. Из чего делаем заключение, что FOLLOW(id)=FOLLOW(factor).
Приравнивать входные сиволы нельзя. Просто, factor - это другой Уровень. Его входными элементами являются сами id. Целиком, а не его составляющие.

Возможно, я выразился слишком туманно, поэтому воспользуюсь аналогией.

В хлебный магазин утром специальная машина привозит хлеб. Буханки переносят в магазин и время от времени подкладывают на полки. Все довольны. И так будет длиться до тех пор, пока машина привозит хлеб, а не его составляющие. Магазинщикам будет далеко не весело, если в фургоне обнаружится гора злаков, политая маслом и перемешанная с солью.

Аналогия про недетерминированность. Если разложить в порядке убывания массовых долей ингредиенты кекса и чёрного хлеба, то получится, что и там, и там первое место занимает мука (FIRST(id)). Но этот факт нам не мешает в магазине отличить первое от второго. А всё потому, что магазин (factor) принимает уже готовые кексы и хлеб (id).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 15:59 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
igor писал(а):
Вечерком отпишусь (постараюсь).
Выполняю обещанное.

Итак, разбираем упражнение 4.2 из книги Вирта.

Множество абстрактных терминальных символов:
{id, string, "=", ".", "|", "(", ")", "[", "]", "{", "}"}

Множество нетерминальных символов:
{syntax, production, expression, term, factor}

FIRST(production) = {id}
FOLLOW(production) = {id, string, "=", ".", "|", "(", ")", "[", "]", "{", "}"}

FIRST(expression) = {id, string, "(", "[", "{"}
FOLLOW(expression) = {id, string, "|", "(", ")", "[", "]", "{", "}"}

FIRST(term) = FIRST(expression)
FOLLOW(term) = FOLLOW(expression)

FIRST(factor) = FIRST(term)
FOLLOW(factor) = FOLLOW(term)

Ну, а теперь множество моих комментариев: :)

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

2. Раз мы перешли к рассмотрению абстрактных терминальных символов, то забудьте про letter, digit и прочую лексику. Терминальные символы (абстрактные или элементарные) рассматриваются как неделимые. На всякий случай перечитайте страницу 30, где Вирт говорит о двух этапах определения синтаксиса.

3. Никаких нарушений условий детерминированности в примере 4.2 я не обнаружил. Да, множество FIRST для приведённых нетерминалов пересекаются. Ну и что? Никакого криминала в этом нет.

Попробую последний пункт пояснить. Рассмотрим для определённости нетерминалы production и factor. И тот, и другой может начинаться с терминала id. Но в приведённом синтаксисе нигде не встречается конструкция вида K = term0 | term1, в которой production и factor выступали бы в роли term0 и term1, соответственно. То же самое можно сказать про конструкцию вида K = fac0 fac1 и про любую пару нетерминалов.

А теперь я жду объяснений. В чём был прикол?
Я серьёзно. Может я смотрю на всё это уже замыленными глазами и не вижу очевидное.
Прошу тогда помочь мне увидеть это нарушение условия детерминированности.

PS: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить.


Последний раз редактировалось igor Понедельник, 01 Февраль, 2010 19:56, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 16:24 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
igor писал(а):
1. Так как в правых частях продукций есть нетерминалы, то этот синтаксис относится уже к классу контекстно-свободных языков, а не регулярных. Здесь мы несколько отошли от темы топика, но я думаю, что это не страшно, можно продолжить обсуждение в этой теме (на усмотрение модераторов).
В правой части автоматной грамматики может содержаться нетерминал. Самое главное, чтобы это был не тот же самый нетерминал, что и слева. Другими словами, не должна появляться рекурсия.

Но это так, комментарий в сторону.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 16:32 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Valery Solovey писал(а):
В правой части автоматной грамматики может содержаться нетерминал.
Да, Вы правы. Спасибо. :)
Принципиальное значение имеет можно ли их исключить подстановками.

А что Вы можете сказать по поводу моего разбора упражнения 4.2? У Вас есть какие-нибудь возражения или дополнения?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 16:40 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Galkov писал(а):
Здесь лексика не выделена, а включена в синтаксис.
Это, видимо, не так. В противном случае, что означает следующая строка:
term = factor {factor}. ?
Здравый смысл говорит нам, что реализация может выглядеть так:
Аа Вв
Однако разделитель НИГДЕ НЕ УПОМЯНУТ и такая запись недопустима!
Аа|Вв - так можно,
а так
Аа Вв - нельзя!

Вообщем, тут лексика тоже должна быть отделена, иначе сам черт ногу сломит.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 16:51 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Galkov писал(а):
Здесь лексика не выделена, а включена в синтаксис.
Здесь к лексике относится только это:
Код:
id = letter {letter | digit}.
string = """ character """.
Лексемы - это и есть абстактные терминальные символы.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 9  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB