9 Mar 2022

Теория и практика разработки компиляторов
-----------------------------------------

В прошлом семестре была теория:
1) формальные языки и грамматики
   определение грамматики и языка;
2) классы грамматик (иерархия Хомского)
    u --> v       u, v <- (Sigma & N)*
                  u содержит хотя бы 1 нетерминал
                  S <- N
                  язык L -- это множество цепочек, выводимых из S
   -- грамматики без ограничений определяют слишком большой класс
      языков: рекурсивно перечислимые языки. Нет алгоритма, который
      позволяет определить принаждежность цепочки языку.
      
   -- контекстно зависимые языки:
    uAv --> uwv,   A <- N, |w| > 0 (неукорачивающая грамматика)
    Допускается также правило 
        S --> eps
    
    L = { a^n b^n c^n,  a, b, c <- Sigma, n > 0 }
          abc, aabbcc, aaabbbccc, ...
Грамматика этого языка:          
    S --> ABc | ABSc            ABABABABcccc
    Bc --> bc
    BA --> AB
    Bb --> bb
    Ab --> ab
    Aa --> aa
    
Вывод aabbcc

S => ABSc => ABABcc => ABAbcc => AABbcc => AAbbcc => Aabbcc => aabbcc

К сожалению, в нашей грамматике есть правило
    BA --> AB
которое не имеет требуемого вида: uAv --> uwv
Но можно место этого правила использовать 3 правила:
    BA --> FA
    FA --> FB
    FB --> AB
    
Любая неукоращивающая грамматика может быть преобразована
до контекстно зависимой, эквивалениной ей в смысле порожденного ей языка.    
    
   -- контекстно-свободные грамматики
      Правила имеют вид
        A --> w     A <- N, w <- (Sigma U N)*
                    в том числе w может быть пустым словом.

Теорема
Класс контекстно-свободных языков является подклассом
      контекстно зависимых языков.
     
Доказательство предоставляется алгоритмом избавления от eps-правил
    A --> eps   такие правила исключаем, если A != S
    
    B --> uAvAw  для таких правил добавляем еще правила
    B --> uvAw | uAvw | uvw
    
Обратное неверно: язык L = { a^n b^n c^n } не контекстно свободный.

Доказательство получается путем применения леммы о разрастании
(pumping lemma, лемма о накачке).

Пусть L -- КС-язык. Тогда существует число K:
    если цепочка u <- L, |u| >= K, то цепочку u можно разбить на 5 частей
        u = v x w y t
    так, что при синхронном повторении подслов x, y мы будем получать
    цепочки из L:
        для всякого i > 0 цепочка
            v x^i w y^i t 
        также принадлежит языку L
            v xx w yy t
            v xxx w yyy t
            v xxxx w yyyy t
            . . .
     Причем | x w y | <= K
     
Дерево вывода (синтаксическое дерево)
Пример: грамматика языка арифм. формул
    S -> S + S | S * S | a | ( S )
    
L состоит из правильный арифметических формул с буквой a в качестве операнда    
    a, a*a, (a), a+a*a, a+(a*a), (a+a)*a, ...
    
Рассмотрим вывод цепочки a+a*a    
S => S + S => S + S * S =>  S + S * a => S + a * a => a + a * a
                S
              / | \  
             S  +  S
             |    /|\      
             a   S * S
                 |   |
                 a   a   
Для той же цепочки можно построить другой правый вывод:
    
S => S * S => S * a => S + S * a => S + a * a => a + a * a
                S
              / | \  
             S  *  S
            /|\    |
           S + S   a
           |   |
           a   a
Такая грамматика называется неоднозначной.

Идея доказательства леммы о разрастании.

Возьмем достаточно длинную цепочку и ее дерево вывода...
В нем повторится какой-нибудь нетерминал на пути от корня к
терминальной вершине...    

Все естественный языки неоднозначны (есть фразы, которые можно
понять по разному).

Пусть x -- элемент идеала I кольца R, который был опеределен
при доказательстве теоремы 1.

Струи Арагвы и Куры узрели русские шатры.

Грамматику языка арифм. формул
    S -> S + S | S * S | a | ( S )
можно преобразовать в однозначную:
    S -> T | S + T
    T -> M | T * M
    M -> a | (S)
Формула a + a*a имеет только одно дерево вывода
(только 1 левый вывод и только 1 правый вывод)
                S
              / + \
             S     T
             |    /|\     
             T   T * M
             |   |   |
             M   M   a
             |   |
             a   a
Формальные языки должны быть однозначными.
Нужно уметь придумывать однозначные грамматики.

КС язык называется существенно неоднозначным, если
для него не существует однозначной грамматики.
Такие языки есть (пример в книге Axo, Ульман "Форм. языки").

Пример: язык правильной расстановки скобок (язык Дика).
        (()())()
Плохая грамматика этого языка:
        S -> () | S S | (S)
Неоднозначна, поскольку цепочка ()()()
имеет два правых вывода: S1 S2, S1 = ()(), S2 = ()
                         S1 S2, S1 = (), S2 = ()()        
Как изменить грамматику?
        S -> T | S T
        T -> () | (S)
Задача:
    L = { цепочки в алфавите Sigma={a, b}, в которых число букв a
                                               равно числу букв b }         
Придумать однозначную грамматику.

    -- автоматные, или праволинейные, или леволинейные, или регулярные языки.
    
Языки, задаваемые конечными автоматами.

Задача разбора противоположна задаче вывода.
Вывод -- начинаем с начального нетерминала S, применяем правила вывода,
         заканчиваем терминальной цепочкой.
Разбор (parsing) -- начинаем с терминальной цепочки, постепенно восстанавливам
         вывод цепочки (справа налево), в конце-концов сворачиваем ее
         к начальному нетерниналу (это при восходящем разборе; бувает еще
         рекурсивный, или нисходящий разбор).
         
===============================================================

16 Mar 2022

Прошлый раз я напомнил определение формальной грамматики Хомского и
языка, порожденного грамматикой.

Sigma -- алфавит терминалов
N -- алфавит метасимволов (нетерминалов)
L -- подмножество Sigma* (Sigma* -- множество конечных цепочек из элементов 
                                    Sigma, включая пустую цепочку eps)
Правила грамматики имеют вид
        u --> v       u, v <- (Sigma U N)*
                      u должна содержать хотя бы один нетерминал.
S <- N -- начальный нетерминал.
Вывод -- последовательность замен:
            tur => tvr
Язык, заданный грамматикой -- этo множество цепочек,
                              выводимых из S                                                          
В общем случае мы получаем класс рекурсивно перечислимых языков,
для которых алгоритмически неразрешима проблема принадлежности цепочки языку.

1. Контекстно-зависимые языки
   Правила имеют вид
    uAv --> uwv     A <- N, u,v,w <- (Sigma U N)*, |w| > 0
    также допускается одно правило 
    S --> eps
    
Прошлый раз было показано, что язык L = { a^n b^n c^n } контекстно зависимый
                                        abc, aabbcc, aaabbbccc, ...
                                        
2. Контекстно-свободные языки
   Правила имеют вид
   A --> u     A <- N, u <- (Sigma U N)*
   
Язык L = { a^n b^n c^n } не является контекстно свободным.
Доказывается с помощью леммы о разрастании:   

Если L -- бесконечный КС язык, то существует число K:
        ecли u <- L, |u| >= K   ==>
        u представима в виде 
            u = v x w y t     |x| + |y| > 0, |x w y| <= K
            причем цепочки
                v xx w yy t
                v xxx w yyy t
                v xxxx w yyyy t
                . . .
                v x^i w y^i t
            тоже принадлежат языку
                
Еще один пример не КС языка:
    L = { u u, u <- {a, b}* }
        
        
3. Право-линейные языки
        A --> uB, u -- терминальная цепочка
        A --> u
   Лево-линейные языки        
        A --> Bu, u -- терминальная цепочка
        A --> u
   Автоматные языки
   Регулярные языки
Теорема Клини утверждает, что классы автоматных и регулярных языков
совпадают.

Вернемся к контекстно свободным языкам.
Мы можем рассмотреть задачу вывода цепочки и обратную задачу
разбора: дана терминальная цепочка, надо восстановить ее вывод.

Утверждение: для КС языков проблема принадлежности цепочки языку
алгоритмически разрешима. Существует алгоритм, основанный на идеях
динамического программирования, работающий за время O(n^3).
Однако этот алгоритм не применяется на практике.
На практике применяются 2 алгоритма разбора:
1) рекурсивный, или нисходящий, или LL(1)-разбор;
   (класс грамматик, допускающих рекурсивный разбор, достаточно узкий).
        S -> S + S | S * S | a | ( S )
    плохая (неоднозначная грамматика a+a*a)   
    хорошая (однозначная) грамматика:
        S -> T | S + T
        T -> M | T * M
        M -> a | (S)
    Правый вывод формулы a+a*a
        S => S + T => S + T => S + T * M => S + T * a => S + M * a =>
             S + a * a => T + a * a => M + a * a => a + a * a
Но! Эта грамматика не допускает рекурсивный разбор.
Эту грамматику можно преобразовать так, чтобы она допускала рекурсивный
разбор:
    вместо правил S -> T | S + T
        S => S + T => S + T + T => S + T + T + ... + T => T + T + T + ... + T
    используем правила
        S -> T H
        H -> eps | + T H
        H -- это хвост формулы
2) восходящий, или LR(1)-разбор
        L -- цепочку чистается слева (Left) направо;
        R -- строятся правые (Right) выводы
        1 -- мы заглядываем на 1 символ вперед.
        
Восходящий разбор выполняется с помощью конечного автомата со
стековой памятью (с "магазинной" памятью).

Рассмотрим понятие LR-процесса.
Состояние LR-процесса задается
1) стеком LR-процесса -- цепочка из терминалов и нетерминалов,
                         которая наращивается с правого конца;
2) аванцепочкой из терминалов (это непрочитанная часть исходной цепочки).

Рассматриваем задачу восстановления вывода данной терминальной цепочки.

LR-процесс как бы противоположен процессу вывода цепочки.
Рассмотрим на примере цепочки a+a*a
Ее правый вывод формулы a+a*a
S => S + T => S + T => S + T * M => S + T * a => S + M * a =>
  => S + a * a => T + a * a => M + a * a => a + a * a

В LR-процессе имеются 2 типа действий:
1) сдвиг (shift) -- перенос первого символа аванцепочки в стек
         +------   
         |aBDaeW    abcab
         +------
   ==>
         +-------   
         |aBDaeWa   bcab
         +-------
2) свертка по правилу F -> eWa  (reduce)
   если слово в вершине стека есть правая часть некоторого правила,
   то оно заменяется на нетерминал в левой части правила
         +-------   
         |aBDaeWa   bcab
         +-------
    ==>
         +-----   
         |aBDaF     bcab
         +-----
    аванцепочка остается без изменений.
    
LR-процесс называется успешным, если по окончанию аванцепочка пустая,
а в стеке начальный метасимвол.    
    
Предложение
Существует взаимно однозначное соотвествие между LR-процессами
и правыми выводами в грамматике.   
    
На примере a+a*a
Правый вывод:
S => S + T => S + T * M => S + T * a => S + M * a =>
  => S + a * a => T + a * a => M + a * a => a + a * a
LR-процесс    
  +-- 
  |    a+a*a  сдвиг 
  +--
  +-- 
  |a   +a*a  свертка по правилу M -> a
  +--
  +-- 
  |M   +a*a  свертка по правилу T -> M
  +--
  +-- 
  |T   +a*a  свертка по правилу S -> T
  +--
  +-- 
  |S   +a*a  два раза сдвиг
  +--
  +--- 
  |S+a   *a  свертка по правилу M -> a
  +---
  +--- 
  |S+M   *a  свертка по правилу T -> M
  +---
  +--- 
  |S+T   *a  два раза сдвиг
  +---
  +----- 
  |S+T*a свертка по правилу M -> a
  +-----
  +----- 
  |S+T*M свертка по правилу T -> T*M
  +-----
  +--- 
  |S+T свертка по правилу S -> S+T
  +---
  +--      
  |S    успешное завершение LR-процесса    
  +--      
                
LR-процесс неоднозначен, если мы сделаем неверное действие,
то можем не довести LR-процесс до успешного завершения.

Для правильного определения действия, которое нужно делать на
каждом шаге LR-процесса, мы строим конечный детерминированный автомат.

Определим множество LR(0)-состояний разбора.
Определение:

ситуацией LR(0)-разбора называется правило грамматики
с отмеченной позицией в правой части. (Позиция отмечается
либо точкой, либо символом подчеркивания).
Пример: для правила
    S -> S + T
имеется 4 ситуации
    S -> _S + T, S -> S_+ T, S -> S+_T, S -> S+T_

Состоянием LR(0)-разбора называется конечное множество ситуаций.

Алгоритм построения множества состояний LR(0)-разбора на примере
несложной грамматики:
    int a, d, c;
    double e, f;
Рассмотрим язык, состоящий из цепочек
    t n;
    t n, n;
    t n, n, n;
Грамматика:
    S -> t L;
    L -> n | L, n
    
1) S -> _t L;

   делая в состоянии 1 сдвиг t, получаем состояние 2:

2) S -> t_L;
   L -> _n
   L -> _L, n

   делая в состоянии 2 сдвиг L, получаем состояние 3:
3) S -> t L_;
   L -> L_, n
     
   делая в состоянии 2 сдвиг n, получаем состояние 4:
4) L -> n_
   
   делая в состоянии 3 сдвиг ;, получим состояние 5:
5) S -> t L;_

   делая в состоянии 3 сдвиг "," получим состояние 6:
6) L -> L,_n
   
   делая в состоянии 6 сдвиг n, получим состояние 7:
7) L -> L,n_
   
Состояние допускает сдвиг терминала x, если есть ситуация, где после
подчеркивания стоит x;

Состояние допускает свертку по правилу A -> w,
если есть ситуация A -> w_ (подчеркивание после конца правой части).

В состоянии есть конфликт сдвиг-свертка, если оно допускает и сдвиг,
и свертку.
В состоянии есть конфликт свертка-свертка, если оно допускает
свертку по двум разным правилам.

Грамматика допускает LR(0)-разбор (или это LR(0)-грамматика),
если конфликтов нет.
Разобранная грамматика является LR(0)-грамматикой.   

============================================================

23 Mar 2022

Любую КС-грамматику можно преобразовать так,
чтобы было только одно правило с левой частью S
и S не встречался бы в правых частях правил.

Иначе берем новый нетерминал S'
и правило
    S' -> S
    S -> w
    . . .
    
В прошлый раз для грамматики
    S -> t L;
    L -> n | L, n
(язык
    t n;
    t n, n;
    t n, n, n;
)
было построено множество состояний LR(0)-разбора
(7 состояний):
1) S -> _t L;
2) S -> t_L;
   L -> _n
   L -> _L, n
3) S -> t L_;
   L -> L_, n
4) L -> n_
5) S -> t L;_
6) L -> L,_n
7) L -> L,n_
Как работает LR-парсер?
У него также есть стек и аванцепочка, только в стеке
хранятся не символы (терминалы и нетерминалы), а номера
состяний LR(0)-разбора. Но стек парсера как бы параллелен
стеку LR-процесса, хотя его глубина на единицу больше.

Выпишем таблицу состояний и переходов LR-парсера
Строки таблицы нумеруются номерами состояний, а столбцы -- терминалами и
                                              нетерминалами грамматики.

        t       n       ,       ;       L       S                                                  
--------------------------------------------------------
1     сдв->2   err     err     err     err     допуск
2      err    сдв->4   err     err   сдв->3    err
3      err     err    сдв->6  сдв->5   err     err
4     свертка по правилу L -> n
5     свертка по правилу S -> t L;
6      err    сдв->7   err     err     err     err
7     свертка по правилу L -> L,n
--------------------------------------------------------

Разберем работу LR-парсера для цепочки
    t n, n;

1) начало
+----    
|1      t n, n;
| 
+----
В соответствии с таблицей, в состоянии 1 делаем сдвиг t и переходим в
                           состояние 2
2) на вершине стека -- состояние 2, делаем сдвиг n и переходим в состояние 4
+----    
|1 2      n, n;
|  t 
+----
                           
3) в состоянии 4 действие -- свертка по правилу по правилу L -> n
+-----    
|1 2 4    , n;
|  t n
+-----
    Парсер выполняет свертку в 2 этапа:
    -- сначала из стека удаляется правая часть правила (если правая часть
       имеет размер k символов, то из стека удаляются верхние k элементов).                        
    А в начало аванцепочки мысленно добавляем левую часть правила
    +----    
    |1 2     L , n;
    |  t 
    +----
    И затем в состоянии на вершине стека (в нашем случае 2) делаем сдвиг L
    и в соответствии с таблицей парсера переходим в состояние 3
    
4) в состоянии 3, делая сдвиг ",", переходим в состояние 6  
+-----    
|1 2 3     , n;
|  t L
+-----

5) в состоянии 6 делаем сдвиг n и переходм в состояние 7
+-------    
|1 2 3 6    n;
|  t L ,
+-------

6) в состоянии 7 выполняем свертку по правилу L -> L , n
+---------  
|1 2 3 6 7   ;
|  t L , n
+---------
    Парсер выполняет свертку в 2 этапа:
    сначала выкидываем из стека правую часть правила и
    в аванцепочку добавляем левую часть правила:
    +---  
    |1 2          L ;
    |  t 
    +---
    И затем в состоянии 2 делаем сдвиг L и переходим в состояние 3
    
7) в состоянии 3 делаем сдвиг ";" и переходим в состояние 5
+-----  
|1 2 3         ;
|  t L
+-----
    
8) в состоянии 5 выполняем свертку по правилу S -> t L ;
+-------  
|1 2 3 5       
|  t L ;
+-------
    Сначала удаляем правую часть правила из стека и добавляем
    в аванцепочку левую часть правила:
    +--  
    |1       S
    |  
    +--
    Делаем в начальном состоянии 1 сдвиг S и переходим в состояние
    "успешное завершение разбора"
    
9) 
+--------  
|1 Допуск      
|  S
+--------

Помимо стека разбора (в котором содержатся номера состояний),
LR-парсер поддерживает также семантический стек, который может
содержать данные любого типа, которые соответствуют
узлам синтаксического дерева. Например, если мы строим дерево
вывода, то каждому нетерминалу в стеке LR-процесса будет соответствовать
поддерево с корнем, помеченным этим нетерминалом

+----------
|......AbCd
|      t h       t -- дерево, соответствующее A, h -- дерево для C
+----------
свертка по правилу F -> AbCd
+----------
|......F
|      s       s -- дерево, соответствующее F
+----------

  Дерево s:     F
             / / \ \
             t b  h d
   
Для арифметических формул семантический стек может хранить,
например, вычисленное значение, соответствующее данному нетерминалу.
Вычисление промежуточных значений происходит во время сверток:
+-------------
|  . . .F + F        свертка F -> F + F
|  . . .7   12
+------------ 
   
+----------
|  . . . F   
|  . . . 19
+---------- 
   
===========================================================

Отметим, что большинство грамматик не являются LR(0)-грамматиками,
т.е. множество LR(0)-состояний, построенное по описанному выше алгоритму,
содержит конфликты:
1) сдвиг-свертка, когда состояние допускает и сдвиг, и свертку;
2) свертка-свертка, когда состояние допускает свертку по двум
   разным правилам.
   
Рассмотрим простой пример грамматика, не являющейся LR(0)-грамматикой.
Вызов функции в языке C имеет вид
    f()
    f(e)        e от слова expression
    f(e, e)   
    f(e, e, e)
    . . .
Грамматика этого языка:
    S -> f(L)
    L -> eps | A            L -- список, который может быть и пустым
    A -> e | A, e           A -- непустой список
Построим множество LR(0)-состояний для этой грамматики

1)  S ->_f(L)
Делая сдвиг f в состоянии 1, получаем
2)  S -> f_(L)
Делая сдвиг ( в состоянии 2, получаем
3)  S -> f(_L)      конфликт сдвиг-свертка
    L -> _          свертка по правилу L -> eps
    L -> _A
    A -> _e         сдвиг e
    A -> _A, e
Делая сдвиг L в состоянии 3, получаем
4)  S -> f(L_)
Делая сдвиг A в состоянии 3, получаем
5)  L -> A_             конфлика сдвиг-свертка
    A -> A_, e
Делая сдвиг e в состоянии 3, получаем
6)  A -> e_
Делая сдвиг ) в состоянии 4, получаем
7)  S -> f(L)_
Делая сдвиг "," в состоянии 5, получаем
8)  A -> A,_e
Делая сдвиг e в состоянии 8, получаем
9)  A -> A,e_

В построенном множестве в двух состояниях 3 и 5 имеется
конфликт сдвиг-свертка. Таким образом, данная грамматика 
не является LR(0)-грамматикой. Как мы увидим, в данном 
случае конфликты разрешаются с помощью учета первого символа
аванцепочки. Например, в состоянии 3 свертка выполняется,
когда первый символ аванцепочки равен ")", а сдвиг --
когда он равен "e". Для учета возможных первых символов
аванцепочки и определения соответствующих действий строится
система состояний LR(1)-разбора; здесь единица означает
учет одного (т.е. первого) символа аванцепочки при принятии
решения об очередном действии.
===========================================================