Построение формального языка L Построение формального языка L WHILE( ) [, , ...])>]; WHILE - входной терминальный символ - условное выражение - некоторая функция, которая может отсутствовать - параметры функции, которые тоже могут отсутствовать Пример правильного синтаксиса: WHILE(A>44 A>44 clrscr() - функция, без параметров Подбор грамматики G[Z] по языку L Любая грамматика, к примеру G[Z], содержит следующие базисные элементы Vt, Vn, Z, P, где: Vt - словарь терминальных символов Vn - словарь нетерминальных символов Z - начальный нетерминальный символ P - множество правил вывода G[<оператор>]: <Оператор> а while( ) [<Функция>]; а T| < T| > T| <= T | >= T | != T а O | T*O | T**O | T+O | T-O | T/O а () | | <ЦБЗ> а Б{Б|Ц} <ЦБЗ> а Ц{Ц} <Функция> а ([ {, }]) а | <ЦБЗ> | к Классификация G[Z] G[<оператор>]: <Оператор> а while( ) [<Функция>]; а T| < T| > T| <= T | >= T | != T а O | T*O | T**O | T+O | T-O | T/O а () | | <ЦБЗ> а Б{Б|Ц} <ЦБЗ> а Ц{Ц} <Функция> а ([ {, }]) а | <ЦБЗ> | к Сделаем замену нетерминальных символов: <Оператор> а Z а A а B а C <Функция > а D а E <ЦБЗ> а F а G Сделаем замену терминальных символов: WHILE а a ( а b ) а c ; а d Ц а f Б а g , а h G[Z]: Z а abAc[D]d Aа B|A B|A <= B |A >= B |A != B B а C | B*C | B**C | B+C | B-C | B/C C а bAc | E | F E а g{g|f} F а f{f} D а Eb[G{hG}]c G а E | F | к Вывод : G[Z] - контекстно-свободная грамматика. Выбор метода анализа Хотя однозначность в общем случае для контекстно-зависимых грамматик не доказана, ее использование возможно для грамматик в которых однозначность очевидна. Наиболее хорошо разработанным методом анализа, для данного типа грамматик является, метод рекурсивного спуска. Диагностика и нейтрализация ошибок Разработанный алгоритм относится к общеизвестному методу синтаксического разбора, предложенный Айронсом. Основная идея метода состоит в том, что по контексту без возврата отбрасываются те символы, которые привели в тупиковую ситуацию и разбор продолжается. Приведем пример синтаксического разбора: While (A > ) cls(); Z а abAc[D]d Aа B|A B|A <= B |A >= B |A != B B а C | B*C | B**C | B+C | B-C | B/C C а bAc | E | F E а g{g|f} F а f{f} D а Eb[G{hG}]c G а E | F | к Z a b A c D B A E C B g{g} b G c E C к g E g While ( A > ) cls ( ) ; тупиковая ситуация Тестирование на цепочках Протокол работы синтаксического распознавателя оператора цикла while языка С. _____________________________________________________________________ Обрабатываем строчку - While(a>)cls(); Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - a Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - ) Проверка на ЦБЗ, текущий символ - ) Проверка на FUNC, текущий символ - c Проверка на IDENT, текущий символ - c Найденные ошибки в строке While(a>)cls(); Предупреждение: Отсутствует условие () Не найден идентификатор или ЦБЗ _____________________________________________________________________ Обрабатываем строчку - while(1<(3*(43+5*(3-4-(4<454)))) ; Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 1 Проверка на ЦБЗ, текущий символ - 1 Проверка на AB Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 5 Проверка на ЦБЗ, текущий символ - 5 Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на FUNC, текущий символ - ; Проверка на IDENT, текущий символ - ; Найденные ошибки в строке while(1<(3*(43+5*(3-4-(4<454)))) ; Отсутствует ) Предупреждение: отсутствует имя функции _____________________________________________________________________ Обрабатываем строчку - 435 4 whilei>>3t*(ewqw++()*we) rscr(456,345,rtgrt,345444rtr,,,) Найден While проверка началась с символа - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - e Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - + Проверка на ЦБЗ, текущий символ - + Проверка на TERM Проверка на O Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - w Проверка на FUNC, текущий символ - r Проверка на IDENT, текущий символ - r Проверка на PAR, текущий символ - 4 Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на PAR, текущий символ - 3 Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на PAR, текущий символ - r Проверка на IDENT, текущий символ - r Проверка на PAR, текущий символ - 3 Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на PAR, текущий символ - , Проверка на IDENT, текущий символ - , Проверка на ЦБЗ, текущий символ - , Найденные ошибки в строке 435 4 whilei>>3t*(ewqw++()*we) rscr(456,345,rtgrt,345444rtr,,,) Отсутствует ( Отсутствует ) Предупреждение: Отсутствует условие () Отсутствует ; после функции Параметр функции не может начинатся с цифры Неизвестный идентификатор(ы) - 435, 4, Не найден идентификатор или ЦБЗ Идентификатор не может начинаться с цифры Не найден или не верный параметр Неизвестная знаковая конструкция _____________________________________________________________________ Обрабатываем строчку - whiLE(43-(sss<233)fewfew) sd(we) Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - s Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - f Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - s Проверка на PAR, текущий символ - w Проверка на IDENT, текущий символ - w Найденные ошибки в строке whiLE(43-(sss<233)fewfew) sd(we) Отсутствует ; после функции Пропущено / или * или ** или + или - _____________________________________________________________________ Обрабатываем строчку - while(i>344>(5445<<2323*343243+2343*(w))>23*232) clrscr(,) Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на AB Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 5 Проверка на ЦБЗ, текущий символ - 5 Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - w Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - c Проверка на PAR, текущий символ - , Проверка на IDENT, текущий символ - , Проверка на ЦБЗ, текущий символ - , Найденные ошибки в строке while(i>344>(5445<<2323*343243+2343*(w))>23*232) clrscr(,) Отсутствует ; после функции Не найден или не верный параметр Неизвестная знаковая конструкция _____________________________________________________________________ Обрабатываем строчку - while(u>r+erhgeerg(e>=rwe+++r+788erwe++)) scr(eee,qee<) Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - u Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - r Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - e Проверка на AB Проверка на TERM Проверка на O Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - e Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - r Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - r Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 7 Проверка на ЦБЗ, текущий символ - 7 Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - s Проверка на PAR, текущий символ - e Проверка на IDENT, текущий символ - e Проверка на PAR, текущий символ - q Проверка на IDENT, текущий символ - q Проверка на PAR, текущий символ - < Проверка на IDENT, текущий символ - < Проверка на ЦБЗ, текущий символ - < Найденные ошибки в строке while(u>r+erhgeerg(e>=rwe+++r+788erwe++)) scr(eee,qee<) Отсутствует ; после функции Пропущено / или * или ** или + или - Идентификатор не может начинаться с цифры Не найден или не верный параметр _____________________________________________________________________ Обрабатываем строчку - while(i>77777u777) clrscr(,...,) Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 7 Проверка на ЦБЗ, текущий символ - 7 Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - c Проверка на PAR, текущий символ - , Проверка на IDENT, текущий символ - , Проверка на ЦБЗ, текущий символ - , Найденные ошибки в строке while(i>77777u777) clrscr(,...,) Отсутствует ; после функции Идентификатор не может начинаться с цифры Не найден или не верный параметр _____________________________________________________________________Обрабатываем строчку - while(4545>>445--- ; Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 4 Проверка на ЦБЗ, текущий символ - 4 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - Проверка на ЦБЗ, текущий символ - Проверка на FUNC, текущий символ - ; Проверка на IDENT, текущий символ - ; Найденные ошибки в строке while(4545>>445--- ; Отсутствует ) Предупреждение: отсутствует имя функции Не найден идентификатор или ЦБЗ Неизвестная знаковая конструкция _____________________________________________________________________ Обрабатываем строчку - while(i>=0); Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 0 Проверка на ЦБЗ, текущий символ - 0 Проверка на FUNC, текущий символ - ; Проверка на IDENT, текущий символ - ; Найденные ошибки в строке while(i>=0); Предупреждение: отсутствует имя функции _____________________________________________________________________ Обрабатываем строчку - while(i>=0) 544(); Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 0 Проверка на ЦБЗ, текущий символ - 0 Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - 5 Найденные ошибки в строке while(i>=0) 544(); Отсутствует ; после функции Предупреждение: отсутствует имя функции _____________________________________________________________________ Обрабатываем строчку - whilei>=0) clrscr();13 Найден While проверка началась с символа - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - i Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 0 Проверка на ЦБЗ, текущий символ - 0 Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - c Найденные ошибки в строке whilei>=0) clrscr();13 Отсутствует ( Предупреждение: Отсутствует условие () _____________________________________________________________________ Обрабатываем строчку - whilertt<=243+++344-23!=345 wwqwq; Найден While проверка началась с символа - r Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - r Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - = Проверка на ЦБЗ, текущий символ - = Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на FUNC, текущий символ - w Проверка на IDENT, текущий символ - w Найденные ошибки в строке whilertt<=243+++344-23!=345 wwqwq; Отсутствует ( Отсутствует ) Не найден идентификатор или ЦБЗ Не найден или не верный параметр _____________________________________________________________________ Обрабатываем строчку - while(dd>>3432*23432) Найден While проверка началась с символа - ( Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - d Проверка на AB Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 3 Проверка на ЦБЗ, текущий символ - 3 Проверка на TERM Проверка на O Проверка на IDENT, текущий символ - 2 Проверка на ЦБЗ, текущий символ - 2 Проверка на FUNC, текущий символ - Проверка на IDENT, текущий символ - Найденные ошибки в строке while(dd>>3432*23432) Отсутствует ; после функции Предупреждение: отсутствует имя функции Неизвестная знаковая конструкция Листинг программы ВАРИАHТ # 10 Синтаксический распознователь оператора цикла While Файл программы - А513.cpp