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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Управляющая программа анализатора)
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 4 участников)
Строка 1: Строка 1:
'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерево разбора]]. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к правилу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивный, чем нисходящий, но зато позволяет разбирать большее множество грамматик.
+
'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерева разбора]]. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.
  
 
== LR(k)-грамматика ==
 
== LR(k)-грамматика ==
 +
=== Определение ===
 +
 
{{Определение
 
{{Определение
 
|id=def_augmented_grammar)  
 
|id=def_augmented_grammar)  
 
|definition=
 
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободная]] грамматика. '''Пополненной грамматикой''' (англ. ''augmented grammar''), полученной из <tex>\Gamma</tex>, назовем грамматику <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex>, где <tex>\Sigma' = \Sigma; N' = N \cup \{S'\}; S' \notin N; P' = P \cup \{S' \to S\}</tex>
+
Пусть <tex>\Gamma =\langle \Sigma, N, E, P \rangle</tex> {{---}} [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободная]] грамматика. '''Пополненной грамматикой''' (англ. ''augmented grammar''), полученной из <tex>\Gamma</tex>, назовем грамматику <tex>\Gamma' =\langle \Sigma', N', E_0, P' \rangle</tex>, где <tex>\Sigma' = \Sigma; N' = N \cup \{E_0\}; E_0 \notin N; P' = P \cup \{E_0 \to E\}</tex>
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|id=def_LR_K  
 
|id=def_LR_K  
 
|definition=
 
|definition=
Пусть <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> явяется '''LR(k)-грамматикой''', если для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов]]:
+
Пусть <tex>\Gamma' =\langle \Sigma', N', E_0, P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> является '''LR(k)-грамматикой''', если из того, что для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов]] верно, что:
* <tex>S' \Rightarrow^* \beta A t z \Rightarrow \beta \alpha t z  \Rightarrow^* w,  </tex> если <tex>|t|=k</tex> или <tex>|t|<k, |z|=0 (z = \varepsilon)</tex>
+
* <tex>E_0 \Rightarrow^* \beta A t z \Rightarrow \beta \alpha t z  \Rightarrow^* w,  </tex> если <tex>|t|=k</tex> или <tex>|t|<k, |z|=0 (z = \varepsilon)</tex>
* <tex>S' \Rightarrow^* \gamma B t z' \Rightarrow \gamma \xi t z' \Rightarrow^* w',  </tex> если <tex>|t|=k</tex> или <tex>|t|<k, |z'|=0 (z' = \varepsilon)</tex>
+
* <tex>E_0 \Rightarrow^* \gamma B t z' \Rightarrow \gamma \xi t z' \Rightarrow^* w',  </tex> если <tex>|t|=k</tex> или <tex>|t|<k, |z'|=0 (z' = \varepsilon)</tex>
  
верно, что <tex>\beta \alpha = \gamma \xi</tex>,  
+
следует, что <tex>\beta \alpha = \gamma \xi</tex>,  
  
следует, что <tex>\beta = \gamma</tex> и <tex>A = B</tex>
+
тогда <tex>\beta = \gamma</tex> и <tex>A = B</tex>.
 
}}
 
}}
Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем <tex>k</tex> символам неразобранной строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).
+
Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем <tex>k</tex> символам неразобранной части строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).
  
LR(k) означает, что  
+
LR(k) означает, что:
* входная цепочка обрабатывается слева направо (англ. ''left-to-right parse'');
+
* входная цепочка обрабатывается слева направо (англ. ''left-to-right parse''),
* выполняется правый вывод (англ. ''rightmost derivation'');
+
* выполняется правый вывод (англ. ''rightmost derivation''),
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
+
* для принятия решения используется не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'').
  
====Замечание о попролненной грамматике====
+
===Замечание о пополненной грамматике===
  
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречается.
+
Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Действительно, если грамматика использует <tex>E</tex> в правых частях правил, то свертка основы в <tex>E</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>E_0</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>E_0</tex> нигде, кроме начальной сентенциальной формы, не встречается.
  
Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненая грамматика имеет следующие правила:  
+
Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненная грамматика имеет следующие правила:  
  
 
<tex>
 
<tex>
(0)\ S' \to S \\
+
(0)\ E_0 \to E \\
(1)\ S \to Sa \\
+
(1)\ E \to Ea \\
(2)\ S \to a \\
+
(2)\ E \to a \\
 
</tex>
 
</tex>
  
Если игнорировать <tex>0</tex>-е правило, то, не заглядывая в правый контекст основы <tex>Sa</tex>, можно сказать, что она должна сворачиваться в <tex>S</tex>. Аналогично основа <tex>a</tex> безусловно должна сворачиваться в <tex>S</tex>. Создается впечатление, что данная грамматика без <tex>0</tex>-го правила есть LR(0)-грамматика. С учетом же <tex>0</tex>-го правила, после свертки в <tex>S</tex>, просматривая <tex>k=0</tex> символов, нельзя определить, делать ли свертку в <tex>S'</tex>, следовательно это не LR(0)-грамматика. Получили противоречие.
+
Если игнорировать <tex>0</tex>-е правило, то, не заглядывая в правый контекст основы <tex>Ea</tex>, можно сказать, что она должна сворачиваться в <tex>E</tex>. Аналогично основа <tex>a</tex> безусловно должна сворачиваться в <tex>E</tex>. Создается впечатление, что данная грамматика без <tex>0</tex>-го правила есть LR(0)-грамматика. Что на самом деле неверно, в чём можно убедиться, рассмотрев процесс [[LR(0)-разбор|LR(0)-разбора]].
--------- TODO тут надо либо дать более формальное объяснение, либо объяснить почему k не должно меняться от пополнения грамматики.
 
----------------
 
  
 
== LR-разборщик ==
 
== LR-разборщик ==
Строка 45: Строка 45:
 
=== Принцип переноса-свёртки ===
 
=== Принцип переноса-свёртки ===
 
При LR(k)-анализе применяется метод '''перенос-свертка''' (англ. ''shift-reduce''). Суть метода сводится к следующему:
 
При LR(k)-анализе применяется метод '''перенос-свертка''' (англ. ''shift-reduce''). Суть метода сводится к следующему:
* Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (операция '''перенос''').  
+
# Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (операция '''перенос''').  
* Далее все символы совпадающей цепочки извлекаются из стека и на их место помещается нетерминал, находящийся в левой части этого правила (операция '''свертка''').  
+
# Далее все символы совпадающей цепочки извлекаются из стека и на их место помещается нетерминал, находящийся в левой части этого правила (операция '''свертка''').
  
 
=== Структура ===
 
=== Структура ===
 
Метод '''перенос-свертка''' использует следующие компоненты:
 
Метод '''перенос-свертка''' использует следующие компоненты:
* Входная строка  
+
* входная строка,
* Стек (для запоминания рассмотренных символов)
+
* стек (для запоминания рассмотренных символов),
* Управляющая таблица (для определения, какое действие применить - перенос или свертку)
+
* управляющая таблица (для выбора следующего действия {{---}} '''перенос''' или '''свертка'''),
* Автомат (для запоминания информации о текущем состоянии стека)
+
* автомат (для запоминания информации о текущем состоянии стека).
  
 
=== Управляющая программа анализатора ===
 
=== Управляющая программа анализатора ===
 
Управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.  
 
Управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.  
  
Для запоминания строки запись в стек имеет вид: <tex>s_0X_1s_1X_2...X_ms_m</tex>, где <tex>s_m</tex> {{---}} вершина стека. Каждый <tex>X_i</tex> {{---}} символ грамматики(терминал или нетерминал), а <tex>s_i</tex> {{---}} состояние автомата. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. <tex>s_0</tex> {{---}} стартовае состояние автомата.
+
Для запоминания строки запись в [[Стек|стек]] имеет вид: <tex>s_0X_1s_1X_2...X_ms_m</tex>, где <tex>s_m</tex> {{---}} вершина стека. Каждый <tex>X_i</tex> {{---}} символ грамматики (терминал или нетерминал), а <tex>s_i</tex> {{---}} состояние автомата. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. <tex>s_0</tex> {{---}} стартовое состояние автомата.
 +
Комбинация символа состояния на вершине стека и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в стеке, однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.  
  
Обращение к таблице происходит слудующим образом <tex>T[s_m, curToken]</tex>, где  
+
Обращение к таблице происходит следующим образом <tex>\mathtt{T[state, token]}</tex>, где  
*<tex>s_m</tex> {{---}} текущее состояние автомата,  
+
*<tex>\mathtt{state}</tex> {{---}} состояние автомата,  
*<tex>curToken</tex> {{---}} текущий входной символ;
+
*<tex>\mathtt{token}</tex> {{---}} входной символ.
В таблице информация имеет следующий вид:
+
Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:
  '''struct''' Cell
+
  '''struct''' Shift  { state: '''int''' } <font color="green">// переход в состояние с номером state</font>
    enum:  
+
  '''struct''' Reduce { rule: '''int''' } <font color="green">// свертка по правилу с номером rule</font>
        Shift
+
  '''enum''' Result = Accept  <font color="green">// допуск </font>
        Reduce
+
            | Error    <font color="green">// ошибка</font>
        Accept  <font color="green">// допуск </font>
+
                     
        Error    <font color="green">// ошибка</font>
+
'''enum''' Cell = Shift
  '''struct''' Shift
+
          | Reduce
    state: '''int''' <font color="green">// переход в стостояние state</font>
+
          | Result
  '''struct''' Reduce
 
    rule: '''int'''  <font color="green">// свертка по правилу rule</font>
 
  
 
=== Алгоритм ===
 
=== Алгоритм ===
 
# Программа читает символ из входной цепочки.  
 
# Программа читает символ из входной цепочки.  
# Обращается к утравляющей таблице.
+
# Обращается к управляющей таблице.
 
# Совершает соответствующее действие.
 
# Совершает соответствующее действие.
 
# Возвращается к первому пункту, пока входная цепочка не закончится.
 
# Возвращается к первому пункту, пока входная цепочка не закончится.
  
{| border="0"
+
   '''Result''' algorithmLR(w: '''string''')
|align="left" colspan="4"|
+
       <font color=green>// curToken {{---}} указатель на первый символ в строке w</font>
<font size=2>
+
       '''while''' hasTokens()
   '''bool''' algorithmLR(w: '''string''')
+
           curState = top()
       curToken {{---}} указатель на перый символ в строке w
+
           '''when'''(<tex>\mathtt{T}</tex>[curState, curToken])
       '''while''' цепочка не закончилась
+
               Shift(s) '''->'''
           s = top()
+
                  push(curToken)
          a = w[ip]
+
                  push(s)
           '''if''' action [s, a] == shift s’
+
                  nextToken()
              push(a)
+
              Reduce(<tex> \to \beta</tex>) '''->'''
               push(s’)
+
                  '''for''' j = 1 '''to''' <tex>|\beta |</tex>   
              ip++
+
                      pop()
          '''else if''' action [s, a] == reduce A <tex> \to \beta</tex>  
+
                      pop()
              '''for''' j = 1 '''to''' <tex>|\beta |</tex>   
+
                  s = top()
                  pop()
+
                  push(<tex>A</tex>)
                  pop()
+
                  push(goto(s, <tex>A</tex>))  
              s’ = top()
+
                  Вывод правила: <tex> A \to \beta</tex>    
              push(A)
+
              Accept '''->''' '''return''' Accept             
              push(goto [s’, A])  
+
               Error  '''->''' '''return''' Error 
              Вывод правила (A <tex> \to \beta</tex>)
 
          '''else''' '''if''' action [s, a] == accept
 
               '''return''' true
 
          '''else'''
 
              '''return''' false   
 
</font>
 
|}
 
  
 
Функция <tex>goto</tex> получает состояние и символ грамматики и выдает состояние. Функция <tex>goto</tex>, строящаяся по грамматике <tex>\Gamma</tex>, есть функция переходов детерминированного магазинного автомата, который распознает язык,
 
Функция <tex>goto</tex> получает состояние и символ грамматики и выдает состояние. Функция <tex>goto</tex>, строящаяся по грамматике <tex>\Gamma</tex>, есть функция переходов детерминированного магазинного автомата, который распознает язык,
Строка 116: Строка 108:
  
 
== Источники информации ==
 
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
+
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301-326.
* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы]
+
* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. Разработка компиляторов на платформе .NET {{---}} Восходящие анализаторы]
* [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223]
+
* [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198-223]
 +
* [http://www.cs.bham.ac.uk/~hxt/2015/mgs-ll-lr/LL-LR-MGS.pdf Nice slides]
  
 
[[Категория: Методы трансляции]]
 
[[Категория: Методы трансляции]]
 
[[Категория: Восходящий разбор]]
 
[[Категория: Восходящий разбор]]

Текущая версия на 19:40, 4 сентября 2022

Восходящий разбор (англ. 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()
         when([math]\mathtt{T}[/math][curState, curToken])
             Shift(s) ->
                 push(curToken)
                 push(s)
                 nextToken()
             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]     
             Accept -> return Accept              
             Error  -> return Error   

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

См. также

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