- •1. Сообщения, информация. Обработка сообщений и обработка информации.
- •2. Понятие системы программирования. Парадигмы программирования.
- •3. Понятие транслятора и способы его реализации. Сравнительный анализ компиляторов, интерпретаторов и псевдокомпиляторов.
- •4.Процедурное программирование. Характеристики языков, реализующих процедурное программирование.
- •6!. Программный интерфейс между процедурами на языке Ассемблера и программой на языке Pascal.
- •7. Язык программирования с – основные конструкции и особенности.
- •8. Сравнительный анализ языков c и Pascal.
- •19. Распознаватели как способ определения языка. Виды распознавателей и их связь с грамматикой.
- •22. Контекстно- свободные языки и их свойства. Дерево вывода.
- •23. Распознаватель со стековой памятью.
- •27.Класс ll(1) грамматик и их свойства. Критерий принадлежности языка к классу ll(1).
- •28.Однопроходный синтаксический анализатор и его алгоритм работы. Управляющая таблица.
- •35.Понятие о фазах трансляции.
- •31.Построение лексического анализатора с помощью утилиты lex. Виды регулярных выражений.
- •33.Грамматики простого предшествования и операторного.
27.Класс ll(1) грамматик и их свойства. Критерий принадлежности языка к классу ll(1).
G называется простой LL(1) гр-ой, если для любого все его альтернативные цепочки начинаются различными терминалами, т.е. LL(k)для выполняется условие
Если в грамматике есть левая рекурсия, то это не LL(k)-грамматика. Критерий принадлежности языка класу LL(1). КС-гр-ка G является гр-ой класса LL(1) т.т.т.к. выполнены условия: для любого нетерминала A, имеющего 2 альтернативных вывода α и β Первая буква L в названии связана с тем, что входная цепочка читается слева направо, вторая L означает, что строится левый вывод входной цепочки, 1 – что на каждом шаге для принятия решения используется один символнепрочитанной части входной цепочки.
Язык для которого существует порождающая его LL(1)-грамматика, называют LL(1)-языком. Доказано, что проблема определения того, порождает ли грамматика LL-язык, является алгоритмически неразрешимой. Неоднозначная грамматика не является LL(1)-грамматикой.
28.Однопроходный синтаксический анализатор и его алгоритм работы. Управляющая таблица.
Однопроходный синтаксический анализатор использует предсказыв. алгоритм, этот алгоритм детерминированный, состоит из
(w,u,x) – входная лента
|
магазин – |X|<-- управл. таблица π – выходная лента
|α|
|$|
При чтении входной цепочки, находящейся на входной ленте, головка может заглядывать вперед на k очередных символов (эту цепочку называют аванцепочкой).
Управляющая таблица использует только 2 входа: символ, который находится во входном потоке и символ с вершины стека. Выходная лента содержит цепочку π, состоящую из номеров правил.
Управл. таблица руководит работой алгоритма. Алгоритм анализирует входную цепочку. На каждом такте сначала определяются аванцепочка u и верхний символ магазина X. Затем для определения того, что нужно делать рассматривается элемент M(X,u) управляющей таблицы.
Пусть u= .
1) -> если M(X,u)= . Здесь верхний символ магазина X заменяется цепочкой и к выходу добавляется номер правила i. Входная головка не сдвигается.
M-управляющая таблица.
2) выброс -> ,если M(a,u)=выброс и . Когда внешний символ магазина совпадает с текущим входным символом (1-м символом цепочки), он выбрасывается из магазина и входная головка сдвигается на 1 символ вправо.
3) допуск. Если алгоритм достигает конфигурации (e,$,π) работа прекращается и входная цепочка π называется разбором первоначальной входной цепочки. M($,e) всегда = допуск.
4)если алгоритм достигает конфигурации (x,Xα, π) и M(X,u)=ошибка, то разбор прекращается и выдается сообщение об ошибке.
Г({S,A},{a,b},P,S).
P: 1)S->aAS
2)S->b
3)A->a
4)A->bSA
w=abbab
(abbab,S$,e)-> (abbab,aAS$,1)
(bbab,AS$,1)-> (bbab,bSAS$,14)
(bab,SAS$,14)-> (bab,bAS$,142)
(ab,AS$,142)-> (ab,aS$,1423)
(b,S$,1423)->(b,b$,14232)
(e,$,14232)
Дерево разбора см. в тетради!
30.Алгоритм построения управляющей таблицы для LL(1) грамматики. Функция FIRST_k и FOLLOW_k.
{возвращает множество всевозможных терминальных цепочек длины не более k, которые могут появиться в процессе вывода из цепочки α}.
Пусть β некоторая цепочка. Пусть она встречается в процессе вывода грамматики, тогда
Рассмотрим алгоритм построения таблицы для LL(1) грамматики:M – управляющая таблица. Входы: символы из магазинного алфавита по горизонтали, терминальные символы и e по вертикали.
1)a) если есть продукция P:A→α и номер продукции i, то ячейка с координатами (A,a) заполняется (i,α), при этом a - это те терминал. символы, которые выводятся из α: и .
b) если же , то надо заполнять парой (i, α) ячейку (A,b), где b – те термин. символы, которые могут встретиться после A, т.е.
2)M(a,a)= выброс.
3)M($,e)=допуск.
4)в остальных случаях ошибка.
Пример.
G0: E->F+T|T
T->T*F|F
F->(E)|a
Есть левая рекурсия! Надо устранить))) , чтобы сделать LL(1).
E->TE`
E`->+TE`
E`->e
T->FT`
T`->*FT`
T`->e
F->(E)
F->a
{+,e}
{*,e}
{(,a}
{),e}
{+,e} Т.е. это грамматика LL(1).
Ячейки, в которых должна стоять ошибка, оставлены пустыми.