LR(k)-грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Управляющая программа анализатора)
(Управляющая программа анализатора: рефакторинг структур)
Строка 65: Строка 65:
 
*<tex>\mathtt{token}</tex> {{---}} входной символ.  
 
*<tex>\mathtt{token}</tex> {{---}} входной символ.  
 
Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:
 
Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:
  '''enum''' Cell
+
  '''struct''' Shift  { state: '''int''' } <font color="green">// переход в состояние с номером state</font>
    Shift  
+
  '''struct''' Reduce { rule: '''int''' } <font color="green">// свертка по правилу с номером rule</font>
    Reduce
+
  '''enum''' Result = Accept  <font color="green">// допуск </font>
    Error    <font color="green">// ошибка</font>
+
            | Error    <font color="green">// ошибка</font>
    Accept  <font color="green">// допуск </font>
+
                     
  '''struct''' Shift
+
'''enum''' Cell = Shift
    state: '''int''' <font color="green">// переход в стостояние state</font>
+
          | Reduce
  '''struct''' Reduce  
+
          | Result
    rule: '''int'''   <font color="green">// свертка по правилу rule</font>
 
 
 
Рузультатом работы управляющей программы будет:
 
  '''enum''' Result
 
    Accept  <font color="green">// допуск </font>
 
    Error    <font color="green">// ошибка</font>
 
  
 
=== Алгоритм ===
 
=== Алгоритм ===

Версия 23:24, 8 сентября 2015

Восходящий разбор (англ. Bottom-up parsing) предназначен для построения дерева разбора. Мы можем представить себе этот процесс как "свертку" исходной строки [math]w[/math] к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки [math]w[/math] и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.

LR(k)-грамматика

Определение

Определение:
Пусть [math]\Gamma =\langle \Sigma, N, E, P \rangle[/math]контекстно-свободная грамматика. Пополненной грамматикой (англ. augmented grammar), полученной из [math]\Gamma[/math], назовем грамматику [math]\Gamma' =\langle \Sigma', N', E_0, P' \rangle[/math], где [math]\Sigma' = \Sigma; N' = N \cup \{E_0\}; E_0 \notin N; P' = P \cup \{E_0 \to E\}[/math]


Определение:
Пусть [math]\Gamma' =\langle \Sigma', N', E_0, P' \rangle[/math] — пополненная грамматика для КС-грамматики [math]\Gamma[/math]. Грамматика [math]\Gamma[/math] является LR(k)-грамматикой, если из того, что для любых двух правосторонних выводов верно, что:
  • [math]E_0 \Rightarrow^* \beta A t z \Rightarrow \beta \alpha t z \Rightarrow^* w, [/math] если [math]|t|=k[/math] или [math]|t|\lt k, |z|=0 (z = \varepsilon)[/math]
  • [math]E_0 \Rightarrow^* \gamma B t z' \Rightarrow \gamma \xi t z' \Rightarrow^* w', [/math] если [math]|t|=k[/math] или [math]|t|\lt k, |z'|=0 (z' = \varepsilon)[/math]

следует, что [math]\beta \alpha = \gamma \xi[/math],

тогда [math]\beta = \gamma[/math] и [math]A = B[/math].

Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем [math]k[/math] символам неразобранной части строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).

LR(k) означает, что:

  • входная цепочка обрабатывается слева направо (англ. left-to-right parse),
  • выполняется правый вывод (англ. rightmost derivation),
  • для принятия решения используется не более [math]k[/math] символов цепочки (англ. k-token lookahead).

Замечание о пополненной грамматике

Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Действительно, если грамматика использует [math]E[/math] в правых частях правил, то свертка основы в [math]E[/math] не может служить сигналом приема входной цепочки. Свертка же в [math]E_0[/math] в пополненной грамматике служит таким сигналом, поскольку [math]E_0[/math] нигде, кроме начальной сентенциальной формы, не встречается.

Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненная грамматика имеет следующие правила:

[math] (0)\ E_0 \to E \\ (1)\ E \to Ea \\ (2)\ E \to a \\ [/math]

Если игнорировать [math]0[/math]-е правило, то, не заглядывая в правый контекст основы [math]Ea[/math], можно сказать, что она должна сворачиваться в [math]E[/math]. Аналогично основа [math]a[/math] безусловно должна сворачиваться в [math]E[/math]. Создается впечатление, что данная грамматика без [math]0[/math]-го правила есть LR(0)-грамматика. Что на самом деле неверно, в чём можно убедиться, рассмотрев процесс LR(0)-разбора.

LR-разборщик

Принцип переноса-свёртки

При LR(k)-анализе применяется метод перенос-свертка (англ. shift-reduce). Суть метода сводится к следующему:

  1. Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (операция перенос).
  2. Далее все символы совпадающей цепочки извлекаются из стека и на их место помещается нетерминал, находящийся в левой части этого правила (операция свертка).

Структура

Метод перенос-свертка использует следующие компоненты:

  • входная строка,
  • стек (для запоминания рассмотренных символов),
  • управляющая таблица (для выбора следующего действия — перенос или свертка),
  • автомат (для запоминания информации о текущем состоянии стека).

Управляющая программа анализатора

Управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.

Для запоминания строки запись в стек имеет вид: [math]s_0X_1s_1X_2...X_ms_m[/math], где [math]s_m[/math] — вершина стека. Каждый [math]X_i[/math] — символ грамматики (терминал или нетерминал), а [math]s_i[/math] — состояние автомата. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. [math]s_0[/math] — стартовое состояние автомата. Комбинация символа состояния на вершине стека и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в стеке, однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.

Обращение к таблице происходит следующим образом [math]\mathtt{T[state, token]}[/math], где

  • [math]\mathtt{state}[/math] — состояние автомата,
  • [math]\mathtt{token}[/math] — входной символ.

Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:

struct Shift  { state: int } // переход в состояние с номером state
struct Reduce { rule:  int } // свертка по правилу с номером rule
enum Result = Accept   // допуск 
            | Error    // ошибка  
                     
enum Cell = Shift
          | Reduce
          | Result

Алгоритм

  1. Программа читает символ из входной цепочки.
  2. Обращается к управляющей таблице.
  3. Совершает соответствующее действие.
  4. Возвращается к первому пункту, пока входная цепочка не закончится.

 Result algorithmLR(w: string)
     // curToken — указатель на первый символ в строке w
     while hasTokens()
         curState = top()
         if [math]\mathtt{T}[/math][curState, curToken] == Shift s 
             push(curToken)
             push(s)
             nextToken()
         else if [math]\mathtt{T}[/math][curState, curToken] == Reduce [math] A  \to \beta[/math] 
             for j = 1 to [math]|\beta |[/math]  
                 pop()
                 pop()
             s = top()
             push([math]A[/math])
             push(goto(s, [math]A[/math])) 
             Вывод правила: [math] A \to \beta[/math]
         else if [math]\mathtt{T}[/math][curState, curToken] == Accept 
             return Accept
         else 
             return Error     

Функция [math]goto[/math] получает состояние и символ грамматики и выдает состояние. Функция [math]goto[/math], строящаяся по грамматике [math]\Gamma[/math], есть функция переходов детерминированного магазинного автомата, который распознает язык, порождаемый грамматикой [math]\Gamma[/math].

См. также

Источники информации