Объяснение о жизнеспособном префиксе

Question

В книге компиляторов Уллмана, в разборе сдвига с понижением, дано следующее определение жизнеспособного префикса:

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

Я не могу понять это определение. Может ли кто-нибудь объяснить значение жизнеспособного префикса на примере?
В частности, пожалуйста, объясните значение
«Эквивалентное определение жизнеспособного префикса состоит в том, что он является префиксом правильной формы предложения, который не продолжается после правого конца самого правого дескриптора этой формы предложения» *

Answer 1

РЕДАКТИРОВАТЬ (или на самом деле переписать): Предложение, которое вы попросили прояснить, - это крупный шарик!Мне нужно было немного освежить язык и автоматизировать себя, чтобы отделить этот шарик.Я нашел эти лекционные заметки очень полезными в этом отношении.

Это также не облегчает определение терминов в терминах раскрытия сверху вниз, в то время как самый правый вывод обычноиспользуется при анализе снизу вверх!

Я буду использовать следующую грамматику выражений для иллюстрации:

    expr -> expr + term | term
    term -> term * factor | factor
    factor -> NUMBER | ( expr )

• A Форма справа-предложения - это предложениеформа, которая может быть достигнута с помощью самого правого деривации, что является другим способом описания повторного расширения только самого правого нетерминального символа при переходе сверху вниз.Это самый правый вывод, и поэтому все формы в нем являются формами с правом предложения:

    expr -> expr + term
         -> expr + term * factor
         -> expr + term * NUMBER
         -> expr + factor * NUMBER
         -> expr + NUMBER * NUMBER
         -> expr + term + NUMBER * NUMBER
         -> expr + NUMBER + NUMBER * NUMBER
         -> term + NUMBER + NUMBER * NUMBER
         -> NUMBER + NUMBER + NUMBER * NUMBER

• A префикс предложения (Право или нет) - это последовательность входных символов, которая сокращает до нуля или более начальных символов этой формы предложения.Пустая последовательность тривиально является префиксом каждой формы предложения, а полная последовательность символов, составляющая форму предложения, также тривиально является ее префиксом.

• A простая фраза - это расширение одного нетерминального символа, который занимает место в форме предложения.Например, term * factor - это простая фраза, потому что это расширение term, а само term встречается в трех производствах.

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

• A жизнеспособный префикс правогоФорма предложения - это префикс, который не выходит за пределы дескриптора этой формы - другими словами, этот префикс является действительным и не содержит сводимых простых фраз с возможным исключением самого дескриптора, если указанный префикс распространяется точно до конца дескриптора.

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

Если вы анализируете язык без контекста, есть довольно удобное свойство, которое помогаетс созданием синтаксического анализатора сдвига-уменьшения на основе таблицы: набор всех жизнеспособных префиксов языка без контекста сам по себе является обычным языком! Таким образом, вы можете построить конечный автомат, который распознает обычный языкжизнеспособные префиксы, и используйте его, чтобы определить, когда сдвигать, а когда уменьшать.Эта комбинация стека и конечного автомата, по сути, является автоматом, работающим по принципу нажатия, который является именно тем классом автоматов, который необходим для распознавания языка без контекста.

Answer 2

Рассмотрим грамматику, приведенную в книге (я ее здесь повторяю)

E -> E+T | T
T -> T*F | F 
F -> (E) | id

, которое дополняется добавлением E '-> E в нем

Теперь взгляните на этот вывод,

E' -> E
   -> E+T
   -> E+T*F

Заявка E + T * является жизнеспособным префиксом

Аргумент: этот вывод является правильной формой предложения, а E + T * является его префиксом. Дескриптор в настоящее время - T * F (поскольку при уменьшении T * F до T мы можем достичь начального символа и, следовательно, успешного анализа)

И, следовательно, E + T * является жизнеспособным префиксом, поскольку он является префиксом правильной формы предложения и не выходит за крайний правый дескриптор этой формы предложения. :)

Другой способ определить это:

The prefixes of right sentential forms that can appear on the stack of a shiftreduce
parser are called viable prefixes.

Answer 3

Я считаю полезным дать формальное определение жизнеспособных префиксов, на тот случай, если кто-то найдет его более понятным (как и я).

Учитывая грамматику , мы говорим, что является жизнеспособным префиксом из , если существует самый правый вывод

такой, что .

Источник .