Студопедия  
Главная страница | Контакты | Случайная страница

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

Билет №14 Способы представления процессов в теории взаимодействующих процессов (теоретико-множественное, процедурное, с помощью выражений над процессами).

Читайте также:
  1. A. 2. Способы расчета ВНП
  2. CОВРЕМЕННЫЕ ЭТИЧЕСКИЕ ТЕОРИИ
  3. I. Понятие, структура и функции религии. Социологические теории религии.
  4. II Способы ценообразования на товар, факторы его выбора
  5. II. Основные теории по анализу международных отношений.
  6. II.1. Оценка финансовой деятельности строительной организации с помощью финансового анализа.
  7. III. Основные положения синтетической теории эволюции
  8. IV. ПРЕДСТАВЛЕНИЯ О ДОСТОИНСТВЕ И СЛУЖЕНИИ ЖЕНЩИНЫ В ИСТОРИЧЕСКОЙ ХРИСТИАНСКОЙ ТРАДИЦИИ.
  9. IV. Цитаты из книги «Из лекций по теории словесности».
  10. IV. ЭВОЛЮЦИОННАЯ И РЕВОЛЮЦИОННАЯ ТЕОРИИ РАЗВИТИЯ ОБЩЕСТВА

 

 

Билет №15 Нисходящий синтаксический анализ.

Задача нисходящего анализа, как правило, сводится к нахождению левого порождения. Процесс нисходящего анализа начинается с символа предложения с последующей генерацией предложения языка.

Рассмотрим в качестве примера язык вида { x m y n |m, n > 0 }, определяемый следующими продукциями:

 

S -> XY

X -> xX

X -> x

Y - >yY

Y -> y

 

Предложение xxxyy можно сгенерировать с помощью следующего левого порождения:

 

S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy.

 

Алгоритм нахождения левого порождения можно наглядно

проиллюстрировать с помощью приводимой ниже таблицы.

_________________________________________________________

Входная строка Продукция Сентенциальная форма

_________________________________________________________

xxxyy S => XY XY

xxxyy X => xX xXY

x xxyy X => xX xxXY

xx xyy X => x xxxY

xxx yy X => x xxxY

xxxy y Y => yY xxxyY

xxxyy Y => yY xxxyY

_________________________________________________________

 

Таблица 3.4.2 -1. Алгоритм нахождения левого порождения.

 

В этой таблице знаки предложения рассматриваются по одному и используются для управленият процессом синтаксического анализа.

После генерации знак предложения подчеркивается во входной строке.

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

синтаксического анализа все знаки входной строки подчеркнуты,

а сентенциальная форма полностью совпадает с заданной строкой.

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

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

нисходящего синтаксического анализа с одним символом предосмотра. Это -так - называемые LL(1) -грамматики. Термин LL(1) означает следующее:первая буква L определяет направление чтения слева

(Left) направо,вторая буква L определяет использование левых

(Leftmost) порождений, цифра 1- один символ предосмотра. Соответственно LL(1) - язык определяется как язык, генерируемый посредством LL(1) -грамматики.В данном пособии этот класс грамматик и языков подробно не рассматривается.

 




Дата добавления: 2015-02-16; просмотров: 59 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав