OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 23 Апрель, 2019 20:59

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




Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9  След.
Автор Сообщение
СообщениеДобавлено: Среда, 03 Февраль, 2010 09:57 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 528
Откуда: Москва
Евгений Темиргалеев писал(а):
Поскольку формально синтаксис сканера не дан, как можно говорить о его детерминированости?
Дать его самим. Текст программы, которая его реализует дан.


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

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


Евгений Темиргалеев писал(а):
Я понимаю так: для кодирования недетерминированного синтаксиса его надо преобразовать в детерминированный (если возможно).
Про "возможность" - вообще никаких сомнений.
Интерпретатор НКА (фишки на диаграммах переходов) - это же алгоритм. Детерминированный. И, как у всякой программы, у него есть "множество состояний".
Что такое "состояние" этого интерпретатора - конкретное расположение фишек на поле. Автоматически (как бы сам собой) получается способ построения ДКА, глядя внимательно на наш НКА.
Каждая фишка, предположим, ответственна за некую лексему. Наверное это вот и называет igor классом лексем, если таких фишек несколько ((но это не более, чем мои предположения))

Возникает ощущение, что, пытаясь смекнуть, как же "это" закодировать - он идет очень похожим путем. Типа, природу не обманешь...


Peter Almazov писал(а):
Дать его самим. Текст программы, которая его реализует дан
В принципе, в природе существует т.н. LEX-формализм.
Но он шибко не похож на синтаксис РБНФ, приводимый Виртом. Скажем, квадратные и фигурные скобки обладают совершенно иным смыслом.
И под С заточен - аж до безобразия.
Мне-то, хоть к пчелам в улей.... Хотя тоже достает его C-шность. Скажем, задача табличного НКА настолька маленькая, что тут и АСМ - совершенно адекватен. Тем более, что тормоза на этом месте совершенно не в тему.

А вот, глядя на основные идеи этого LEX-формализма, сделать его хоть бы и в Оберон - почему бы и нет.
Нет более лучшего способа стать Мастером, видимо....
Главное, "ребенка не выплеснуть"


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 12:11 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4489
Откуда: Россия, Орёл
Евгений Темиргалеев писал(а):
Peter Almazov писал(а):
Регулярный язык для синтаксического анализатора (парсера)
Этот язык не регулярный.
В выражениях и процедурах присутствует рекурсия. Одним РБНФ-выражением не записать...
Peter Almazov писал(а):
Евгений Темиргалеев писал(а):
Поскольку формально синтаксис сканера не дан, как можно говорить о его детерминированости?
Дать его самим. Текст программы, которая его реализует дан.
Это не возможно сделать однозначно. Например:
{ ">" | ">=" }
{ ">" [ "=" ] }


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

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1183
Peter Almazov писал(а):
Регулярный язык для лексического анализатора (сканера):
{ > | >= } – недетерминированный

В каком смысле недетерминированный?


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 528
Откуда: Москва
Trurl писал(а):
Peter Almazov писал(а):
Регулярный язык для лексического анализатора (сканера):
{ > | >= } – недетерминированный

В каком смысле недетерминированный?
В смысле отрицания того, что Вирт в своей книге называет детерминированным.


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

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1537
Откуда: Беларусь, Минск
Илья Ермаков писал(а):
Т.е. имеется в виду, что детерминированный синтаксис - это такой, по которому не получится при всём желании НКА?
Нет. Просто не надо путать недетерминированность синтаксиса и недетерминированность конечного автомата. Они друг с другом не связаны.


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

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1537
Откуда: Беларусь, Минск
Peter Almazov писал(а):
Trurl писал(а):
Peter Almazov писал(а):
Регулярный язык для лексического анализатора (сканера):
{ > | >= } – недетерминированный

В каком смысле недетерминированный?
В смысле отрицания того, что Вирт в своей книге называет детерминированным.
Он детерминированный. Просто для указанного случая семантика невнятная. Её одним простым словом не выразишь. Но можно выразить каким-нибудь абстрактным элементом. Например A.

Код:
<
→ (A) → (СтрогоМеньше)
   ↓=
  (МеньшеРавно)
Из каждого состояния (они заключены в скобки - кружков нарисовать не могу) строго по одному выходу для каждого из вариантов. Над стрелками указываются символы, побуждающие перейти в соответствующие состояния.


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 528
Откуда: Москва
igor писал(а):
PS: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить.
Интересно было бы посмотреть на рисунки. Не по теме, а вообще. Не пропадать же трудам.
А по теме - надоело уже толочь воду в ступе.


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

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
2Valery Solovey
В Вашем случае правильно рисовать так, мне кажется
Код:
<
→ (A) → (СтрогоМеньше)
   ↓=
  (B)
   ↓
  (МеньшеРавно)
Ну скажем, для "изтропности"
"Семанитика" срабатывает в каждом target-состоянии по символу "other" (непомеченная стрелочка)



Евгений Темиргалеев писал(а):
Это не возможно сделать однозначно. Например:
{ ">" | ">=" }
{ ">" [ "=" ] }
Ну да, не возможно. Поэтому сначала надо нарисовать формальное определение, а потом применить именно к этому, нарисованному - формальные правила.
Вы взяли очень простые лексемы
А если такие ?
Код:
integer      = digit{digit} |      //семантика 1
               digit{hexDigit}"H"  //семантика 2
CharConstant = '"'character'"'|    //семантика 3
               digit{hexDigit}"X"  //семантика 4
string       = '"'{character}'"'   //семантика 5
Здесь под семантикой предполагается не только руководящее указание про LexemID, но и некие действия по преобразованию текста, например - в число.
Ни в коем случае я не утверждаю, что нельзя написать некие хитромудрые регулярные выражения, которые будут детерминироваными.
Но кто в них потом разберется, спрашивается :?:
((но утверждаю, между прочим, что никакой "тупой компьютер" не поймет из РБНФ: кто такой "A" - string, или CharConstant))

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


Последний раз редактировалось Galkov Вторник, 09 Февраль, 2010 22:25, всего редактировалось 2 раз(а).

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

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1183
Peter Almazov писал(а):
В смысле отрицания того, что Вирт в своей книге называет детерминированным.


А что он называет детерминированным?


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 528
Откуда: Москва
Trurl писал(а):
Peter Almazov писал(а):
В смысле отрицания того, что Вирт в своей книге называет детерминированным.

А что он называет детерминированным?
А почему Ви спгашиваете?


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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Peter Almazov писал(а):
igor писал(а):
Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису.
Интересно было бы посмотреть на рисунки.
Как всегда несколько комментариев к рисунку:

1. На рисунке изображён граф магазинного автомата для контекстно-свободного синтаксиса РБНФ из упражнения 4.2 в книге Вирта.

2. Вид графа в общем случае зависит от метода разбора. Данный граф выведен исходя из метода рекурсивного спуска.

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

4. Кружочки соответствуют состояниям автомата (а также вызовам вложенных автоматов). Стрелки соответствуют переходам. Над стрелкой записаны множество символов, которые могут быть считаны перед переходом в следующее состояние. Символами BEGIN и END обозначены соответственно начальное и конечное состояние каждого автомата.

5. Множество терминальных символов я расширил символом eot (end of text). Обозначение ~eot означает "любой символ, кроме eot".

6. Один такт работы автомата состоит из следующих шагов: 1) Автомат считывает ровно один следующий символ; 2) Переходит в новое состояние в соответствии с функцией перехода. Аргументами для функции перехода служат текущее состояние и последний считанный символ.

7. Я не претендую на безупречность составленной схемы. Схема составлена на скорую руку, любые замечания приветсвуются.


Вложения:
Граф.jpg
Граф.jpg [ 56.47 КБ | Просмотров: 5264 ]
Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 19:08 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4489
Откуда: Россия, Орёл
Peter Almazov писал(а):
Trurl писал(а):
Peter Almazov писал(а):
В смысле отрицания того, что Вирт в своей книге называет детерминированным.

А что он называет детерминированным?
А почему Ви спгашиваете?
Чтобы понять о чём Вы говорите. Думаю, тут уместна цитата из книги вида ".... называется детерминированным ....". Если строго придерживаться слов "Вирт в своей книге называет".

Мне тоже не ясно. Поясните, пожалуйста.

Согласитесь, догадок делать смысла не имеет, можно ошибиться.


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 528
Откуда: Москва
Евгений Темиргалеев писал(а):
Чтобы понять о чём Вы говорите. Думаю, тут уместна цитата из книги вида ".... называется детерминированным ....". Если строго придерживаться слов "Вирт в своей книге называет".
Мне тоже не ясно. Поясните, пожалуйста.
Согласитесь, догадок делать смысла не имеет, можно ошибиться.
Все уже сказано, повторяться не вижу смысла.
Можете поискать в книге слова вида "детерменирован*" и посмотреть, что там стоит рядом. Потом дадите свою трактовку.


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 528
Откуда: Москва
igor писал(а):
1. На рисунке изображён граф магазинного автомата
А чем рисовали?


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

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1183
Peter Almazov писал(а):
Все уже сказано, повторяться не вижу смысла.


Сказано очень много слов. Но, не зная законов языка ирокезского...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 04 Февраль, 2010 05:50 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Peter Almazov писал(а):
А чем рисовали?
Visio


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

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
igor, у меня возникли смутные сомнения... Те не Легалова часом усиленно штудируешь :?:


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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Galkov писал(а):
igor, у меня возникли смутные сомнения... Те не Легалова часом усиленно штудируешь :?:
Вирта, Гриса, Легалова, Свердлова, Молчанова, Ахо и Ко. И этим не ограничиваюсь.
Всё как всегда, знания приходится добывать по крупицам из разных источников.


Последний раз редактировалось igor Пятница, 05 Февраль, 2010 19:10, всего редактировалось 1 раз.

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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3041
Откуда: Астрахань
igor писал(а):
Galkov писал(а):
igor, у меня возникли смутные сомнения... Те не Легалова часом усиленно штудируешь :?:
Вирта, Гриса, Легалова, Свердлова, Мочалова, Ахо и Ко. И этим не ограничиваюсь.
Всё как всегда, знания приходится добывать по крупицам из разных источников.

Молчанова - вы хотели сказать... :)
Еще порекомендую:
Льюис, Розенкранц, Стирнз;
МакКиман, Хорнинг;
Робин Хантер - первую книжку, но можно и вторую... :)
Мозговой М.В. - Классика программирования...
И вот такая интересненькая книжка: Залогова Л.А. Разработка Паскаль-компилятора. - М.: БИНОМ. Лаборатория знаний, 2007.
Можно еще продолжить... :)


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

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


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

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


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

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