Нисходящие распознаватели КС-языков Метод рекурсивного спуска Дано: Построить: распознаватель грамматики методом рекурсивного спуска. - презентация

1 Нисходящие распознаватели КС-языков Метод рекурсивного спуска Дано: Построить: распознаватель грамматики методом рекурсивного спуска

2 Обозначения: СH – текущий символ исходной строки; gc – процедура считывания очередного символа исходной строки в СH; Err - процедура обработки ошибок, возвращающая по коду сообщение об ошибке.

3 Процедуры разбора S AB procedure S; begin A; B; if CH<> then ERR end;

4 Процедуры разбора A cA | a procedure A; begin if CH= a then gc else if CH= c then begin gc; A end else Err end;

5 Процедуры разбора B bA procedure B; begin if CH= b then begin gc; А end else Err end;

6 Достаточные условия применимости метода рекурсивного спуска 1) A, где (V T V N )*; 2) A a 1 1 | a 2 2 |…| a n n, где a i V T для каждого i=1, 2,…, n; a i a j для i j, i (V T V N )*

7 L a | a,L или L a{,a} Устранение рекурсии правил procedure L; begin if CH<>a then Err else gc; while CH=, do begin gc; if CH<>a then Err else gc end end;