OberonCore :: - Детерминированность лексики Оберона

Здесь слово сканер - это моя отсебятина, классик (Galkov) говорил "лексика".
Я этим словом обозначил, что речь идет о синтаксисе для сканера, а не для парсера.
Так что речь идет именно о теории, а не о конкретном сканере.

В общем случае - нет. Где он об этом сказал?

Вообще-то понятно что имелось в виду, но сказано коряво.

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

Код:

expression = term {" " term}.

Правильно ???
Да, не сказал. Но мне представляется более значительным, что он не сказал и обратного (что в общем случае - нет). Тут, правда, я могу говорить лишь о русском варианте, но который читал очень внимательно.
Поставьте себя на место студизо, который первый раз, и именно здесь, прочитал определение регулярного синтаксиса.
Будет ли у него правильное понимание после прочтения ???

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

igor писал(а):

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

Определить множества символов FIRST и FOLLOW для конструкций РБНФ production, expression, term и factor. Используя эти множества, проверить, что РБНФ является детерминированной.

В конце концов, упражнения даются, чтобы их делать. Вот я - сделал, А Вы - нет.

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

Вечерком отпишусь (постараюсь).

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

В правой части автоматной грамматики может содержаться нетерминал.

Здесь лексика не выделена, а включена в синтаксис.

Автор:	Peter Almazov [ Воскресенье, 31 Январь, 2010 16:11 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Здесь слово сканер - это моя отсебятина, классик (Galkov) говорил "лексика". Я этим словом обозначил, что речь идет о синтаксисе для сканера, а не для парсера. Так что речь идет именно о теории, а не о конкретном сканере.

Автор:	igor [ Воскресенье, 31 Январь, 2010 16:25 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Peter Almazov писал(а): Здесь слово сканер - это моя отсебятина, классик (Galkov) говорил "лексика". Я этим словом обозначил, что речь идет о синтаксисе для сканера, а не для парсера. Так что речь идет именно о теории, а не о конкретном сканере. Хм... Интересно. Тогда можно говорить о двух эквивалентных лексиках языка. Одна - это та, которая описана в "Сообщении о языке". А другая - та, по которой "шпарит" конкретный сканер. Относительно лексики, которая в сканере, похоже разногласий нет, и все согласны, что она там детерминированная.

Автор:	Galkov [ Воскресенье, 31 Январь, 2010 19:19 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Сергей Оборотов писал(а): В общем случае - нет. Где он об этом сказал? Если я еще не потерял мысль в этом тасовании колоды постов, то речь идет о том, что Вирт не сказал, что регулярные языки являются обязательно детерминированными. Правильно ??? Да, не сказал. Но мне представляется более значительным, что он не сказал и обратного (что в общем случае - нет). Тут, правда, я могу говорить лишь о русском варианте, но который читал очень внимательно. Поставьте себя на место студизо, который первый раз, и именно здесь, прочитал определение регулярного синтаксиса. Будет ли у него правильное понимание после прочтения ??? Мне кажется - не факт. Про себя скажу: по первому разу запутался. Азы читал давно, а по жизни меня больше интересует генерация кода из графической схемы, чем из текста. Не, ну вспомнил, конечно же. Но у меня таки была первичная подготовка, а каково бедному студиозо ??? Сергей Оборотов писал(а): Вообще-то понятно что имелось в виду, но сказано коряво. Ну вот, уже более конкретно. Сергей, мне непонятно, в чем заключается корявость. Поясните пожалуйста. Или как это должно сказать не коряво... Пока мне кажется все нормальным. Если, конечно у нас одинаковое понимание термина "лексика" Но именно это и есть предмет обсуждение в топике. Как мне кажется... Несмотря на его сегодняшнее название

Автор:	Galkov [ Воскресенье, 31 Январь, 2010 19:42 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
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. И считаю это не совсем допустимым. Точнее - совсем недопустимым Вот Вам и весь сказ

Автор:	Peter Almazov [ Воскресенье, 31 Январь, 2010 20:52 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Galkov писал(а): Код: expression = term {" " term}. Что-то я не понял про опечатки, а книги нет под рукой. Может все-таки как в оригинале: expression = term {"\|" term}. ?

OberonCore https://forum.oberoncore.ru/

Детерминированность лексики Оберона https://forum.oberoncore.ru/viewtopic.php?f=61&t=2279	Страница 4 из 9

Автор:	Сергей Оборотов [ Воскресенье, 31 Январь, 2010 23:14 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Galkov писал(а): Правильно ??? Да, не сказал. Но мне представляется более значительным, что он не сказал и обратного (что в общем случае - нет). Тут, правда, я могу говорить лишь о русском варианте, но который читал очень внимательно. Поставьте себя на место студизо, который первый раз, и именно здесь, прочитал определение регулярного синтаксиса. Будет ли у него правильное понимание после прочтения ??? Да, правильно. Если это написано в "Конструировании компиляторов" и получилось сделать у Вирта то может получиться и у студента, который будет это пособие читать. Как-то так. Galkov писал(а): Сергей, мне непонятно, в чем заключается корявость. Поясните пожалуйста. Или как это должно сказать не коряво... Пока мне кажется все нормальным. Если, конечно у нас одинаковое понимание термина "лексика" Но именно это и есть предмет обсуждение в топике. Как мне кажется... Несмотря на его сегодняшнее название Нет, не одинаковое. Лексика - следствие определения, а недетерминированность - конструирования.

Автор:	igor [ Понедельник, 01 Февраль, 2010 07:21 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Galkov писал(а): igor писал(а): Относительно лексики, которая в сканере, похоже разногласий нет, и все согласны, что она там детерминированная Ну если все согласны, тогда у меня ко всем абсолютно конкретное предложение - проверить правила Вирта для следующего синтаксиса (это из упражнения 4.2, с исправлением опечаток) В сканере такой лексики нет! Откройте в Блэкбокс модуль DevCPS, найдите в нём процедуру Get, и по ней и проверяйте правила Вирта для "лексики, которая в сканере".

Автор:	Galkov [ Понедельник, 01 Февраль, 2010 08:17 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
И причем здесь за рыбу деньги Есть упражнение, в котором написано: Цитата: Определить множества символов FIRST и FOLLOW для конструкций РБНФ production, expression, term и factor. Используя эти множества, проверить, что РБНФ является детерминированной. Проверить-то можно, или нельзя В конце концов, упражнения даются, чтобы их делать. Вот я - сделал, А Вы - нет. Но при этом Вы мне говорите, что это я говорю ерунду про недетерминированность. А по моему, так - наоборот. Кто-то разве говорит, что некие коды сделаны неправильно Чего Вы так распереживались, непойму. Как будто, сказавши НКА, отобрали тем самым веру в Деда Мороза. Нормальные коды. Просто сделаны они не совсем из тех правил, которые даны Виртом для детерминированного синтаксиса.

Автор:	Peter Almazov [ Понедельник, 01 Февраль, 2010 13:36 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Не нашел там никакой недетерминированности. Причем, все упрощается тем, что ни одна конструкция (кроме самой верхней) не может породить пустую последовательность. Надо "сверить часы" - где там недерминированность?

Автор:	Valery Solovey [ Понедельник, 01 Февраль, 2010 14:06 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Цитата: Определить множества символов FIRST и FOLLOW для конструкций РБНФ production, expression, term и factor. Используя эти множества, проверить, что РБНФ является детерминированной. FIRST(id) = char, FOLLOW(id) = char \| digit. FIRST(string) = <">, FOLLOW(string) = char \| <">. У нетерминалов, естественно, FIRST() нет.

Страница 4 из 9	Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/

Автор:	Galkov [ Воскресенье, 31 Январь, 2010 21:55 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
Спасибо коллега, в книге эта строчка правильно нарисована. Там в строке factor аналогичные "пропуски палок" А я скопировал (и поправил factor) из Упражнения.txt на диске. И попался ((выше поправил))

Автор:	Galkov [ Понедельник, 01 Февраль, 2010 14:29 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
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) - пересекаются Ну и все, типа - кердык Просьба критиковать. Желательно не все сразу, а по отдельным утверждениям. А я буду сопротивляться Да, вот: плюсик я тут употреблял как обединение множеств...

Автор:	Valery Solovey [ Понедельник, 01 Февраль, 2010 15:12 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
А разве id - нетерминал? Чёрт, забыл. Galkov писал(а): 2) Ищем вхождения id в синтаксис - это только нетерминал factor. Из чего делаем заключение, что FOLLOW(id)=FOLLOW(factor). Приравнивать входные сиволы нельзя. Просто, factor - это другой Уровень. Его входными элементами являются сами id. Целиком, а не его составляющие. Возможно, я выразился слишком туманно, поэтому воспользуюсь аналогией. В хлебный магазин утром специальная машина привозит хлеб. Буханки переносят в магазин и время от времени подкладывают на полки. Все довольны. И так будет длиться до тех пор, пока машина привозит хлеб, а не его составляющие. Магазинщикам будет далеко не весело, если в фургоне обнаружится гора злаков, политая маслом и перемешанная с солью. Аналогия про недетерминированность. Если разложить в порядке убывания массовых долей ингредиенты кекса и чёрного хлеба, то получится, что и там, и там первое место занимает мука (FIRST(id)). Но этот факт нам не мешает в магазине отличить первое от второго. А всё потому, что магазин (factor) принимает уже готовые кексы и хлеб (id).

Автор:	igor [ Понедельник, 01 Февраль, 2010 15:59 ]
Заголовок сообщения:	Re: Детерминированность лексики Оберона
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: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить.