Пояснение относительно жизнеспособного префикса

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

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

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

Ответы

Ответ 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 жизнеспособный префикс правой-условной формы - это префикс, который не распространяется за пределы этого дескриптора формы - другими словами, этот префикс действителен и не содержит приводимых простых фраз, с возможным исключением самого дескриптора, если указанный префикс проходит точно до конца дескриптора.

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

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

Ответ 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.

Ответ 3

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

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

такое, что .

Источник.