Разбор снизу вверх сдвиг свертка

Содержание

Разбор снизу вверх сдвиг свертка

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

Приведенная грамматика продуцирует цепочки вида ** aa + aa +* aaa . Из правил грамматики видно, что первая замена производится по правилу A :: a , иначе в цепочке просто нет необходимых нетерминалов для подстановки. Затем в нетерминалу A справа «присоединяются» терминалы a из входной строки, а уже затем – символы * слева.

Теперь нужно обсудить, как будет выглядеть распознаватель и каковы будут принципы его работы. Во-первых, по аналогии с нисходящим разбором можно предположить, что для обнаружения основы достаточно пары символов – последнего символа основы и следующего символа строки (в нашем примере это сочетание aa ) . Т.е. для каждой пары символов грамматики однозначно можно сформулировать утверждение, является ли эта пара концом основы или нет. Опять-таки это связано с глубиной просмотра вперед входной строки – она равна 1.

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

Теперь можно сформулировать основные принципы восходящего разбора c использованием магазинного автомата (МА), именуемого также методом «свертка-перенос»:

Первоначально в стек помещается первый символ входной строки, а второй становится текущим;

МА выполняет два основных действия: перенос (сдвиг — shift ) очередного символа из входной строки в стек (с переходом к следующему);

Поиск правила, правая часть которого хранится в стеке и замена ее на левую – свертка ( reduce );

Решение, какое из действий – перенос или свертка выполняется на данном шаге, принимается на основе анализа пары символов – символа в вершине стека и очередного символа входной строки. Свертка соответствует наличию в стеке основы, при ее отсутствии выполняется перенос. Управляющими данными МА является таблица, содержащая для каждой пары символов грамматики указание на выполняемое действие (свертка, перенос или недопустимое сочетание -ошибка) и сами правила грамматики.

Положительным результатом работы МА будет наличие начального нетерминала грамматики в стеке при пустой входной строке.

Как следует из описания, алгоритм не строит синтаксическое дерево, а производит его обход «снизу-вверх» и «слева-направо». В соответствии с этим, грамматика, допускающая распознавание подобным методом, называется LR (1) – ( left –просмотр входной строки слева направо, right —правая подстановка – замена правой части на левую, восходящий разбор, 1-глубина просмотра входной строки для принятия решения).

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

Конспект лекций По предмету Системное программное обеспечение Ташкент 2008

Название	Конспект лекций По предмету Системное программное обеспечение Ташкент 2008
страница	9/30
Дата	29.05.2013
Размер	5.65 Mb.
Тип	Конспект лекций
скачать

1. /Sistemnoe_programnoe_obespecheniye.doc

Конспект лекций По предмету Системное программное обеспечение Ташкент 2008

Распознаватель на основе алгоритма «сдвиг-свертка»

Принцип работы восходящего распознавателя по алгоритму «сдвиг-свертка»

Этот распознаватель строится на основе расширенного МП-автомата с одним состоянием q: R(,V,Z,5,q,S,). Автомат распознает цепочки КС-языка, заданного КС-грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит терминальные символы грамматики: V = VT; а алфавит магазинных символов строится из терминальных и нетерминальных символов грамматики: Z = VTuVN.

Начальная конфигурация автомата определяется так: (q,a,X) — автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов aeVT», стек пуст.

Конечная конфигурация автомата определяется так: (q,X,S) — автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S.

Функция переходов МП-автомата строится на основе правил грамматики:

(q,A)e8(q,^,y), AeVN, ye(VTuVN)*, если правило А-»у содержится во множестве правил Р грамматики G: А->у е Р.
(q,a)e5(q,a,A.) VaeVT.

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

Данный расширенный МП-автомат строит правосторонние выводы для грамматики G(VT,VN,P,S). Для моделирования такого автомата необходимо, чтобы грамматика G(VT,VN,P,S) не содержала ^.-правил и цепных правил (в противном случае, очевидно, автомат может войти в бесконечный цикл из сверток). Поскольку, как было доказано выше, произвольную КС-грамматику всегда можно преобразовать к виду без ^.-правил и цепных правил, то этот алгоритм применим для любой КС-грамматики, следовательно, им можно распознавать цепочки любого КС-языка.

Этот расширенный МП-автомат строит правосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода снизу вверх. Такой распознаватель называется восходящим.

Данный расширенный МП-автомат потенциально имеет больше неоднозначностей, чем рассмотренный ваше МП-автомат, основанный на алгоритме подбора альтернатив. На каждом шаге работы автомата надо решать следующие вопросы:

что необходимо выполнять: сдвиг или свертку;
если выполнять свертку, то какую цепочку у выбрать для поиска правил (цепочка у должна встречаться в правой части правил грамматики);
какое правило выбрать для свертки, если окажется, что существует несколько правил вида А-»у (несколько правил с одинаковой правой частью).

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

Реализация распознавателя с возвратами на основе алгоритма «сдвиг-свертка»

Существует несколько реализаций для алгоритма моделирования работы такого расширенного МП-автомата [6, т. 1, 40]. Один из вариантов рассмотрен ниже.

Для работы алгоритма всем правилам грамматики G(VT,VN,P,S ), на основе которой построен автомат, необходимо дать порядковые номера. Будем нумеровать правила грамматики в направлении слева направо и сверху вниз в порядке их записи в форме Бэкуса—Наура. Входная цепочка символов имеет вид а = aia₂. a_n,

Алгоритм моделирования расширенного МП-автомата, аналогично алгоритму нисходящего распознавателя, использует дополнительное состояние b и дополнительный стек возвратов L₂. В стек помещаются номера правил грамматики, использованных для свертки, если на очередном шаге алгоритма была выполнена свертка, или 0, если на очередном шаге алгоритма был выполнен сдвиг.

В итоге алгоритм работает с двумя стеками: L] — стек МП-автомата и L₂ — стек возвратов. Первый представлен в виде цепочки символов, второй — цепочки целых чисел от 0 до т, где т — количество правил грамматики G. Символы в це- почку стека Li помещаются справа, числа в стек L₂ — слева. В целом состояние алгоритма на каждом шаге определяется четырьмя параметрами: (Q, i, L,, L₂), где Q. — текущее состояние автомата (q или b); i — положение считывающей головки во входной цепочке символов а (К i • (q, i, аА, jy), если А-»Р — это первое и:

всех возможных правил из множества правил Р с номером j для подцепочки р

причем оно есть первое подходящее правило для цепочки ар, для которой пра

вило вида А-»р существует. Если удалось выполнить свертку — возвращаемся i

шагу 1, иначе — переходим к шагу 2.

Шаг 2 (Перенос — сдвиг). Если i (q, i+1, аг_ь Оу), a, eVT

Если i = n+1, то перейти к шагу 3, иначе перейти к шагу 1.

Шаг 3 (Завершение). Если состояние соответствует (q, n+1, S, у), то разбор завер

шен, алгоритм заканчивает работу, иначе перейти к шагу 4.

Шаг 4 (Переход к возврату), (q, n+1, а, у) -» (Ь, п+1, а, у). Шаг 5 (Возврат). Если исходное состояние (b, i, аА, jy), то:

О перейти в состояние (q, i, а’В, ky), если j > 0, и А-»Р — это правило с номе ром j и существует правило В->Р’ с номером к, к > j, такое, что ар = а’Р после чего надо вернуться к шагу 1;

О перейти в состояние (Ь, п+1, ар, у), если i = n+1, j > 0, А->Р — это правил с номером j и не существует других правил из множества Р с номеро: k > j, таких, что их правая часть является правой подцепочкой из цепочк ар; после этого вернуться к шагу 5;

О перейти в состояние (q, i+1, ар^, Оу), aj eVT, если i * n+1, j > 0, A->P — эт правило с номером j и не существует других правил из множества Р с^нс мером k>j, таких, что их правая часть является правой подцепочкой у цепочки аР; после этого перейти к шагу 1;

О иначе сигнализировать об ошибке и прекратить выполнение алгоритма.

Если исходное состояние (b, i, аа, Оу), a eVT, то если i > 1, тогда перейти в cm

дующее состояние (b, i-1, а, у) и вернуться к шагу 5; иначе сигнализировать с

ошибке и прекратить выполнение алгоритма.

В случае успешного завершения алгоритма цепочку вывода можно построить i

основе содержимого стека L₂, полученного в результате выполнения алгоритм

Для этого достаточно удалить из стека L₂ все цифры 0 — и получим последов

тельность номеров правил.

Этот алгоритм может быть напрямую использован для построения распознав

телей. Следует помнить, что для применения этого алгоритма исходная грамм

тика не должна допускать циклов и не должна содержать ^-правил. Если это условие не удовлетворяется, то грамматику надо предварительно преобразовать к приведенной форме.

Возьмем в качестве примера грамматику G(<+,-,/,*,а,b>, , P, S):

S -> S+T | S-T | Т*Е | Т/Е | (S) | а | b

Т -» Т*Е | Т/Е | (S) | а | b

Это грамматика для арифметических выражений, в которой устранены цепные правила (ее уже рассматривали в разделе «Преобразование КС-грамматик. Приведенные грамматики»). Следовательно, в ней не может быть циклов 1 . Кроме того, видно, что в ней нет ^.-правил. Таким образом, цепочки языка, заданного этой грамматикой, можно распознавать с помощью алгоритма восходящего распознавателя с возвратами.

Проследим разбор цепочки а+(а*Ь) из языка этой грамматики. Работу алгоритма будем представлять в виде последовательности его состояний, взятых в скобки <> (фигурные скобки используются, чтобы не путать их с круглыми скобками, предусмотренными в правилах грамматики). Правила будем нумеровать слева направо и сверху вниз (всего в грамматике получается 15 правил). Для пояснения каждый шаг работы сопровождается номером шага алгоритма, который был применен для перехода в очередное состояние (записывается перед состоянием через символ : — двоеточие).

Алгоритм работы восходящего распознавателя с возвратами при разборе цепочки а+(а*Ь) будет выполнять следующие шаги:

На основании полученной цепочки номеров правил: 1, 10, 3, 15, 11, 6 получаем правосторонний вывод: S => S+T => S+(S) => S+(T*E) => S+(T*b) => S+(a*b) => a+(a*b). Соответствующее ему дерево вывода приведено на рис. 11.3.

Рис. 11.3. Дерево вывода для грамматики без цепных правил

В приведенном примере очевиден тот же недостаток алгоритма восходящего разбора с возвратами, что и у алгоритма нисходящего разбора с возвратами — значительная временная емкость: для разбора достаточно короткой входной цепочки (всего 7 символов) потребовалось 45 шагов работы алгоритма. Такого результата и следовало ожидать, исходя из экспоненциальной зависимости необходимых для работы алгоритма вычислительных ресурсов от длины входной цепочки. Это существенный недостаток данного алгоритма.

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

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

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

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

Табличные распознаватели для КС-языков

Общие принципы работы табличных распознавателей

Табличные распознаватели используют для построения цепочки вывода К( грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, ог получают на вход цепочку входных символов а = aia₂. a_n, aeVT*, |a| = n,an строение вывода основывают на правилах заданной КС-грамматики G(VT,VN,P,S Принцип их работы заключается в том, что искомая цепочка вывода строится ) сразу — сначала на основе входной цепочки порождается некоторое промеж точное хранилище информации объема п*п (промежуточная таблица) 1 , а поте уже на его основе строится вывод.

Табличные алгоритмы обладают полиномиальными характеристиками требу мых вычислительных ресурсов в зависимости от длины входной цепочки. Д. произвольной КС-грамматики G(VT,VN,P,S) время выполнения алгоритма ‘ имеет кубическую зависимость от длины входной цепочки, а необходимый об ем памяти М_э — квадратичную зависимость от длины входной цепочки: а, ае V п = |а|: Т_э = 0(п 3 ) и М_э = 0(п 2 ), Квадратичная зависимость объема необходим! памяти от длины входной цепочки напрямую связана с использованием пром жуточного хранилища данных.

1 В алгоритме Кока—Янгера—Касами промежуточная таблица используется в явном ви, а в алгоритме Эрли она завуалирована под хранилище, именуемое «список ситуацш которое организовано несколько сложнее, чем простая таблица.

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

Алгоритм Кока—Янгера—Касами для заданной грамматики G(VT,VN,P,S) и цепочки входных символов а = aia₂. a_n, aeVT*, |a| = п строит таблицу Т_п._п, такую, что VAeVN: AeT[i,j], тогда и только тогда, если A=>+a_i. a_i₊j.₁. Таким образом, элементами таблицы Т_п»_п являются множества нетерминальных символов из алфавита VN.

Тогда существованию вывода S=>*a соответствует условие SeT[l,n].

При условии существования вывода по таблице Т_п._п можно найти всю полную цепочку вывода S=s>*a.

Для построения вывода по алгоритму Кока—Янгера—Касами грамматика G(VT, VN,P,S) должна быть в нормальной форме Хомского. Поскольку, как было показано выше, любую произвольную КС-грамматику можно преобразовать в нормальную форму Хомского, это не накладывает дополнительных ограничений на применимость данного алгоритма.

Алгоритм Кока—Янгера—Касами фактически состоит из трех вложенных циклов. Поэтому ясно, что время выполнения алгоритма имеет кубическую зависимость от длины входной цепочки символов. Таблица Т_п»_п, используемая для хранения промежуточных данных в процессе работы алгоритма, является таблицей множеств. Очевидно, что требуемый для ее хранения объем памяти имеет квадратичную зависимость от длины входной цепочки символов.

Сам алгоритм Кока—Янгера—Касами можно описать следующим образом:

Цикл для j от 1 до п

T[l.j] := <А | 3 АтМ, eP >— i T[l,j] включаются все нетерминальные символы,

для которых в грамматике G существует правило А->а.

Конец цикла для j.

Хотя табличные распознаватели и являются самыми эффективными среди универсальных распознавателей, тем не менее они не находят широкого применения. Дело в том, что полиномиальная зависимость требуемых вычислительных ресурсов от длины входной цепочки символов является неудовлетворительной для компиляторов (длины входных цепочек — тысячи и десятки тысяч символов). Поэтому практически всегда используются не универсальные, а более узкие, специализированные алгоритмы распознавателей, которые имеют обычно линейную зависимость требуемых вычислительных ресурсов от длины входной цепочки символов. К универсальным алгоритмам прибегают только тогда, когда специализированный распознаватель построить не удается. Шаг 2.

Цикл для i от 2 до п

Цикл для j от 1 до n-1+l T[i.j] := 0; Цикл для к от 1 до п-1

Tti.j] : = T[i.j] и <А | .3 А^ВС € P. BeT[k.j]. CeT[i-k.j+k]>Конец цикла для к. Конец цикла для j. Конец цикла для i. Результатом работы алгоритма будет искомая таблица Т_п._п. Для проверки супц ствования вывода исходной цепочки в заданной грамматике остается только прс верить условие SeT[l,n].

Если вывод существует, то необходимо получить цепочку вывода. Для этот, существует специальная рекурсивная процедура R. Она выдает последовательность номеров правил, которые нужно применить, чтобы получить цепочку вь вода. Ее можно описать следующим образом: R(i,j,A), где AeVN.

Если j = 1 и существует правило A-»aj, то выдать номер этого правила.
Иначе (если j > 1) возьмем к как наименьшее из чисел, для которых 3 А—»ВХ е Р, BeT[k,j], CeT[i-k,j+k] (таких правил может быть несколько, д; определенности берем наименьшее к). Пусть правило А-»ВС имеет номер i Тогда нужно выдать этот номер ш, потом вызвать сначала R(i,k,B), а затем R(i-k,j+k,C).

Для получения всей последовательности номеров правил нужно вызвать R(l,n,S Рекурсивная процедура R не требует дополнительной памяти для своего выпо нения, кроме стека, необходимого для организации рекурсии. Время ее выполн ния имеет квадратичную зависимость от длины входной цепочки. На основании последовательности номеров правил, полученной с помощью алг ритма Кока—Янгера—Касами и рекурсивной процедуры R, можно построить лев сторонний вывод для заданной грамматики G(VT,VN,P,S) и цепочки входных си волов а. Таким образом, с помощью данного алгоритма решается задача разбора.

Алгоритм Эрли (основные принципы)

Алгоритм Эрли основан на том, что для заданной КС-грамматики G(VT,VN,P, и входной цепочки со = а^.-.а. goeVT , |со| = п строится последовательность era ков ситуаций 1,1_1?. 1_п. Каждая ситуация, входящая в список Ij для входной i почки со, представляет собой структуру вида [A->X₁X₂. X_k»X_k₊₁. X_m,i], N X_ke(VNuVT), причем правило A-^Х^..Х. принадлежит множеству правил грамматики G, и 0 Х). Х_т. Если цепочка символов правг пустая (А—>Х), то ситуация будет выглядеть так: [A—>«,i]. Список ситуаций строится таким образом, что Vj, 0 a»p,i]eIj тогда и только тогда, если 3 S=>*yAS, у=>*а1. а, и a=>*a_i₊₁. aj. Иначе говоря, между вторым компонентом ситуации и номером списка, в котором он появляется, заключена часть входной цепочки, выводимая из А. Условия ситуации L гарантируют возможность применения правила А-»сф в выводе некоторой входной цепочки, совпадающей с заданной цепочкой со до позиции j.

Условием существования вывода заданной входной цепочки со в грамматике G(VN,VT,P,S) после завершения алгоритма Эрли служит [S-Ko»,0]sl_n. На основании полученного в результате выполнения алгоритма списка ситуаций можно затем с помощью специальной процедуры построить всю цепочку вывода и получить номера применяемых правил. Причем проще построить правосторонний вывод.

Алгоритм Эрли подробно здесь не рассматривается. Его описание можно найти, например, в книге [6, т. 1].

Как и все табличные алгоритмы, алгоритм Эрли обладает полиномиальными характеристиками в зависимости от длины входной цепочки. Доказано, что для произвольной КС-грамматики G(VN,VT,P,S) время выполнения данного алгоритма Т_э будет иметь кубическую зависимость от длины входной цепочки, а необходимый объем памяти М_э — квадратичную зависимость от длины входной цепочки: а, ае VT*, п т |а|: Т_э = 0(п 3 ) и М_э = 0(п 2 ). Но для однозначных КС-грамматик алгоритм Эрли имеет лучшие характеристики — его время выполнения в этом случае квадратично зависит от длины входной цепочки: Т_э = 0(п 2 ). Кроме того, для некоторых классов КС-грамматик время выполнения этого алгоритма линейно зависит от длины входной цепочки (правда, для этих классов, как правило, существуют более простые алгоритмы распознавания). В целом алгоритм Эрли имеет лучшие характеристики среди всех универсальных алгоритмов распознавания входных цепочек для произвольных КС-грамматик. Он превосходит алгоритм Кока—Янгера—Касами для однозначных грамматик (которые представляют интерес в первую очередь), хотя и является более сложным в реализации.

Принципы построения распознавателей КС-языков без возвратов

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

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

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

Далее будут рассмотрены некоторые из таких распознавателей. Все они имеют линейные характеристики — линейную зависимость необходимых для выполнения алгоритма разбора вычислительных ресурсов от длины входной цепочки. Для каждого распознавателя рассматривается класс КС-грамматик, с которым он связан. Это значит, что он может принимать только входные цепочки из КС-языков, заданных такими грамматиками. Всегда описываются ограничения, налагаемые на правила грамматики, или дается алгоритм проверки принадлежности произвольной КС-грамматики к заданному классу.

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

Существуют два принципиально разных класса распознавателей. Первый — нисходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз. Второй — восходящие распознаватели, которые порождают цепочки правостороннего вывода и строят дерево вывода снизу вверх. Названия «нисходящие» и «восходящие» связаны с порядком построения дерева вывода. Как правило, все распознаватели читают входную цепочку символов слева направо, поскольку предполагается именно такая нотация в написании исходного текста программ.

автомата (шаг «выброс» в этом автомате всегда выполняется однозначно). Алгоритм подбора альтернатив без модификаций был рассмотрен выше.

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

Далеко не все известные распознаватели с линейными характеристиками рассматриваются в данном пособии. Более полный набор распознавателей, а также описание связанных с ними классов КС-грамматик и КС-языков вы можете найти в [5, 6, 23, 42, 65]. Далее будут рассмотрены только самые часто встречающиеся и употребительные классы.

Классы кс-языков и грамматик.

Нисходящие распознаватели КС-языков без возвратов

Левосторонний разбор по методу рекурсивного спуска

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

Наиболее очевидным методом выбора одной из множества альтернатив являете выбор ее на основании символа ае VT, обозреваемого считывающей головкой ai томата на каждом шаге его работы (находящегося справа от положения текуще головки во входной цепочке символов). Поскольку в процессе нисходящего ра: бора именно этот символ должен появиться на верхушке магазина для продв! жения считывающей головки автомата на один шаг (условие 5(q,a,a) = <(q,^-) VaeVT в функции переходов МП-автомата), то разумно искать альтернатив где он присутствует в начале цепочки, стоящей в правой части правила грамм; тики. По такому принципу действует алгоритм разбора по методу рекурсивного спуска

Алгоритм разбора по методу рекурсивного спуска

В реализации этого алгоритма для каждого нетерминального символа AeV грамматики G(VN,VT,P,S) строится процедура разбора, которая получает i вход цепочку символов а и положение считывающей головки в цепочке i. Ecj для символа А в грамматике G определено более одного правила, то процедура разбора ищет среди них правило вида А-»ау, aeVT, ye(VNuVT)*, первый символ правой части которого совпадал бы с текущим символом входной цепочки а = оц. Если такого правила не найдено, то цепочка не принимается. Иначе (если найдено правило А-»ау или для символа А в грамматике G существует только одно правило А-»у), то запоминается номер правила, и когда а = ocj , то считывающая головка передвигается (увеличивается i), а для каждого нетерминального символа в цепочке у рекурсивно вызывается процедура разбора этого символа. Название метода происходит из реализации алгоритма, которая заключается в последовательности рекурсивных вызовов процедур разбора. Для начала разбора входной цепочки нужно вызвать процедуру для символа S с параметром i = 1.

Условия применимости метода можно получить из описания самого алгоритма—в грамматике G(VN,VT,P,S) VAeVN возможны только два варианта правил:

А->у, ye(VNuVT)* и это единственное правило для А;

Этим условиям удовлетворяет незначительное количество реальных грамматик. Это достаточные, но не необходимые условия. Если грамматика не удовлетворяет этим условиям, еще не значит, что заданный ею язык не может распознаваться с помощью метода рекурсивного спуска. Возможно, над грамматикой просто необходимо выполнить ряд дополнительных преобразований.

К сожалению, не существует алгоритма, который бы позволил преобразовать произвольную КС-грамматику к указанному выше виду, равно как не существует и алгоритма, который бы позволял проверить, возможны ли такого рода преобразования. То есть для произвольной КС-грамматики нельзя сказать, анализируема ли она методом рекурсивного спуска или нет.

Можно рекомендовать ряд преобразований, которые способствуют приведению грамматики к требуемому виду, но не гарантируют его достижения.

Исключение ^-правил.
Исключение левой рекурсии.
Добавление новых нетерминальных символов. Например:

если правило: A->aa₁|aa₂|. |aa_n|b₁p₁|b₂p₂|. |b_mp_m,

4. Замена нетерминальных символов в правилах на цепочки их выводов.
Например:

если имеются правила:

В целом алгоритм рекурсивного спуска эффективен и прост в реализации, но имеет очень ограниченную применимость.

Пример реализации метода рекурсивного спуска

С.-> АаВЬ Необходимо построить распознаватель, работающий по методу рекурсивного спуска.

Видно, что грамматика удовлетворяет условиям, необходимым для построения такого распознавателя.

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

цепочка входных символов;
положение указателя (считывающей головки МП-автомата) во входной цепочке;
массив для записи номеров примененных правил;
порядковый номер очередного правила в массиве.

Результатом работы каждой процедуры может быть число, отличное от нуля («истина»), или 0 («ложь»). В первом случае входная цепочка символов принимается распознавателем, во втором случае — не принимается. Для удобства реализации в том случае, если цепочка принимается распознавателем, будем возвращать текущее положение указателя в цепочке. Кроме того, потребуется еще одна дополнительная процедура для ведения записей в массиве последовательности правил (назовем ее WriteRules).

void WriteRulesdnt* piRul. int* iP, int iRule)

int proc_S (char* szS, int IN, int* piRul, int* iP)

Принципы построения распознавателей КС-языков без возвратов

Читайте также:

Aрхитектурныe основы построения нейросистем на базе нейрочипа
I, d – диаграмма влажного воздуха и принцип ее построения
I. Медико-гигиеническое воспитание, цели, задачи, принципы.
I. Предмет, цели, задачи, принципы специальной психологии
I. Предмет, цели, задачи, принципы специальной психологии
I.3. Основные принципы психологии.
II. Принципы производственного обучения
III. Организация вахты на мостике. Общие принципы организации вахты
III. Основные факторы и принципы, определяющие развитие психологии. Категориальный строй психологии.
IV. Первая медицинская помощь и основные принципы лечения.
IV. Принципы экологического права.
А. Основополагающие принципы прав человека

Общие принципы работы табличных распознавателей

Табличные распознаватели для КС-языков

Табличные распознаватели используют для построения цепочки вывода КС-грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, они получают на вход цепочку входных символов a = а₁а₂…a_n, aÎVT * , | a| = n, a построение вывода основывают на правилах заданной КС-грамматики G(VT,VN,P,S). Принцип их работы заключается в том, что искомая цепочка вывода строится не сразу — сначала на основе входной цепочки порождается некоторое промежуточное хранилище информации объема n*n (промежуточная таблица), а потом уже на его основе строится вывод.

Табличные алгоритмы обладают полиномиальными характеристиками требуемых вычислительных ресурсов в зависимости от длины входной цепочки. Для произвольной КС-грамматики G(VT,VN,P,S) время выполнения алгоритма Т_э имеет кубическую зависимость от длины входной цепочки, а необходимый объем памяти М_э — квадратичную зависимость от длины входной цепочки: a, aÎVT * , n= |a|: Т_э = O(n 3 ) и М_э= О(n 2 ). Квадратичная зависимость объема необходимой памяти от длины входной цепочки напрямую связана с использованием промежуточного хранилища данных.

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

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

Дата добавления: 2014-01-20 ; Просмотров: 637 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Shift-уменьшить анализатор — Shift-reduce parser

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

содержание

обзор

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

Сдвиг-синтаксический анализ уменьшения экспрессии A = B + C*2 рассматриваются.

На этапе 7 в примере разбора, только «А = В +» был проанализирован. Только затененный левый нижний угол синтаксического дерева существует. Ни один из узлов дерева синтаксического анализа пронумерованных 8 и выше пока не существует. Узлы 1, 2, 6, и 7 являются корнями изолированных поддеревьев, охватывающих все пункты 1..7. Узел 1 является переменной А, узел 2 представляет собой разделитель = узел 6 является слагаемым В, и узел 7 является оператором +. Эти четыре корневых узлов временно хранится в стеке синтаксического анализа. Остальная неанализируемая часть входного потока является «С * 2».

Сдвиг-свертка синтаксического анализа работы, делая некоторые комбинации шагов смещаться и уменьшить шаги, отсюда и название.

Сдвиг шагом продвигается во входном потоке на один символ. Это сдвинуты символ становится новым одним узлом дерева синтаксического анализа.
Уменьшить шаг применяется законченную правило грамматики с некоторыми из последних деревьев синтаксического анализа, соединив их вместе , как одно дерево с новым корневым символом.

Анализатор продолжает с этими шагами, пока все входа не было потреблено и все разбора деревьев были сокращены до одного дерева, представляющего весь правовой вход.

шаги построения дерева

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

шаг	Анализировать Стек	Посмотрите вперед	непроверенные	Parser Action
	пустой	Я бы	= В + С * 2	сдвиг
1	Я бы	знак равно	В + С * 2	сдвиг
2	>	Я бы	+ С * 2	сдвиг
3	>	+	C * 2	Сократить Значение ← идентификатор
4	Идентификатор = Значение	+	C * 2	Сократить продукты ← Значение
5	>	+	C * 2	Сократить сумм ← Продукты
6	>	+	C * 2	сдвиг
7	>	Я бы	* 2	сдвиг
8	>	*	2	Сократить Значение ← идентификатор
9	>	*	2	Сократить продукты ← Значение
10	>	*	2	сдвиг
11	>	ИНТ	ВФ	сдвиг
12	>	ВФ	Сократить Value ← Int
13	>	ВФ	Сократить продукты ← Продукты * Значение
14	>	ВФ	Сократить суммы ← СУММ + Products
15	>	ВФ	Снизить на Присвоить ← ид = сумм
16	приписывать	ВФ	Готово

См более простой пример.

грамматики

Грамматика является набором шаблонов или правил синтаксиса для языка ввода. Он не охватывает все правила языка, такие как размер чисел, или последовательное использование имен и их определений в контексте всей программы. Shift-уменьшить парсеры использовать контекстно-свободную грамматику , которая занимается только с местными узорами символов.

Пример грамматики как крошечное подмножества языка Java или C , способного согласования A = B + C*2 может быть:

Назначают ← идентификатор = Суммы Суммирование ← Суммы + Продукты Суммирование ← Продукты Продукты ← Продукты * Значение Продукты ← Значение Значение ← ИНТ Значение ← идентификатор

Грамматик в терминальных символами являются символами мультисимвольных или «жетоны» , найденными во входном потоке с помощью лексического сканера . Здесь они включают = + * и Int для любого целого числа, константы и идентификатора для любого имени идентификатора. Грамматика не волнует то , что ИНТ значение или идентификаторы правописание является, и не заботится о заготовках или разрывах строк. Грамматика использует эти терминальные символы , но не определяет их. Они всегда находятся в нижнем густом конце синтаксического дерева.

Капитализированные термины , как суммы нетерминальные символы . Это названия понятий или образов в языке. Они определены в грамматике и никогда не возникают сами во входном потоке. Они всегда выше нижней части дерева синтаксического анализа. Они происходят только в результате синтаксического анализа , применяя некоторые грамматические правила. Некоторые нетерминалы определяются с двумя или более правил; эти альтернативные модели. Правила могут вернуться к себе. Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики для полных языков используют рекурсивные правила для обработки списков, выражения в скобках и вложенные оператор.

Любой данный компьютерный язык можно описать несколько различных грамматик. Грамматика для сдвига, уменьшить синтаксический анализатор должна быть однозначной сама по себе, или может быть дополнена ничьи правил приоритета. Это означает , что есть только один правильный способ применить грамматику данного юридического например языка, в результате уникального синтаксического дерева и уникальной последовательностью сдвига / уменьшения действия для этого примера.

Стол управляемого анализатор имеет все свои знания о грамматике , закодированной в неизменные данные , которые называются парсер таблица. Программный код парсера простой общий цикл , который применяется в неизмененном многие грамматики и языках. Таблицы могут быть разработаны вручную для методов очередности. Для методов LR, сложные таблицы механически получены из грамматики с помощью какой — то парсер генератора инструмента , как Bison . Таблицы синтаксического анализа, как правило , намного больше , чем грамматики. В других анализаторах, которые не являются таблицами с приводом, например, рекурсивным спуском , каждая конструкция языка анализируются с помощью другой подпрограммы, специализирующийся на синтаксис этой одной конструкции.

Parser действия

Эффективность сдвиг-свертка парсера от не делает ни одного резервного копирования или откаты. Его общее время масштабируется линейно с длиной входного и размером полного дерева разбора. Другие методы синтаксического анализа , что BackTrack может принимать N 2 или N 3 раз , когда они угадать плохо.

Для того, чтобы избежать гадать, сдвиг-свертка анализатор часто смотрит вперед (вправо) на следующем сканированного символа, прежде чем решить , что делать с ранее отсканированных символов. Лексический сканер работает один символ впереди остальной части синтаксического анализатора. Опережения символ является «правой рукой контекст» для каждого решения синтаксического анализа. (Редко, два или более символы предварительных просмотра могут быть использованы, хотя большинство практических грамматик могут быть разработаны , чтобы использовать один символ опережения.)

Сдвиг-свертка анализатор ждет, пока она не сканируются и разобраны все части некоторой конструкции, прежде чем совершать то, что комбинированная конструкция является. Анализатор затем действует непосредственно на комбинации, а не ждать дальше. В примере дерева синтаксического анализа выше, фраза B получает сводится к стоимости, а затем продукты и сумм на этапах 3-6, как только предпросмотр + видно, а не ждать, пока какой-нибудь позже, чтобы организовать эти части дерева синтаксического разбора. Решения о том, как обращаться с B основаны только на том, что анализатор и сканер уже видели, не считая вещи, которые появляются гораздо позже вправо.

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

Когда правило грамматики, как

Продукты ← Продукты * Значение

применяется, верхний стек хранит дерево разбора «. Продукты * Value». Это нашло экземпляр правой части создания правила называется ручкой . Шаг снижения заменяет ручку «Продукты * Значение» по левой стороне нетерминал, здесь большие продукты. Если анализатор строит полное дерево разбора, три дерева для внутренних продуктов, * и Value объединены новым корнем дерева для продуктов. В противном случае, смысловые детали из внутренних продуктов и значения выводится на более поздний проход компилятора, или объединены и сохранены в новом символе Products.

Анализатор продолжает применять сокращения в верхней части стека разбора, пока он продолжает находить недавно законченные примеры грамматических правил там. Когда нет больше правил не может быть применен, анализатор затем сдвигает символ опережения на стек разбора, сканирует новый символ опережения, и пытается снова.

Типы сменно-Reduce Парсеры

Таблицы синтаксического анализа показывают, что делать дальше, для каждого юридического сочетания символов вершинных стека синтаксического анализа и символа опережения. Это следующее действие должно быть уникальным; либо сдвиг, либо уменьшить, но не оба. (Это предполагает некоторые дополнительные ограничения на грамматике, за быть однозначным.) Деталь таблицы сильно различается между различными типами сдвигом, уменьшить анализаторы.

В очередности анализаторах, правый конец ручки находится путем сравнения уровня старшинства или грамматическая затяжки верхних символов стеки, что и символ опережения. В приведенном выше примере, INT и идентификатор принадлежат внутренним уровням грамматики по сравнению с разделителем заявления ; , Так ИНТ и идентификатор оба считаются более высокий приоритет , чем ; и должны быть сведены к чему -то еще , когда следует ; , Существуют различные варианты очередности анализаторов, каждый с различными способами нахождения левого конца РУЧКИ и правильный выбором правила для применения:

Оператор-старшинство анализатор , очень простой численный метод , который работает для выражений , но не общий синтаксис программы.
Простое старшинство анализатор использует одну большую таблицу MxN , чтобы найти правые и левые концы. Используется в ПЛ360 . Не обрабатывать общие языки программирования.
Слабое старшинство анализатор использует таблицу очередности только найти правильные концы ручек. Ручки больше, чем грамматик простого предшествования.
Расширенная старшинство анализатор.

Смешанная стратегия Внеочередного анализатор, используемый оригинальная версия XPL . Расширяет «двойники», присущий любой старшинства распознавателя, включают в себя «тройки». Менее мощные , чем SLR. Как правило , имеет очень большие таблицы, даже для относительно небольших языков, таких как сам XPL, из — за огромные множество «троек» , которые необходимы признать грамматики вне ограничений , накладываемых методами очередности.

Очередность парсеры ограничены в грамматик они могут обрабатывать. Они игнорируют большую часть стека синтаксического анализа при принятии решений. Они считают, что только имена верхних символов, а не полный контекст, где в грамматике эти символы теперь появляются. Внеочередной требует, чтобы подобные выглядящим комбинации символов должны быть проанализированы и использованы в одинаковых способах по всей грамматике, однако эти комбинации случаются, вне зависимости от контекста.

LR парсеры более гибкая форма сдвига, уменьшить разборе, обработки гораздо больше грамматик.

LR Parser Processing

LR — анализаторы функционируют как конечный автомат , выполняя переход состояния для каждого сдвига или уменьшить действие. Они используют стек , где текущее состояние нажато (вниз) действия сдвига. Этот стек затем совал (вверх) по сокращению действия. Этот механизм позволяет LR анализатор для обработки всех детерминированных контекстно-свободных грамматик, супернабор очередностью грамматик. LR — анализатор полностью реализован анализатором Canonical LR . Look-Ahead LR и простые LR парсеры реализовать упрощенные варианты него , что значительно сниженные требования к памяти. Недавние исследования определили методы , с помощью которых канонических парсеры LR может быть реализованы с резко сниженными требованиями таблицы над алгоритмом таблица здания Кнута.

Является ли LR, LALR или SLR, основное состояние машины одно и то же; только таблицы разные, и эти таблицы почти всегда механически генерироваться. Кроме того, эти таблицы обычно реализуются таким образом, что УМЕНЬШИТЬ приводит к вызову в закрытую подпрограмму, которая является внешним по отношению к государственной машине и которая выполняет функцию, которая вытекает из семантики правила грамматики, сокращаются. Таким образом, анализатор разбивается на инвариантную состоянии часть машины, и часть семантики вариант. Это фундаментальное различие способствует развитию высококачественных анализаторов, которые являются исключительно надежными.

Принимая во внимание особое состояние стека и символ опережения, имеется ровно четыре возможные действия, ошибки, SHIFT, уменьшение и СТОП (далее по тексту конфигурации). Наличие точки, • в конфигурации представляет текущую позицию опережения, с символом опережения показано справа от точки (и который всегда соответствует терминальному символу), и текущее состояние стеки слева от точки (и которые , как правило , соответствуют нетерминальному символу).

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

00b представляет ERROR 01b представляет SHIFT 10b представляет СНИЖЕНИЯ 11b представляет СТОП

(СТОП быть частным случаем SHIFT). Весь массив обычно включает в себя в основном ERROR конфигурации, грамматики определенного числа SHIFT и УМЕНЬШИТЬ конфигурации, и одну конфигурацию STOP.

В системах программирование , которые поддерживают спецификацию значений в четвертичной системе счисления (основание 4, два бита на четвертичную цифру), такие как XPL, они закодированы как, например:

«(2) . . » представляет ОШИБКУ «(2) . 1 . » представляет SHIFT «(2) . 2 . » представляет СНИЖЕНИЯ «(2) . 3 . » представляет СТОП

SHIFT и таблицы ИЗБЕЖАНИЯ реализуются отдельно от массива. Вспомогательный массив «зондировали» только для текущего состояния и опережения символа. (Вспомогательный) массив «полный», в то время как (сдвиг и уменьшить) таблицы могут быть очень «разреженным» на самом деле, и значительные эффективности может быть достигнуто за счет оптимального «разложение» тех SHIFT и УМЕНЬШИТЬ таблицы (ERROR и STOP , не нужны никакие таблицы ).

SHIFT и ИЗБЕЖАНИЕ конфигурация очевидны из основного определения SHIFT-СНИЖЕНИЯ анализатора.

СТОП, а затем, представляет собой конфигурацию , в которой состояние в верхней части стеки и опережение терминального символа является в пределах предмета грамматики, и представляет собой окончание программы:

что нельзя переложить за последний ⊥ так, чтобы достичь, концептуально

ОШИБКА, то, представляет собой конфигурацию , в которой состояние на вершине стека, а опережения терминальный символ не является в пределах предмета грамматики. Это дает возможность вызвать процедуру восстановления после ошибки, возможно, в наиболее упрощенной форме, чтобы отказаться от опережения терминального символа и прочитать следующий терминальный символ, но и многие другие запрограммированные действия возможны, в том числе обрезки стека, или отбрасывая предпросмотр терминальный символ и обрезки стек (и в патологическом случае, это, как правило , можно получить

В большинстве случаев, стек намеренно предварительно загруженным, то есть, инициализируется с

при этом начальная ⊥ предполагается уже были признаны. Это, тогда, представляет собой начало программы, и, таким образом, позволяет избежать необходимости отдельной конфигурации START, который концептуально

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

Очевидно, что такой анализатор имеет ровно одну конфигурации (неявная) START и один (явные) конфигурации СТОП, но он может, и обычно имеет сотню SHIFT и УМЕНЬШИТЬ конфигурации, а также, возможно, тысячи конфигураций ОШИБОК.

3.3 lr17 (Лекции по конструированию компиляторов. В.А. Серебряков)

Описание файла

Файл «3.3 lr17» внутри архива находится в папке «Лекции по конструированию компиляторов. В.А. Серебряков». Документ из архива «Лекции по конструированию компиляторов. В.А. Серебряков», который расположен в категории «лекции и семинары». Всё это находится в предмете «формальные языки и автоматы» из шестого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Онлайн просмотр документа «3.3 lr17»

Текст из документа «3.3 lr17»

3.3. Разбор снизу-вверх типа сдвиг-свертка

В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной строки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как «свертку» строки w к начальному символу грамматики. На каждом шаге свертки подстрока, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подстрока, то в обратном порядке прослеживается правосторонний вывод (рис. 3.13).

Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к S, как показано на рис. 3.14.б). Дерево этой строки приведено на рис. 3.14 в).

В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F — левую часть правила F->id, то получим строку F+b*c. Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод:

Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы выделены. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A->v, не обязательно является основой, поскольку свертка по правилу A->v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c, которая не может быть сведена к S.

Формально, основа правой сентенциальной формы z — это правило вывода A->v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S=>*uAw=>uvw, то A->v в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с разбираемой строки w. Если w — слово в рассматриваемой грамматике, то w=Z_n, n-я правая сентенциальная форма еще неизвестного правого вывода

Чтобы восстановить этот вывод в обратном порядке, выделяем основу V_n в Z_n и заменяем V_n на левую часть некоторого правила вывода A_n -> V_n, получая (n-1)-ю правую сентенциальную форму Z_n-1. Затем повторяем этот процесс, т.е. выделяем основу V_n-1 в Z_n-1 и сворачиваем эту основу, получая правую сентенциальную форму Z_n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.

Таким образом, главная задача анализатора типа сдвиг-свертка — это выделение и отсечение основы.

В названии LR(k) символ L означает, что разбор осуществляется слева-направо, R — что строится правый вывод в обратном порядке, k — число входных символов, на которые заглядывает вперед анализатор при разборе. Когда k опущено, имеют в виду 1.

LR-анализ привлекателен по нескольким причинам:

— LR-анализ — наиболее мощный метод анализа без возвратов типа сдвиг-свертка;

— LR-анализ может быть реализован довольно эффективно;

— практически LR-анализаторы могут быть построены для всех конструкций языков программирования;

класс грамматик, которые могут быть проанализированы LR-методом, строго включает класс грамматик, которые могут быть анализированы предсказывающими анализаторами (сверху вниз типа LL).

Схематически структура LR-анализатора изображена на рис. 3.15. Он состоит из входа, выхода, магазина, управляющей программы и таблицы анализа, которая имеет две части — действий и переходов. Управляющая программа одна и та же для всех анализаторов, разные анализаторы различаются таблицами анализа. Программа анализатора читает символы из входного буфера по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида SX₁S₁X₂S₂. X_mS_m (S_m — верхушка магазина). Каждый X_i — символ грамматики (терминальный или нетерминальный), а S_i — символ, называемый состоянием. Каждый символ состояния выражает информацию, содержащуюся в магазине ниже него, а комбинация символа состояния на верхушке магазина и текущего входного символа используется для индексации таблицы анализа и определяет решение о сдвиге или свертке. В реализации символы состояния не обязательно должны размещаться в магазине. Однако их использование удобно для упрощения понимания поведения LR-анализатора.

Выход
Магазин S_m LR
анализатор
X_m

Таблица анализа состоит из двух частей: действия (action) и переходов (goto). Начальное состояние этого ДКА — это состояние, помещенное на верхушку магазина LR-анализатора в начале работы.

Конфигурация-LR анализатора — это пара, первая компонента которой — содержимое магазина, а вторая — непросмотренный вход:

(S0 X1 S1 X2 S2 . Xm Sm, ai ai+1 . an $)

Эта конфигурация соответствует правой сентенциальной форме

Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Основа сентенциальной формы всегда располагается на верхушке магазина. Таким образом, активный префикс — это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы.

Очередной шаг анализатора определяется текущим входным символом a_i и символом состояния на верхушке магазина S_m. Элемент таблицы действий action[S_m,a_i] для состояния S_m и входа a_i, может иметь одно их четырех значений:

1) shift S, сдвиг, где S — состояние,

2) reduce A->w, свертка по правилу грамматики A -> w,

3) accept, допуск,

Конфигурации, получающиеся после каждого из четырех типов шагов, следующие

1. Если action[S_m,a_i]=shift S, то анализатор выполняет шаг сдвига, переходя в конфигурацию

В магазин помещаются как входной символ a_i, так и следующее состояние S, определяемое action[S_m,a_i]. Текущим входным символом становится a_i+1.

2. Если action[S_m,a_i]=reduce A->w, то анализатор выполняет свертку, переходя в конфигурацию

где S=goto[S_m-r,A] и r — длина w, правой части правила вывода. Функция goto таблицы анализа, построенная по грамматике G, — это функция переходов детерминированного конечного автомата, распознающего активные префиксы G. Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние S_m-r. Затем анализатор помещает в магазин как A — левую часть правила вывода, так и S — содержимое таблицы goto[S_m-r,A]. На шаге свертки текущий входной символ не меняется. Для LR-анализаторов X_m-r+1 . X_m — последовательность символов грамматики, удаляемых из магазина, всегда соответствует w — правой части правила вывода, по которому делается свертка.

После осуществления шага свертки генерируется выход LR-анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например печатаются номера правил, по которым делается свертка.

3. Если action[S_m,a_i]=accept, то разбор завершен.

4. Если action[S_m,a_i]=error, анализатор обнаружил ошибку, то выполняются действия по диагностике и восстановлению.

Ниже приведен алгоритм LR-анализа. Все LR-анализаторы ведут себя одинаково. Разница между ними заключается в различном содержании таблиц действий и переходов.

Алгоритм 3.7. Алгоритм LR-анализа.

while (true)
<Пусть S - состояние на верхушке магазина;
if (action[S,InSym]==“shift S’“)
<поместить InSym и затем S' на верхушку
магазина;
прочитать в InSym следующий входной символ;
>
else if (action[S,InSym]==“reduce N->w”)
<удалить из магазина 2*|w| символов;
пусть теперь на верхушке магазина состояние S’;
поместить на верхушку магазина N, а
затем состояние goto[S’,N];
вывести правило N->w;
>
else if (action[S,InSym]==“accept”)
break;
>
else break;
>
>

Вначале в магазине помещено начальное состояние S, а в буфере w$, InSym содержит первый символ w$; Анализатор выполняет приведенную программу до тех пор, пока будет достигнуто либо состояние accept, либо состояние error.

Пример 3.6. На рис. 3.16 изображены функции action и goto LR-таблиц для грамматики арифметических выражений с бинарными операциями + и * примера 3.5. Здесь S_i означает сдвиг и помещение в магазин состояния i, R_j — свертку по правилу номер j, acc — допуск, пустая клетка — ошибку.

Diplom Consult.ru

ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ

Непосредственную левую рекурсию, т.е. рекурсию вида A → Aα , можно удалить следующим способом. Сначала группируем A -правила:

A → Aα 1 | Aα 2 | . | Aα m | β 1 | β 2 | . | β n ,

где никакая из строк β i не начинается с A . Затем заменяем этот набор

A → β 1 A 0 | β 2 A 0 | . | β n A 0

A 0 → α 1 A 0 | α 2 A 0 | . | α m A 0 | e

где A 0 – новый нетерминал. Из нетерминала A можно вывести те же цепочки, что и раньше, но теперь нет левой рекурсии. С помощью этой процедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шага. Приведенный ниже алгоритм 4.7 позволяет удалить все левые рекурсии из грамматики.

Алгоритм 4.7. Удаление левой рекурсии.

Вход . КС-грамматика G без e -правил (правил вида A → e ). Выход . КС-грамматика G 0 без левой рекурсии, эквивалентная G . Метод . Выполнить шаги 1 и 2.

(1) Упорядочить нетерминалы грамматики G в произвольном порядке.

(2) Выполнить следующую процедуру: for (i=1;i for (j=1;j A j → β 1 | β 2 | . | β k — все текущие правила для A j ; заменить все правила вида A i → A j α

на правила A i → β 1 α | β 2 α | . | β k α ;

удалить правила вида A i → A i ;

удалить непосредственную левую рекурсию в правилах для A i ;

После ( i − 1 )-й итерации внешнего цикла на шаге 2 для любого правила вида A k → A s α , где k , выполняется s > k . В результате на следующей итерации (по i ) внутренний цикл (по j ) последовательно увеличивает нижнюю границу по m в любом правиле A i → A m α , пока не будет m > i . Затем, после удаления непосредственной левой рекурсии для A i — правил, m становится больше i .

Алгоритм 4.7 применим, если грамматика не имеет e -правил (правил вида A → e ). Имеющиеся в грамматике e -правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e -правила.

4.3. ПРЕДСКАЗЫВАЮЩИЙ РАЗБОР СВЕРХУ-ВНИЗ

4.3.6 Левая факторизация

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

Если A → αβ 1 | αβ 2 – два A -правила и входная цепочка начинается с непустой строки, выводимой из α , мы не знаем, разворачивать ли по первому правилу или по второму. Можно отложить решение, развернув A → αA 0 . Тогда после анализа того, что выводимо из α , можно развернуть по A 0 → β 1 или по A 0 → β 2 . Левофакторизованные правила принимают вид

Алгоритм 4.8. Левая факторизация грамматики.

Вход . КС-грамматика G .

Выход . Левофакторизованная КС-грамматика G 0 , эквивалентная G .

Метод . Для каждого нетерминала A ищем самый длинный префикс α , общий для двух или более его альтернатив. Если α 6= e , т.е. существует нетривиальный общий префикс, заменяем все A -правила

A → αβ 1 | αβ 2 | . | αβ n | z,

где z обозначает все альтернативы, не начинающиеся с α , на

A 0 → β 1 | β 2 | . | β n

где A 0 – новый нетерминал. Повторно применяем это преобразование, пока никакие две альтернативы не будут иметь общего префикса.

Пример 4.7. Рассмотрим вновь грамматику условных операторов из примера 4.6:

S → if E then S | if E then S else S | a E → b

После левой факторизации грамматика принимает вид

S → if E then SS 0 | a S 0 → else S | e

К сожалению, грамматика остается неоднозначной, а значит, и не LL(1).

ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ

4.3.7 Рекурсивный спуск

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

В процедуре A для случая, когда имеется правило A → u i , такое, что u i e (напомним, что не может быть больше одного правила, из которого выводится e ), приведены два варианта 1.1 и 1.2. В варианте 1.1 де-

лается проверка, принадлежит ли следующий входной символ F OLLOW ( A ) . Если нет – выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую A .

if ( InSym F IRST ( u i )) // только одному! if (parse( u i ))

result(» A → u i «); else error();

if (имеется правило A → u i такое, что u i e ) //Вариант 1.1

if ( InSym F OLLOW ( A )) result(» A → u i «);

//Конец варианта 1.1 //Вариант 1.2: result(» A → u i «); //Конец варианта 1.2

//Конец варианта 1 //Вариант 2:

if (нет правила A → u i такого, что u e ) error();

//Конец варианта 2

if ( InSym 6= a ) return (false);

else InSym = getInsym();

4.4. РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА

else // X — нетерминал B B;

4.3.8 Восстановление после синтаксических ошибок

В приведенных программах рекурсивного спуска использовалась процедура реакции на синтаксические ошибки error(). В простейшем случае эта процедура выдает диагностику и завершает работу анализатора. Но можно попытаться некоторым разумным образом продолжить работу. Для разбора сверху вниз можно предложить следующий простой алгоритм.

Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ A и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либо из F IRST ( A ) , либо из F OLLOW ( A ) . В первом случае разворачиваем A по соответствующему правилу, во втором – удаляем A из магазина.

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

4.4 Разбор снизу-вверх типа сдвиг-свертка

В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как “свертку” цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис. 4.7). Здесь ко входной цепочке, так же как и при анализе LL(1)-грамматик, приписан концевой маркер $.

Подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой цепочки. Самая левая подцепочка, которая сопоставляется правой части некоторого правила вывода A →

ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ

γ , не обязательно является основой, поскольку свертка по правилу A →

γ может дать цепочку, которая не может быть сведена к аксиоме.

Формально, основа правой сентенциальной формы z – это правило вывода A → γ и позиция в z , в которой может быть найдена цепочка γ такие, что в результате замены γ на A получается предыдущая сентенциальная форма в правостороннем выводе z . Таким образом, если S r αAβ r αγβ , то A → γ в позиции, следующей за α , это основа цепочки αγβ . Подцепочка β справа от основы содержит только терминальные символы.

Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод αγβ и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с исходной цепочки w . Если w – слово в рассматриваемой грамматике, то w = α n , где α n – n -я правая сентенциальная форма еще неизвестного правого вывода S = α 0 r α 1 r . r α n−1 r α n = w .

Чтобы восстановить этот вывод в обратном порядке, выделяем основу γ n в α n и заменяем γ n на левую часть некоторого правила вывода A n → γ n , получая ( n − 1) -ю правую сентенциальную форму α n−1 . Затем повторяем этот процесс, т.е. выделяем основу γ n−1 в α n−1 и сворачиваем эту основу, получая правую сентенциальную форму α n−2 . Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S , то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.

4.4. РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА

Таким образом, главная задача анализатора типа сдвиг-свертка – это выделение и отсечение основы.

В названии LR(1) символ L указывает на то, что входная цепочка читается слева-направо, R – на то, что строится правый вывод, наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.

LR(1)-анализ привлекателен по нескольким причинам:

– LR(1)-анализ – наиболее мощный метод анализа без возвратов типа сдвиг-свертка;

– LR(1)-анализ может быть реализован довольно эффективно;

– LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;

– класс грамматик, которые могут быть проанализированы LR(1)-методом, строго включает класс грамматик, которые могут быть проанализированы предсказывающими анализаторами (сверхувниз типа LL(1)).

Схематически структура LR(1)-анализатора изображена на рис. 4.8. Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части – функцию действий ( Action ) и функцию переходов ( Goto ). Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Программа анализатора читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S 0 X 1 S 1 X 2 S 2 . X m S m ( S m – верхушка магазина). Каждый X i – символ грамматики (терминальный или нетерминальный), а S i –

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

Элемент функции действий Action [ S m , a i ] для символа состояния S m

и входа a i T < $ >, может иметь одно из четырех значений:

1) shift S (сдвиг), где S – символ состояния,

2) reduce A → γ (свертка по правилу грамматики A → γ ),

Linux.yaroslavl.ru

Когда Bison читает лексемы, он помещает их в стек вместе с их семантическими значениями. Стек называется стеком анализатора . Помещение лексемы в стек традиционно называется сдвигом .

Например, предположим, что инфиксный калькулятор прочёл `1 + 5 *’ , а далее во входном тексте следует `3′ . Стек будет содержать четыре элемента, по одному на каждую лексему, для которой был выполнен сдвиг.

Но стек не всегда содержит по элементу для каждой прочитанной лексемы. Когда последние n лексем и групп, для которых был выполнен сдвиг, соответствуют компонентам правила грамматики, они могут быть объединены в соответствии с этим правилом. Это называется свёрткой . Эти лексемы и группы заменяются в стеке одной группой, символ которой является результатом (левой частью) этого правила. Выполнение действия правила — часть процесса свёртки, потому что именно тогда вычисляется семантическое значение полученной группы.

Например, если стек анализатора инфиксного калькулятора содержит:

и следующая лексема — это литера новой строки, то последние три элемента могут быть свёрнуты до 15 правилом:

После этого стек будет содержать только три элемента:

В этот момент можно произвести ещё одну свёртку, получая единственное значение 16. Затем можно выполнить сдвиг для лексемы новой строки.

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

Этот тип анализаторов известен в литературе как анализатор снизу вверх.

Анализатор Bison не всегда выполняет свёртку немедленно, как только последние n лексем и групп соответствуют правилу. Причина этого в том, что такая простая стратегия не подоходит для обработки большинства языков. Вместо этого, когда свёртка возможна, анализатор иногда «смотрит вперёд» на следующую лексему, чтобы решить, что делать.

Когда лексема прочитана, сдвиг не выполняется сразу же, сначала она становится предпросмотренной лексемой , которая не помещена в стек. Теперь анализатор может выполнить одну или более свёрток лексем и групп в стеке, в то время, как предпросмотренная лексема остаётся за его пределами. Когда больше свёрток выполнять не следует, предпросмотренная лексема сдвигается в стек. Это не означает, что произведены все возможные свёртки, это зависит от типа предпросмотренной лексемы, некоторые правила могут предпочесть отложить своё применение.

Вот простой случай, когда нужен предпросмотр. Эти три правила определяют выражения, содержащие бинарную операцию сложения и постфиксную унарную операцию факториала ( `!’ ), а также допускают группировку скобками.

Предположим, что прочитаны и сдвинуты лексемы `1 + 2′ , что следует делать дальше? Если далее следует лексемы `)’ , то первые три лексемы должны быть свёрнуты до expr . Это единственный правильный вариант, поскольку сдвиг `)’ создаст последовательность символов term ‘)’ , но ни одно правило этого не допускает.

Если же далее следует лексема `!’ , она должна быть немедленно сдвинута, чтобы `2 !’ можно было свернуть до term . Если бы вместо этого анализатор выполнил свёртку ранее сдвига, `1 + 2′ стало бы expr . Тогда было бы невозможно сдвинуть `!’ , потому что сдвиг создал бы в стеке последовательность символов expr ‘!’ . Ни одно правило не допускает такой последовательности.

Текущая предпросмотренная лексема находится в переменной yychar . См. раздел 5.4 Специальные возможности, используемые в действиях.

Предположим, мы разбираем язык, имеющий операторы if-then и if-then-else, с помощью такой пары правил:

Здесь мы предполагаем, что IF , THEN и ELSE — терминальные символы лексем конкретных ключевых слов.

Когда лексемы ELSE прочитана и стала предпросмотренной лексемой, содержимое стека (предполагая, что входной текст правилен), как раз подходит для свёртки по первому правилу. Но законно также и сдвинуть ELSE , потому что это приведёт к последующей свёртке по второму правилу.

Такая ситуация, когда допустимы как сдвиг, так и свёртка, называется конфликтом сдвиг/свёртка . Bison разработан так, что он разрешает эти конфликты, выбирая сдвиг, за ислючением случаев, когда объявления приоритета операций указывают обратное. Чтобы понять причину этого решения, сравним его с другой возможной альтернативой.

Поскольку анализатор предпочитает сдвинуть ELSE , в результате предложение else будет относиться к самому внутреннем оператору if, что сделает два следующих входных текста эквивалентными:

Но если анализатор выбирал при возможности свёртку, а не сдвиг, в результате предложение else относилось бы к самому внешнему оператору if, что сделает эквивалентными следующие два входных текста:

Конфликт возникает потому что грамматика написана неоднозначно: правомерен любой способ разбор простого вложенного оператора if. Общепринятое соглашение состоит в том, что такие неоднозначности разрешаются отнесением предложения else к самому внутреннему оператору if. Именно это делает Bison, выбирая сдвиг, а не свёртку (идеальным было бы написать однозначную грамматику, но в данном случае это сделать очень трудно). Эта конкретная неоднозначность впервые встретилась в спецификации Algol 60 и называется неоднозначностью «кочующего else «.

Чтобы избежать предупреждений Bison о предсказуемых, законных конфликтах сдвиг/свёртка используйте объявление %expect n . Тогда предупреждений не последует до тех пор, пока число конфликтов сдвиг/свёртка в точности равно n . См. раздел 4.7.5 Подавление сообщений о конфликтах.

Определение if_stmt выше лишь несёт ответственность за возникновение конфликта, но на самом деле конфликт не возникнет без дополнительных правил. Вот полный фходной файл Bison, действительно обнаруживающий конфликт:

Другая ситуация, когда возникают конфликты сдвиг/свёртка, — это в арифметических выражениях. Здесь сдвиг — не всегда предпочтительное решение, объявления Bison приоритета операций позволят вам указать, когда выполняется сдвиг, а когда свёртка.

Рассмотрим следующий фрагмент неоднозначной грамматики (неоднозначной, потому что входной текст `1 — 2 * 3′ может юбыть разобран двумя разными способами):

Предположим, что анализатор рассмотрел лексемы `1′ , `-‘ и `2′ . Должен ли он выполнить свёртку по правилу для операции вычитания? Это зависит от следующей лексемы. Конечно, если далее следует лексема `)’ , мы должны выполнить свёртку, сдвиг будет неверным решением, потому что ни одно правило не может свернуть ни последовательность лексем `- 2 )’ , ни что-либо, начинающееся с неё. Но если следующая лексема — `*’ или ` , у нас есть выбор: как сдвиг, так и свёртка позволят удачно завершить разбор, но с разными результатами.

Чтобы решить, что должен делать Bison, мы должны рассмотреть результаты. Если сдвинуть следующую лексему знака операции op , она должна быть свёрнута первой, чтобы дать возможность свернуть разность. Результатом (на самом деле) будет `1 — (2 op 3′ . С другой стороны, если вычитание свернуть до сдвига op , результатом будет `(1 — 2) op 3′ . Поэтому ясно, что выбор сдвига или свёртки должен зависеть от относительного приоритета операций `-‘ и op : `*’ должна быть сначала сдвинута, а ` — нет.

А что можно сказать о таком входном тексте, как `1 — 2 — 5′ , должен ли он означать `(1 — 2) — 5′ или `1 — (2 — 5′ ? Для большинства операций мы предпочтаем первый вариант, называемый левой ассоциативностью . Второй вариант — правая ассоциативность желателен для операций присваивания. Выбор левой или правой ассоциативности — это вопрос о том, будет анализатор выбирать сдвиг или свёртку, когда стек содержит `1 — 2′ и предпросмотренная лексема — `-‘ . Сдвиг даёт правую ассоциативность.

Bison позволяет вам указать требуемый выбор с помощью объявлений приоритета операций %left и %right . Каждое такое объявление содержит список лексем, являющихся операциями, приоритет и ассоциативность которых определяется объявлением. Объявление %left делает эти все эти операции левоассоциативными, а %right — правоассоциативными. Третий вариант — %nonassoc , устанавливающий, что появление одной операции два раза «подряд» будет синтаксической ошибкой.

Относительный приоритет различных операций управляется порядком, в котором они объявляются. Первое в файле объявление %left или %right задаёт операции самого низкого приоритета, следующее такое объявление задаёт операции, приоритет которых немного выше и т.д.

В нашем примере нам нужны были следующие объявления:

В более законченном примере, поддерживающем также другие операции, нам следует объявлять их группами равного приоритета. Например, ‘+’ объявляется вместе с ‘-‘ :

(здесь NE и т.п. соответствуют операциям «не равно» и т.д. Мы полагаем, что эти лексемы содержат более одной литеры, и поэтому представляются именами, а не строками).

Во-первых, объявление приоритета присваивает уровни приоритета объявленным терминальным символам. Во-вторых, присваиваются уровни приоритета определённым правилам: каждое правило получает приоритет, равный приоритету последнего терминального символа среди его компонентов (вы можете также явно задать приоритет правила. См. раздел 6.4 Контекстно-зависимый приоритет.)

Наконец, конфликт разрешается сравнением приоритета рассматриваемого правила с приоритетом предпросмотренной лексемы. Если приоритет лексемы выше, выполняется сдвиг, если ниже — свёртка. Если приоритеты одинаковы, выбор делается исходя из ассоциативности этого уровня приоритета. Подробный выходной файл, создаваемый при использовании параметра `-v’ (см. раздел 10. Вызов Bison), объясняет, как был разрешён каждый конфликт.

Не все правила и не все лексемы имеют приоритет. Если у правила или у предпросмотренной лексемы нет приоритета, по умолчанию производится сдвиг.

Часто приоритет операции зависит от контекста. На первый взгляд, это звучит странно, но на самом деле это очень распространённый случай. Например, знак «минус» обычно имеет очень высокий приоритет как унарная операция, и несколько меньший (меньший, чем умножение) как бинарная операция.

Объявления приоритета Bison — %left , %right и %nonassoc — для данной лексемы могут использоваться только один раз, поэтому лексема имеет только один приоритет, объявленный таким образом. Чтобы воспользоваться контекстно-зависимым приоритетом, вам нужно использовать дополнительный механизм: модификатор правил %prec .

Модификатор %prec объявляет приоритет конкретного правила, указывая терминальный символ, приоритет которого следует использовать для этого правила. Этот символ не обязательно должен появляться в самом правиле. Синтаксис модификатора таков:

Он ставится после всех компонентов правила. В результате правилу вместо приоритета, который должен быть присвоен ему обычным способом, присваивается приоритет символа терминальный_символ . Затем изменённый приоритет правила влияет на разрешение конфликтов с участием этого правила (см. раздел 6.3 Приоритет операций).

Вот как %prec решает проблему унарного минуса. Во-первых, объявим приоритет фиктивного терминального символа UMINUS . Лексем такого типа нет, этот символ служит только для определения его приоритета.

Теперь приоритет UMINUS можно использовать в правилах:

Функция yyparse реализована с использованием машины с конечным числом состояний. Значения, помещаемые в стек анализатора — не просто коды типов лексем, они представляют всю последовательность терминальных и нетерминальных символов на вершине стека или около неё. Текущее состояния содержит всю информацию о более раннем входном тексте, относящуюся к решению вопрос, что делать далее.

Каждый раз, когда читается предпросмотренная лексема, текущее состояние анализатора и тип предпросмотренной лексемы ищутся в таблице. Эта ячейка таблицы может говорить, например: «Выполнить сдвиг для предпросмотренной лексемы». В этом случае она также задаёт новое состояние анализатора, помещаемое на вершину стека. Или же она может говорить: «Выполнить свёртку, используя правило номер n «. Это означает, что определённое количество лексем и групп снимаются с вершины стека и заменяются одной группой. Другими словами, из стека вынимаются несколько состояний, и в него помещается одно новое.

Есть ещё одна возможность — таблица может сказать, что предпросмотренная лексема в текущем состоянии недопустима. Это запускает процесс обработки ошибок (см. раздел 7. Восстановление после ошибок).

Конфликт свёртка/свёртка возникает, когда есть два правила или более, применимых к одной последовательности входного текста. Это обычно свидетельствует о серьёзной ошибке в грамматике.

Например, вот ошибочная попытка определить последовательность нуля или более групп word :

Ошибка состоит в неоднозначности: есть более одного способа разобрать одиночное слово word в sequence . Оно может быть свёрнуто до maybeword , а затем до sequence по второму правилу. Или же «совсем ничто» может быть свёрнуто до sequence по первоум правилу, и объединено с word , используя третье правило для sequence .

Есть также более одного способа свёртки «совсем ничего» в sequence . Это может быть непосредственно сделано по первому правилу, или косвенно через maybeword , и затем применением второго правила.

Вы можете думать, что это безразлично, потому что это не влияет на то, является какой-либо входной текст правильным, или нет. Но это влияет на то, какие правила выполняются. Один порядок разбора выполнит действие второго правила, другой — действия первого и третьего правила. В этом примере изменится вывод программы.

Bison разрешает конфликты свёртка/свёртка, выбирая правило, появляющееся в грамматике раньше, но полагаться на это очень рискованно. Каждый конфликт свёртка/свёртка должен быть изучен и обычно исключён. Вот правильный способ определения sequence :

Вот ещё одна распространённая ошибка, приводящая к конфликтам свёртка/свёртка:

Здесь сделана попытка определить последовательность, которая может содержать либо группы word , либо redirects . Сами по себе определения sequence , words и redirects не содержат ошибок, но все вместе создают тонкую неоднозначность: даже пустая строка может быть разобрана бесконечным числом способов!

А именно: «совсем ничто» может быть words . Или оно может быть двумя words подряд, тремя, или любым другим количеством. Или оно может быть words , за которым следуют три redirects , а затем ещё одно words . И так далее.

Есть два способа исправить эти правила. Во-первых, сделать последовательность одноуровнневой:

Во-вторых, запретить, чтобы words или redirects были пустыми:

Иногда могут возникать конфликты свёртка/свёртка, выглядящие неоправданными. Вот пример:

Может показаться, что эта грамматика может быть разобрана с предпросмотром только на одну лексему: если прочитано param_spec , то ID является name , если далее следует запятая или двоеточие, и type , если следует ID . Другими словами, эта грамматика является LR(1)-грамматикой.

Тем не менее, Bison, как и большинство генераторов анализаторов, на самом деле может обрабатывать не все LR(1)-грамматики. В этой грамматике два контекста — после ID в начале param_spec и контекст в начале return_spec достаточно похожи, чтобы Bison полагал их одинаковыми. Они оказываются похожими, потому что должен действовать один и тот же набор правил — правило свёртки до name и правило свёртки до type . В этой стадии обработки Bison неспособен определить, что в разных контекстах правилам потребуются разные предпросмотренные лексемы, и поэтому создаёт одно состояние анализатора для них обоих. Объединение этих двух контекстов позднее вызовет конфликт. В терминологии синтаксических анализаторов, этот случай означает, что грамматика не является LALR(1).

В общем, лучше устранить недостатки, чем документировать их. Но этот конкретный недостаток по его природе трудно устранить — генератор анализаторов, который может обрабатывать LR(1)-грамматики трудно написать, и он будет создавать очень большие анализаторы. На практике Bison более полезен в том виде, в котором он существует сейчас.

Когда возникает эта проблема, вы часто можете решить её, выявив два состояния анализатора, которые были смешаны, и добавляя что-нибудь, чтобы они выглядели по-разному. В вышеприведённом примере добавление одного правила к return_spec , как указано ниже, устранит проблему:

Это решит проблему, поскольку появляется возможность использования ещё одного правила в контексте после ID в начале return_spec . Это правило не действует в соответствующем контекта в param_spec , поэтому эти два контекста получат разные состояния анализатора. До тех пор, пока лексема BOGUS не генерируется yylex , добавленное правило не изменит способ разбора ни одного реального входного текста.

В этом конкретном примере есть и другой способ решения проблемы: переписать правило для return_spec , чтобы оно использовало ID непосредственно, а не через name . Это также приведёт к тому, что два путающихся контекста будут иметь различные наборы действующих правил, потому что контекст return_spec задействует изменённое правило для return_spec , а не правило для name .

Стек анализатора Bison может переполниться, если для слишком многих лексем выполнен сдвиг и не выполнена свёртка. Когда это происходит: функция анализатора yyparse завершает работу и возвращает ненулевое значение, лишь вызвав перед этим yyerror чтобы сообщить об ошибке.

Определяя макрос YYMAXDEPTH , вы можете указать, какой глубины может достичь стек анализатора перед тем, как произойдёт переполнение стека. Определите этот макрос целым значением. Это значение — максимальное число лексем, для которых может быть выполнен сдвиг (и не выполнена свёртка) до того, как произойдёт переполнение. Оно должно быть константным выражением, значение которого известно во время компиляции.

Не обязательно выделять всё допустимое для стека пространство. Если вы задаёте большое значение YYMAXDEPTH , анализатора на самом деле сначала выделяет небольшой стек, и затем постепенно увеличивает его по мере необходимости. Это последовательное выделение происходит автоматически и незаметно. Поэтому вам не нужно делать YYMAXDEPTH болезненно малым только для того, чтобы сберечь память для обычных входных текстов, не нуждающихся в большом объёме стека.

Значение YYMAXDEPTH по умолчанию, если вы не определили его, составляет 10000.

Вы можете управлять размером стека, выделяемого при инициализации, определяя макрос YYINITDEPTH . Это значение также должно быть целочисленной константой, доступной во время компиляции. Значение по умолчанию составляет 200.

Принципы построения распознавателей КС-языков без возвратов

Читайте также:

Aрхитектурныe основы построения нейросистем на базе нейрочипа
I, d – диаграмма влажного воздуха и принцип ее построения
I. Медико-гигиеническое воспитание, цели, задачи, принципы.
I. Предмет, цели, задачи, принципы специальной психологии
I. Предмет, цели, задачи, принципы специальной психологии
I.3. Основные принципы психологии.
II. Принципы производственного обучения
III. Организация вахты на мостике. Общие принципы организации вахты
III. Основные факторы и принципы, определяющие развитие психологии. Категориальный строй психологии.
IV. Первая медицинская помощь и основные принципы лечения.
IV. Принципы экологического права.
А. Основополагающие принципы прав человека

Поделитесь ссылкой пожалуйста:

Общие принципы работы табличных распознавателей

Табличные распознаватели для КС-языков

Дата добавления: 2014-01-20 ; Просмотров: 638 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Конспект лекций По предмету Системное программное обеспечение Ташкент 2008

Название	Конспект лекций По предмету Системное программное обеспечение Ташкент 2008
страница	9/30
Дата	29.05.2013
Размер	5.65 Mb.
Тип	Конспект лекций
скачать

1. /Sistemnoe_programnoe_obespecheniye.doc

Конспект лекций По предмету Системное программное обеспечение Ташкент 2008

Распознаватель на основе алгоритма «сдвиг-свертка»

Принцип работы восходящего распознавателя по алгоритму «сдвиг-свертка»

Функция переходов МП-автомата строится на основе правил грамматики:

(q,A)e8(q,^,y), AeVN, ye(VTuVN)*, если правило А-»у содержится во множестве правил Р грамматики G: А->у е Р.
(q,a)e5(q,a,A.) VaeVT.

что необходимо выполнять: сдвиг или свертку;
если выполнять свертку, то какую цепочку у выбрать для поиска правил (цепочка у должна встречаться в правой части правил грамматики);
какое правило выбрать для свертки, если окажется, что существует несколько правил вида А-»у (несколько правил с одинаковой правой частью).

Реализация распознавателя с возвратами на основе алгоритма «сдвиг-свертка»

всех возможных правил из множества правил Р с номером j для подцепочки р

причем оно есть первое подходящее правило для цепочки ар, для которой пра

вило вида А-»р существует. Если удалось выполнить свертку — возвращаемся i

шагу 1, иначе — переходим к шагу 2.

Шаг 2 (Перенос — сдвиг). Если i (q, i+1, аг_ь Оу), a, eVT

Если i = n+1, то перейти к шагу 3, иначе перейти к шагу 1.

Шаг 3 (Завершение). Если состояние соответствует (q, n+1, S, у), то разбор завер

шен, алгоритм заканчивает работу, иначе перейти к шагу 4.

Шаг 4 (Переход к возврату), (q, n+1, а, у) -» (Ь, п+1, а, у). Шаг 5 (Возврат). Если исходное состояние (b, i, аА, jy), то:

О иначе сигнализировать об ошибке и прекратить выполнение алгоритма.

Если исходное состояние (b, i, аа, Оу), a eVT, то если i > 1, тогда перейти в cm

дующее состояние (b, i-1, а, у) и вернуться к шагу 5; иначе сигнализировать с

ошибке и прекратить выполнение алгоритма.

В случае успешного завершения алгоритма цепочку вывода можно построить i

основе содержимого стека L₂, полученного в результате выполнения алгоритм

Для этого достаточно удалить из стека L₂ все цифры 0 — и получим последов

тельность номеров правил.

Этот алгоритм может быть напрямую использован для построения распознав

телей. Следует помнить, что для применения этого алгоритма исходная грамм

Возьмем в качестве примера грамматику G(<+,-,/,*,а,b>, , P, S):

S -> S+T | S-T | Т*Е | Т/Е | (S) | а | b

Т -» Т*Е | Т/Е | (S) | а | b

Рис. 11.3. Дерево вывода для грамматики без цепных правил

Табличные распознаватели для КС-языков

Общие принципы работы табличных распознавателей

Тогда существованию вывода S=>*a соответствует условие SeT[l,n].

При условии существования вывода по таблице Т_п._п можно найти всю полную цепочку вывода S=s>*a.

Сам алгоритм Кока—Янгера—Касами можно описать следующим образом:

Цикл для j от 1 до п

T[l.j] := <А | 3 АтМ, eP >— i T[l,j] включаются все нетерминальные символы,

для которых в грамматике G существует правило А->а.

Конец цикла для j.

Цикл для i от 2 до п

Цикл для j от 1 до n-1+l T[i.j] := 0; Цикл для к от 1 до п-1

Если j = 1 и существует правило A-»aj, то выдать номер этого правила.
Иначе (если j > 1) возьмем к как наименьшее из чисел, для которых 3 А—»ВХ е Р, BeT[k,j], CeT[i-k,j+k] (таких правил может быть несколько, д; определенности берем наименьшее к). Пусть правило А-»ВС имеет номер i Тогда нужно выдать этот номер ш, потом вызвать сначала R(i,k,B), а затем R(i-k,j+k,C).

Алгоритм Эрли (основные принципы)

Алгоритм Эрли подробно здесь не рассматривается. Его описание можно найти, например, в книге [6, т. 1].

Принципы построения распознавателей КС-языков без возвратов

Классы кс-языков и грамматик.

Нисходящие распознаватели КС-языков без возвратов

Левосторонний разбор по методу рекурсивного спуска

Алгоритм разбора по методу рекурсивного спуска

А->у, ye(VNuVT)* и это единственное правило для А;

Исключение ^-правил.
Исключение левой рекурсии.
Добавление новых нетерминальных символов. Например:

если правило: A->aa₁|aa₂|. |aa_n|b₁p₁|b₂p₂|. |b_mp_m,

4. Замена нетерминальных символов в правилах на цепочки их выводов.
Например:

если имеются правила:

Пример реализации метода рекурсивного спуска

С.-> АаВЬ Необходимо построить распознаватель, работающий по методу рекурсивного спуска.

Видно, что грамматика удовлетворяет условиям, необходимым для построения такого распознавателя.

цепочка входных символов;
положение указателя (считывающей головки МП-автомата) во входной цепочке;
массив для записи номеров примененных правил;
порядковый номер очередного правила в массиве.

void WriteRulesdnt* piRul. int* iP, int iRule)

int proc_S (char* szS, int IN, int* piRul, int* iP)

Почему снизу вверх разбор чаще, чем сверху вниз разбор?

November 2020

9.7k раз

Кажется, что рекурсивные спуском парсеры не только проще всего объяснить, но и проще разрабатывать и поддерживать. Они не ограничивается LALR (1) грамматика, а сам код может быть понят простыми смертными. В отличие от этого, снизу вверх парсеры имеют ограничения на грамматик они способны распознать, и должны быть получены с помощью специальных инструментов (поскольку таблицы, подталкивают их в следующем за невозможно произвести вручную).

Почему же тогда, как снизу вверх (то есть сдвиг-свертка) разбор чаще, чем сверху вниз (то есть рекурсивный спуск) разбор?

6 ответы

Я никогда не видел реальное сравнение между сверху вниз и сдвиг-свертка анализатор:

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

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

так, как говорить честно о чем-то мы никогда не делали: сравнения строго два подхода?

Чтобы добавить другие ответы, это важно понимать , что помимо эффективности, восходящие парсеры могут принимать значительно больше грамматик , чем рекурсивный спуска парсеров делать. Нисходящие парсеры -whether предсказания ИЛИ НЕ может только иметь 1 опережение маркера и потерпеть неудачу , если текущий маркер и все , что непосредственно следует маркеру , может быть получена с использованием двух различных правил. Конечно, вы могли бы реализовать синтаксический анализатор , чтобы иметь больше lookaheads (например , LL (3)), но как далеко вы готовы толкать его , прежде чем он становится столь же сложным , как снизу вверх парсер? Восходящие парсеры (LALR специально) с другой стороны, сохранить список firsts и follows и может обрабатывать случаи , когда сверху вниз парсеры не может.

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

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

Разница в производительности становится усиливается по мере усложнения грамматики возрастает.

Если вы выбираете мощный генератор парсеров, вы можете кодировать грамматику, не заботясь о специфических свойствах. (LA) LR означает, что вам не придется беспокоиться о левой рекурсии, один меньше головной боли. РВО означает, что вам не придется беспокоиться о локальной двусмысленности или опережающего просмотра.

А снизу вверх парсеры имеют тенденцию быть довольно эффективным. Таким образом, как только вы заплатили цену немного сложной техники, то проще написать grammers и парсеры работают хорошо.

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

У меня есть два предположения, хотя я сомневаюсь, что либо полностью объясняет:

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

Лучшие инструменты. Если вы можете выразить язык в каком-то варианте EBNF, то скорее всего, вы можете Lex / Yacc свой путь мимо всего много утомительного кода. Там, кажется, не будут так много инструментов, чтобы помочь автоматизировать задачу собирает сверху вниз анализатор. И давайте посмотрим правде в глаза, скрипели код парсера просто не забавная часть поигрывая языков.

Это происходит от нескольких различных вещей.

BNF (и теория грамматик и такой) происходят от компьютерной лингвистики: людей, исследующей естественного языка разбора. BNF очень привлекательный способ описания грамматики, и поэтому естественно, хотят, чтобы потреблять эти обозначения, чтобы произвести синтаксический анализатор.

К сожалению, методы синтаксического анализа сверху вниз, как правило, падают, когда применяются к таким обозначениям, потому что они не могут обрабатывать много общих дел (например, левая рекурсии). Это оставляет вас с семьей LR, который выполняет хорошо, и может обрабатывать грамматик, и так как они производятся на машине, кто заботится, что код выглядит?

Вы правы, хотя: сверху вниз парсеры работать «интуитивно», поэтому они легче отлаживать и поддерживать, и как только вы немного практики, они так же, как легко писать, как генерируемые инструментами. (Особенно, когда вы получаете в сдвиг / свёртка ад конфликтов.) Многие из ответов говорят о разборе производительности, но на практике сверху вниз парсеры часто могут быть оптимизированы, чтобы быть столь же быстро, как машинно генерируемых анализаторами.

Именно поэтому многие производственные компиляторы используют рукописный лексические и парсер.