Конструирование трансляторов для языков программирования высокого уровня. Ярушкина Н.Г. - 18 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

- 19 -
нетермы N = { <арифметич. выражение>, <операнд>,
<операция сложения>, <операция умножения>,
<первичное>,<терм>}
правила Р = {<операнд>::=а¦..¦z¦A¦..¦Z
<первичное>::=<операнд>¦(<арифметич. выражение>)
<терм>::=<терм><операция умножения><арифметич.
выражение>¦<первичное>
<арифметич. выражение>::=<терм><операция сложения><арифметич.
выражение>¦<терм> }
Алгоритм грамматического разбора на один шаг вперед
Используют прямую и обратную схему разбора. Для обработки
входных предложений некоторого контекстно свободного языка осу-
ществляют грамматический разбор предложения, причем грамматичес-
кий разбор можно начать от начального символа к предложению или
наоборот. В любом случае возникает дерево грамматического разбо-
ра. Корни - начальный символ, вершины - термы и нетермы граммати-
ки, термы входного предложения - это листья дерева грамматическо-
го разбора.
Следовательно, синтаксический анализ предложения сводится к
обходу дерева. Выделяют 2 вида обхода: полный обход и направлен-
ный обход. Использование направленного поиска позволяет избежать
возвратов и поэтому нашло применение в реальных трансляторах.
Условия применимости алгоритма
1) При разработке транслятора контекстно-свободного языка
применим алгоритм просмотра на один шаг вперед в том случае, если
для любого правила грамматики, в правой части которого есть аль-
тернатива, каждая такая альтернатива начинается с уникального
терминального символа.
Например: S::=XS¦A
A::=Y¦Z.
2) Запрещается использование левой рекурсии, т.е. любое ре-
курсивное правило должно иметь вид: <нетерм>::=терм<нетерм>
В большинстве случаев вместо применения правой рекурсии дос-
таточно использовать модифицированную нотацию, включающую
повторы
с явным заданием условия ограничения повтора.

Страницы