OberonCore
https://forum.oberoncore.ru/

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

Автор:  igor [ Понедельник, 01 Февраль, 2010 17:22 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Valery Solovey писал(а):
А разве id - нетерминал? Чёрт, забыл.
С точки зрения сканера id - нетерминал, а с точки зрения парсера id - терминал.
Я уже советовал выше, перечитайте страницу 30. :wink:

Автор:  Евгений Темиргалеев [ Понедельник, 01 Февраль, 2010 18:36 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

igor писал(а):
можно продолжить обсуждение в этой теме (на усмотрение модераторов)
Моё мнение такое: когда товарищ Galkov решил переключиться с лексики Оберона на синтаксис РБНФ, ему стоило создать новую тему.

Автор:  Galkov [ Вторник, 02 Февраль, 2010 13:51 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Valery Solovey писал(а):
Приравнивать входные символы нельзя. Просто, factor - это другой Уровень. Его входными элементами являются сами id. Целиком, а не его составляющие.

Еще как ЗЯ :)
Просто по определению, FIRST и FOLLOW - это множества именно терминальных символов. Попробую подтвердить, что я не одинок в этом мнении: у Вирта в разделе 7.2 (стр.57-58) перечислены эти множества для нетерминалов, невзирая на их уровень.
    [offtop] Правда, первая же строчка: FIRST(selector)={"." "[" "*"} - ставит в тупик. Но, в качестве рабочей гипотезы, я отношу это к опечаткам: вместо звездочки должен быть символ "пустышки"[/offtop]
Да, Вирт не определил толком эти множества. Считая, видимо, это не самым сложным для самостоятельного размышления. И серьезных оснований спорить с ним по этому поводу у меня просто нет.
Ну ладно, попробую (это значит, что излагаю лишь мысли, которые можно критиковать) самостоятельно, не заглядывая в буквари...

FIRST значительно проще, он определен для произвольного выражения (что собственно и нарисовано в правилах генерации кода по регулярным выражениям на стр.29). Будем пробовать "конструктивное" определение:
1) Для терминального символа это просто множество из одного элемента - того самого терминального символа
2) Для круглых скобок тождественное равенство: FIRST((exp)) = FIRST(exp)
3) Для альтернативы: FIRST(exp1|exp2) = FIRST(exp1)+FIRST(exp2)
4) Для "повторения" и "необязательности": FIRST({exp}) = FIRST([exp]) = FIRST(exp)+NULL
5) Для конкатенации: FIRST(exp1 exp2) = FIRST(exp1) + (if NULL in exp1 then FIRST(exp2))
- ну и как бы альтернативы и конкатенации считаем левоассоциативными. Или право... никак пока в толк не возьму разницы...
Ну вот, кто нам мешает определить FIRST для "чего угодно" - спускаемся вниз по уровням до терминалов. А у нас в данный момент это получатся letter, digit и char - которые уже сами определены где-то (нет смысла заморачиваться с конкретными записями, все более или менее очевидно) как множества входных символов. Буковок, грубо говоря

Попробуем поразмышлять про FOLLOW... Тут мне ничего в голову не приходит, как сказать, что сие определено только для нетерминалов, для которых я могу изучить вхождение в наш синтаксис, и там уже смотреть first того, что за ним следует. В общем, ПОЙДЕМ ЛОГИЧЕСКИМ ПУТЕМ (надеюсь: пойдем вместе)
Ну, скажем, нетерминал expression... Видим вхождение его в левую часть определения production, и понимаем, что после epression МОЖЕТ следовать ".". Первое вхождение в левую часть определения factor: может ли входить в FOLLOW(expression) символ ")" ??? Может, ОНИ ОБА МОГУТ ((дальше, как Вы помните, следует торжественное рукопожатие))
Вот так и получается, что если начать с пустого множества FOLLOW, и на каждом шаге добавлять first того, что за ним следует, то получится, что FOLLOW(expression)={"." ")" "]" "}"}
Остался последний вопрос: а если ничего не следует ??? Мне представляется логичным такой ответ: так не бывает, следует, и это множество FOLLOW для того нетерминала, в левой части которого мы и копаемся
Т.е., в отличие от FIRST мы будем подниматься "вверх по уровням", пока не дойдем до стартового символа
Тут для синтаксического анализатора все понятно. Ничего за стартовым символом не следует.
А если мы шутим с написанием такого для лексера (упомянутая igor-ем стр.30), то фигня получается. Фиг его знает, что следует за нетерминалом symbol, следовательно - мы не можем определить множества FOLLOW, следовательно - проверить правила детерминированности Вирта, следовательно - написать код лексера.
Не, написать-то можно. Говорить, что все написано по правилам (типа: "да все следует из синтаксиса!!!") - НЕЛЬЗЯ.
    [offtop] типа: igor, привет! Мы не только перечитали стр.30, но кое-что для нее проверили :D [/offtop]

Ну как, нам удалось пройти до конца логическим путем вместе ??? :)

Автор:  Galkov [ Вторник, 02 Февраль, 2010 15:35 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Peter Almazov писал(а):
В общем, тут лексика тоже должна быть отделена, иначе сам черт ногу сломит

Золотые слова :!: :D
Дополнительно отметил бы, что просто добавление {blank} в хвост или начало определиния id - никак не спасут отца русской демократии.
И хотелось бы акцентировать внимание на том, что "тут тоже" - мне не представляется до конца правильным :)
Мне думается, что ВЕЗДЕ. Грубо говоря: мухи - отдельно, котлеты - отдельно.
Иначе - всегда будут такие сюрпризы.
И прежде всего - в определении синтаксиса Оберона. Смотрим, и видим первые две (для Оберон-0) строки
Код:
   ident    = letter {letter | digit}.
   integer  = digit {digit}.
Это же ровно те же яйца, только в профиль!!!
И чего у нас получается ??? Здесь играть, здесь не играть, а здесь рыбу заворачивали ???
Посмотрите на множества FISRT и FOLLOW на стр.57-58 - они там идут ведь как терминалы. И получается все в порядке. Естественно.
И это вовсе не вопрос "студент должен додумать сам", а вопрос аккуратности. Да, пусть (предположим) студент сам додумывает про FIRST и FOLLOW. Но с ними-то все в книге предельно аккуратно (мне пока именно так кажется а опечатки - не считаются).
А здесь - не согласный я :)

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

Мое предложение такое:
  1. Забыть как страшный сон про объединение патернов лексера с синтаксисом
  2. Пусть даже только для себя, но определить таки, что такое лексер (типа: делает то-то, и то-то), и какими (и как - очень важно) патернами он при этом пользуется.
  3. Записать наконец в этом формализме некий Лексер. Например для Оберон[-0]
  4. И совершенно формальными методами (теми же правилами Вирта, или их адаптацией) проверить наконец-то детерминированность этого несчастного синтаксиса.

А то иначе - сил моих бабских больше нету :lol:
Ну вот Игорь категорически утверждает про то, что лексер в каждый момент знает какую лексему он рассматривает
Мы ему показываем пальцем на разные лексемы, начинающиеся с одинаковых символов
Нет, говорит он, они принадлежат одному классу лексем (не открывая нам глаза на определение класса)
Ну спрошу я его, к примеру, чем же таким этот "класс" отличается от нескольких фишек на диаграмме переходов НКА
А он мне, видимо, скажет, что не видит особого смысла рисовать НКА, когда можно нарисовать ДКА
А единого регулярного выражения (он же - патерн) для лесем integer и CharConstant (начинающихся с одного символа) - так и не нарисовал. А комментарий - так это вообще не лексема, а безобразие какое-то
Потому что тот факт, что мы говорим про Оберон, уже как-то и подзабылся :)

Надо же как-то кончать эту сказку про белого бычка, выходить как-то из замкнутого круга :D

Автор:  Peter Almazov [ Вторник, 02 Февраль, 2010 16:02 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Согласен со всем.
И даже программа из 4 пунктов совместными усилиями практически выполнена.
А "этот несчастный синтаксис" - недетерминирован.
А дальше-то что?

Автор:  Trurl [ Вторник, 02 Февраль, 2010 17:41 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Peter Almazov писал(а):
Согласен со всем.

не согласен я. С обоими.
Цитата:
А дальше-то что?

Да что тут предлагать?.. А то пишут, пишут... Конгресс, немцы какие-то... Голова пухнет.

Автор:  Peter Almazov [ Вторник, 02 Февраль, 2010 18:10 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Давайте разберемся.
Термины "Регулярный язык с детерминированной лексикой" и "Регулярный язык с недетерминированной лексикой" (ужасно выглядит, согласен) принадлежат Вирту.
Первый означает, что при реализации распознающего автомата обязательно получится ДКА.
Второй - все остальное.

Возьмем такой регулярный язык
{ > | >= }

Для него можно построить НКА, т.к. из состояния, где мы принимаем символ > к двум разным вершинам ведут 2 дуги, обе с меткой >.
По определению, это - "Регулярный язык с недетерминированной лексикой".

В чем заключаются возражения?

Автор:  Valery Solovey [ Вторник, 02 Февраль, 2010 18:39 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Galkov писал(а):
Мне представляется логичным такой ответ: так не бывает
Ничего себе аргумент...

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

Galkov писал(а):
Говорить, что все написано по правилам (типа: "да все следует из синтаксиса!!!") - НЕЛЬЗЯ.

Согласен.

Автор:  Евгений Темиргалеев [ Вторник, 02 Февраль, 2010 20:35 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Peter Almazov писал(а):
Термины "Регулярный язык с детерминированной лексикой" и "Регулярный язык с недетерминированной лексикой" (ужасно выглядит, согласен) принадлежат Вирту.
Это из "Построения компиляторов"? ... в любом случае, дайте ссылку, пожалуйста.

Автор:  Peter Almazov [ Вторник, 02 Февраль, 2010 21:37 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Книга осталась на работе.
Посмотрите, например, что предлагается сделать в упр. 4.2:
"Using these sets, verify that EBNF is deterministic."

Автор:  Galkov [ Вторник, 02 Февраль, 2010 21:38 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

А я с собой ношу :D

Там такого прямого указания НЕТ
Там примерно такая последовательность изложения (стр.28-29):
  1. Определяются регулярные языки. Хоть коротко, но точно, имхо
  2. Сообщается, что для их распознавания достаточно иметь конечный автомат (никаких намеков на НКА или ДКА)
  3. Следом, единственное упоминание на то, что в природе существует недетерминированность, выглядит так:
    Цитата:
    Если очередное состояние уникально, то машина состояний является детерминированной, иначе недетерминированной
  4. Далее приводятся правила построения кода из регулярного выражения
  5. И уже потом - правила, лишь при выполнении которых возможно таковое построение кода. Магический термин все таки употреблен: "возможно лишь при условии детерминированного синтаксиса"
Т.е., прямого указания нет. А косвенное (за которое еще нужно догадаться) - есть
Самое главное косвенное указание: правила Вирта выделяют из всех регулярных синтаксисов, только ту ее часть, которую можно кодировать напрямую (названо - прозрачно), и этот синтаксис явно назван детерминированным.
Но мы должны догадаться, что оставшаяся часть - это недерминированные языки, и для них тоже кодирование вполне возможно, хотя и менее прозрачно.

Мне лично кажется, что более понятной была бы иная последовательнось изложения:
  1. Определение регулярного синтаксиса
  2. Сообщение, что для их распознавания достаточно конечного автомата, который может быть как ДКА, так и НКА
  3. Правила Вирта, которые разделяют языки на те, которым нужен НКА (недетерминированные), и на те - которым достаточно ДКА (детерминированные)
  4. И вот для детерминированных - вот Вам правила генерации кода. И мы, типа, будем их успешно использовать далее. Наши победили

Но это уже - так, ИМХО

Автор:  Trurl [ Вторник, 02 Февраль, 2010 23:07 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Galkov писал(а):
Правила Вирта, которые разделяют языки на те, которым нужен НКА (недетерминированные), и на те - которым достаточно ДКА (детерминированные)


Боюсь, таких "правил Вирта" не существует. ;) Разделять эти языки бессмысленно, ибо они суть одно и то же.

Автор:  Galkov [ Вторник, 02 Февраль, 2010 23:23 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

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


Объяснение первое: Вы решили не ту задачку, которая предложена в упражнении 4.2!!!
Есть формальное определение синтаксиса, и работать надо с ним. Применение "здравого смысла" - это же подгонка под ответ.
Давайте так... Есть у Вирта упражнение 5.1 (которое тоже приведено, чтобы его решали, извлекая для себя при этом новые знания :D )
Цитата:
Расширьте программу распознавания РБНФ таким образом, чтобы она генерировала (1) список терминальных символов, (2) список нетерминальных символов и (3) множества начальных (first) и последующих (follow) символов для каждого нетерминального символа
- и все это (обращаю внимание!!!) только исходя из текста "программы", которая в нашем случае - тот самый формальный синтаксис.
Спрашивается, какой список терминалов и нетерминалов выдаст эта программа :?:
Вовсе не тот, что у Вас.
Но мы же взрослые люди, и понимаем, что "здравый смысл", побудивший Вас выкинуть две последние строчки из синтаксиса - действительно является здравым.
Иначе ответ не сойдется.
В этом и прикол: стоит пристегнуть патерны лексики к синтаксису - и получится полный кердык.
И это не мой ведь прикол, это упражнение Вам дал Вирт. Возможно (точно я не знаю) для того, чтобы мы понимали, чего будет, если свалить все в одну кучу.

Объяснение второе: выполнение Вами упражнения, хоть и с другими условиями, имело и так великую пользу, поскольку продемонстрировало, что мы с Вами по разному считаем FOOLOW. Вот я уже два раза по шагам рассказывал как я его считаю, а Вы - нет. А результаты не сходятся.
При этих "объяснениях" выше, я мимоходом посчитал FOLLOW(expression) - сравните, не совпадает ведь :(
Но это же не дает нам возможность двигаться дальше :!:
Предположим что Вы согласительс п.1 "программы", что мух с котлетами смешивать нельзя. Если не согласитесь, то мы попросим Вас посчитать таки нашу задачу без применения "здравого смысла" - ибо через руки доходит лучше всего.
Но Вы ведь все равно не согласитесь с п.2, я же знаю :) И даже знаю как Вы будете не соглашаться: сошлетесь на стр.30, и скажите: "вот же symbol, из него все ясно, все детерминировано, и т.п."
На возражения, что невозможно определить FOLLOW(symbol) - скажите: "да вот он у меня!!!".
А ответы-то у нас разные...
igor, ну критикуйте мое определение для follow, ну все же я рассказал, что мог и умел...
Разве-что одно: нафига мне нужен этот follow...
Он мне нужен, когда при применении 3-го правила эти скобки находятся в конце. Например для factor{factor}
С чем мне сравнивать first от второго factor-а ??? Я сравниваю с follow(term).
А Вы с чем ??? Если ни с чем, то нафиг нам вообще нужен это дурацкий follow ...
Разобраться с этим надо всенепременно. Иначе - клинч.


igor писал(а):
PS: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить
А чего там рисунки :D
Есть у Вирта следующее упражнение - 4.3
Это уже те же рисунки, но воплощенные в код (кстати говоря, именно эту программу предлагает расширить Вирт в упражнении 5.1). И это уже очень интересно.
Почти боевой бизон :!:
При этом, с целью практичности, можно расширить РБНФ. Например так, как Вы и предлагали: символом char в стиле Оберон, и "диапазоном"

P.S. две точки - вот Вам и недетерминированность, получится. А если бы их было три, получилась бы еще и "откатность" - ужас

P.P.S. Выполненное упражнение 5.1 позволило бы и "третейское судейство": запузыриваешь в нее синтаксис Оберон-0, и сравниваешь результаты с приведенными на ст.57-58

Автор:  Евгений Темиргалеев [ Среда, 03 Февраль, 2010 02:26 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Присоединяюсь к сказанному выше Trurl-ем. Язык --- множество предложений, порождаемых грамматикой(ами). Синтаксис в последних может быть детерминирован/недетерминирован.

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

Автор:  Илья Ермаков [ Среда, 03 Февраль, 2010 02:28 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Т.е. имеется в виду, что детерминированный синтаксис - это такой, по которому не получится при всём желании НКА?

Автор:  Peter Almazov [ Среда, 03 Февраль, 2010 09:03 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Да

Автор:  Peter Almazov [ Среда, 03 Февраль, 2010 09:22 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

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

Вот маленький пример.
Регулярный язык для лексического анализатора (сканера):
{ > | >= } – недетерминированный
Регулярный язык для синтаксического анализатора (парсера):
{ ЗнакБольше | ЗнакБольшеИлиРавно } - вполне себе детерминированный.

Автор:  Евгений Темиргалеев [ Среда, 03 Февраль, 2010 09:29 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Такой момент...
Для Оберона Вирт формально определяет грамматику для синтаксического разбора (для парсера). (Для заметки: там ">", ">=" являются разными "буквами" алвафита.) Сканер частично определяется продукциями, частично неформальными правилами --- см. в конце 7.1.

Поскольку формально синтаксис сканера не дан, как можно говорить о его детерминированости?

Автор:  Евгений Темиргалеев [ Среда, 03 Февраль, 2010 09:34 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Peter Almazov писал(а):
Регулярный язык для синтаксического анализатора (парсера)
Этот язык не регулярный.

2) Peter Almazov, хотелось бы вернуться к вопросу: viewtopic.php?p=41707#p41707. Указанные Вами определения даны у Вирта? Или мы о них сами "догадываемся" навроде того, как описывает Galkov тут: viewtopic.php?p=41711#p41711

Это вообще-то вещи разные.

Автор:  Peter Almazov [ Среда, 03 Февраль, 2010 09:55 ]
Заголовок сообщения:  Re: Детерминированность лексики Оберона

Евгений Темиргалеев писал(а):
Peter Almazov писал(а):
Регулярный язык для синтаксического анализатора (парсера)
Этот язык не регулярный.
А какой же?
Евгений Темиргалеев писал(а):
2) Peter Almazov, хотелось бы вернуться к вопросу: viewtopic.php?p=41707#p41707. Указанные Вами определения даны у Вирта? Или мы о них сами "догадываемся" навроде того, как описывает Galkov тут: viewtopic.php?p=41711#p41711

Это вообще-то вещи разные.
Сами догадываемся, Galkov полностью раскрыл тему.

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