Лексический и синтаксический анализатор языка высокого уровня Государственное образовательное учреждение высшего профессионального образования Кубанский государственный технологический университет (КубГТУ) Армавирский механико-технологический институт Кафедра внутризаводского электрооборудования и автоматики ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по дисциплине: Теория языков программирования на тему: «Лексический и синтаксический анализатор языка высокого уровня» Государственное образовательное учреждение высшего профессионального образования Кубанский государственный технологический университет (КубГТУ) Армавирский механико-технологический институт Кафедра внутризаводского электрооборудования и автоматики Утверждаю Заведующий кафедрой ВЭА Проф. ____________ В.И. Куроедов ЗАДАНИЕ на курсовой проект Студенту группы____________курса__________________ специальности 230105(2204) «Программное обеспечение вычислительной техники и автоматизированных систем» Тема проекта: «Лексический и синтаксический анализатор языка высокого уровня» Содержание задания: Спроектировать и построить лексический и синтаксический анализаторы для заданного формального языка программирования. Построить и реализовать в лексическом анализаторе распознаватель лексем с заданной структурой: нагруженное дерево (один элемент дерева хранит один символ (букву входного алфавита) лексемы). Учебный язык включает директиву using, функцию main(), описание переменных, констант, цикла for, операторов присваивания, арифметические операции. За основу лексики, синтаксиса и семантики учебного языка принять стандарты языка программирования С#. Объем работы: Пояснительная записка 35 – 40 листов Графическая часть 2-3 листа формата А3 Рекомендуемая литература: 1. Ключко В.И. Теория вычислительных процессов и структур. Учебное пособие, - КубГТУ, 1998; 2. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб. Пособие, - М.: Финансы и статистика, 2004. – 320 с.: ил. 3. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. - СПб.: Питер, 2001. - 736 с. Срок выполнения проекта: с «___»____________ «___»_____________20___ г. Срок защиты «___»____________ 20___ г. Дата выдачи задания «___»_____________20___ г. Дата сдача проекта на кафедру «___»_____________20___ г. Руководитель канд. техн. наук, доцент _____________________ Задание принял студент______________________________ Нормативные ссылки ГОСТ Р ИСО 9001-2001 Системы менеджмента качества. Требования. ГОСТ 7.1-2003 СИБИД. Библиографическая запись. Библиографическое описание. Общие требования и правила составления. ГОСТ 19.101-77 ЕСПД. Виды программ и программных документов. ГОСТ 19.102-77 ЕСПД. Стадии разработки. ГОСТ 19.103-77 ЕСПД. Обозначение программ и программных документов. ГОСТ 19.105-78 ЕСПД. Общие требования к программным документам ГОСТ 19.202-78 ЕСПД. Спецификация. Требования к содержанию и оформлению. ГОСТ 19.404-79 ЕСПД. Пояснительная записка Требования к содержанию и оформлению. ГОСТ 19.701-90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения. Пояснительная записка к курсовому проекту содержит 37 листов, 8 рисунков, 3 таблицы, 9 литературных источников, 2 приложения. К пояснительной записке прилагается 1 диск с готовой программой и материалами к ней, а также графическая часть, состоящая из трех листов. СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, АВТОМАТ – РАСПОЗНАВАТЕЛЬ, РЕГУЛЯРНОЕ МНОЖЕСТВО, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ Объект: лексический и синтаксический анализатор. Цель: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов. Рассмотрен синтаксис заданного языка программирования, разработана грамматика регулярных множеств. Спроектированы автоматы для лексического анализа и распознавания лексем. Разработана формальная LL(1) грамматика для заданного языка программирования, спроектирован автомат с магазинной памятью для нисходящего анализа программы. Написана программа на языке высокого уровня Microsoft Visual C++ для лексического и синтаксического анализа текста на учебном языке программирования. Содержание Введение 1 Синтез лексического анализатора (сканера) 1.1 Описание синтаксиса формального языка программирования 1.2 Система регулярных выражений 1.3 Распознаватели констант и служебных слов 1.4 Управляющая таблица конечного автомата лексического анализа 2 Синтез синтаксического анализатора 2.1 Описание формальной грамматики 2.2 Построение множества ВЫБОР(n) 2.3 Построение управляющей таблицы 3 Описание программы 4 Результаты тестирования 5 Руководство пользователя Заключение Список используемой литературы Приложение А. Листинг лексического анализатора Приложение Б. Листинг синтаксического анализатора Введение Целью данного проекта является: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов. Задачи: написать транслирующую грамматику для учебного языка программирования; спроектировать и построить лексический анализатор; спроектировать и построить синтаксический анализатор. Входной информацией является файл, содержащий текст программы, написанной на учебном языке. Выходной информацией являются таблицы лексем и имен, а также подтверждение того, что код соответствует синтаксису. Результатом курсового проекта должна быть программа-анализатор, состоящая из двух частей: лексического анализатора, разбивающего исходный текст программы на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста заданной грамматике. 1 Синтез лексического анализатора (сканера) 1.1 Описание синтаксиса формального языка программирования Директива using позволяет в текущем пространстве имен использовать типы данных, определенные в другом пространстве имен. Синтаксис: using System.Text; В данном случае лексема using является ключевым словом. С помощью ключевого слова class определяются классы. Например: public class TestClass { // Определение полей и методов класса } Ключевое слово public определяет уровень доступности класса. Поля класса определяются как переменные: public class TestClass { public uint a, b = 35, i; public bool c, d; public const long int e = 9L; } Для каждого поля прописывается модификатор доступа (public) и тип поля (double, int или decimal). Методы класса определяются так же, как и обычные функции: public class TestClass { public int Main(Param1, Param2) { } } Как и для полей класса, для методов задается модификатор доступа и тип возвращаемого значения метода. Тело метода класса согласно учебному языку может содержать: –определение цикла со счетчиком: for (<выражение>; <условие>; <выражение>) { <блок операторов> } –вызовы процедур: write (<список параметров>); read (<список параметров>); –операторы присваивания: a = <выражение>; d *= <выражение>; f /= <выражение>; –арифметические выражения, содержащие бинарные операции: a = b - (c + d); Так же в тексте программы могут содержаться многострочные комментарии: /* многострочный комментарий */ Для записи идентификаторов используются буквы английского языка и цифры. Идентификаторы начинаются с буквы. Целые константы записываются арабскими цифрами. 1.2 Система регулярных выражений Для записи грамматики лексем языка применим форму Бэкуса-Наура. Для записи идентификаторов используются буквы английского языка и цифры. Идентификаторы начинаются с буквы. Синтаксис идентификаторов определяется праволинейной регулярной грамматикой: <S> -> L <I>( 1) <I> -> L <I>( 2) <I> -> D <I>( 3) <I> -> е( 4) где L - буква множества (A..Z), D - цифра множества (0..9), е - пустая цепочка или символ окончания лексемы. Целые константы записываются арабскими цифрами. Праволинейная грамматика целого числа: <ЦЧ> → +<Ц>|-<Ц> <Ц> → н<Ц> <Ц> → н|е 1.3 Распознаватели констант и служебных слов Заданная грамматика может бать реализована автоматом со следующими состояниями: S - состояние ожидания первого символа лексемы; I - состояние ожидания символов идентификаторов: буквы, цифры; С - состояние ожидания символов целой части числа; E -состояние ошибки; R - состояние допуска лексемы. Автомат переходит в допустимое состояние R из состояния I для идентификаторов и из состояния C для чисел. Регулярная грамматика для заданных условий записи лексем задается следующими множествами: Р: [P1, P2, … ,P4] – множество правил; G: [S, I, C, E, R] – множество состояний, где S – начальный символ; [0..9, A..Z, «–», «#», «(», «)», «*», «,», «.», «/», «:», «;», «{«, «}», «+», «=»] – множество входных символов, из них разделительные символы и уникальные лексемы [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»]. Символы пробел и табуляции означают конец лексемы. Эти символы не является лексемой и требуют выполнения операции «СДВИГ» над входной строкой. По символу пробел автомат допускает лексему и переходит в начальное состояние анализа следующего символа входной строки автомата. Символы: «–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=» являются одновременно разделительными знаками и началом следующей лексемы, даже если перед ними нет символа конца лексемы. Операция «СДВИГ» после этих символов не требуется, автомат допускает лексему и переходит в начальное состояние для анализа этих же символов. Таблица 1 – Таблица переходов автомата распознавателя идентификаторов L D e S I E S Нач. состояние I I I R E Ошибка R Допустить Идентификация служебных слов реализована автоматом распознавателя: нагруженное дерево (Рисунок 1). Множество служебных слов: BREAK CLASS CONST CONTINUE LONG INT BOOL FOR UINT PUBLIC READ USING WRITE. Рисунок 1 – Нагруженное дерево (часть) Структура данных для формирования нагруженного дерева: protected struct KeywordTree { public bool bIsWordEnd; public char cLetter; public List<KeywordTree> pNextList; } KeywordTree pKeywordsList; Процедура заполнения нагруженного дерева: private void Form1_Load(object sender, EventArgs e) {String[] KeyWords = {"BREAK", "CLASS", "CONST", "CONTINUE", "LONG", "BOOL", "FOR", "INT", "UINT", "PUBLIC", "READ", "USING", "WRITE"}; KeywordTree p, q; pKeywordsList = new KeywordTree(); pKeywordsList.cLetter = '#'; pKeywordsList.pNextList = new List<KeywordTree>(); pKeywordsList.bIsWordEnd = true; for(int i = 0; i < KeyWords.Length; i++) {String KeyWord = KeyWords[i]; p = pKeywordsList; for (int j = 0; j < KeyWord.Length; j++) {if (p.pNextList.Count == 0) {q = new KeywordTree(); q.cLetter = KeyWord[j]; q.pNextList = new List<KeywordTree>(); //если последний символ в ключ. слове q.bIsWordEnd = (j + 1 == KeyWord.Length) ? (q.bIsWordEnd = true) : (q.bIsWordEnd = false); p.pNextList.Add(q); p = q; } else {bool bIsAlready = false; for (int k = 0; k < p.pNextList.Count; k++) if (p.pNextList[k].cLetter == KeyWord[j]) {bIsAlready = true; p = p.pNextList[k]; break; } if (bIsAlready == false) {q = new KeywordTree(); q.cLetter = KeyWord[j]; q.pNextList = new List<KeywordTree>(); q.bIsWordEnd = false; p.pNextList.Add(q); p = q; }}}}} Функция идентификации служебных слов: private bool IsKeyword(String sLexeme) {int j, k; KeywordTree p = pKeywordsList; for (j = 0; j < sLexeme.Length; j++) {if (p.pNextList.Count == 0) break; else {bool bIsFound = false; for (k = 0; k < p.pNextList.Count; k++) if (p.pNextList[k].cLetter == sLexeme[j]) {bIsFound = true; p = p.pNextList[k]; break; } if (!bIsFound) break; }} return ((j == sLexeme.Length) && (p.bIsWordEnd)); } 1.4 Управляющая таблица конечного автомата лексического анализа Управляющая таблица лексического анализатора для заданной выше грамматики показана в таблице 2. Листинг программы, реализующей данную управляющую таблицу, приведен в приложении А. При составлении таблицы использовались следующие обозначения: – первым символом указывается состояние, в которое переходит автомат при поступлении соответствующего символа; – символ «+» означает добавление входного символа к лексеме; – символ «>>» означает сдвиг входной строки на один символ. Таблица 2 – Управляющая таблица конечного автомата лексического анализатора Spaces Letters Digits Symbols S S, >> I, +, >> C, +, >> R, +, >> C R E C, +, >> R I R I, +, >> I, +, >> R E Ошибка R S, Допустить Spaces – множество символов пробела (сам пробел и знак табуляции); Letters – множество букв латинского алфавита [A..Z, «_»]; Digits – множество арабских цифр [0..9]; Symbols – множество разделительных символов [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»]. 2 Синтез синтаксического анализатора 2.1 Описание формальной грамматики Грамматика целевого символа: ( 1) <S> -> using <USING_LIST> <NEXT> ( 2) <S> -> public <CLASS> <NEXT> ( 3) <NEXT> -> ; <S> ( 4) <NEXT> -> e Грамматика описания using: ( 5) <USING_LIST> -> ID <NEXT_USING> ( 6) <NEXT_USING> -> . <USING_LIST> ( 7) <NEXT_USING> -> e Грамматика описания класса: ( 8) <CLASS> -> class ID { <CLASS_BODY> } ( 9) <CLASS_BODY> -> public <DEF> <NEXT_BODY> (10) <NEXT_BODY> -> ; <CLASS_BODY> (11) <NEXT_BODY> -> e Грамматика описания определения полей и методов класса: (12) <DEF> -> uint <DEF_LIST> (13) <DEF> -> bool <DEF_LIST> (14) <DEF> -> const long int <DEF_LIST> (15) <DEF_LIST> -> ID <NEXT_DEF> (16) <NEXT_DEF> -> ( <VAR_LIST> ) { <OPER_LIST> } (17) <NEXT_DEF> -> , <VAR_LIST> (18) <NEXT_DEF> -> = <EXPR> <VAR_LIST> (19) <NEXT_DEF> -> e (20) <VAR_LIST> -> ID <NEXT_VAR> (21) <NEXT_VAR> -> , <VAR_LIST> (22) <NEXT_VAR> -> = <EXPR> <VAR_LIST> (23) <NEXT_VAR> -> e Грамматика описания списка операторов: (24) <OPER_LIST> -> <OPERATOR> <NEXT_OPER> (25) <NEXT_OPER> -> ; <OPER_LIST> (26) <NEXT_OPER> -> e Грамматика описания операторов: (27) <OPERATOR> -> for ( ID = <EXPR> ; <COND> ; ID <LET> ) { <OPER_LIST> } (28) <OPERATOR> -> break (29) <OPERATOR> -> continue (30) <OPERATOR> -> write ( <VAR_LIST> ) (31) <OPERATOR> -> read ( <VAR_LIST> ) (32) <OPERATOR> -> ID <LET> (33) <LET> -> = <EXPR> (34) <LET> -> * = <EXPR> (35) <LET> -> / = <EXPR> Грамматика описания арифметического выражения: (36) <EXPR> -> ( <EXPR> ) <OPERATION> (37) <EXPR> -> ID <OPERATION> (38) <EXPR> -> NUM <OPERATION> (39) <OPERATION> -> + <EXPR> (40) <OPERATION> -> - <EXPR> (41) <OPERATION> -> e Грамматика описания условия: (42) <COND> -> ( <COND> ) <RELATION> (43) <COND> -> <EXPR> <RELATION> (44) <RELATION> -> > <COND> (45) <RELATION> -> < <COND> (46) <RELATION> -> = = <COND> (47) <RELATION> -> e 2.2 Построение множества ВЫБОР(n) Построение множества ПЕРВ(n). Шаг 0. Для построения множества ПЕРВ(n) = FIRST(1, A), где А - нетерминал в правой части n – го правила, определим множества первых символов, стоящих в начале правых частей правил, для каждого нетерминала в левой части правил. ПЕРВ(<S>) using public ПЕРВ(<NEXT>) ; ПЕРВ(<USING_LIST>) ID ПЕРВ(<NEXT_USING>) . ПЕРВ(<CLASS>) class ПЕРВ(<CLASS_BODY>) public ПЕРВ(<NEXT_BODY>) ; ПЕРВ(<DEF>) uint bool const ПЕРВ(<DEF_LIST>) ID ПЕРВ(<NEXT_DEF>) ( , = ПЕРВ(<VAR_LIST>) ID ПЕРВ(<NEXT_VAR>) , = ПЕРВ(<OPER_LIST>) ПЕРВ(<NEXT_OPER>) ; ПЕРВ(<OPERATOR>) for break continue write read ID ПЕРВ(<LET>) = * / ПЕРВ(<EXPR>) ( ID NUM ПЕРВ(<OPERATION>) + - ПЕРВ(<COND>) ( ПЕРВ(<RELATION>) > < = Шаг 1. Внесем во множество первых символов ПЕРВ(n)i для каждого правила символы, стоящие в начале правых частей правил. Индекс i = 0 – номер итерации. ПЕРВ(1) 0 using ПЕРВ(2) 0 public ПЕРВ(3) 0 ; ПЕРВ(4) 0 ПЕРВ(5) 0 ID ПЕРВ(6) 0 . ПЕРВ(7) 0 ПЕРВ(8) 0 class ПЕРВ(9) 0 public ПЕРВ(10) 0 ; ПЕРВ(11) 0 ПЕРВ(12) 0 uint ПЕРВ(13) 0 bool ПЕРВ(14) const ПЕРВ(15) 0 ID ПЕРВ(16) 0 ( ПЕРВ(17) 0 , ПЕРВ(18) = ПЕРВ(19) 0 ПЕРВ(20) 0 ID ПЕРВ(21) 0 , ПЕРВ(22) = ПЕРВ(23) 0 ПЕРВ(24) 0 <OPERATOR> ПЕРВ(25) 0 ; ПЕРВ(26) 0 ПЕРВ(27) 0 for ПЕРВ(28) 0 break ПЕРВ(29) 0 continue ПЕРВ(30) 0 write ПЕРВ(31) 0 read ПЕРВ(32) 0 ID ПЕРВ(33) 0 = ПЕРВ(34) 0 * ПЕРВ(35) 0 / ПЕРВ(36) 0 ( ПЕРВ(37) 0 ID ПЕРВ(38) NUM ПЕРВ(39) 0 + ПЕРВ(40) 0 - ПЕРВ(41) 0 ПЕРВ(42) 0 ( ПЕРВ(43) 0 <EXPR> ПЕРВ(44) 0 > ПЕРВ(45) 0 < ПЕРВ(46) 0 = ПЕРВ(47) 0 Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), определенное на шаге 0. ПЕРВ(1) 1 using ПЕРВ(2) 1 public ПЕРВ(3) 1 ; ПЕРВ(4) 1 ПЕРВ(5) 1 ID ПЕРВ(6) 1 . ПЕРВ(7) 1 ПЕРВ(8) 1 class ПЕРВ(9) 1 public ПЕРВ(10) 1 ; ПЕРВ(11) 1 ПЕРВ(12) 1 uint ПЕРВ(13) 1 bool ПЕРВ(14) 1 const ПЕРВ(15) 1 ID ПЕРВ(16) 1 ( ПЕРВ(17) 1 , ПЕРВ(18) 1 = ПЕРВ(19) 1 ПЕРВ(20) 1 ID ПЕРВ(21) 1 , ПЕРВ(22) 1 = ПЕРВ(23) 1 ПЕРВ(24) 1 for break continue write read ID <OPERATOR> ПЕРВ(25) 1 ; ПЕРВ(26) 1 ПЕРВ(27) 1 for ПЕРВ(28) 1 break ПЕРВ(29) 1 continue ПЕРВ(30) 1 write ПЕРВ(31) 1 read ПЕРВ(32) 1 ID ПЕРВ(33) 1 = ПЕРВ(34) 1 * ПЕРВ(35) 1 / ПЕРВ(36) 1 ( ПЕРВ(37) 1 ID ПЕРВ(38) 1 NUM ПЕРВ(39) 1 + ПЕРВ(40) 1 - ПЕРВ(41) 1 ПЕРВ(42) 1 ( ПЕРВ(43) 1 ( ID NUM <EXPR> ПЕРВ(44) 1 > ПЕРВ(45) 1 < ПЕРВ(46) 1 = ПЕРВ(47) 1 Шаг 3. Если ПЕРВ(n)i+1 ≠ ПЕРВ(n)i, то i = i + 1 и перейти к шагу 2, иначе закончить. Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), определенное на шаге 0. ПЕРВ(1) 2 using ПЕРВ(2) 2 public ПЕРВ(3) 2 ; ПЕРВ(4) 2 ПЕРВ(5) 2 ID ПЕРВ(6) 2 . ПЕРВ(7) 2 ПЕРВ(8) 2 class ПЕРВ(9) 2 public ПЕРВ(10) 2 ; ПЕРВ(11) 2 ПЕРВ(12) 2 uint ПЕРВ(13) 2 bool ПЕРВ(14) 2 const ПЕРВ(15) 2 ID ПЕРВ(16) 2 ( ПЕРВ(17) 2 , ПЕРВ(18) 2 = ПЕРВ(19) 2 ПЕРВ(20) 2 ID ПЕРВ(21) 2 , ПЕРВ(22) 2 = ПЕРВ(23) 2 ПЕРВ(24) 2 for break continue write read ID ПЕРВ(25) 2 ; ПЕРВ(26) 2 ПЕРВ(27) 2 for ПЕРВ(28) 2 break ПЕРВ(29) 2 continue ПЕРВ(30) 2 write ПЕРВ(31) 2 read ПЕРВ(32) 2 ID ПЕРВ(33) 2 = ПЕРВ(34) 2 * ПЕРВ(35) 2 / ПЕРВ(36) 2 ( ПЕРВ(37) 2 ID ПЕРВ(38) 2 NUM ПЕРВ(39) 2 + ПЕРВ(40) 2 - ПЕРВ(41) 2 ПЕРВ(42) 2 ( ПЕРВ(43) 2 ( ID NUM ПЕРВ(44) 2 > ПЕРВ(45) 2 < ПЕРВ(46) 2 = ПЕРВ(47) 2 Шаг 3. Если ПЕРВ(n)i+1 ≠ ПЕРВ(n)i , то i = i + 1 и перейти к шагу 2, иначе закончить. Построение множества ПЕРВ(А). Множества ПЕРВ(А) необходимо для определения множеств СЛЕД(А). Шаг 1. Для построения множества ПЕРВ(А) = FIRST(1, A), где А - нетерминал в правой части правил, определим множества первых символов, стоящих в начале правых частей правил, для каждого нетерминала в левой части правил. ПЕРВ(<S>) using public ПЕРВ(<NEXT>) ; ПЕРВ(<USING_LIST>) ID ПЕРВ(<NEXT_USING>) . ПЕРВ(<CLASS>) class ПЕРВ(<CLASS_BODY>) public ПЕРВ(<NEXT_BODY>) ; ПЕРВ(<DEF>) uint bool const ПЕРВ(<DEF_LIST>) ID ПЕРВ(<NEXT_DEF>) ( , = ПЕРВ(<VAR_LIST>) ID ПЕРВ(<NEXT_VAR>) , = ПЕРВ(<OPER_LIST>) <OPERATOR> ПЕРВ(<NEXT_OPER>) ; ПЕРВ(<OPERATOR>) for break continue write read ID ПЕРВ(<LET>) = * / ПЕРВ(<EXPR>) ( ID NUM ПЕРВ(<OPERATION>) + - ПЕРВ(<COND>) <EXPR> ( ПЕРВ(<RELATION>) > < = Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), i=0. ПЕРВ(<S>)0 using public ПЕРВ(<NEXT>)0 ; ПЕРВ(<USING_LIST>)0 ID ПЕРВ(<NEXT_USING>)0 . ПЕРВ(<CLASS>)0 class ПЕРВ(<CLASS_BODY>)0 public ПЕРВ(<NEXT_BODY>)0 ; ПЕРВ(<DEF>)0 uint bool const ПЕРВ(<DEF_LIST>)0 ID ПЕРВ(<NEXT_DEF>)0 ( , = ПЕРВ(<VAR_LIST>)0 ID ПЕРВ(<NEXT_VAR>)0 , = ПЕРВ(<OPER_LIST>)0 for break continue write read ID ПЕРВ(<NEXT_OPER>)0 ; ПЕРВ(<OPERATOR>)0 for break continue write read ID ПЕРВ(<LET>)0 = * / ПЕРВ(<EXPR>)0 ( ID NUM ПЕРВ(<OPERATION>)0 + - ПЕРВ(<COND>)0 ( ID NUM ПЕРВ(<RELATION>)0 > < = Шаг 3. Выполнение шага 2 привело к изменению множеств ПЕРВ(А), поэтому повторим шаг 2. Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), i=1. ПЕРВ(<S>)1 using public ПЕРВ(<NEXT>)1 ; ПЕРВ(<USING_LIST>)1 ID ПЕРВ(<NEXT_USING>)1 . ПЕРВ(<CLASS>)1 class ПЕРВ(<CLASS_BODY>)1 public ПЕРВ(<NEXT_BODY>)1 ; ПЕРВ(<DEF>)1 uint bool const ПЕРВ(<DEF_LIST>)1 ID ПЕРВ(<NEXT_DEF>)1 ( , = ПЕРВ(<VAR_LIST>)1 ID ПЕРВ(<NEXT_VAR>)1 , = ПЕРВ(<OPER_LIST>)1 for break continue write read ID ПЕРВ(<NEXT_OPER>)1 ; ПЕРВ(<OPERATOR>)1 for break continue write read ID ПЕРВ(<LET>)1 = * / ПЕРВ(<EXPR>)1 ( ID NUM ПЕРВ(<OPERATION>)1 + - ПЕРВ(<COND>)1 ( ID NUM ПЕРВ(<RELATION>)1 > < = Шаг 3. Дальнейшее выполнения шага 2 не приведет к изменению множеств ПЕРВ(А), поэтому закончим. Построение множества СЛЕД(А). Множества СЛЕД(А) строятся для всех нетрминальных символов грамматики методом последовательного приближения. Шаг 1. Внесем во множество последующих символов СЛЕД(А) = FOLLOW(1, A) для каждого нетерминала А все символы, которые в правых частях правил встречаются непосредственно за символом А; i=0. СЛЕД(<S>)0 СЛЕД(<NEXT>)0 СЛЕД(<USING_LIST>)0 <NEXT> СЛЕД(<NEXT_USING>)0 СЛЕД(<CLASS>)0 <NEXT> СЛЕД(<CLASS_BODY>)0 } СЛЕД(<NEXT_BODY>)0 СЛЕД(<DEF>)0 <NEXT_BODY> СЛЕД(<DEF_LIST>)0 СЛЕД(<NEXT_DEF>)0 СЛЕД(<VAR_LIST>)0 ) СЛЕД(<NEXT_VAR>)0 СЛЕД(<OPER_LIST>)0 } СЛЕД(<NEXT_OPER>)0 СЛЕД(<OPERATOR>)0 <NEXT_OPER> СЛЕД(<LET>)0 ) СЛЕД(<EXPR>)0 <VAR_LIST> ; ) <RELATION> СЛЕД(<OPERATION>)0 СЛЕД(<COND>)0 ; ) СЛЕД(<RELATION>)0 Шаг 2. Внесем пустую цепочку (или символ конца строки) во множество последующих символов для целевого символа <S>. СЛЕД(<S>)0