М.Ю. Харламов, ВНУ им. В.Даля, 2009

получает строку токенов от лексического анализатора и проверяет, может ли эта строка по­ рождаться грамматикой исходного языка сообщает о всех выявленных ошибках выходом СА является некоторое представление дерева разбора входного потока токенов Тема 5. Синтаксический анализ Лексический анализатор Синтаксический анализатор Прочие задачи фазы анализа Таблица символов Исходная программа Токен Запрос токена Дерево разбора

Типы ошибок лексические лексические (например неверно записанные идентификаторы, ключевые слова или операторы…) синтаксические синтаксические (например арифметические выражения с несбалансированными скобками) семантические семантические (такие как операторы, применяемые к несовместимым с ними опе­рандам) логические логические (например бесконечная рекурсия) Стратегии восстановления после ошибок режим паники режим паники (пропуск входных символы по одному до токена-разделителя) уровень фразы уровень фразы (попытка выполнить локальную коррекцию оставшегося входного потока) продукции ошибок продукции ошибок (расширение грамматики языка продукциями, порождающими ошибочные конструкции) глобальная коррекция глобальная коррекция (ряд алгоритмов, допускающих минимально возможное количество изменений) Тема 5. Синтаксический анализ

Построение дерева вывода «сверху вниз»: Помещается вершина, соответствую­щая аксиоме S К 1 ому символу входной цепочки определяется правило S X 1 X 2..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X 1, и т.д., до правила Y a... (а VT). Процесс применяется для следующего самого левого терминального сим­вола Тема 5. Синтаксический анализ S a S a X1X1 X2X2 … ……………… Y S a X1X1 X2X2 … Y Z ………… $$$

Модель нерекурсивного предиктивного синтаксического анализатора Тема 5. Синтаксический анализ Программа предсказывающего анализатора X Y Z $ a+b$ Таблица анализатора Стек Входной буфер Выходной поток

Xa X - символ на вершине стека; a - текущий входной символ 1. X = a = $: анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты 2. X = a $: анализатор удаляет X из стека и продвигает указатель входного потока на следующий символ 3. X - терминал, и X a: анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку. 4. X – терминал: анализатор обращается к таблице M[X, a]: M[X, a] – правило для X: анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается. M[X, a] - ошибка: анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку Тема 5. Синтаксический анализ

FIRST (α) - множество терминалов, с которых начинаются строки, выводимые из α. Если α *e, то e также принадлежит FIRST (α) Тема 5. Синтаксический анализ Вычисление FIRST для символов грамматики: 1) Если X - терминал, то положить FIRST(X) = {X}; если X - терминал, положить FIRST(X) =. 2) Если в P имеется правило X e, то добавить e к FIRST(X). 3) Пока ни к какому множеству FIRST(X) нельзя уже будет доба­вить новые элементы, выполнять: если X - терминал и имеется правило вывода X Y 1 Y 2...Y k, то включить a в FIRST(X), если a FIRST(Y i ) для некоторого i, 1 i k и e принадлежит всем FIRST(Y 1 ),..., FIRST(Y i-1 ), то есть Y 1... Y i-1 e. Если e принадлежит FIRST(Y i ) для всех i = 1, 2,..., k, то добавить e к FIRST(X). Вычисление FIRST для символов грамматики: 1) Если X - терминал, то положить FIRST(X) = {X}; если X - терминал, положить FIRST(X) =. 2) Если в P имеется правило X e, то добавить e к FIRST(X). 3) Пока ни к какому множеству FIRST(X) нельзя уже будет доба­вить новые элементы, выполнять: если X - терминал и имеется правило вывода X Y 1 Y 2...Y k, то включить a в FIRST(X), если a FIRST(Y i ) для некоторого i, 1 i k и e принадлежит всем FIRST(Y 1 ),..., FIRST(Y i-1 ), то есть Y 1... Y i-1 e. Если e принадлежит FIRST(Y i ) для всех i = 1, 2,..., k, то добавить e к FIRST(X). Вычисление FIRST для цепочки: 1) Вычислить FIRST(X) для каждого X (VN VT). 2) Положить FIRST(X 1 X 2... X n ) =. 3) Добавить к FIRST(X 1 X 2... X n ) все не e-элементы из FIRST(X 1 ). Добавить к нему также все не e-элементы из FIRST(X 2 ), если e FIRST(X 1 ); не e- элементы из FIRST(X 3 ), если e FIRST(X 1 ) и e FIRST(X 2 ), и т.д. Наконец, добавить цепочку e к FIRST(X 1 X 2... X n ), если e FIRST(X i ) для всех i. Вычисление FIRST для цепочки: 1) Вычислить FIRST(X) для каждого X (VN VT). 2) Положить FIRST(X 1 X 2... X n ) =. 3) Добавить к FIRST(X 1 X 2... X n ) все не e-элементы из FIRST(X 1 ). Добавить к нему также все не e-элементы из FIRST(X 2 ), если e FIRST(X 1 ); не e- элементы из FIRST(X 3 ), если e FIRST(X 1 ) и e FIRST(X 2 ), и т.д. Наконец, добавить цепочку e к FIRST(X 1 X 2... X n ), если e FIRST(X i ) для всех i.

FOLLOW (A) для терминала A - множество терминалов a, которые могут появиться непосредственно справа от A в неко­торой сентенциальной форме грамматики (S αAaβ для некоторых α, β (N U T) * ) Тема 5. Синтаксический анализ Вычисление FOLLOW для терминалов грамматики G(VN, VT, P, S): 1) Положить FOLLOW(X) = для каждого символа X VN. 2) Добавить $ к FOLLOW(S). 3) Если в P есть правило вывода A Bβ, где, β е (VN VT) * то все элементы из FIRST (β), за исключением e, добавить к FOLLOW (B). 4) Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять: если в P есть правило A B или A Bβ, где FIRST(β) содержит e (т.е. β * e), то все элементы из FOLLOW (A) добавить к FOLLOW(B). Вычисление FOLLOW для терминалов грамматики G(VN, VT, P, S): 1) Положить FOLLOW(X) = для каждого символа X VN. 2) Добавить $ к FOLLOW(S). 3) Если в P есть правило вывода A Bβ, где, β е (VN VT) * то все элементы из FIRST (β), за исключением e, добавить к FOLLOW (B). 4) Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять: если в P есть правило A B или A Bβ, где FIRST(β) содержит e (т.е. β * e), то все элементы из FOLLOW (A) добавить к FOLLOW(B).

Дана грамматика G = ({E, E', T, T', F}, {id, +,, (,)}, P, E) E TET' FT E' +TET' e E' eF (E) T FTF id FIRST(E) = FIRST(T) = FIRST(F) = {(, id} FIRST(E') = {+, e} FIRST(T ) = {*, e} FOLLOW(E) = FOLLOW (E') = {),$} FOLLOW(T) = FOLLOW(T ) = {+,), $} FOLLOW(F) = {+,*,),(, id, $} Тема 5. Синтаксический анализ

Построение таблицы предсказывающего анализатора Тема 5. Синтаксический анализ Вход. КС-грамматика G = (VN, VT, P, S). Выход. Таблица M[A, a] предсказывающего анализатора, A VN, a VT {$}. Метод. Для каждого правила вывода A грамматики выполнить шаги 1 и 2. После этого выполнить шаг 3. 1) Для каждого терминала a из FIRST( ) добавить A α к M[A, a]. 2) Если e FIRST ( ), добавить A к M[A, b] для каждого терминала b из FOLLOW (A). Кроме того, если e FIRST( ) и $ FOLLOW ( A), добавить A к M[A, $]. 3) Положить все неопределенные входы равными ошибка. Вход. КС-грамматика G = (VN, VT, P, S). Выход. Таблица M[A, a] предсказывающего анализатора, A VN, a VT {$}. Метод. Для каждого правила вывода A грамматики выполнить шаги 1 и 2. После этого выполнить шаг 3. 1) Для каждого терминала a из FIRST( ) добавить A α к M[A, a]. 2) Если e FIRST ( ), добавить A к M[A, b] для каждого терминала b из FOLLOW (A). Кроме того, если e FIRST( ) и $ FOLLOW ( A), добавить A к M[A, $]. 3) Положить все неопределенные входы равными ошибка.

Предсказывающий анализатор, построенный для LL(1)-грамматики, называется LL(1)- анализатором L - входная цепочка читается слева направо L - строится левый вывод входной цепочки 1 - на каждом шаге для приня­тия решения используется один символ непрочитанной части входной цепочки LL(1)-грамматика не может быть неоднозначной или леворекурсивной и должна удовлетворять след.условиям для продукции A и A 1) FIRST( ) FIRST( ) = 2) Если e FIRST( ), то FIRST( ) FOLLOW(A) = Тема 5. Синтаксический анализ

Методы нисходящего разбора не в состоянии работать с леворекурсивными грамматиками, поэтому требуется преобразование грамматики, которое устранило бы из нее левую рекурсию. Левую рекурсию (A Aα), можно удалить следующим способом. Сначала группируем A -правила: A Aα 1 | Aα 2 |... | Aα m |β 1 |β 2 |... | β n, где никакая из строк β i не начинается с A. Затем заменяем этот набор правил на A β 1 A' | β 2 A' |... | β n A' A' α 1 A' | α 2 A' |... | α m A' | e где A' - новый терминал. Тема 5. Синтаксический анализ S Aa|b A Ac|Sd|e S Aa|b A Ac|Sd|e S Аа|b А bdА'|А' А' сА'|аdА'|e S Аа|b А bdА'|А' А' сА'|аdА'|e

Когда существует неопределенность, какую из двух альтернатив надо использовать для развертки терминала A, нужно применять алгоритм левой факторизации stmt if expr then stmt else stmt | if expr then stmt 1) Для каждого терминала A ищем самый длинный префикс α, общий для двух или более его альтернатив. Заменяем все A-правила A αβ 1 | αβ 2 |... | αβ n | z на A αA' | z 2) A' β 1 |β 2 |... | β n где A' - новый терминал Тема 5. Синтаксический анализ S if E then S | if E then S else S | a E b S if E then S | if E then S else S | a E b S if E then SS' | a S' else S | e E b S if E then SS' | a S' else S | e E b

Суть алгоритма заключается в последовательности рекурсивных вызовов процедур разбора. В допускаемой грамматике возможны только 2 варианта правил: А, (VN VT)* и это единственное правило для А А a 1 1 | a 2 2 | … | a n n, i: a i VT, i (VN VT) * и если i j, то а i а j 1) Для каждого терминального символа A VN грамматики G(VN, VT, P, S) строится процедура разбора, которая получает на вход цепочку символов а и положение считывающей головки в цепочке i процедура разбора ищет среди P правило вида А a, a VT, (VN VT)*, первый символ правой части которого совпадал бы с текущим символом входной цепочки а = i. Если такого правила не найдено, то цепочка не принимается. Иначе, запоминается номер правила и, когда а = i считывающая головка передвигается (увеличивается i), а для каждого терминального символа в цепочке рекурсивно вызывается процедура разбора этого символа 2) Для начала разбора входной цепочки нужно вызвать процедуру для символа S с параметром i=1 Тема 5. Синтаксический анализ

void A(){//A u 1 |u 2 |... |u k if (InSym FIRST(u i )) //только одному! if (parse(u i )) result("A u i "); else error(); else //Вариант 1: if (имеется правило A u i такое, что u i * e) //Вариант 1: if (InSym FOLLOW (A)) result("A u i "); else error(); //Конец варианта 1 //Вариант 2: result(" A u i "); //Конец варианта 2 if (нет правила A u i такого, что u * e) error(); } void A(){//A u 1 |u 2 |... |u k if (InSym FIRST(u i )) //только одному! if (parse(u i )) result("A u i "); else error(); else //Вариант 1: if (имеется правило A u i такое, что u i * e) //Вариант 1: if (InSym FOLLOW (A)) result("A u i "); else error(); //Конец варианта 1 //Вариант 2: result(" A u i "); //Конец варианта 2 if (нет правила A u i такого, что u * e) error(); }