Изучение алгоритмов грамматического разбора предложений

Содержание работы: В процессе выполнения лабораторной работы должны быть изучены структуры синтаксических графов и возможность их применения для задачи нисходящего распознавания предложений языка для заданного синтаксиса. Заданный синтаксис некоторого языка удобно представлять в виде синтаксического графа или графа распознавания. Такой граф отражает управление ходом работы при грамматическом анализе предложений. Синтаксический граф является эквивалентным...

2014-07-24

12.95 KB

5 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Лабораторная   работа  №4.

Изучение алгоритмов  грамматического  разбора предложений.

Цель  работы: Изучение  алгоритма  грамматического  разбора  для  заданного  синтаксиса.

Содержание  работы:  В  процессе  выполнения  лабораторной  работы  должны  быть изучены    структуры  синтаксических  графов и возможность  их  применения  для  задачи нисходящего распознавания  предложений  языка для  заданного  синтаксиса.

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

Пусть  оператор,  полученный  с  помощью  преобразования  графа  S,  обозначается  через  Т(S).

  1.  Необходимо  свести  систему  графов  к  как  можно  меньшему  числу  отдельных  графов  с  помощью  соответствующих  подстановок.
  2.  Необходимо  преобразовать  каждый  граф  в  описание  процедуры  в  соответствии  с  нижеприведенными  правилами  3 – 7.
  3.  Последовательность  элементов  графа  

преобразуется  в  составной  оператор  следующего  вида:

{ T(S1); T(S2); ………..T(SN) }  Здесь { и } – операторные скобки.  Могут  быть  beginend.

  1.  Выбор  элементов

переводится  в  оператор  выбора  типа Case  или  switch  или  условный  оператор  if.

  1.  Цикл  вида

переводится  в  оператор  цикла  типа  while.

  1.  Элемент  графа,  обозначающий  другой  граф    А

переводится  в  оператор  обращения  к  процедуре  А.

  1.  Элемент  графа,  обозначающий  терминальный  символ  

переводится  в  оператор   вида:  if  ch = x then  read(ch) else  error();  где  ch – очередной  прочитанный  терминальный  символ.

Применение  правил 1 – 7 иллюстрируется  следующим  примером.

Пусть  имеется  синтаксический  граф  следующего  вида:

 

Здесь  «х», «»,  «+»,  «)» - терминальные  символы.  Язык,  соответствующий  данному  графу,  состоит  из  предложений вида: х, (х), (х+х),  ((х))  и т. п.  Применение  правил  1 – 7  к  этому графу  дает  следующий  алгоритм.

Parse

 ch: char;

   Procedure A;

     begin

       if  ch = ‘x’  then read(ch)

         else

       if  ch = ‘(‘ then

         begin

            read(ch);

            A;

           while ch = ‘+’  do

             begin

                read(ch);

                A

             end;

           if  ch = ‘)’ then read(ch)  else error()

         end else error()

     end; //A

Основной  блок  алгоритма Parse:

  read(ch);

  A.

Некоторые  комментарии  к  данному  алгоритму:  

  1.  Алгоритм  имеет  рекурсивную  структуру;
  2.  Операция  read(ch)  означает  чтение  очередного  символа  из входной  последовательности;
  3.  Считается,  что  терминальные  символы  имеют  длину  один  байт;
  4.  Процедура  error() предназначена  для  обработки  синтаксических  ошибок.

Порядок  выполнения  лабораторной  работы.

Для  выполнения  настоящей  лабораторной  работы  необходимо:

  1.  В  соответствии  с  полученным  заданием  в  виде  синтаксического  графа  некоторого  языка  построить  алгоритм  грамматического  разбора  согласно  правилам  1 – 7;
  2.  По  заданному  синтаксическому  графу  построить  несколько  предложений  языка,  в  том числе  и  неправильное,  и  проанализировать   работу алгоритма.
  3.  Разработать  приложение,  реализующее   построенный  алгоритм.  Приложение  должно  читать  предложения,  вводимые  с  клавиатуры   и  выполнять их  грамматический  разбор.  В  случае  ошибки  в  исходном предложении  должна  выдаваться  информация  о  ней,  например,  в  виде  местонахождения  неправильной  конструкции, а  работа приложения – завершаться.

Содержание  отчета.

Отчет  по  лабораторной  работе  должен  включать  в  себя:

  1.  Краткий  листинг  разработанного  приложения  с  комментариями (В  части реализации  разработанных  алгоритмов).
  2.  Заданный  синтаксический  граф  и  контрольные  примеры  в  соответствии  с  п. 1 порядка  выполнения  лабораторной  работы.
  3.  Пошаговую  работу  алгоритма  для  случаев  правильного  и  неправильного  исходных  предложений  в  соответствии  с  контрольными  примерами  по  п. 2.

Литература:

  1.  Н.  Вирт. «Алгоритмы + структуры  данных = программы». М.:  «Мир», 1985 г.


S1

S2

SN

S

А

х

(

)

+

А

х



 

Другие похожие работы, которые могут вас заинтересовать.
3145. Восходящий алгоритм синтаксического разбора контекстно-свободных грамматик 9.9 KB
  Кроме того она способна генерировать внятные синтаксические ошибки вида неразбираемый символ такойто в такойто позиции и в случае если во всей строке таблицы разбора есть только 1 операция сдвига вида ожидался такойто символ. Введем понятие символ RK L то есть символ на который указывает цепочка. Это Lый символ из правой части правила K. Завершенная цепочка не указывает ни на какой символ.
14498. Требования программы и критерии отбора грамматического минимума для средней школы. Принципы обучения коммуникативной грамматике 11.04 KB
  Требования программы и критерии отбора грамматического минимума для средней школы. Способы введения грамматического материала. Коммуникативный подход использование грамматического материала в начале обучения в естественном общении или приближенном к нему. Главное требование к отбору и объёму грамматического материала объём должен быть достаточен для реализации коммуникативных целей преподавания языка в пределах предусмотренных программой.
3585. Сборник домашних заданий в помощь логопедам и родителям для преодоления лексико-грамматического недоразвития речи у дошкольников с ОНР 46.75 KB
  Совместно с воспитателями ознакомить с детским садом — его помещениями, групповой комнатой, умывальной комнатой, спальней, раздевалкой, кабинетом логопеда, физкультурным и музыкальным залами, при этом объяснить назначение каждой комнаты, а также познакомить с сотрудниками детского сада: логопедом, воспитателями, няней, медицинской сестрой...
1471. Программирование и исследование алгоритмов вычисления определенных интегралов 160.41 KB
  На практике часто возникает необходимость вычислить определённый интеграл. Если интеграл берётся в алгебраических функциях, то всё в порядке и взять его вручную не представляет труда. А если интеграл не берётся в алгебраических функциях или просто их очень много, то приходится прибегать к помощи компьютерной техники
4471. Программирование алгоритмов управления в АСУ ТП с использованием TRACE MODE 6 34.57 KB
  Изучение языка программирования Техно ST, представленного в SCADA-системе TRACE MODE 6. Изучение средств TRACE MODE 6 для составления и запуска программ. Моделирование системы программного управления с ПИД-регулятором с использованием TRACE MODE 6.
12246. ИССЛЕДОВАНИЕ ЛИНЕЙНЫХ АЛГОРИТМОВ И УСТРОЙСТВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ 68 KB
  Успешное воплощение перспектив развития инфокоммуникационных технологий во многом базируется на достижениях цифровой обработки сигналов (ЦОС), призванной решать задачи приема, формирования, обработки и передачи информации в реальном масштабе времени
15959. Исследование алгоритмов изменения кривых притока по модельным данным при свабировании 656.78 KB
  В настоящее время для исследования малодебитных скважин применяются такие методы как свабирование компрессирование и отработка скважины струйным насосом. Проведение исследований и интерпретация полученных результатов не учитывают особенности процесса работы пласта и скважины что часто приводит к ошибочным результатам при определении фильтрационно-емкостных параметров пласта...
13105. Комплексное диахроническое исследование грамматического и лексических способов выражения будущего действия в древнеанглийском, среднеанглийском, ранненовоанглийском и современном периодах истории английского языка 160.18 KB
  Категория времени слагается из трех делений: настоящего, прошедшего и будущего; английский глагол обладает четырьмя временными формами: прошедшей, настоящей, будущей, «зависимой будущей»; в системе английского глагола категория времени состоит из бинарной оппозиции «прошедшее - непрошедшее время», то есть она двучленна.
20424. Разработка алгоритмов построения типовых бизнес-процессов на основе слабоструктурированных данных 755.56 KB
  Разработка алгоритмов построения типовых бизнес-процессов на основе слабоструктурированных данных. Также построена модель выявления типовых бизнес-процессов описан механизм ее реализации. Анализ методов оценки эффективности бизнес процессов.
12192. РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПОСТРОЕНИИ ГЕОМЕТРИЧЕСКИЕ ФРАКТАЛОВ НА БАЗЕ R-ФУНКЦИИ 65.38 KB
  В нашей республике уделяется огромное внимание для эффективного использования информационных технологий в научной и производственной деятельности. Количество различных масштабов длины в естественных формах можно считать бесконечным для каких угодно практических задач. Программное обеспечение может быть использовано в текстильной промышленности при рисовании узоров для штамповки на ковры ткани и т. В 1988 году известные американские специалисты в теории динамических...
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.