Перейти к основному содержимому

LALR

Реализация: LALR-by-SLR.

  1. LR(0) item sets & translation table
  2. Extended grammar
  3. FIRST sets
  4. FOLLOW sets
  5. Action & goto table
    • initialize
    • gotos
    • shifts
    • reductions

Item set collection​

Item​

Item (элемент) — это правило грамматики с позицией.
Позиция как правило обозначается точкой.

  • A→⋅BA \to \cdot B означает "BB вот-вот встретится"
  • A→B⋅A \to B \cdot означает "BB только что встретился"

Алгоритм CLOSURE​

Если II — множество элементов грамматики GG, тогда CLOSURE(I)CLOSURE(I) (замыкание) — это множество элементов, построенное из II по следующим шагам:

  1. Множество инициализируется всеми элементами из II.
  2. Если элемент A→α⋅BβA \to \alpha \cdot B \beta находится во множестве (т.е. непосредственно за точкой следует нетерминал) и B→δB \to \delta — правило грамматики, то во множество добавляется элемент B→⋅δB \to \cdot \delta, если его ещё нет.
  3. Предыдущий шаг повторяется до тех пор, пока добавляются новые элементы.

Множество элементов, которые были добавлены на этапе инициализации, называется ядром.

Пример

Грамматика:

  1. S→NS \to N
  2. N→V=EN \to V=E
  3. N→EN \to E
  4. E→VE \to V
  5. V→xV \to x
  6. V→∗EV \to *E

Начальный набор: { S→⋅N }\Set{ S \to \cdot N }

{S→⋅N⇒{S→⋅NN→⋅V=EN→⋅E⇒{S→⋅NN→⋅V=EN→⋅EV→⋅xV→⋅∗EE→⋅V\begin{cases} \boxed{ S \to \cdot N } \end{cases} \rArr \begin{cases} \boxed{ S \to \cdot N } \\ \color{beige} N \to \cdot V=E \\ \color{beige} N \to \cdot E \end{cases} \rArr \begin{cases} \boxed{ S \to \cdot N } \\ N \to \cdot V=E \\ N \to \cdot E \\ \color{beige}V \to \cdot x \\ \color{beige}V \to \cdot *E \\ \color{beige}E \to \cdot V \end{cases}

Алгоритм GOTO​

Если II — множество элементов, а XX — символ грамматики, то GOTO(I,X)GOTO(I, X) определяется как замыкание таких элементов A→αX⋅βA \to \alpha X \cdot \beta, что элемент A→α⋅XβA \to \alpha \cdot X \beta принадлежит II.

Этот алгоритм используется для определения переходов между состояниями LR(0) автомата. Набор состояний конечного автомата соответствует множествам элементов, а GOTO определяет переход из II при вводе XX.

Расширенная грамматика​

Обозначения:

  • 0∗2≡I0→∗I2{_0 * _2} \equiv I_0 \overset{*}{\to} I_2 — переход от I0I_0 к I2I_2 через подачу на вход ∗*
  • 2E6≡I2→EI6{_2 E _6} \equiv I_2 \overset{E}{\to} I_6 — переход от I2I_2 к I6I_6 через подачу на вход EE
  • 0V3≡I0→VI3{_0 V _3} \equiv I_0 \overset{V}{\to} I_3 — переход от I0I_0 к I3I_3 через подачу на вход VV

Общий шаблон:

aSb→aXc cYd dZe{{\color{coral}_a} S _b} \to {{\color{coral}_a} X {\color{orange}_c}} \space {{\color{orange}_c} Y {\color{orange}_d}} \space {{\color{orange}_d} Z _e}

Для пустого правила конечная точка это первая цифра:

iXj→ϵ{{\color{coral}_i} X _j} \to \epsilon

FIRST и FOLLOW​

Множество FIRST для символа в КС-грамматике — это множество терминальных символов, которые могут появиться в начале строк, выводимых из символа.

Множество FOLLOW для символа в КС-грамматике — это множество терминальных символов, которые могут следовать непосредственно за данным символов в выводе (развёртывании).

Алгоритм построения FIRST​

# T  - terminals
# NT - non-terminals
# P  - rules in grammar

for a in [*T, EOF, EPS]:
  FIRST(a) = a

for A in NT:
  FIRST(A) = set()

while FIRST changes:
  for A -> b[1..k] in P:
    rhs = FIRST(b[1]) - { EPS }
    i = 1

    # adding first for eps-gen symbols
    while EPS in FIRST(b[i]) and i <= k - 1:
      rhs |= FIRST(b[i + 1]) - { EPS }
      i += 1
    if i == k and EPS in FIRST(b[k]):
      rhs |= { EPS }
    FIRST(A) |= rhs

Алгоритм построения FOLLOW​

# NT - non-terminals
# P  - rules in grammar

for A in NT:
  FOLLOW(A) = set()

FOLLOW(S) = { EOF }

while FOLLOW changes:
  for A -> b[1..k] in P:
    trailer = FOLLOW(A)
    for i in range(k, 0, -1):
      if b[i] in NT:
        FOLLOW(b[i]) |= trailer
        if EPS in FIRST(b[i]):
          trailer |= FIRST(b[i]) - { EPS }
        else:
          trailer = FIRST(b[i])
      else:
        trailer = FIRST(b[i])

Генерация таблицы​

Разрешение конфликтов:

  1. shift/reduce →\to shift
  2. reduce/reduce →\to reduce по более длинному правилу

Проблемные правила​

Для правила ниже возникает неоднозначность, которую нельзя разрешить имея lookahead в один токен.

params
  : '(' (param (',' param)* ','?)? ')'
  ;

Решением как правило является преобразование грамматики.

params
  : '(' param (',' param)* ')'
  | '(' (param ',')* ')'
  ;

Очень подробное описание на примере простой грамматики:
https://web.cs.dal.ca/~sjackson/lalr1.html