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

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

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

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

Рассмотрим в качестве примера язык вида { x ^m y ⁿ |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) -грамматики.В данном пособии этот класс грамматик и языков подробно не рассматривается.