Задача разбора

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

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

Различают две категории алгоритмов разбора: нисходящий(сверху вниз) и восходящий( снизу вверх. Эти термины соответствуют способу построения синтаксических деревьев. При нисходящем разборе дерево строится от корня (начального символа) вниз к концевым узлам. Рассмотрим предложение 35 в следующей грамматике целых чисел.

На каждом последующем шаге самый левый элементарный символ V текущей сентенциальной формы xV y заменяется на правую часть правила V::=u, в результате получается следующая сентенциальная форма. Этот процесс для предложения 35 представлен в виде 5 деревьев. Требуется получить сентенциальную форму, которая совпадает с заданной цепочкой.

Метод восходящего разбора состоит в том, что отправляясь от заданной цепочки пытаются привести её к начальному символу. На первом шаге терминал 3 приводится к Д, в результате чего получается сентенциальная форма Д5.

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

Определение 12:

Непосредственный вывод хUу => xuy называется каноническим и записывается хUу => xuy, если у содержит только терминалы.

Вывод W=>⁺V называется каноническим и записывается W=>⁺V, если каждый непосредственный вывод в нём является каноническим.

Классификация грамматик по Холмскому.

По Холмскому грамматика – это четвёрка (V, T, P, Z).

1. V – алфавит.

2. Т V - алфавит терминальных символов

3. Р – конечный набор правил постановки.

4. Z – начальный символ, который не является терминалом ( V – T)

Язык, порождаемый грамматикой, - это множество терминальных цепочек, которые можно вывести из Z.

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

Говорят, что G – это грамматика типа 0(по Холмскому) или грамматика с фазовой структурой, если правила имеют вид: u::=U, где u V⁺, U V*, т.е. левая часть u может быть тоже последовательностью символов, а правая – пустой. Грамматики с фазовой структурой имеют небольшой употребление.

Если ввести ограничения на правила подстановки, то получится более интересный класс языков типа 1, называемых контекстно – зависимыми. Правила подстановки имеют вид:

xUу::=xuy, где U V-T; u V⁺; x,y V*

Термин контекстно-зависимые отражает тот факт, что можно заменить U на u в контексте х…..у.

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

U::=u, где U V-T и u V*

В КС – грамматиках может появится правило вида U::=λ.

По заданной КС – грамматике G можно сконструировать неукорачивающую грамматику типа G1 или λ – свободную, такую что L(G1)=L(G) – { λ} (тот же самый язык)

Если мы ограничим правила ещё раз, приведя их к виду U::=u или U::=WN, где N T U,W V-T, то мы получим грамматику типа 3 или регулярную грамматику.

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

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

Большинство символов в языках программирования попадают в один из следующих классов: идентификаторы, служебные слова (подмножество идентификаторов), целые числа, однолитерные разделители (+, -, *, :=, и.т.д. ). Эти символы могут быть описаны следующим простыми правилами:

<идентификатор>::= буква |<идентификатор>

буква |<идентификатор> цифра

<целое>::<цифра>|<целое> цифра

<разделитель>::=+|- | ( | ) | / |…

<разделитель>::=<SLASH>|<SLASH>*|<AST>*|

<COLON>=

<SLASH>::=/

<AST>::= *

<COLON>::=:

Правила могут быть ещё проще, но мы их записываем так, чтобы каждое правило имело вид U::=Т – левая часть терминал или U::=VT- левая часть начинается с нетерминала. Грамматики с такими правилами – регулярные грамматики.

Рассмотрим эффективный способ разбора предложений регулярной грамматики.

грамматики.