Восходящий алгоритм синтаксического разбора контекстно-свободных грамматик

Кроме того она способна генерировать внятные синтаксические ошибки вида неразбираемый символ такойто в такойто позиции и в случае если во всей строке таблицы разбора есть только 1 операция сдвига вида ожидался такойто символ. Введем понятие символ RK L то есть символ на который указывает цепочка. Это Lый символ из правой части правила K. Завершенная цепочка не указывает ни на какой символ.

2014-07-24

9.9 KB

17 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


LR(0) — Восходящий алгоритм синтаксического разбора контекстно-свободных грамматик, один из видов LR.

LR(0) редко применяется на практике из-за узкого класса разбираемых грамматик, но является основой для более мощных алгоритмов SLR(1) и LALR(1), последний из которых имеет богатое практическое применение.

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

Такая фаза исполнения работает очень быстро (линейное время), способна разбирать все LALR(1)-языки, то есть почти все используемые языки программирования. Кроме того, она способна генерировать внятные синтаксические ошибки вида «неразбираемый символ такой-то в такой-то позиции» и, в случае, если во всей строке таблицы разбора есть только 1 операция сдвига — вида «ожидался такой-то символ».

Ввиду высокой сложности построения таблицы разбора для алгоритмов LR(0), SLR(1) и LALR(1) обычно для этого используется генератор анализаторов типа yacc, при необходимости быстро написать анализатор вручную используется метод рекурсивного спуска или же LL(1).

[править] Построение таблицы разбора при генерации анализатора

Введем понятие «цепочка». Это — правая часть некоего правила в грамматике, и позиция в ней, от 0 дo N (длина правой части), позиция N означает — за концом правой части правила. Обозначим цепочку R(K, L), где K — номер правила, а L — позиция в правой части.

Цепочку, где L = длина правой части правила K, назовем завершенной.

Введем понятие «символ R(K, L)», то есть символ, на который указывает цепочка. Это L-ый символ из правой части правила K. Завершенная цепочка не указывает ни на какой символ.

Введем понятие «множество начальных цепочек для нетерминала». Для нетерминала A в множество начальных цепочек входят:

  •  все цепочки R(K, 0), если K-ое правило имеет A в левой части.
  •  все цепочки R(M, 0), если M-ое правило имеет в левой части нетерминал, на который указывает одна из уже найденных начальных цепочек.

Введем понятие «состояние» как множества цепочек.

Введем понятие «начальное состояние» как множество начальных цепочек символа E — начала грамматики.

Введем понятие «сдвиг» (shift) как переход из состояния в состояние под действием символа (нетерминала или терминала). Новое состояние строится из старого при сдвиге по символу A следующим образом:

  •  из множества удаляются все цепочки, которые указывают на символ, отличный от A
  •  оставшиеся цепочки заменяются R(K, L) → R(K, L + 1)
  •  для каждой из замененных цепочек определяется символ, на который они указывают, и, если это нетерминал, к множеству добавляется множество начальных цепочек для этого нетерминала.

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

Для грамматики строится начальное состояние.

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

Далее строится таблица разбора, по вертикали — номера состояний (0 — начальное состояние), по горизонтали — символы (терминалы, нетерминалы и символ «конец потока»).

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

Далее заменяется начало грамматики S → E и для нового начала S в клеточку (S, конец потока) заносится значение «успешное окончание разбора».

Далее в таблицу заносятся действия приведения (reduce), только для терминалов, следующим образом: если в состоянии S есть завершенная цепочка, то во все клеточки (S, терминал) заносится значение «приведение по правилу R, правая часть длиной N символов, получаем нетерминал C из левой части правила».

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

[править] Исполнение анализатора по потоку символов

Используется стек анализатора, где находятся номера состояний, входной (терминалы и конец потока) и выходной (номера правил) потоки.

Вначале в стек заносится 0.

Далее, пока не получена синтаксическая ошибка или успешное окончание разбора:

  •  по состоянию на вершине стека S и следующему символу входного потока I производится обращение к клеточке (S, I) таблицы разбора
  •  если клеточка пуста — это синтаксическая ошибка.
  •  если в клеточке «успешное окончание разбора» — это успешное окончание разбора (возникает только в конце входного потока, и не всегда).
  •  если в клеточке «сдвиг в состояние S-штрих» — то затолкнуть S-штрих в стек, и поглотить символ из входного потока.
  •  если в клеточке «приведение по правилу R, правая часть длиной N символов, получаем нетерминал C из левой части правила» — то а) вывести R в выходной поток, б) вытолкнуть верхние N номеров из стека, в) обратиться к клеточке таблицы (S, C), получить оттуда номер состояния и г) затолкнуть его в стек. Символ входного потока не поглощается.



 

Другие похожие работы, которые могут вас заинтересовать.
3214. ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО ГРАФА 18.84 KB
  Один из них это написать универсальную программу грамматического разбора пригодную для всех возможных грамматик заданного класса. Другой метод – это разработка программы грамматического разбора специально для заданного конкретного языка; при этом его синтаксис по определенным правилам отображается в последовательность операторов т. Такую реализацию разбора будем называть программно управляемой. Программа грамматического разбора предназначенная специально для...
3183. Изучение алгоритмов грамматического разбора предложений 12.95 KB
  Содержание работы: В процессе выполнения лабораторной работы должны быть изучены структуры синтаксических графов и возможность их применения для задачи нисходящего распознавания предложений языка для заданного синтаксиса. Заданный синтаксис некоторого языка удобно представлять в виде синтаксического графа или графа распознавания. Такой граф отражает управление ходом работы при грамматическом анализе предложений. Синтаксический граф является эквивалентным...
13551. Замон фалсафий, мантиқий ва грамматик бирлик сифатида 17.64 KB
  Замон категорияси феълдан англашилган ишҳаракат тасдиғи ёки инкорини вақт тушунчасига боғлаб қайд этади. Демак замон шаклини ясовчи қўшимчалар объектив борлиқда рўй берган рўй бераётган ёки рўй бериши кутилган воқеаҳодисаларнинг бажарилиш вақтини ифодалайди. Маълумки борлиқ материя объектив характерга эга бўлиб унинг мавжудлик шакллари макон ва замондир.
8077. D-алгоритм 37.33 KB
  Алгоритм Рота сформулирован на языке кубических комплексов, координатой кубического комплекса является одно из значений алгоритма {0, x, 1, d, не d}. Алгоритм начинается с места проверяемой неисправности и дялее двигается от места неисправности к выходам схемы, при этом на каждом цикле вычислений отбрасываются несущественные пути. Эта процедура называется прямой фазой продвижения алгоритма.
6665. Генетический алгоритм (ГА) 64.45 KB
  Генетический алгоритм (ГА) — адаптивный поисковый метод, основанный на селекции лучших элементов в популяции, подобно эволюционной теории Ч.Дарвина. Свои принципы и терминологию ГА заимствуют из естественной генетики.
13723. Энциклопедия Амосова. Алгоритм здоровья 786.97 KB
  Как жить, чтобы укрепить свое здоровье, сохранить до глубокой старости ясный ум и работоспособность? О научных основах жизни человека, о том, как лучше организовать свой труд, отдых, питание, семейную жизнь, почему вредны всякого рода излишества, вы узнаете из книги видного ученого, известного хирурга, кибернетика Н.М. Амосова.
17606. Rриптографический алгоритм шифрования Хаффмана 136.04 KB
  Обоснование цели разработки программы Использование программы шифрования обеспечит: Надёжную защиту данных от несанкционированного доступа. Функции программы должны выполняться безошибочно также должна быть защита информации от вторжения пользователей не имеющих прав доступа к использованию данной информации.
220. Модифицированный алгоритм Роббинса-Монро 51.25 KB
  Модификация алгоритма РоббинсаМонро для условий когда известны диапазоны изменения контролируемых признаков только для работоспособного состояния объекта 2. Группировка обучающих образов и ранжирование групп 1 Множественная определенность априорной информации об объекте охватывает случай когда известны диапазоны изменения контролируемых признаков только для работоспособного состояния: Δj = [] j = . 6 Произвольное наблюдаемое состояние принадлежащее iму...
1381. Алгоритм оптимизации диска методом чувствительности 1.12 MB
  При постановке задач оптимизации используется параметризованный чертеж (эскиз разрабатываемой конструкции) с рядом размеров, допускающих варьирование в заданных пределах. Они называются параметрами проектирования.
9027. АЛГОРИТМ ПОСТРОЕНИЯ МАКСИМАЛЬНОГО ПОТОКА В ТРАНСПОРТНОЙ СЕТИ 73.94 KB
  Определение прибавляющей цепи. Алгоритм построения максимального потока в транспортной сети. Определение прибавляющей цепи Из теоремы Форда-Фолкерсона следует что максимальный поток в сети не превосходит минимальной пропускной способности разреза то есть .
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.