Восходящие распознаватели - это транслятор, которое строит синтаксическое дерево сверху- вниз.

Основа - дочерние узлы какого-либо куста синтаксического дерева.

Восходящие распознаватели выполняют следующую последовательность шагов:

1- Выполняют поиск основы Х

2- Выполняют поиск правила грамматики:

<U>::= х;

3- Привязывают х к нетерминальному символу <U> и таким образом строят куст

синтаксического дерева.

Алгоритм продолжается, начиная с пункта 1.

В дальнейшем восходящие распознаватели рассматривают на примере операторных грамматик.

Грамматика G(<Z>) называют операторной, если ни одно из ее правил не записано в следующем виде:

<U>::= <V> <W>, то есть никакая правая часть любого правила не содержит двух соседних нетерминальных символов.

Примеры: грамматика арифметического выражения;

Условие поиска в операторе SELECT.

Для разработки восходящего распознавателя необходимо определить следующие компоненты:

1- Отношения между операторами грамматики (операторы- терминальные символы, которые разделяют нетерминальные символы в правых частях правил команд).

2- Необходимо определить числовые функции предшествования f и g.

I. Рассмотрим отношения между операторами:

Можно выделить 3 типа отношений между операторами:

1- отношение: r◦<s: означает оператор r непосредственно предшествует оператору S но перед оператором r вначале надо вычислить S.

Пример:

а) для арифметических выражений:

+◦<* а+в*с (+ это r; * это s)

б) для логических выражений: Или ◦< и

OR ◦<AND A=3 OR B= 2 AND C<5

2- отношение: r◦>s Оператор r непосредственно предшествует S и перед определением S необходимо вычислить r.

Пример:

а) для арифметических выражений:

а + в - с (+ это r, - это s)

б) для логических выражений: OR ◦> OR

3- отношение: r◦ = s Означает, что оператор r непосредственно предшествует S; r и S необходимо в дальнейшем исключить из рассмотрения:

а) (◦=) для арифметического выражения

б) для логического (◦ =)

II. Определим функции предшествования:

Числовые функции f и g называются функциями предшествования, если они удовлетворяют условиям:

1- Отношение r◦<S эквивалентно f(r)<g(s)

2- Отношение r◦<s эквивалентно f(r) > g(s)

3- Если r◦=s эквивалентно f(r) = g(s)

Примеры отношений между операторами и функции предшествования для грамматики арифметического выражения

Пусть задана грамматика арифметического выражения:

1) <Z>::=<E>

<E>::=<T>| <E> + <T>|<E>-<T>

2) <T> ::= <F> | <T> * <F> | <T>/<F>

<F>::= (<E>)i

Здесь не учитывается возведение в степень, i- константа или идентификатор. Здесь операторами являются +, -, *, /, ( ).

Определим отношения

между операторами, сведем эти отношения в таблицу.

‘0’- конец строки

По концу строки должны выполняться операторы.