ЛАБОРАТОРНАЯ РАБОТА № 2. СИНТАКСИЧЕСКИЙ АНАЛИЗ МЕТОДОМ РЕКУРСИВНОГО СПУСКА
Цель лабораторной работы.
Изучение методов синтаксического анализа, получение навыков в программировании алгоритмов синтаксического разбора.
Теоретическое введение
Постановка задачи синтаксического анализа. Организация данных. Общая схема алгоритмов детерминированного разбора
Синтаксический анализ (разбор) - это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она условиям, сформулированным в определении синтаксиса языка /1/. Выходом синтаксического анализатора является синтаксическое дерево разбора, которое представляет синтаксическую структуру исходной программы.
Пример.
Зададим грамматику G(V,T,P,S) следующим набором правил (полагая, что терминальные символы в правых частях правил представлены соответствующими кодами лексем):
1) <S> ::= <E>
2) <E> ::= <T> + <E>
3) <E> ::= <T>
4) <T> ::= <F> * <T>
5) <T> ::= <F>
6) <F> ::= i
В результате синтаксического анализа цепочки i*i+i может быть построено синтаксическое дерево разбора (рис. 1) .
<S>
│
┌─────<E>─────┐
│ │
┌──<T>────┐ + <E>
│ │ │ │
<F>* <T> <T>
|
|
|
│ │ │
i <F> <F>
│ │
i i
Рис.2.1. Синтаксическое дерево разбора
Метод рекурсивного спуска
Пример: пусть дана грамматика G =({a,b,c, ^}, {S,A,B}, P, S), где
P: S AB^
A a | cA
B bA
и надо определить, принадлежит ли цепочка caba языку L(G).
Построим вывод этой цепочки:
S AB^ cAB^ caB^ cabA^ caba^
Следовательно, цепочка принадлежит языку L(G).
Последовательность применений правил вывода эквивалентна построению дерева разбора методом "сверху вниз":
Метод рекурсивного спуска (РС-метод) реализует этот способ практически "в лоб": для каждого нетерминала грамматики создается своя процедура, носящая его имя; ее задача - начиная с указанного места исходной цепочки найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибки, которая выдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор. Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочки, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.
|
|
|
Пример: совокупность процедур рекурсивного спуска для грамматики
G = ({a,b,c,^}, {S,A,B}, P, S), где
P: S AB^
A a | cA
B bA
будет такой:
#include <stdio.h>
int c;
FILE *fp;/*указатель на файл, в котором находится анализируемая цепочка */
void A();
void B();
void ERROR(); /* функция обработки ошибок */
void S() {A(); B();
if (c != '^') ERROR();
}
void A() {if (c=='a') c = fgetc(fp);
else if (c == 'c') {c = fgetc(fp); A();}
else ERROR();
}
void B() {if (c == 'b') {c = fgetc(fp); A();}
else ERROR();
}
void ERROR() {printf("ERROR !!!\n"); exit(1);}
main() {fp = fopen("data","r");
c = fgetc(fp);
S();
printf("SUCCESS !!!\n"); exit(0);
}
Дата добавления: 2019-02-12; просмотров: 763; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!