OberonCore
https://forum.oberoncore.ru/

Детерминированность лексики Оберона
https://forum.oberoncore.ru/viewtopic.php?f=61&t=2279		 Страница 8 из 9
Автор:  igor [ Вторник, 09 Февраль, 2010 15:03 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
... (основанное на понимании диаграмм Вирта в стиле Легалова).
Странно... Честно говоря, Легалова я читал по диагонали.
Galkov писал(а):
И это не не я говорю бред, а - Вы (встречная просьба извинить за прямоту) :P
Со стороны это, должно быть, выглядит так, как будто мы говорим друг другу бред, при чём каждый - свой. :lol:
Автор:  igor [ Вторник, 09 Февраль, 2010 15:13 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Peter Almazov писал(а):
igor писал(а):
3. Натыкайте меня носом :) в то место в моём файле, из которого следует, что хотя бы одно условие детерминированности нарушено.
Если в файл добавить лексемы > и >= , непонятно почему выкинутые, то FIRST(>)=FIRST(>=).

(Я уже чувствую себя попугаем).

Пожалуйста, посмотрите на условия детерминированности, сформулированные Виртом на странице 29, ещё раз, и скажите, где там написано, что множество First() для ЛЮБЫХ двух лексем не должно пересекаться?

Задумайтесь и вот над чем. Множество всех лексем хоть и не бесконечно, но очень велико, во всяком случае гораздо больше, чем количество элементарных символов, которыми мы располагаем. Если следовать Вашей логике, то получается, что для любого детерминированного синтаксиса число всех лексем не может превышать 256 (с учётом расширенной таблицы ASCII). Разве для Вас не очевидна абсурдность такого утверждения?
Автор:  Peter Almazov [ Вторник, 09 Февраль, 2010 15:34 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
igor писал(а):
Пожалуйста, посмотрите на условия детерминированности, сформулированные Виртом на странице 29, ещё раз, и скажите, где там написано, что множество First() для ЛЮБЫХ двух лексем не должно пересекаться?
Не любых, а альтернативных, т.е. идущих через |. Правило № 1.
igor писал(а):
Задумайтесь и вот над чем. Множество всех лексем хоть и не бесконечно, но очень велико, во всяком случае гораздо больше, чем количество элементарных символов, которыми мы располагаем. Если следовать Вашей логике, то получается, что для любого детерминированного синтаксиса число всех лексем не может превышать 256 (с учётом расширенной таблицы ASCII). Разве для Вас не очевидна абсурдность такого утверждения?
Все лексемы Oberon перечислены в CASE на границе стр. 170-171. Бесконечное множество создают лексемы, начинающиеся на "0".."9" и на "A".."Z","a".."z". Никакой абсурдности нет.
Автор:  Galkov [ Вторник, 09 Февраль, 2010 16:13 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Можно даже веселее сказать :D

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

И в чем причина жуткого переживания за его "недерминированность" - не понятно совершенно :)
Автор:  Peter Almazov [ Вторник, 09 Февраль, 2010 18:06 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
Для LL(1) парсера без детерминированности - "смерть всем китайцам".
Что это означает - непонятно.
Автор:  Валерий Лаптев [ Вторник, 09 Февраль, 2010 18:19 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Peter Almazov писал(а):
Galkov писал(а):
Для LL(1) парсера без детерминированности - "смерть всем китайцам".
Что это означает - непонятно.

Это означает, что LL(1) без FIRST и FOLLOW просто не работает.
Автор:  igor [ Вторник, 09 Февраль, 2010 18:32 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Peter Almazov писал(а):
igor писал(а):
Пожалуйста, посмотрите на условия детерминированности, сформулированные Виртом на странице 29, ещё раз, и скажите, где там написано, что множество First() для ЛЮБЫХ двух лексем не должно пересекаться?
Не любых, а альтернативных, т.е. идущих через |. Правило № 1.

... | "<" ["="] | ">" ["="] | ...

Где здесь пересекаются множества First() для альтернатив?
Автор:  igor [ Вторник, 09 Февраль, 2010 18:45 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Peter Almazov писал(а):
Все лексемы Oberon перечислены в CASE на границе стр. 170-171.
Кстати, код, приведённый на странице 170, в точности соответствует тому фрагменту продукции, который я только что привёл.
Но почему мы с Вами так по разному видим один и тот же код? :)
Автор:  Peter Almazov [ Вторник, 09 Февраль, 2010 18:49 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
igor писал(а):
... | "<" ["="] | ">" ["="] | ...

Где здесь пересекаются множества First() для альтернатив?
Вы изменили грамматику. Это, конечно, похвально, но в таком случае Вы напоретесь на правило № 3. Ибо:
...| "<" ["="] | ">" ["="] | "="|
Автор:  igor [ Вторник, 09 Февраль, 2010 20:44 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Peter Almazov писал(а):
Вы изменили грамматику. Это, конечно, похвально, но в таком случае Вы напоретесь на правило № 3. Ибо:
...| "<" ["="] | ">" ["="] | "="|
Да, нет же. В правиле №3 слова "... и символов, которые могут следовать за K" означают, что могут следовать в самом исходном тексте, а не в тексте продукции, как например в том фрагменте, который Вы привели.

И грамматику я не менял. Она была такая изначально. Но таковой она была в исходных текстах. А в сообщении о КП (например), продукции для лексем, которые мы сейчас рассмотрели, не приводятся. Там все эти лексемы просто перечислены. Мол, есть такие, и всё.
Автор:  Galkov [ Вторник, 09 Февраль, 2010 21:26 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Валерий Лаптев писал(а):
Peter Almazov писал(а):
Galkov писал(а):
Для LL(1) парсера без детерминированности - "смерть всем китайцам".
Что это означает - непонятно.

Это означает, что LL(1) без FIRST и FOLLOW просто не работает.
Ну да, как-то так
Мне кажется, было бы точнее: это означает, что LL(1) без проверок правил Вирта (для проверки которых обязательно нужны и FIRST, и FOLLOW для всех нетерминалов) просто не работает.
Единичка означает, что мелодия угадывается с первой ноты. Если со второй, то это не меньше, чем LL(2)... ну и так далее :)


Peter Almazov писал(а):
Вы изменили грамматику. Это, конечно, похвально, но в таком случае Вы напоретесь на правило № 3. Ибо:
...| "<" ["="] | ">" ["="] | "="|
Все правильно.
Но давайте себя спросим: на какой такой важный вопрос отвечает регулярное выражение для lexeme ???
Ответ: является ли некоторый текст (весь, целиком) одной лексемой.
Спрашивается далее, нафига нам нужен ответ на такой куцый вопрос.
Нам интересно совсем другое: разбивается ли некий текст на последовательность лексем ??? И однозначно ли разбивается ???
А на этот вопрос отвечает уже другое регулярное выражение: program={lexeme}.
И проверка правил Вирта совершенно однозначно определяет однозначность разбиения.

Даже и проверять не буду, настолько предсказуем результат. :lol:
Абсолютно объективный критерий - каждый может проверить сам.



igor писал(а):
3. Натыкайте меня носом :) в то место в моём файле, из которого следует, что хотя бы одно условие детерминированности нарушено.
Дык я тыкал. Без ответа, между прочим :)
Galkov писал(а):
6) Затрону таки нетерминал comment
Ибо нарисован он неправильно, а я об этом уже заикнулся ранее.
Так вот, символ, следующий за {sym} - это "*"
Пересечение sym и "*" - не пусто => правило 3 невыполняется
Но ужас положения не в недерминированности. По большому счету-то, сканеру - пофиг
Вопрос в том, что он будет делать (а он сделает, проблем нет) по такому "заказу"
А он будет делать следующее: встретивши префикс первого комментария, просканирует весь текст (например 100К) до конца, вернется к концу самого последнего комментария (например на -5К), промежуток выкинет нафиг.
Ровно на тех же основаниях, на которых Вы заставляете сканер принимать числовые константы "до упора".
Основания правильные, и называется правило СДЛ.
А патерн - легаловщина :D
Автор:  Galkov [ Вторник, 09 Февраль, 2010 21:29 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
igor писал(а):
Да, нет же. В правиле №3 слова "... и символов, которые могут следовать за K" означают, что могут следовать в самом исходном тексте, а не в тексте продукции, как например в том фрагменте, который Вы привели
Контрольный выстрел: а какие символы могут следовать :?:
Автор:  igor [ Вторник, 09 Февраль, 2010 21:44 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
Дык я тыкал. Без ответа, между прочим :)
Дык, камнем преткновения стал термин Follow() :), из-за которого всё "тыканье" оказалось не правильным. Позже я пытался объяснить, но безрезультатно.
Автор:  igor [ Вторник, 09 Февраль, 2010 21:59 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
Контрольный выстрел: а какие символы могут следовать :?:
Вот!!! Вот тот вопрос, ответ на который давно уже будоражит мой мозг :) .

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

Другими словами говоря, ответ на Ваш вопрос даёт правило № 3.

Все учебники кричат о том, что любой НКА можно преобразовать в ДКА (вложенные комментарии с их КС-ной натурой уже "обсасывали", оставим их в покое, чтобы не повторяться). Если язык так же прост, как Оберон, то только идиот станет городить сканер на базе НКА. Сам сканер, со своей стороны вправе рассчитывать на то, что его разрабатывал не идиот. :wink:
Автор:  Galkov [ Вторник, 09 Февраль, 2010 22:09 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Ну я-то методы определения follow расписал подробно как только мог.
А ВЫ - нет. Но говорите, что неправ именно я. Почему-то
Ну и как Вам помочь в этом, если Вы партизаните!!!

Вот в заключение пост. Писал я его на работе, дракона под рукой не было. НО я перечитал дядюшку АхО. И обнаружил у себя неточности:
1) в п.5 для FIRST в правой части не просто FIRST(expr1), а еще и за вичитанием из него преположительно имеющегося там NULL
2) для FOLLOW стартового символа - он не пустой, а содержит EOF, и больше не содержит ничего.

Но ведь не подействовало же !!! Наши определения этого несчастного множества до сих пор отличаются :)
Автор:  Galkov [ Вторник, 09 Февраль, 2010 22:21 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
igor писал(а):
Новая доктрина звучит так: не только синтаксис стараются сделать детерминированным для того, чтобы облегчить построение лексического анализатора, но и сам лексический анализатор выполняет разбор исходя из предположения, что синтаксис является детерминированным
Абсолютно неправильная доктрина.
1) Синтаксис делают детерминированным, чтобы с аттрибутными грамматиками башку себе не сломать. И с детерминированным - разберитесь сначала. Плевать при этом хотели на проблемы сканера. Которых и нет к тому же.
2) Не исходит он (сканер) из этого. Потому-что к этому нет никаких технических причин

igor писал(а):
то только идиот станет городить сканер на базе НКА.
Есть иное мнение: только идиот будет изобретать детерминированную версию таких патернов:
Код:
integer      = digit{digit} |      //семантика 1
               digit{hexDigit}"H"  //семантика 2
CharConstant = '"'character'"'|    //семантика 3
               digit{hexDigit}"X"  //семантика 4
string       = '"'{character}'"'   //семантика 5
- когда и с недетерминироваными все просто и понятно.
Кстати, эти патерны я не сам придумал, а переписал из приложения А2

Так кто, Вы говорите, у нас Вирт :?: :lol:
Автор:  igor [ Вторник, 09 Февраль, 2010 22:58 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
Есть иное мнение: ...
Кажется у меня наступило прозрение :D .
Вернее догадка, в чём корень не понимания.

Работая над своим проектом (в котором есть и сканер, и парсер, и всё остальное :wink: ) я обратил внимание на то, что мне пришлость составить два варианта правил РБНФ: один вариант для спецификации языка, а другой - для реализации сканера и парсера. Эти два варианта отличаются друг от друга, но относятся к одному и тому же языку. Отличия обусловлены тем, что при их составлении ставились совершенно разные цели. В спецификации языка целью было "объяснить пользователю смысл синтаксических конструкций". А в программной документации цель была в том, чтобы "предельно точно специфицировать алгоритм распознавателя".

Так вот! Я всё время в рассуждениях держал в уме РБНФ для сканера и парсера. Мне интересно только это. Я в основном смотрю в исходники, а не сообщение о языке. С самого начала темы я обозначил эту свою позицию, помните (?): "Это слова разработчика". А Вы, судя по приведённым Вами фрагментам РБНФ, пользуютесь исключительно описаниями из сообщения о языке или другими подобными. То есть Вы наивно полагаете, что сканер строится непосредственно по тем РБНФ, которые были приведены их авторами для пояснения смысла синтаксических конструкций.
Автор:  Galkov [ Среда, 10 Февраль, 2010 01:35 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
один вариант для спецификации языка, а другой - для реализации сканера и парсера
Так я и именно это и говорю - легаловщина: здесь играть, здесь не играть, а здесь рыбу заворачивали.

Galkov писал(а):
А Вы, судя по приведённым Вами фрагментам РБНФ, пользуютесь исключительно описаниями из сообщения о языке или другими подобными.
Вовсе нет
Мне известен LEX-формализм, мне известно что в нем надо записать (например, для КП), и у меня есть инструмент (flex), который может сделать сканер из этой формальной записи - минутное дело.
Но я Вам не могу изложить полную формальную запись (хотя сам формализм-то - уже пытался), пока Вы занимаетесь легаловщиной.
Можно коды и ручками написать - не более чем не сложная техническая задача. Творчества в ней - нуль. День - не больше. Язык кодинга не особенно и важен.

igor писал(а):
То есть Вы наивно полагаете, что сканер строится непосредственно по тем РБНФ, которые были приведены их авторами для пояснения смысла синтаксических конструкций
Дожился до подозрения в наивности :wink:

Первое, что я говорил, если Вы помните, что точная формальная запись лексики для КП в "Сообщении" - не настолько кошмарная вещь, чтобы ее заменять некими словесами. Вовсе не сложнее формального и точного описания синтаксиса.
Тут такая фигня - я уже лет эдак 30, как профессиональный Разработчик. И у меня нет наивности, чтобы думать, что разработка ведется логически от Технического Задания. Но я абсолютно точно знаю, что акты приемки подписываюся на основании соответствия "результата разработки" Техническому Заданию.
Формальное описанние сканера - Техническое Задание.
Коды на неком языке - Реализация
Соответствует Реализация (показатели назначения) ТЗ - молодец, будем смотреть следующие характеристики Реализации (быстродействие, память, и т.д..)
Не соответствует - двойка тебе, иди учиться дальше.

Вот коллеги показывали разные коды для comment.
Они правильные ??? Вообще-то - ДА. А юридически - надо просто проверить на соответствие ТЗ
Не Вашего, естественно. От Вашего (легаловского) - нормальный разработчик должен со стула упасть.
В этом-то и есть квинтэссенция непонимания

_____________________________________________________________________________________________

Вот она, новая генерация ИТ-девелоперов. Ни хрена в самой сути процесса разработки не смыслят, велосипеды изобратают :lol:
Автор:  Peter Almazov [ Среда, 10 Февраль, 2010 09:18 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
igor писал(а):
Galkov писал(а):
Контрольный выстрел: а какие символы могут следовать :?:
Вот!!! Вот тот вопрос, ответ на который давно уже будоражит мой мозг :) .
Новая доктрина звучит так: ...
Ну а что следует-то? В "самом исходном тексте, а не в тексте продукции"?
Не доктрина же следует?
Автор:  igor [ Среда, 10 Февраль, 2010 10:47 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона
Galkov писал(а):
Тут такая фигня - я уже лет эдак 30, как профессиональный Разработчик.
...
Вот она, новая генерация ИТ-девелоперов. Ни хрена в самой сути процесса разработки не смыслят, велосипеды изобратают :lol:
Так вот оно в чём дело! Профессиональный Разработчик с 30-летнем стажем и с предвзятым отношением к ИТ-девелоперам. Это многое объясняет. Теперь для меня со всей очевидностью стало ясно, что я совершенно напрасно надрывался, пытаясь Вам что-то доказать. А я неудомевал, почему Вы решительно игнорировали все мои рассуждения по теме ("Это не доказательства, а витание в облаках было ... Рассуждения словесами."). Теперь всё встало на свои места.
Страница 8 из 9 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/