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

На данной фазе осуществляется анализ корректности грамматики и приведение её к виду (внутреннему представлению), ускоряющему грамматический разбор текстов ЛОЗ на специфицируемом языке. При анализе выявляется наличие тупиков (недости­жи­мых и неопределенных нетерминалов) и многократно определенных нетерминалов, ошибки в атрибутах, именах синтермов, следовании метасимволов и т.п.

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

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

::= - разделитель синтаксического понятия и синтаксического выражения (левой и правой частей продукции);

<_ - левая скобка нетерминала в правой части продукции;

_> - правая скобка нетерминала в правой части продукции;

?_ - левая скобка альтернативы;

_? - правая скобка альтернативы;

_|_ - разделитель альтернативы,

{_ - левая итеративная скобка;

_} - правая итеративная скобка;

[ _ - левая факультативная скобка,

_ ] - правая факультативная скобка,

(_ - левая скобка семантики,

_) - правая скобка семантики,

@_ - левая скобка синтерма,

_@ - правая скобка синтерма,

** - конец продукции.

Запись продукции в системе имеет вид:

левая часть продукции::= правая часть продукции **

Начальная фраза каждой продукции, заканчивающаяся разделителем ¢ ::= ¢, рассматривается системой как синтаксическое понятие (нетерминал). Фраза между разделителями ¢::=¢ и ¢**¢ (правая часть продукции) является синтаксическим выражением, определяющим множество сентенциальных форм, связанных с синтаксическим понятием, определенным левой частью этой же продукции.

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

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

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

LEX - произвольная лексема (разделитель или элемент между разделителями);

IDN - идентификатор, т.е. набор букв и цифр, начинающихся с буквы (буквы, как латинского, так и русского алфавита);

INT - целое число;

REL - действительное число;

TXT - текстовая константа (в апострофах или кавычках);

EOF - конец исходного файла.

Любой текст S в факультативных скобках рассматривается как синтаксическое выражение, порождающее множество сентенциальных форм, являющихся объединением пустой последовательности и S. Таким образом, правило вида

A::= B [_S_] C **

представляет собой, по сути дела, два правила:

A::= BC ** и A::= BSC **.

Здесь и далее S - обозначает синтаксическое выражение.

Любой текст S в итеративных скобках рассматривается как синтаксическое выражение, порождающее множество сентенциальных форм, являющихся объединением пустой последовательности и S, SS, SSS, и т.д. Правило вида

А::= B {_,S_} C **

представляет счетное множество:

A::= BC **, A::= B,SC **, A::= B,S,SC **, A::= B,S,S,SC **, ¼

Альтернативная фраза вида: ?_ S1 _|_ S2 _|_ S3 _|_... SN _?, где S1,...,SN - синтаксические выражения, определяет множество сентенциальных форм, являющееся объединением S1,S2,...,SN, то есть правило

А::= B?_ S1 _|_ S2 _|_ ¼ SN _? C **

определяет правила

A::= B S1 C **, А::= B S2 C **, ¼ A::= B SN C **.

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

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

1. Запрещена левая рекурсия, то есть использование правил вида:

A::= <_ A _>... **

или

A::= <_ A1 _>... **,

A1::= <_ A2 _>... **,

...,

AN::= <_ A _>... **.

Леворекурсивные правила необходимо устранять, преобразуя их в праворекурсивные с помощью введения дополнительных нетерминалов или используя итерацию.

Так леворекурсивное правило вида

А::=?_ B _|_ <_ A _> B _|_ <_ A _> C _? **

можно преобразовать к

A::= B [_ <_ A1 _> _] **

A1::=?_ B _|_ C _? [_ <_ A1 _> _] **

или

A::= B {_?_ B _|_ C _? _} **

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

A::=?_ BCD _|_ BC _|_ B _?

верно, тогда как

A::=?_ B _|_ BC _|_ BCD _?

может приводить к ошибкам. В последнем случае анализатор, исследуя цепочку BC или BCD и прочтя в анализируемой строке B, ответит TRUE, не дойдя до C (CD). Алгоритм с ограниченными возвратами, дойдя до первого варианта альтернативы, дающего ответ TRUE, остальные варианты исключает из рассмотрения.

Заметим, что без учета семантики рассматриваемое правило целесообразно представить без вариантов:

A::= B [_ C [_ D _] _] **.

3. В правилах вида A::= ¼ [_ S1 _] S2 ¼ ** пересечение множеств терминальных цепочек, выводимых из S1 и S2 должно быть пусто. В частности, запись

A::= [_ B _] B **

приводит к ошибкам, ее необходимо заменить продукцией

A::= B [_ B _] **.

В более сложных случаях необходимы и более сложные модификации правил. Так запись вида

A::= [_ B, _] B,?_ B _|_ C _?; **

необходимо преобразовать к виду

A::= B,?_ B [_,?_ B _|_ C _? _] _|_ C _?; **

или

A::=?_ B, B,?_ B _|_ C _? _|_ B,?_ B _|_ C _? _?; **.

При анализе грамматики осуществляется выявление возможных ошибок: наличия в грамматике внутренних или внешних тупиков, многократного определения нетерминалов, ошибок в следовании метасимволов, неверных имен синтермов и номеров семантических процедур и т.п.

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

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

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

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

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

Таким образом, из корректного исходного текста грамматики (файла *.GRM), который можно подготовить с помощью любого текстового редактора, на фазе Ф1 формируется файл грамматики во внутренней форме (*.GRR) и файл разделителей и терминалов (*.GRT).

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

Ниже мы коротко остановимся на каждом из этих проходов.

Поиск по сайту: