Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

α₂=*Е β₂=i

Е = β₁E’/ β₂E’

E’= α₁E’/ α₂E’/ε

E→ (E)E’

E → iE’

E’ → +EE’

E’ → *EE’

E’ → ε

1. Грамматика является левофакторизованной, потому что не встречается правил вида:

А →аС

А → аD

1. По преобразованной грамматике построим деревья разбора

1. i*(i+i)

1. i*i+i

1. (i+i)*(i+i)

Задача 3 «Построение таблицы предиктивного анализатора»

Теоретическая часть

Определение: Предиктивный анализатор представляет собой программу, содержащую процедуры для каждого нетерминального символа.

Определение: Анализ методом рекурсивного спуска (recursive-descent parsing) представляет собой способ нисходящего синтаксического анализа, при котором выполняется рад рекурсивных процедур для обработки входного потока (процедура связана с каждым нетерминальным символом грамматики).

Определение: Предиктивный анализ – анализ, при котором сканируемый символ однозначно определяет процедуру, выбранную для каждого нетерминала.

При построении предиктивного синтаксического анализатора можно создать его план в виде диаграммы переходов. Для построения диаграммы переходов предиктивного синтаксического анализатора на основе грамматики вначале следует устранить из нее левые рекурсии, а затем провести левую факторизацию. После этого для каждого нетерминала А выполняется следующее.

1. Создаем начальное и заключительное состояния.

2. Для каждой продукции А →Х₁Х₂…Х_n создаем путь от начального к заключительному состоянию с дугами, помеченными как Х₁, Х₂, …, Х_n.

FIRST и FOLLOW

Если α – произвольная строка символов грамматики, то определим FIRST(α) как множество терминалов, с которых начинаются строки, выводимые из α. Если α → ε, то ε € FIRST(α).

Определим FOLLOW(A) для нетерминала А как множество терминалов, которые могут располагаться непосредственно справа от А в некоторой сентенциальной форме, т е множество терминалов а, таких, что существует порождения вида S=>αAaβ для некоторых α и β.

Чтобы вычислить FIRST(X) для всех символов грамматики Х, будем применять следующее правило до тех пор, пока ни к одному из множеств FIRST не смогут быть добавлены ни терминалы, ни ε.

1. Если Х – терминал, то FIRST(X) = {X}.

2. Если имеется продукция Х → ε, добавим ε к FIRST(X).

3. Если Х – нетерминал и имеется продукция Х → Y₁Y₂…Y_k, то поместим а в FIRST(X), если для некоторого i a € FIRST(Y_i) и ε входит во все множества FIRST(Y₁), …, FIRST(Y_i-1), т е Y₁ … Y_i-1 =>ε. Если ε имеется во всех FIRST(Y_i), i=1..k, то добавляем ε к FIRST(X).

Теперь можно вычислить FIRST для любой строки Х₁Х₂… Х_n следующим образом. Добавим к FIRST(Х₁Х₂… Х_n) все не-ε символы из FIRST(Х₁). Добавим также все не-ε символы из FIRST(Х₂), если ε € FIRST(Х₁), все не-ε символы из FIRST(Х₃), если ε имеется как в FIRST(Х₁), так и в FIRST(Х₂) и т д. Добавим FIRST(Х₁Х₂… Х_n), если для всех i FIRST(Х_i) содержит ε.

Чтобы вычислить FOLLOW(A) для всех нетерминалов А, будем применять следующие правила до тех пор, пока ни к одному множеству FOLLOW нельзя будет добавить ни одного символа.

1. Поместим $ в FOLLOW(S), где S – стартовый символ, а $ - правый ограничитель входного потока.

2. Если имеется продукция А → αВβ, то все элементы множества FIRST(β), кроме ε помещаются в множество FOLLOW(В).

3. Если имеется продукция А → αВ или А →αВβ, где FIRST(β) содержит ε, то все элементы из множества FOLLOW(А) помещаются в множество FOLLOW(В).

Для построения таблицы предиктивного анализа данной грамматики G может использоваться приведенный далее алгоритм. Идея алгоритма в следующем. Предположим, что А → α представляет собой продукцию, у которой а € FIRST(α). Тогда синтаксический анализатор заменит А строкой α при текущем входном символе а. Единственная сложность возникает при α=ε или α=>ε. В этом случае мы снова должны заменить А на а, если текущий входной символ имеется в FOLLOW(А) или из входного потока получен $, который входит в FOLLOW(А).

Алгоритм «Построение таблицы предиктивного анализатора»

Вход. Грамматика G.

Выход. Таблица анализа М.

Метод.

1. Для каждой продукции грамматики А → α выполняем шаги 2 и 3.

2. Для каждого терминала а из FIRST(α) добавляем А → α в ячейку М[A,a].

3. Если в FIRST(α) входит ε, для каждого терминала b из FOLLOW(А) добавим А → α в ячейку М[A,b]. Если ε входит в FIRST(α), а $ - в FOLLOW(А), добавим А → α в ячейку М[A,$].

4. Сделаем каждую неопределенную ячейку таблицы М указывающей на ошибку.

Восстановление после ошибок

Правила восстановления после ошибок в «режиме паники»:

1. В качестве первого приближения можем поместить в синхронизирующее множество для нетерминала А все символы из множества FOLLOW(A). Если пропустим все токены до элемента из FOLLOW(A) и снимем А со стека, вероятно, мы сможем продолжить синтаксический анализ.

2. В качестве синхронизирующего множества для А недостаточно использовать FOLLOW(A). К синхронизирующему множеству конструкций нижнего уровня можно добавить символы, с которых начинаются конструкции более высокого уровня.

3. Если мы добавим символы из FIRST(A) в синхронизирующее множество для нетерминала А, станет возможным продолжение анализа в соответствии с А, когда во входном потоке появится символ из множества FIRST(A).

4. Если нетерминал может порождать пустую строку, то в качестве продукции по умолчанию в качестве продукции может использоваться, порождающая ε. Это может отсрочить обнаружение ошибки, зато не может вызвать ее пропуск, и сокращает число нетерминалов, которые должны быть рассмотрены в процессе восстановления после ошибки.

5. Если терминал на вершине стека не может быть сопоставлен с входным символом, то простейший метод состоит в снятии терминала со стека, генерации сообщения о вставке терминала в программу и продолжении синтаксического анализа.

Условие:

1. По описанию языка построить КС-грамматику.

2. Определить свойства полученной грамматики.

3. Если грамматика не обладает свойствами, требуемыми для построения таблицы предиктивного анализатора, то преобразовать грамматику к требуемой форме.

4. Определить значение функций FIRST и FOLLOW для разработанной грамматики.

5. Построить таблицу предиктивного анализатора.

6. Проверить правильность построения на трех примерах (один правильный, два неправильных).

Варианты:

Пример построения таблицы предиктивного анализатора:

1. Дано описание языка: <E> ::= <E> ‘+’ <E> | <E> ‘*’ <E> | ‘(‘ <E> ‘)’ | ‘i’

2. По описанию языка построили КС-грамматику:

3. Полученная грамматика является леворекурсивной и левофакторизованной. Преобразуем грамматику к требуемой форме.

α₁=+Е β₁=(Е)

Характеристики

Список файлов книги