Методические указания (1114907), страница 8

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

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

FIRST(F) ={‘,’, ε} FOLLOW(F) = {)}

1. Построим множество пунктов. Для этого пронумеруем правила и добавим фиктивное нулевое правило. После этого грамматика примет вид:

1. D’ -> D

2. D -> i(P);

3. P -> iF

4. P -> ε

5. F -> ,iF

6. F -> ε

А) Нулевой пункт I₀ будет состоять из результата функции closure( { [D’ -> ∙D] } )

Б) Подсчитываем результат функции closure({[D’ -> ∙D]})

i) I₀={ D’ -> ∙D}; Поскольку пункт стоит перед нетерминалом D, то пытаемся добавить в I₀ пункт D -> ∙i(P); Такого пункта в I₀ нет, поэтому добавляем его.

ii) I₀ = { D’ -> ∙D, D -> ∙i(P);}. Поскольку пункт стоит только перед терминалами, а остальные нетерминалы уже проверялись, то множество пунктов I₀ сформировано.

В) Подсчитываем I₁ = goto(I₀, D) = closure({[D’ -> D∙]})

i) I₁ = {D’ -> D∙}. Поскольку пункт стоит только перед символами ε, то множество пунктов I₁ сформировано.

Г) Подсчитываем I₂ = goto(I₀, i) = closure({[D -> i∙(P);]})

i) I₂ = {D -> i∙(P);}. Поскольку пункт стоит только перед терминалами, то множество пунктов I₂ сформировано.

Д) Подсчитываем I₃ = goto(I₂, ‘(‘) = closure ({[D -> i(∙P);]}).

i) I₃ = {D -> i(∙P);}. Поскольку пункт стоит перед нетерминалом P, то пытаемся добавить в I₃ пункты P -> ∙iF и P -> ∙ . Таких пунктов в I₃ нет, поэтому добавляем их.

ii) I₃ = {D -> i(∙P); , P -> ∙iF, P -> ∙}. Поскольку пункт стоит

только перед терминалами, а остальные нетерминалы уже

проверялись, то множество пунктов I₃ сформировано.

Е) Подсчитываем I₄ = goto(I₃,P) = closure ({[D -> i(P∙);]}).

i) I₄ = {D -> i(P∙);}. Поскольку пункт стоит только перед терминалами, то множество пунктов I₄ сформировано.

Ж) Подсчитываем I₅ = goto(I₃, i) = closure({[P -> i∙F]}).

i) I₅ = {P -> i∙F}. Поскольку пункт стоит перед нетерминалом F, то пытаемся добавить в I₆ пункты F -> ∙,iF и F -> ∙ . Таких пунктов в I₅ нет, поэтому добавляем их.

ii) I₅ = {P -> i∙F, F -> ∙,iF, F -> ∙}. Поскольку пункт стоит

только перед терминалами, а остальные нетерминалы уже

проверялись, то множество пунктов I₅ сформировано.

З) Подсчитываем I₆ = goto(I₄, ‘)’) = closure({[D -> i(P)∙;]}).

i) I₆ = {D -> i(P)∙;}. Поскольку пункт стоит только перед

терминалами, то множество пунктов I₆ сформировано.

И) Подсчитываем I­₇ = goto(I₅, F) = closure({[P -> iF∙]}).

i) I₇ = {P -> iF∙}. Поскольку пункт стоит только перед

терминалами, то множество пунктов I₇ сформировано.

K) Подсчитываем I₈ = goto(I₅, ‘,’) = closure({[F ->,∙iF]}).

i) I₈ = {F ->,∙iF}. Поскольку пункт стоит только перед

терминалами, то множество пунктов I₈ сформировано.

И) Подсчитываем I₉ = goto(I₆, ;) = closure({[D -> i(P);∙]}).

i) I₉ = {D -> i(P);∙}. Поскольку пункт стоит только перед

терминалами, то множество пунктов I₉ сформировано.

Л) Подсчитываем I₁₀ = goto(I^­₈, i) = closure({[F ->,i∙F]}).

i) I₁₀ = {F ->,i∙F}. Поскольку пункт стоит перед нетерминалом F, то пытаемся добавить в I₁₀ пункты F -> ∙,iF и F -> ∙ . Таких пунктов в I₁₀ нет, поэтому добавляем их.

ii) I₁₀ = {F ->,i∙F, F -> ∙,iF, F -> ∙}. Поскольку пункт стоит

только перед терминалами, а остальные нетерминалы уже

проверялись, то множество пунктов I₁₀ сформировано.

М) Подсчитываем I₁₁ = goto(I₁₀, F) = closure({[F ->,iF∙]}).

i) I₁₁ = {F ->,iF∙}. Поскольку пункт стоит только перед

терминалами, то множество пунктов I₁₁ сформировано.

Л) Подсчитываем I₁₂ = goto(I₁₀, ‘,’) = closure({[F ->,∙iF]}).

i) I₁₂ = {F ->,∙iF}. Поскольку пункт стоит только перед

терминалами, то множество пунктов I₁₂ сформировано. Замечаем, что I_12­ = I₈, поэтому не формируем нового множества пунктов. Таким образом, результат этого шага I₈ = goto(I₁₀, ‘,’) = {F ->,∙iF}.

Н) Больше множеств пунктов построить нельзя, поскольку либо все пункты расположены либо после символов ε, либо не порождают новых состояний.

Приведем подпрограммы для обработки ошибок.

Множество пунктов для данной грамматики имеет вид:

• I₀ = {D’ -> ∙D, D -> ∙i(P);}

• I₁ = {D’ -> D∙}

• I₂ = {D -> i∙(P);}

• I₃ = {D -> i(∙P); , P -> ∙iF, P -> ∙}

• I₄ = {D -> i(P∙);}

• I₅ = {P -> i∙F, F -> ∙,iF, F -> ∙}

• I₆ = {D -> i(P)∙;}

• I₇ = {P -> iF∙}

• I₈ = {F ->,∙iF}

• I₉ = {D -> i(P);∙}

• I₁₀ = {F ->,i∙F, F -> ∙,iF, F -> ∙}

• I₁₁ = {F ->,iF∙}

1. Диаграмма переходов представляет собой ориентированный граф, вершинами которого являются состояния, а дугами – переходы между этими состояниями.

Матрица смежности этого графа будет иметь вид.

Диаграмма переходов, построенная на основании приведенной выше матрицы смежности, имеет вид:

1. Строим таблицу SLR-анализатора.

Рассматриваем последовательно каждое состояние, заполняя функции action и goto в таблице.

А) Для множества пунктов I₀ получаем action[I₀, i] = s2 по правилу 2.1. алгоритма 4.2., goto[I₀, D] = 1 по правилу 3 алгоритма 4.2..

Б) Для множества пунктов I₁ получаем action[I₁, $] = accept по правилу 5 алгоритма 4.2.

В) Для множества пунктов I₂ получаем action[I₂, (] = s3 по правилу 2.1. алгоритма 4.2.

Г) Для множества пунктов I₃ получаем action[I₃, )] = r3 по правилу 2.2. алгоритма 4.2., action[I₃, i] = s5 по правилу 2.1. алгоритма 4.2., goto[I₃, P] = 4 по правилу 3 алгоритма 4.2.

Д) Для множества пунктов I₄ получаем action[I₄, )] = s6 по правилу 2.1. алгоритма 4.2.

Е) Для множества пунктов I₅ получаем action[I₅, )] = r5 по правилу 2.2. алгоритма 4.2., action[I₅, ‘,’] = s8 по правилу 2.1. алгоритма 4.2., goto[I₅, F] = 7

Ж) Для множества пунктов I₆ получаем action[I₆, ;] = s9 по правилу 2.1. алгоритма 4.2..

З) Для множества пунктов I₇ получаем action[I₇, )] = r2 по правилу 2.2. алгоритма 4.2..

И) Для множества пунктов I₈ получаем action[I₈, i] = s10 по правилу 2.1. алгоритма 4.2.

К) Для множества пунктов I₉ получаем action[I₉, $] = r1 по правилу 2.2. алгоритма 4.2..

Л) Для множества пунктов I₁₀ получаем action[I₁₀, )] = r5 по правилу 2.2. алгоритма 4.2., action[I₁₀, ‘,’] = s8 по правилу 2.1. алгоритма 4.2., goto[I₁₀, F] = 11 по правилу 3 алгоритма 4.2.

М) Для множества пунктов I₁₁ получаем action[I₁₀, )] = r4 по правилу 2.2. алгоритма 4.2.

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

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