OberonCore
https://forum.oberoncore.ru/

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

Автор:  igor [ Суббота, 30 Январь, 2010 10:29 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

igor писал(а):
Galkov писал(а):
Смотрим правил 3 и спрашиваем себя: какие это такие символы "могут следовать за K".
Вот в моем понимание, это ничто иное, как FOLLOW(lexeme)
Похоже, что Вы не правильно истолковали правило 3. Или я не правильно истолковал :) . Но об этом позже (постараюсь завтра, но не обещаю).
Приступаю к обещанному :) .

Peter Almazov писал(а):
У нас обратная задача - решить, порождена ли конкретная лексема ААА123 этой грамматикой. Т.е., внимание!, я принял решение о том, что считать лексемой еще до распознавания.
Совершенно согласен с этим утверждением и приму его в качестве отправного пункта.

Допустим, мы решили записать подряд две лексемы: "name" и "56". То есть изначально именно они являются правильными и вопрос в том, сможет ли лексический анализатор их правильно распознать. Первая лексема относится к классу ident, вторая - к классу number.

Мы рассмотрим два случая: 1) эти лексемы записаны слитно; и 2) записаны раздельно.
Синтаксические формулы для этих двух случаев могут выглядеть так:
  1. letter {letter | digit} digit {digit}
  2. letter {letter | digit} blank digit {digit}
Нас сейчас интересует только первая фигурная скобка и какой символ следует непосредственно за ней. Напомню правило 3:
Вирт писал(а):
K = [exp] | {exp}. Множество начальных символов exp и символов, которые могут следовать за K, не должны пересекаться.
Множество начальных символов exp равно: First(exp) = {"A".."Z", "0".."9"}.
Множество символов, которые могут следовать за K, равно: 1) {"0".."9"}; 2) {20X, 09X, 0DX}.

Что мы видим? То, что в первом случае указанные множества пересекаются (правило 3 нарушается), а во втором случае - не пересекаются (правило 3 соблюдается).

В свете сказанного, следующее утверждение
Galkov писал(а):
... Вот в моем понимание, это ничто иное, как FOLLOW(lexeme)
у меня вызывает недоумение. Никакого FOLLOW(lexeme) правило 3 не рассматривает.

2Galkov. Вы по прежнему считаете лексику Оберонов недетерминированной?

Автор:  igor [ Суббота, 30 Январь, 2010 10:45 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

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

Вложенные комментарии относятся к классу контестно-свободных языков (а не регулярных), но при этом их синтаксис остаётся детерминированным . Три правила Вирта справедливы и для них (и для синтаксиса всего Оберона в целом).

Спор касался детерминированности, а не принадлежности к классу регулярных языков.

Автор:  igor [ Суббота, 30 Январь, 2010 10:56 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

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

Автор:  igor [ Суббота, 30 Январь, 2010 11:11 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

Galkov писал(а):
3) [u]Нетерминал ident.
... Применяем правило 2, и получаем, что ...
Правило 2 применять не на чём, в моём файле не встречается конструкция fac0 fac1.

Автор:  Galkov [ Суббота, 30 Январь, 2010 17:07 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

Валерий Лаптев писал(а):
Это правили родилось из практических соображений, причем, насколько я понимаю, в основном при трансляции С++. Ранее я что-то не помню СПЕЦИАЛЬНОГО упоминания об этом правиле.
Скажем так, Дядюшка Ахо ((с) Илья Ермаков, чего-то мне понравилось это словосочетание, если ударение в фамилии делать на последний слог) явно указывает на таковое.
Это уж точно ДО всяких там C++, мне кажется...
А точнее, мне кажется так, что сие используется вообще везде, после появления самого разделения "работы" на лексер/парсер.
Вот коллега Trurl справедливо указал на Фортран, как нарушитель этого правила. А ведь он был сделан раньше фундаментальных трудов по компиляторам... вроде бы.

Автор:  Galkov [ Суббота, 30 Январь, 2010 17:19 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

Peter Almazov писал(а):
Отсюда видно, что вопрос о длине лексемы не связан с РБНФ, никак из нее не выводится.
Есть еще более очевидная вещь.
Разные лексемы могут быть и одинаковой длины. Например, "ELSE" и ident с последующим пробелом
Автор имеет право сделать лексику, в которой выбирается именно та альтернатива, на которую он (автор, а не некий тупой компьютер) показал пальцем.
Но совершенно очевидно, что этот выбор никак определяется РБНФ-фомулой
Код:
Start = "ELSE"|"ELSIF"|(letter{letter|digit}).

Автор:  igor [ Суббота, 30 Январь, 2010 19:22 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Евгений Темиргалеев писал(а):
Реализация сканера Оберона объединена с этим "фильтром" в целях оптимизации.
Да, это так. Но наш спор с Галковым не касался реализации сканера, а касался самой лексики Оберонов, является ли она детерминированной.

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

Или для этого потребуется инструмент с бОльшим "интеллектом": предпросмотр вперёд более, чем на один символ; откаты и перебор вариантов в поиске правильного; привлечение семантической информации в процессе разбора и т.д.

А Вы тоже считаете (как и Galkov), что лексика Оберонов является недетерминированной?

Автор:  Евгений Темиргалеев [ Суббота, 30 Январь, 2010 22:47 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

igor писал(а):
Но наш спор с Галковым не касался реализации сканера, а касался самой лексики Оберонов, является ли она детерминированной.
Значит не понял вас (обоих), когда выносил тему. Думаю, Вам стоит указать более точный заголовок темы (вместо записанного мною).
igor писал(а):
А Вы тоже считаете (как и Galkov), что лексика Оберонов является недетерминированной?
Мне кажется что можно построить детерминированный магазинный (конечный) автомат, который будет "сканером" для Оберона.

Автор:  igor [ Суббота, 30 Январь, 2010 23:08 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Евгений Темиргалеев писал(а):
Значит не понял вас (обоих), когда выносил тему.
Напомню из-за чего весь сыр-бор:
igor писал(а):
igor писал(а):
И сканер, и парсер во всех Оберонах работают с детерминированным синтаксисом.
Galkov писал(а):
Вот и славненько. Только лексика Оберонов, являясь регулярной, не является детерминированной
И так. Детерминированная ли лексика у Оберонов?

Автор:  Galkov [ Воскресенье, 31 Январь, 2010 00:33 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

Евгений Темиргалеев писал(а):
Мне кажется что можно построить детерминированный магазинный (конечный) автомат, который будет "сканером" для Оберона
Кое-что можно сказать и точно.
Например, Lex-формализм может описать комментарий вместе с фокусами INC(level)/DEC(level), который был Вами (по памяти, извините если что) как-то и нарисован.
Скажем так:
Код:
...
<*>"(*"            { level++; BEGIN(comment);   }
<comment>{
  "*)"             { if(--level==0) BEGIN(0);     }
  {sym}            { /*пропуск одного символа*/ }
}
...
И можно точно утверждать, что это все скомпилируется в табличный ДКА, и даже и не магазинный.
И это даже будет работать

Автор:  Galkov [ Воскресенье, 31 Январь, 2010 01:53 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

2igor
Думал я , думал... из-за чего весь сыр-бор.
И показалось мне, что от того, что Вы себе не очень правильно представляете процесс patern matching-а (русский эквивалент как-то сразу в голову не приходит)
Вы все время пытаетесь принять какое-то решение при альтернативе, даже тогда, когда однозначного его не существует.
Поэтому, когда Вам говорят, что у Вас нет основаваний именно для такого решения (например - повторить содержимое данных фигурных скобок), Вы считаете, что я настаиваю на противоположном решении (прекратить повторение), и из такого предположения находите противоречие.
Считая, что нашли противоречие у меня.

Да ни в коем случае :!:
Если у нас нет точных оснований для какого-то однозначного разрешения альтенативы, значит мы должны продолжить изучение ОБОИХ вариантов. Не зная еще какой из них правильный.
Только такая тактика позволит нам обнаружить принадлежность нашего текста множеству фраз, порожденных синтаксисом.

igor, монопольку знаете ??? Там Вы передвигаете фишку по клеточкам. Если Вы будете передвигать ее по диаграмме состояний, то это будет интерпретатор конечного автомата. Каждый раз Вы передвигаете фишку в тот узел, в который ведет стрелочка, помеченная входным символом.
Что делать, когда у нас "нет оснований" передвижения в одном конкретном направлении, и мы должны изучать несколько вариантов ??? Т.е., из одного узла исходят несколько стрелочек с одним символом. Мы должны начать играть несколькими фишками, вот и вся проблема. Несмотря на страшное название - недетерминированность.
На каждом шаге мы должны передвинуть все фишки. Если нет стрелочек с нужной буквой - фишка выкидывается, что означает, что изучаемая нами альтернатива приказала долго жить. Если несколько фишек пришли в один узел диаграммы переходов, они объединяются в одну, естественно.
Текст кончился, если какая-то из оставшихся фишек находится в целевом (target) состоянии, значит наш текст принадлежит множеству, порожденному нашей регулярной грамматикой. Patern matching - по буржуинскому.
Если фишки закончились, или ни одна из оставшихся не находится в "правильном" узле - ну значит не получилось.

Все же просто. Просто не всегда можно "угадать эту мелодию с одной ноты". Для того, чтобы определить возможность "с одной" - проверяем правила, изложенные Виртом.
Вы спрашиваете про лексику Оберонов ???
Вот Вам встречное предложение угадать лексему "с одной буквы": в тексте идет символ "1", какая это будет лексема :?:
Если можете, ну считайте лексику детеминированной. А вот я - нет... ну дальше - Вы в курсе :D

Автор:  igor [ Воскресенье, 31 Январь, 2010 10:15 ]
Заголовок сообщения:  Re: Строгое определение лексики Оберона

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

Galkov писал(а):
Вот Вам встречное предложение угадать лексему "с одной буквы": в тексте идет символ "1", какая это будет лексема :?:
Если можете, ну считайте лексику детеминированной. А вот я - нет... ну дальше - Вы в курсе :D
Я легко отвечу на этот вопрос, взглянув на множества First() и Follow() в своём файле. Если это первый символ в лексеме, то этот символ однозначно принадлежит лексеме number (см. множество First() для классов лексем). Если это не первый символ в лексеме, то он может относиться к лексеме ident или number или string (или к комментарию) (см. множество Follow() для классов лексем).

Замечу, что в случае, когда символ "1" встретился в середине лексемы, неопределённость возникает только у меня (и проистекает из неопределённости самого вопроса), а сам лексический анализатор всегда :!: знает какого класса лексему он разбирает в настоящий момент.

Замечу также, что окончание лексемы лексический анализатор всегда легко "вычислит" именно благодаря детерминированности синтаксиса.

Galkov писал(а):
Если можете, ну считайте лексику детеминированной.
Ну, как? Я прошёл Ваш тест на детерминированность? :D

Автор:  Peter Almazov [ Воскресенье, 31 Январь, 2010 11:08 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Перенесено отсюда: viewtopic.php?p=41293#p41293
Пожалуй, надо выступить в защиту г-на Galkov, т.к. истина превыше всего.
Trurl осудил его за фразу "Только лексика Оберонов, являясь регулярной, не является детерминированной"
Trurl писал(а):
Регулярный и недетерминированный язык - это как целое трансцендентное число.
На самом деле во всем виноват Вирт.
Говоря о регулярных языках, он пишет: "The application of these simple translations rules generating a parser from a given syntax is, however, subject to the syntax being deterministic". (выделение моё).
Т.е., Вирт говорит, что синтаксис регулярных языков может быть детерминированым , а может быть и недетерминированым. Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
А Galkov справедиво указал, что для сканера Oberon это не так. Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".

Автор:  Сергей Оборотов [ Воскресенье, 31 Январь, 2010 12:45 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Peter Almazov писал(а):
Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
В общем случае - нет. Где он об этом сказал?
Peter Almazov писал(а):
Trurl осудил его за фразу "Только лексика Оберонов, являясь регулярной, не является детерминированной"
Вообще-то понятно что имелось в виду, но сказано коряво.
Peter Almazov писал(а):
Речь идет не об общем случае, а о смысле слов "syntax being deterministic".
То что я процитировал о том и говорил. Общий случай для первого варианта.

Автор:  Peter Almazov [ Воскресенье, 31 Январь, 2010 12:51 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Сергей Оборотов писал(а):
Peter Almazov писал(а):
Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
В общем случае - нет. Где он об этом сказал?
Речь идет не об общем случае, а о смысле слов "syntax being deterministic".
Цитаты из Compiler Construction 2005

Автор:  Евгений Темиргалеев [ Воскресенье, 31 Январь, 2010 15:11 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Peter Almazov писал(а):
А Galkov справедиво указал, что для сканера Oberon это не так. Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".
Дуги-то две. Но текущие литеры, которые определяют переход по ним --- разные. У Вирта так и определено (выделил жирным):
Compiler Construction, 3 Regular Languages писал(а):
For the recognition of regular sentences a finite automaton, also called a state machine, is necessary and sufficient. In each step the state machine reads the next symbol and changes state. The resulting state is solely determined by the previous state and the symbol read. If the resulting state is unique, the state machine is deterministic, otherwise nondeterministic. If the state machine is formulated as a program, the state is represented by the current point of program execution.
Тут картинка: http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 1.82.D1.8C

Автор:  igor [ Воскресенье, 31 Январь, 2010 15:14 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Peter Almazov писал(а):
Т.е., Вирт говорит, что синтаксис регулярных языков может быть детерминированым , а может быть и недетерминированым. Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
А Galkov справедиво указал, что для сканера Oberon это не так. Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".
Вы говорите о том, что в Оберонах есть пары лексем типа: ":" и ":=", ">" и ">=", "<" и "<=" и т.д. И из этого делаете вывод, что КА является недетерминированным, потому что якобы из вершины, соответсвующей этому текущему состоянию автомата, идут две дуги.

Пожалуйста, внимательно посмотрите на прилагаемый рисунок. На нём изображён фрагмент ДКА для лексем ">", ">=", ":" и ":=". Названия текущих состояний автомата я взял прямо из исходника Блэкбокс (кроме начального состояния, которое я обозначил словом begin).

А теперь вопрос. Где Вы тут увидели две дуги, соответствующие лексемам ":" и ":=" и идущие из одной и той же вершины?

Не спешите тыкать пальцем в две дуги, исходящие из начальной вершины. Сначала прочитайте вот эту цитату из книги "Языки программирования и методы трансляции":
С. З. Свердлов писал(а):
На вход КА поступают символы, принадлежащие входному алфавиту. ... Находясь в некотором состоянии и получив на вход очередной символ, автомат переходит в следующее состояние, определяемое значением функции переходов для данной пары символ-состояние, и считывает очередной символ. В общем случае функция переходов может определять переход в несколько состояний для данной пары символ-состояние. В этом случае говорят о недетерминированном конечном автомате (НКА). Автомат останавливается, когда заканчиваются символы на его входе.
В нашем случае нет ни одной пары символ-состояние, для которой функция переходов имела бы более одного значения. Значит, наш конечный автомат является детерминированным. Две дуги, исходяшие из начальной вершины соответствуют РАЗНЫМ очередным символам! Поэтому функция перехода однозначно переведёт автомат либо в состояние colon, если очередной символ равен ":", либо в состояние gtr, если очередной символ равен ">".

PS: Евгений Темиргалеев немного опередил меня с разъяснениями :)

Вложения:
ФрагментДКА.jpg
ФрагментДКА.jpg [ 9.98 КБ | Просмотров: 5709 ]

Автор:  igor [ Воскресенье, 31 Январь, 2010 15:32 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Peter Almazov писал(а):
... идут 2 дуги. То же самое верно для символа ">".
Уверен, что Вы предполагали что-то типа этого (см. рисунок). Но не учли, что автомат на каждом шаге принимает только один элементарный символ.

Вложения:
Фрагмент2.jpg
Фрагмент2.jpg [ 6.76 КБ | Просмотров: 5704 ]

Автор:  Peter Almazov [ Воскресенье, 31 Январь, 2010 15:50 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Не понял, зачем было вываливать сюда большой рассказ о ДКА, в который всегда можно преобразовать НКА.
Было-то написано:
Peter Almazov писал(а):
Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".

Автор:  igor [ Воскресенье, 31 Январь, 2010 16:05 ]
Заголовок сообщения:  Re: Лексические тонкости Оберонов

Peter Almazov писал(а):
Не понял, зачем было вываливать сюда большой рассказ о ДКА, в который всегда можно преобразовать НКА.
Очень хороший вопрос.

Потому что Вы сказали:
Peter Almazov писал(а):
А Galkov справедиво указал, что для сканера Oberon это не так.
То есть речь идёт о реальном сканере, а не только о чистой теории формальных языков. А все сканеры Оберонов всегда строятся на основе ДКА. Какой смысл было бы использовать НКА, если его всегда можно преобразовать в ДКА, исключив тем самым множество проблем.

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