АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ЯЗЫКИ И ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ

Читайте также:
  1. I. ИНДОЕВРОПЕЙСКИЕ ЯЗЫКИ
  2. I. ИНДОЕВРОПЕЙСКИЕ ЯЗЫКИ
  3. LL(k) ЯЗЫКИ И ГРАММАТИКИ
  4. XX. ИНДЕЙСКИЕ (АМЕРИНДСКИЕ) ЯЗЫКИ
  5. Алтайские языки
  6. Бух.учет операций по договору простого товарищества. ПБУ 19/02
  7. Другорядні члени речення; їх роль у формуванні структури простого речення
  8. ОПЕРАТОРНАЯ ГРАММАТИКА ПРЕДШЕСТВОВАНИЯ
  9. Племенные языки и образование родственных языков.
  10. Пошук даних у режимі простого запиту. Збереження інформації у текстових файлах
  11. Проблемно-ориентированные языки. Языки представления знаний.
  12. Синтаксис как раздел грамматики

 

Одна из центральных проблем детерминированного восходящего синтаксического анализа состоит в однозначном определении основы – самой левой подцепочки сентенциальной формы, которую требуется редуцировать на данном этапе разбора. Хотелось бы, “перемещаясь” по цепочке слева направо и рассматривая одновременно только два соседних символа, суметь определить, нашли ли мы хвост основы (конец редуцируемой части). А затем, продвигаясь назад к левому концу найти голову основы, опять таки анализируя лишь два соседних символа. То есть мы сталкиваемся с такой задачей: если задана сентенциальная форма ... x y... (где x, y Î N È S), то всегда ли x – хвост основы, или x и y принадлежат основе, или возможны другие варианты? Для решения этой задачи требуется еще до начала разбора исследовать грамматику языка и принять решения относительно каждой пары символов x и y.

Пусть x, y Î N È S грамматики G. Предположим, что в языке, определяемом G, при выводе цепочки языка существует сентенциальная форма ... x y.... На некотором этапе разбора либо x, либо y, либо оба символа одновременно должны войти в основу. При этом возникают три различных варианта:

 
 


1). x – часть основы, а точнее ее хвост, а y в основу не входит. Эту ситуацию мы будем обозначать x ·> y и говорить, что x больше, а, более строго, x предшествует y, так как x редуцируется раньше, чем y. Заметим, что x в этом случае должен быть последним, хвостовым, самым правым символом в правой части некоторого правила грамматики U ®... x (рис. 5.5). Отметим также, что основа располагается слева от y, и следовательно y должен быть терминалом, так как имеет место канонический разбор.

       
 
 
   
Рис. 5.6


2). Оба символа входят в основу. При этом говорят, что x и y имеют одинаковое отношение предшествования, они редуцируются одновременно и изображают это отношение: x y. Очевидно, что в грамматике при этом имеет место правило U ®... x y... (рис. 5.6).

 
 

 


3). y – часть основы, а точнее ее голова, а x в основу не входит. Эта ситуация обозначается x <· y и можно говорить, что x меньше y или x следует за y. При этом символ y должен быть первым, самым левым в правой части некоторого правила
U ® y... (рис. 5.7).

Если сентенциальной формы ... x y... при выводе цепочек в грамматике G не существует, то мы будем считать что между упорядоченной парой символов (x, y) не определено отношение предшествования (обозначим этот факт как x y).

Заметим, что ни одно из определенных выше отношений не является симметричным: из x y вовсе не следует, что y x, и уж тем более x <· y не свидетельствует о том, что y ·> x.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)