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

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

G4 = ({B, C, S}, {a, b, c}, P, S) где P:

1. S → aSBC;

2. S → abc;

3. CB → BC;

4. bB → bb;

5. bC → bc;

6. cC → сc,

порождает язык { a ⁿ b ⁿ c ⁿ }, n ≥ 1.

По определению КЗ-грамматика не допускает правил: А → ε, где ε - пустая цепочка. Т.е. КС-грамматика с пустыми цепочками в правой части правил не является контекстно-зависимой. Наличие пустых цепочек ведет к грамматике без ограничений.

Условие:

1. По описанию языка построить порождающую грамматику.

2. Построить для трех примеров цепочки порождения.

Варианты:

Пример построения порождающей грамматики:

Задан язык:{ aⁿbⁿcⁿ | n≥1 }

Грамматика:

1. S → aSBC

2. S → aBC

3. CB → HB

4. HB → HC

5. HC → BC

6. aB → ab

7. bB → bb

8. bC → bc

9. cC →cc

Цепочка порождения aaa bbb ccc:

→₁ aSBC

→₁ aaSBCBC

→₂ aaaBCBCBC

→₃ aaaBHBCBC

→₄ aaaBHCCBC

→₅ aaaBBCCBC

→₃ aaaBBCHBC

→₄ aaaBBCHCC

→₅ aaaBBCBCC

→₃ aaaBBHBCC

→₄ aaaBBHCCC

→₅ aaaBBBCCC

→₆ aaabBBCCC

→₇ aaabbBCCC

→₇ aaabbbCCC

→₈ aaabbbcCC

→₉ aaabbbccC

→₉ aaabbbccc

Цепочка порождения aa bb cc:

→₁ aSBC

→₂ aaBCBC

→₃ aaBHBC

→₄ aaBHCC

→₅ aaBBCC

→₆ aabBCC

→₇ aabbCC

→₈ aabbcC

→₉ aabbcc

Цепочка порождения a b c:

→₂ aBC

→₆ abC

→₈ abc

Задача 4 «Построение таблицы SLR-анализатора»

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

Определение: Восходящий синтаксический анализ – такой вид синтаксического анализа, который пытается строить дерево разбора для входной строки, начиная с листьев (снизу) и работая по направлению к корню дерева (вверх).

В данной задаче будет рассмотрен метод восходящего синтаксического анализа, известный как синтаксический анализ типа «перенос/свертка» (ПС-анализ).

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

Определение: Рассмотрим наиболее простой метод LR-анализа, который называется SLR-анализом (Simple LR, простой LR). Недостатком этого метода является достаточно небольшое число грамматик, с которыми он работает, однако этот метод наиболее прост в реализации. Таблицу, построенную таким методом, будем называть SLR-таблицей, а синтаксический анализатор, работающий с SLR-таблицей, SLR-анализатором (а соответствующую грамматику – SLR-грамматикой).

Определение: LR(0)-пункт, или элемент грамматики G – продукция G с точкой в некоторой позиции правой части. Следовательно, продукция, A -> XYZ дает четыре пункта:

1. A -> ∙XYZ

2. A -> X∙YZ

3. A -> XY∙Z

4. A -> XYZ

Продукция A -> ε генерирует только один пункт, A -> ∙ . Интуитивно, пункт указывает, какую часть продукции мы уже увидели в данной точке в процессе синтаксического анализа. Например, первый пункт, приведенный выше, определяет, что во входном потоке мы ожидаем встретить строку, порождаемую XYZ. Второй пункт указывает, что у нас уже есть строка, порожденная X, и мы ожидаем получить из входного потока строку, порождаемую YZ.

Система LR(0)-пунктов, которую назовем канонической, обеспечивает основу для построения SLR-анализаторов. Для построения канонической LR(0)-системы грамматики мы определим расширенную грамматику и две функции – closure и goto.

Если G – грамматика со стартовым символом S, то G’, расширенная грамматика (augmented grammar) грамматика G, представляет собой G с новым стартовым символом S’ и продукцией S’ -> S. Назначение этой новой стартовой продукции – указать синтаксическому анализатору, когда он должен прекратить разбор и объявить о допущении входной строки. Таким образом, допуск строки происходит тогда и только тогда, когда синтаксический анализатор выполняет свертку, соответствующую продукции S’ -> S.

Операция замыкания (closure).

Если I – множество пунктов грамматики G, то closure(I) – множество пунктов, построенное из I по следующим правилам.

1. Изначально в closure(I) входят все пункты из I.

2. Если A -> α∙Bβ входит в closure(I) и B -> γ представляет собой продукцию, то добавляем в closure(I) пункт B -> ∙γ (если его там еще нет). Мы применяем это правило до тех пор, пока не внесем все возможные пункты в closure(I).

Наличие A -> α∙Bβ в closure(I) указывает, что в некоторый момент в процессе синтаксического анализа мы полагаем, что можем встретить во входном потоке подстроку, выводимую из Bβ. Но если имеется продукция B -> γ, то, естественно, мы также можем встретить в этот момент строку, выводимую из γ, поэтому включаем B -> ∙γ в closure(I).

Операция goto.

Второй полезной функцией является goto(I, X), где I является множеством пунктов, а X – символом грамматики. goto(I, X) определяется как замыкание (closure) множества всех пунктов [A -> α∙Bβ] ϵ I. Интуитивно, если I является множеством пунктов, допустимых для некоторого активного префикса γ, то goto(I, X) есть множество пунктов, допустимых для активного префикса γX.

Алгоритм построения C системы множества пунктов для расширенной грамматики G’

Приведем алгоритм, который позволяет построить каноническую систему LR(0)-пунктов для некоторой расширенной грамматики. Данный алгоритм использует описанные выше операции closure и goto.

procedure items(G’);

begin

C := {closure( { [S’ -> ∙S] } ) };

repeat

for каждое множество пунктов I в С и каждый символ грамматики X, такой, что goto(I, X) не является пустым и не принадлежит C do

добавить goto(I, X) к С

until больше нет множеств, которые можно добавить к C

end

Алгоритм 4.1.

Алгоритм построения таблицы SLR-анализатора.

Данный алгоритм строит функции action и goto SLR-анализа (эти функции будут описаны ниже при описании алгоритма LR-анализа (алгоритм 4.3.)). Он не дает однозначно определенные таблицы действий для всех грамматик, но он успешно работает для многих грамматик языков программирования. Данную грамматику G необходимо расширить до грамматики G’, и на основе G’ строим C – каноническую систему множества пунктов для G’ (алгоритм 4.1.). По системе C строим action, функцию действий синтаксического анализа, и goto, функцию переходов, в соответствии с приведенным далее алгоритмом. Он требует знания FOLLOW(A) для каждого нетерминала A грамматики.

Вход. Расширенная грамматика G’

Выход. Функции action и goto таблицы SLR-анализа для грамматики G’.

Алгоритм.

1. Построим C = {I₀, I₁, …, I_n} - систему множества LR(0)-пунктов для грамматики G’.

2. Состояние i строится на основе I_i. Действия синтаксического анализа для состояния i определяются следующим образом:

   1. Если [A -> α∙aβ] ϵ I_i и goto(I_i, a) = I_j, то определить action[i, a] как “перенос j”; здесь a должно быть нетерминалом;

   2. Если [A -> α∙] ϵ I_i, то определить action[i, a] как “свертка A -> α” для всех a из FOLLOW(A); здесь A не должно быть S’;

   3. Если [S’ -> S∙] ϵ I_i, то определить action[i, $] как “допуск”.

Если по этим правилам генерируются конфликтующие

действия, мы говорим, что грамматика не является SLR(1).

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

1. Переходы goto для состояния i и всех нетерминалов A строятся по правилу: если goto(I_i, A) = I_j, то goto[i,A] = j.

2. Все записи, не определенные по правилам (2) и (3), указываются как “ошибка”.

3. Начальное состояние синтаксического анализатора представляет собой состояние, построенное из множества пунктов, содержащего [S’ -> S].

Алгоритм 4.2.

Таблица синтаксического анализа, состоящая из функций action и goto, определяемых алгоритмом 4.2., называется SLR(1)-таблицей грамматики G. LR-анализатор, использующий SLR(1)-таблицу для грамматики G, называется SLR(1)-анализатором для G, а соответствующая грамматика - SLR(1)-грамматикой. Обычно при указании SLR(1) часть “(1)” опускается, поскольку мы не работаем более чем с одним символом предпросмотра.

Алгоритм LR-анализа.

LR-анализатор состоит из входного потока, выхода, стека, управляющей программы и таблицы синтаксического анализа, состоящей из двух частей (действие (action) и переход (goto)). Управляющая программа для всех LR-анализаторов одна и та же; изменяются только таблицы синтаксического анализа. Программа синтаксического анализа считывает символы из входного буфера по одному и использует стек для хранения строк вида s₀X₁s₁X₂s₂…X_ms_m (s_m находится на вершине стека). Каждый символ X_i является символом грамматики, а каждый s_i – символом, именуемым состоянием. Каждый символ состояния обобщает информацию, содержащуюся в стеке ниже его. Комбинация символа и состояния на вершине стека и текущего входного символа используется в качестве индекса таблицы синтаксического анализа и определяет дальнейшее действие – перенос или свертку. При реализации грамматические символы не обязаны появляться в стеке.

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

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