Рассмотрим алгоритм построения направляющих множеств, для приведенной контекстно-свободной грамматики (такая грамматика не содержит леворекурсивных правил).

Скажем, что цепочка a называется аннулирующей, если из нее может быть получена пустая цепочка (a® *l).

Множество Перв(a) определяется как множество первых символов цепочек, которые можно получить из a.

Множество След (А), где А –нетерминальный символ, как множество символов, которые могут стоять за А в сентенциальных формах.

Пусть правило подстановки имеет вид А ®a, тогда через Напр(А ®a) обозначим направляющее множество для правила А ®a.

Если a не аннулирующая цепочка, то Напр(А ®a) = Перв(a).

Если a аннулирующая цепочка, то Напр(А ®a) = Перв(a) È След (А).

 

Необходимым условием обладания грамматикой признаком LL(I)-грамматики является не пересекаемость множеств направляющих символов, соответствующих правым частям альтернативных порождающих правил для каждого нетерминального символа.

 

Для языков, описываемых LL(I)-грамматикой, можно построить простые, надежные и достаточно небольшие синтаксические анализаторы. Основная трудность заключается в описании конкретного входного языка грамматикой, обладающей признаком LL(I)-грамматики. Однако обычно очень большое число конкретно свободных языков в САПР можно представить в требуемой форме.

Преимущества применения LL(I)-анализаторов:

1. Время синтаксического анализа входного текста пропорционально его длине, что позволяет отнести LL(I)-анализаторы к наиболее быстрым программам такого типа.

2. Анализатор имеет хорошие диагностические характеристики и обладает возможностью коррекции синтаксических ошибок.

3. Таблицы синтаксического разбора меньше, чем соответствующие таблицы в других методах синтаксического анализа.

4. LL(I)-разбор применим к достаточно широкому классу языков.

 

 СВЯЗЬ LL (I)-ГРАММАТИКИ С МП-АВТОМАТАМИ.

Для любой LL(I)-грамматики можно построить МП-автомат с одним состоянием, который будет принимать язык, порождаемой этой грамматикой.

Алгоритм построения МП-автомата для LL(I)-грамматики.

Итак, пусть дана LL(1) грамматика, Т- множество ее терминальных символов, N – множество нетерминальных символов, S – начальный символ, Р – множество правил подстановки.

Пусть А,Х – нетерминальные символы, t,r, t_n – терминальные символы, l - пустая цепочка, a, b - цепочки состоящие из любого числа терминальных и нетерминальных символов. Если некоторая цепочка a помещается в стек, то ее символы помещаются в порядке справа налево, что бы левый символ цепочки был на вершине стека.

Соответствующий этой грамматики МП-автомат будет иметь:

1. Внешний алфавит А=Т È{*};

2. Алфавит магазинной памяти М=NÈ{r|rÎT и содержится в цепочке a, которая либо имеет вид Хb и является правой частью правила подстановки, либо правой частью правила подстановки будет цепочка ta}:

3. Q – множество состояний автомата состоит из единственного состояния q, которое мы не будем указывать в командах автомата;

4. Начальное состояние автомата равно q;

5. Начальная запись в магазинной памяти S#, где S – начальный символ грамматики, # - маркер дна магазина;

6. Команды МП-автомата определяются следующим образом:

a. Если правило имеет вид A®ta, то этому правилу ставится в соответствие команда At®a сдвиг;

b. Если правило имеет вид A®a, где a = Хb, тогда для всех терминальных символов t_n из множества Напр(A®a) ставятся в соответствие команды А t_n ®a Стоп;

c. Если правило имеет вид A®l, тогда для всех терминальных символов t_n из множества Напр(A®l) ставятся в соответствие команды А t_n ®l Стоп;

d. Если правило имеет вид A®t, то этому правилу ставится в соответствие команда At®l Сдвиг;

e. Если по одной из команд МП-автомата, в магазин попадает терминальный символ t, то в этом случае формируется команда tt®lСдвиг;

f. Если *- знак конца строки, #-маркер конца стека, то формируется команда *#®Допустить.

 

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

 

 

 РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНОЙ РАБОТЫ

Для разработки LL(I)-синтаксического анализатора рекомендуется использовать МП-автомат, созданный во второй лабораторной работе.

При этом надо изменить команды МП-автомата

 

 

 Этапы выполнения лабораторной работы

Подготовительный этап:

 

1. Изучить основные сведения, приведенные в описании данной работы.

3. Ответить на все контрольные вопросы.

 

Этап проектирования

 

· Найти 20 слов языка, порождаемого грамматикой, определенной вариантом задания или выяснить закономерность, определяющую слова, входящие в этот язык.

· Построить направляющие множества для грамматики, определенной вариантом;

· Проверить является ли заданная грамматика LL(1) грамматикой;

· Построить МП-автомат, принимающий язык, порождаемый заданной грамматикой. На данном этапе команды автомата записать в виде таблицы.

· Записать команды автомата в стандартном виде.

· Проанализировать МП-автомат, разработанный во второй лабораторной работе. Внести необходимые изменения так, что бы он решал новую задачу.

План отчета

 

1. Название и цель работы.

2. 20 слов языка, порождаемого грамматикой, определенной вариантом задания или закономерность, определяющую слова, входящие в этот язык.

3. Направляющие множества для грамматики, определенной вариантом;

4. Проверка того, является ли заданная грамматика LL(1) грамматикой;

5. Таблица команд МП- автомата, принимающего язык порождаемый заданной грамматикой..

6. Текст программы.

7. Результаты работы LL(I)-анализатора как для правильных, так и ошибочных цепочек символов.

 

 

Варианты индивидуальных заданий

 

1. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®AB|bS                

A®aA|dB                     

B®AB|c                   

 

2. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®aAaB|bAbB                

A®dS| λ                               

B®cB|a                                

 

3. Множество терминальных символов V_t={a,b,c,d,m}.

Множество нетерминальных символов V_n={A,B,D}

Начальное состояние S=A

Правила подстановки:

A®aB|bA

B®cD| λ

D®dBd|m

 

4. Множество терминальных символов V_t={a,b,d,m,q}.

Множество нетерминальных символов V_n={X,Y,Z,S}

Начальное состояние S=S

Правила подстановки:

S®aXY| bYZ             

X®mXq| λ           

Y®bY|d                                 

Z®S|qZ                                                                  

 

5. Множество терминальных символов V_t={a,b,c,d,q,p}.

Множество нетерминальных символов V_n={X,Y,N,S}

Начальное состояние S=S

Правила подстановки:

S®aXY|XY                      

X®bY|cN| λ                           

N®qY|p                                 

Y®dN                                    

6. Множество терминальных символов V_t={x,y,c,m}.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®AB|xCB

A®yA|m

B®aC|c

C®bC|λ

 

 

7. Множество терминальных символов V_t={ x,y,c,m }.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®AB|xCB

A®yA| λ

B®aC|c

C®bC|m

 

8. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®aAaB|bAbB                

A®mS| λ                               

B®dmB|a                                

 

9. Множество терминальных символов V_t={a,b,c,d,m}.

Множество нетерминальных символов V_n={S,A,B,D}

Начальное состояние S=S

Правила подстановки:

S®aAa|bAb

A®aBa|bA

B®cD| λ

D®dBd|m

 

10. Множество терминальных символов V_t={a,b,d,m,q}.

Множество нетерминальных символов V_n={X,Y,Z,S}

Начальное состояние S=S

Правила подстановки:

S®aX| bYZ             

X®mXq| λ           

Y®bY|d                                     

Z®S|qZ        

 

11. Множество терминальных символов V_t={a,b,c,d,q,p}.

Множество нетерминальных символов V_n={X,Y,N,S}

Начальное состояние S=S

Правила подстановки:

S®aXY|XY                      

X®cN| λ                           

N®qY|p                                 

Y®dN                                    

12. Множество терминальных символов V_t={x,y,c,m}.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®AB|xCa

A®yA|m

B®aC|c

C®bC|λ

 

 

13. Множество терминальных символов V_t={ x,y,c,m,n }.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®An|CB

A®yA| λ

B®aB|c

C®bC|m

 

14. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®AB|bS                

A®aA| | λ                    

B®dB|c                   

 

                                                         

Контрольные вопросы

 

 

1.Что такое сентенциальная форма, предложение?

2.Что такое синтаксическое дерево?

3.Что такое неоднозначная грамматика?

4.Понятие восходящего и нисходящего разбора предложений?

5.Проблемы,возникающие при нисходящем и восходящем разборе предложений, с чем они связаны?

6.Каким образом решается проблема возвратов при восходящем разборе предложений?

7. Каким образом решается проблема возвратов при нисходящем разборе предложений?

    8.Дать определение S-грамматики.

9.Привести пример S-грамматики.

10.Привести пример LL(I)- грамматики.

11.Как LL(I)-грамматика связаны с S-грамматикой.

12.Как LL(I)-грамматика связана с МП-автоматом.

13.Можно ли язык, порождаемый LL(I)-грамматикой или S-грамматикой анализировать с помощью детерминированного конечного автомата? Ответ пояснить.

14.Дать определение фразы, основы. Когда эти понятия используются?

15.Что такое множество направляющих символов?

16.Каковы достоинства и недостатки LL(I)-анализаторов.

 

Литература:

1. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий, 2-е изд., М.: Вильямс, 2008.

 

2. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений, М.: Вильямс, 2002.

 

3.Р.И.Компаниец, Е.В.Маньков, Н.Е.Филатов, Системное программирование. Основы построения трансляторов. Санк-Петербург, 2000.

 

Оглавления

Лабораторная работа №1. 2

Лексический анализ. Детерминированный конечный автомат. Демонстрация работы детерминированного конечного автомата. 2

Теоретический материал, необходимый для выполнения лабораторной работы.. 2

Этапы выполнения лабораторной работы.. 4

План отчета. 5

Варианты индивидуальных заданий. 6

Контрольные вопросы.. 6

Лабораторная работа №2. 7

Детерминированного автомата с магазинной памятью.. 7

Теоретический материал, необходимый для выполнения лабораторной работы.. 7

Этапы выполнения лабораторной работы.. 9

План отчета. 10

Варианты индивидуальных заданий. 10

Контрольные вопросы.. 14

Лабораторная работа №3. 14

Разработка синтаксического анализатора предложений, порожденных LL(1)- грамматикой 14

Теоретический материал, необходимый для выполнения лабораторной работы.. 15

Этапы выполнения лабораторной работы.. 18

План отчета. 19

Варианты индивидуальных заданий. 20

Контрольные вопросы.. 22

Литература: 23

Оглавления. 23