Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Вопрос по РБНФ помогите кто может !


Автор: andreyzl 8.9.2011, 09:42
Братья по разуму, дали мне несколько заданий, справился со всеми ! Кроме одного. Просто никогда не сталкивался с этим. Пытался изучать этот вопрос, но уже время истекает ! Помогите кто может решить эту задачу. Базу данных я отструктурировал, теперь вот говорят надо проверить валидность. А я не в зуб ногой...Ниже привожу структуру и задание. Буду очень признателен !


<!ELEMENT PRIMITIVE (#PCDATA)>

<адресная книга> ::= {<адресная запись>}*
<адресная запись> ::= <Индекс><Страна>[<Область>]+<Город><Район><Посёлок><Хутор>*<Тип улицы><Улица><Дом><Строение>*<Корпус>*<Квартира>*
<Индекс> ::= 197738
 <Страна> ::= Россия
  <Область> ::= Ленинградская область
   <Город> ::= Репино
       <Тип улицы> ::= Переулок
      <Улица> ::= Цветочный
     <Дом> ::= 6
<Индекс> ::= 347914
 <Страна> ::= Россия
  <Область> ::= Ростовская область
   <Город> ::= Таганрог
       <Тип улицы> ::= Улица
      <Улица> ::= 17-Й Квартальный проезд
     <Дом> ::= 25
    <Строение> ::= 2
  <Корпус> ::= 4
<Кватира> ::= 110

1.    Постройте грамматику, описывающую структуру российских почтовых адресов, которой бы удовлетворяли приведенные ниже адреса, и запишите ее в нотации EBNF. Описание нотации и примеры записи по ссылке: http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form

Почтовые адреса:
197738, Россия, Ленинградская область, Репино, Цветочный переулок, 6
194295, Россия, г. Санкт-Петербург, улица Ивана Фомина, 10к2
234223, Россия, Нижегородская область, г. Нижний Новгород, ул. Политотдельская, 32
140120, Россия, Московская область, Раменский район, хутор Ильинский, улица Наты Бабушкиной, 77

Автор: esperanto 8.9.2011, 18:10
В чем у вас именно проблема? Что вам не понятно?

Как вы строили грамматику?

Автор: andreyzl 8.9.2011, 18:51
В том то и дело что я не знаю как её построить...задание прям таки  и было поставлено.

1.    Постройте грамматику, описывающую структуру российских почтовых адресов, которой бы удовлетворяли приведенные ниже адреса, и запишите ее в нотации EBNF. Описание нотации и примеры записи по ссылке: http://en.wikipedia.org/wiki/Extended_Back...%80%93Naur_Form

Почтовые адреса:
197738, Россия, Ленинградская область, Репино, Цветочный переулок, 6
194295, Россия, г. Санкт-Петербург, улица Ивана Фомина, 10к2
234223, Россия, Нижегородская область, г. Нижний Новгород, ул. Политотдельская, 32
140120, Россия, Московская область, Раменский район, хутор Ильинский, улица Наты Бабушкиной, 77

Добавлено через 3 минуты и 50 секунд
esperanto, В том то и дело что я не знаю как её построить...задание прям таки  и было поставлено.

1.    Постройте грамматику, описывающую структуру российских почтовых адресов, которой бы удовлетворяли приведенные ниже адреса, и запишите ее в нотации EBNF. Описание нотации и примеры записи по ссылке: http://en.wikipedia.org/wiki/Extended_Back...%80%93Naur_Form

Почтовые адреса:
197738, Россия, Ленинградская область, Репино, Цветочный переулок, 6
194295, Россия, г. Санкт-Петербург, улица Ивана Фомина, 10к2
234223, Россия, Нижегородская область, г. Нижний Новгород, ул. Политотдельская, 32
140120, Россия, Московская область, Раменский район, хутор Ильинский, улица Наты Бабушкиной, 77 

Автор: htoit 8.9.2011, 19:39
Цитата(andreyzl @ 8.9.2011,  18:51)
В том то и дело что я не знаю как её построить...задание прям таки  и было поставлено.


Почтовые адреса:
197738, Россия, Ленинградская область, Репино, Цветочный переулок, 6
194295, Россия, г. Санкт-Петербург, улица Ивана Фомина, 10к2
234223, Россия, Нижегородская область, г. Нижний Новгород, ул. Политотдельская, 32
140120, Россия, Московская область, Раменский район, хутор Ильинский, улица Наты Бабушкиной, 77

Начните с понимания, лучше всего это делать не через БН, а через синтаксические диаграммы Вирта.
Идея простая, есть терминальные символы (которые не расшифровываются, константы) и нетерминальные, которые должны быть раскрыты и в конце концов сведены к терминальным.

терминальные символы у Вас: запятая, цифры, буквы алфавита русского, слова "Россия", "область", "район", "улица", "переулок", сокращения -- "г.", "ул.".
Нетерминальные -- (адрес), (индекс), (название области), (название города), (название), (номер дома).

а теперь раскрывайте свой нетерминальный символ (адрес) через остальные символы
Код

(адрес) -> (индекс) -> "," -> "Россия" -> ...

...

(индекс) -> "0" ->  ->   -> "0" ->  ->  -> "0" ->  ->  -> "0" ->  ->  -> "0" ->  ->  ->  "0"  ->  -> 
               -> "1" ->        -> "1" ->        -> "1" ->       -> "1" ->        -> "1" ->       ->  "1"  ->  
                ......................................................................................
               -> "9" ->        -> "9" ->        -> "9" ->       -> "9" ->        -> "9" ->       ->  "9"  ->  



стрелки разветвляются и снова сходятся, возвращаются обратно и проч. проходя по стрелкам вы получаете возможные варианты.
Как освоите синт.диагр. с БНФ будет проще.


Автор: VelSyd 23.9.2011, 19:38
Здравствуйте. У меня такое же задание. Полный список почтовых адресов:

197738, Россия, Ленинградская область, Репино, Цветочный переулок, 6
194295, Россия, г. Санкт-Петербург, улица Ивана Фомина, 10к2
234223, Россия, Нижегородская область, г. Нижний Новгород, ул. Политотдельская, 32
140120, Россия, Московская область, Раменский район, хутор Ильинский, улица Наты Бабушкиной, 77
140120, Россия, Московская область, Раменский р-н, х-р Ильинский, 3-й Октябрьский пер., 3а
142403, Россия, Московская область, Ногинский район, г. Ногинск Больничный проезд, 6
347900, Россия, Ростовская область, Таганрог, улица Нижняя Линия, 295/2, корп. 3, кв. 25
347924, Россия, Ростовская область, Таганрог, 17-Й Квартальный проезд, 25, строение 2, корпус 4, квартира 110
347904, Россия, Ростовская обл, город Таганрог, 1-Я Садовая Площадка, 1
478545, Россия, Красноярский кр., г. Красноярск, пр-кт Молокова, 72г
658745, Россия, Сахалинская область, поселок Сахалинский, Петропавловское шоссе, 23-1, кв. 23
236544, Россия, Еврейская автономная область, Биробиджан, пр-кт им. Жукова, 32/3, кв 1

Я составил, но незнаю правильно ли. Мой код:

<почтовый код> = <индекс> <знак> <страна> <знак> [<регион> <знак>] <населенный пункт> <знак> <адрес>;
<индекс> = <число> {<число>};
<число> = <цифра> {<цифра>};
<цифра> = “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”;
<знак> = “,”;
<страна> = “Россия”;
<регион> = <название региона> <тип региона> <знак> [<район> <знак>];
<название региона> = <буква> {<буква>};
<буква> = “А” | ”Б” | ”В” | ”Г” | ”Д” | ”Е” | ”Ж” | ”З” | ”И” | ”Й” | ”К” | ”Л” | ”М” | ”Н” | ”О” | ”П” | ”Р” | ”С” | ”Т” | ”У” | ”Ф” | ”Х” | ”Ц” | ”Ч” | ”Ш” | ”Щ” | ”Ь” | ”Ы” | ”Ъ” | ”Э” | ”Ю” | ”Я;
<тип региона> = “область” | “обл.” | “кр.” ;
<район> = <название района> <тип района>;
<название района> = <буква> {<буква>};
<тип района> = “район” | “р-н”;
<населенный пункт> = [<тип населенного пункта>] <название населенного пункта>;
<тип населенного пункта> = “город” | ”хутор” | ”г.” | “х-р”, | “поселок”;
<название населённого пункта> = <буква> {<буква> | “-”};
<адрес> = <улица> <знак> <номер дома> [<знак> <строение>] [ <знак> <корпус>] [<знак> <квартира>];
<улица> = [<тип улицы>] <название улицы> | <название улицы> [<тип улицы>];
<название улицы> = <буква> | <цифра> {<буква> | <цифра> | “-” | “.”};
<тип улицы> = “улица” | “проезд” | “шоссе” | “пр-кт” | “пер.” | “ул.” | “переулок”;
<номер дома> = <цифра> {<цифра> | <буква> | “/” | “-“};
<строение> = <название строения> <номер строения>;
<название строения> = “строение”;
<номер строения> = <цифра> {<цифра>};
<корпус> = <название корпуса> <номер корпуса>;
<название корпуса> = “корпус”;
<номер корпуса> = <цифра> {<цифра>};
<квартира> = [“квартира” | ”кв.” | “кв” | “к”] <номер квартиры>; 
<номер квартиры> = <цифра> {<цифра>}.

Попробую описать.
Здесь терминальные символы: символы "/", "-", точка, запятая, цифры от 0 до 9, буквы русского алфавита, слова "Россия", "область", "район", "город", "хутор", "поселок", "улица", "проезд", "шоссе", "переулок", "строение", "корпус", "квартира" и сокращения "обл.", "кр.", "р-н", "г.", "х-р", “пр-кт”, “пер.”, “ул.”, ”кв.”, “кв”.
Нетерминальные символы: <индекс>, <страна>, <регион>, <населенный пункт>, <адрес>.

Почтовые коды (данные здесь) можно определить через: индекс, указание страны, региона (который может быть не указан, как например в адресе 2), указания населённого пункта и адреса(и записанных через запятую).
Индекс состоит из набора цифр, цифры от 0 до 9. Страна - Россия. Нетерминальный символ регион можно определить как <название региона>, <тип региона> и <район> (который может быть не всегда указан, как например в адресах 1-3, 7-12). Название региона определим через терминальные символы - это буквы русского алфавита, тип региона - это терминальные символы либо "область" либо "обл." либо "кр.". Район можно определить через <название района> и <тип района>. Название района - представляем как буквы русского алфавита от А до Я, тип района через терминальные символы которые могут быть либо "район" либо "р-н". Населенный пункт определяем через <тип населенного пункта> (который может быть указан не всегда, как например в адресах 1,7,8,12) и <название н.п.>. Тип определяем через терминальные символы либо “город” либо ”хутор” либо ”г.” либо “х-р” либо “посёлок”. Название через буквы русского алфавита и символы "-", например Санкт-Петербург. Адрес определяем через <улицу>, <номер дома>, иногда могут быть указаны <корпус>, <строение> и квартира. Улицу определяем через <тип улицы> (который может быть не указан как в адресе 9) <название улицы>. Может быть сначала указан тип улицы, а затем название, как например в адресе 2, либо сначала название, а затем тип, как в адресе 1. Название улицы может состоять из букв русского алфавита и символов "/", ".". Тип улицы определяем через терминальные символы либо “улица” либо “проезд” либо “шоссе” либо “пр-кт” либо “пер.” либо “ул.” либо “переулок”. <номер дома> может состоять из набора цифр, букв (например 3а), символов "/", "-". Строение и корпус я представил как названия и номера. <Квартира> можно определить через терминальные символы (которые могут быть “квартира”, ”кв.”, “кв”, “к”) и номера квартиры.
Как-то так. Если кто разбирается в этом подскажите в чём я не прав.

Автор: NoviceF 14.3.2012, 08:02
Кто разбирается в теме, пожалуйста, прокомментируйте пост VelSyd, спасибо.

Автор: htoit 14.3.2012, 16:23
Цитата(NoviceF @ 14.3.2012,  08:02)
Кто разбирается в теме, пожалуйста, прокомментируйте пост VelSyd, спасибо.

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

Например:
Код

 ”Я;


здесь явно описка, не хватает закрывающей скобки.

ну и например,

Код

<индекс> = <число> {<число>};


здесь, по-видимому, надо указывать шестизначный индекс.
Это будет так:

Код

<индекс> = <цифра> <цифра> <цифра> <цифра> <цифра> <цифра>;


я еще и идентификатор заменил, потому как это цифра, а не число.


Автор: NoviceF 14.3.2012, 18:13
Цитата(htoit @ 14.3.2012,  16:23)
Цитата(NoviceF @ 14.3.2012,  08:02)
Кто разбирается в теме, пожалуйста, прокомментируйте пост VelSyd, спасибо.

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

Например:
Код

 ”Я;


здесь явно описка, не хватает закрывающей скобки.

ну и например,

Код

<индекс> = <число> {<число>};


здесь, по-видимому, надо указывать шестизначный индекс.
Это будет так:

Код

<индекс> = <цифра> <цифра> <цифра> <цифра> <цифра> <цифра>;


я еще и идентификатор заменил, потому как это цифра, а не число.

Спасибо.

Автор: NoviceF 15.3.2012, 10:06
Ещё возник вопрос по пробелам. Ведь пробелы есть в названиях городов и улиц, но в представленной грамматике это не учитывается. Нужно ли учитывать пробелы? Можно ли их указывать просто как " "?

Автор: htoit 15.3.2012, 13:36
Цитата(NoviceF @ 15.3.2012,  10:06)
Ещё возник вопрос по пробелам. Ведь пробелы есть в названиях городов и улиц, но в представленной грамматике это не учитывается. Нужно ли учитывать пробелы? Можно ли их указывать просто как " "?

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

ну, а в общем, это зависит от контекста задачи, для чего это делается.

например, если пишет человек, то вариантов написания адреса может быть очень много:

"проспект имени академика Иванова" может быть написан тысячью способами.
и "пр."
и "проспект"
и "пр-т", и "им.", и "акад."

или <<проспект имени газеты "Красноярский рабочий">>. Вполне себе реальная улица в г. Красноярске.

Ответ сильно зависит от того, чего хочется получить.



Автор: NoviceF 15.3.2012, 14:34
Цитата(htoit @ 15.3.2012,  13:36)
Цитата(NoviceF @ 15.3.2012,  10:06)
Ещё возник вопрос по пробелам. Ведь пробелы есть в названиях городов и улиц, но в представленной грамматике это не учитывается. Нужно ли учитывать пробелы? Можно ли их указывать просто как " "?

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

ну, а в общем, это зависит от контекста задачи, для чего это делается.

Ответ сильно зависит от того, чего хочется получить.

Спасибо ещё раз smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)