Блог

У меня есть эта грамматика

 E -> E   i
E -> i
  

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

 E' -> E
E -> E   i
E -> i
  

Теперь я пытаюсь расширить набор элементов 0

 I0)
 E' -> .E
 E  -> .E   i
 E  -> .i
  

Затем, поскольку у меня есть .E in I0 , я бы расширил его, но тогда я получу другое E правило и так далее, Это мое первое сомнение.

Предполагая, что это нормально, следующие наборы элементов

 I0)
 E' -> .E
 E  -> .E   i
 E  -> .i

I1) (I moved the dot from I0, no variables at rhs of dot)
E' -> E.
E -> E.   i
E -> i.

I2) (I moved the dot from I1, no vars at rhs of dot)
E -> E  . i

I3) (I moved the dot from I2, also no vars)
E -> E   i.
  

Тогда у меня будет этот DFA

 I0 -(E, i)-> I1 -( )-> I2 -(i)-> I3
              |                   |
               -(∅)-> acpt <-(∅)-- 
  

Я чего-то не понимаю, потому что E -> E i должен принять i i .. , но DFA не возвращается к I0, поэтому мне это кажется неправильным. Я предполагаю, что у него должен быть переход от I0 к I0, но тогда я не знаю, что делать с точкой.

То, что вы называете «расширением» набора элементов, на самом деле является замыканием; именно так это описывается во всех описаниях алгоритма, которые я видел (по крайней мере, в учебниках). Как и в любой операции закрытия, вы просто продолжаете выполнять преобразование, пока не достигнете фиксированной точки; как только вы включили productions для E , они включены.

Но существенным моментом является то, что вы не создаете DFA. Вы создаете нажимной автомат, и DFA — это всего лишь одна из его частей. DFA используется для операций сдвига; когда вы сдвигаете новый терминал (поскольку текущий стек синтаксического анализа не является дескриптором), вы выполняете переход состояния в соответствии с DFA. Но вы также помещаете текущее состояние в стек КПК.

Интересная часть заключается в том, что происходит, когда автомат решает выполнить сокращение, которое заменяет правую часть производственного процесса на его левую часть, не являющуюся терминалом. (Правая сторона в верхней части стека называется «дескриптором».) Чтобы выполнить сокращение, вы разматываете стек, извлекая каждый символ с правой стороны (и соответствующее состояние DFA), пока не дойдете до начала создания. Что это делает, так это возвращает DFA в состояние, в котором он находился до того, как он переместил первый символ с правой стороны. (Обратите внимание, что только на этом этапе вы точно знаете, какая продукция использовалась.) Сбросив таким образом DFA, теперь вы можете переместить найденный нетерминал, выполнить соответствующий переход DFA и продолжить синтаксический анализ.

Основой для этой процедуры является тот факт, что стек синтаксического анализа всегда является «жизнеспособным префиксом»; то есть последовательностью символов, которые являются префиксом некоторой правильной формы предложения, которая может быть получена из начального символа. Что интересно в наборе жизнеспособных префиксов для контекстно-свободной грамматики, так это то, что это обычный язык, и, следовательно, он может быть распознан DFA. Приведенная выше процедура сокращения точно представляет эту процедуру распознавания, когда дескрипторы «обрезаются» (если использовать оригинальный словарь Кнута).

В этом смысле на самом деле не имеет значения, какая процедура используется для определения того, какой дескриптор следует обрезать, если он предоставляет действительный ответ. Вы могли бы, например, разветвлять синтаксический анализ каждый раз, когда потенциальный дескриптор замечен в верхней части стека, и продолжать параллельно с обоими разветвлениями. Благодаря умному управлению стеком этот параллельный поиск может выполняться в наихудшем случае O (n ³) раз для любой контекстно-свободной грамматики (и это может быть сокращено, если грамматика не является двусмысленной). Это очень приблизительное описание анализаторов Earley.

Но в случае анализатора LR (k) мы требуем, чтобы грамматика была однозначной, и мы также требуем, чтобы мы могли идентифицировать сокращение, просматривая не более k большего количества символов из входного потока, что является операцией O (1), поскольку k исправлено. Если в каждой точке синтаксического анализа мы знаем, сокращать или нет, и если да, то какое сокращение выбрать, то сокращения могут быть реализованы так, как я описал выше. Каждое сокращение может быть выполнено за O (1) время для фиксированной грамматики (поскольку максимальный размер правой части в конкретной грамматике фиксирован), и поскольку количество сокращений в синтаксическом анализе линейно зависит от размера входных данных, весь синтаксический анализ может быть выполнен за линейное время.

Все это было немного неформально, но я надеюсь, что это послужит интуитивным объяснением. Если вас интересует формальное доказательство, оригинальную статью Дональда Кнута 1965 года (О переводе языков слева направо) легко найти и легко читается по ходу дела.