Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн
Подождите немного. Документ загружается.
221
Примеры:
Expression Integral Part
F21 IntegralPart
Оба написания Integral Part (с пробелом) и IntegralPart (без пробела)
воспринимаются как один и тот же идентификатор.
Терминалы определяются своим появлением в словаре терминальных
символов или в правых частях правил грамматики. В спецификации
трансляции они скорее играют роль лексических классов
138
, чем символов,
непосредственно составляющих предложение языка.
Синтаксис
TERMINAL : " ' " , DENOTATION , " ' " ; ' " ' , DENOTATION , ' " '.
DENOTATION : 'Любая цепочка литер'.
Другими словами, терминал — это произвольная последовательность литер,
заключенная между двумя одинаковыми ограничителями, в качестве которых
можно использовать апострофы (') или двойные кавычки ("). Терминал должен
заканчиваться на той же строчке, на которой начинается. Два разных вида
ограничителей дают возможность использовать эти символы в составе
терминалов.
Примеры:
':='
"'"{Апостоф с двойных кавычках}
'd'
'begin'
'"'{Двойные кавычки между апостофами}
"2"
Синонимы используются в качестве грамматических терминов в
диагностических сообщениях об ошибках на входе процессора. Они могут
определяться для нетерминалов и вспомогательных понятий грамматики и
позволяют формулировать сообщения об ошибках с их привязкой к
синтаксической структуре входного языка в терминах, понятных
пользователям. Синонимы входят в описания соответствующих словарей, а в
правилах грамматики не используются. Следует иметь в виду, что пробелы,
встречающиеся в синонимах, игнорируются. Рекомендуется использовать
символ подчеркивания '_' в качестве видимого пробела.
Синтаксис
SYNONYM : TAG.
Пример:
AUXILIARY NOTIONS : IP ( целая _часть ) ,
FP ( дробная _часть ) .
Здесь целая_часть и дробная_часть — синонимы вспомогательных понятий (IP
и FP — акронимы).
138
Именно они используются транслитератором или сканером при формировании входной
лексемы для анализатора.
222
8.5. ОПИСАНИЕ МИКРОЛЕКСИКИ
Транслитерация. Описание микролексики специфицирует транслитера-
тор
— языковой процессор самого нижнего уровня, который каждую литеру
из входного потока относит к одному из микролексических классов.
Транслитератор преобразует входную литеру в микролексему, т. е. структуру
из двух целочисленных кодов, представляющих номер микролексического
класса и номер элемента этого класса; третье поле этой структуры — сама
входная литера. Описание микролексики как раз и определяет упомянутые
микролексические классы.
Описание микролексики необходимо при спецификации сканеров —
языковых процессоров, распознающих конкретные представления
терминальных символов грамматики (основных символов входного языка), или
простейших (регулярных) конструкций языка, таких, как литеральные
константы и идентификаторы.
Синтаксис
MICROLEXICS DECLARATION : 'MICROLEXICS',
LEXICAL CLASSES, LEXICAL CLASS DECLARATION
*
.
LEXICAL CLASSES : 'Lexical classes' , ':' , ITEM LIST, '.' .
LEXICAL CLASS DECLARATION : TAG , ':' , [ ( LITERAL ; SUBRANGE ) # ',' ] , '.' .
ITEM LIST : ITEM # ',' .
ITEM : TAG ; LITERAL ; SUBRANGE .
TAG : LETTER, (LETTER ; DIGIT)
*
.
SUBRANGE : LOWER BOUND, '..' , UPPER BOUND.
LOWER BOUND : LITERAL.
UPPER BOUND : LITERAL.
LITERAL : ' " ' , ( TOKEN ; " ' " ) , ' " ' ; " ' " , ( TOKEN ; ' " ' ) ," ' " ; ' # ', ASCII
CODE .
TOKEN : Любая представимая литера .
ASCII CODE : Целое из диапазона 0..255 .
Раздел описания микролексики начинается символом MICROLEXICS. После
этого символа следует список микролексических классов (LEXICAL
CLASSES), т.е. терминальных символов, использующихся в управляющей
грамматике
139
, предваряемый ключевой фразой Lexical classes и двоеточием.
Элементы списка разделяются запятыми. Список заканчивается точкой.
Порядок перечисления классов не существенен, поскольку их нумерация
определяется порядком появления соответствующих им терминальных
символов в описании синтаксиса в этой же спецификации трансляции.
139
С точки зрения управляющей грамматики (микро) лексический класс является
терминальным символом. Способ обработки всех входных (микро) лексем одного класса — один
и тот же.
223
Различаются литераные и именованные микролексические классы. В
списке микролексических классов они могут всречаться в любом порядке.
Литеральный класс представляется литерой, заключенной в апострофы,
и не нуждается в дальнейшем описании. Для описания литеры ' (апостроф)
используется форма "'" (апостроф между двумя двойными кавычками). Для
описания литеры " (двойные кавычки) используется форма '"' (двойные
кавычки между двумя апострофами). Допускается использовать сокращенное
описание нескольких литеральных классов, если ASCII-коды их элементов-
литер имеют последовательные значения. Такое описание состоит из
начального и конечного литералов, разделенных специальным знаком ".." (две
точки подряд). Например, следующее описание:
Lexical classes : 'A' , '0'..'9'.
определяет набор из 11 (одноэлементных) литеральных классов.
Именованные классы представляются в списке микролексических
классов их именами (идентификаторами без апострофов и кавычек). Имя
класса, заключенное в апострофы или двойные кавычки, используется в
правилах управляющей грамматики в качестве терминала
140
наряду с
литеральными микролексическими классами.
Каждое имя именованного микролексического класса должно определяться
соответствующим описанием (LEXICAL CLASS DECLARATION). Эти
описания следуют за списком микролексических классов.
Состав именованного класса определяется правилом. Указывается имя
класса (из списка классов), затем следует двоеточие и список элементов класса,
который записывается по тем же правилам, что и список литеральных классов
в предложении Lexical classes. Но для спецификации литер, не отображаемых
на экране, служит другая форма представления — это знак '#', после которого
следует десятичное число из диапазона 0 .. 255, обозначающее ASCII-код
литеры. Порядковый номер
141
элемента в списке элементов класса
транслитератором упаковывается во второе поле микролексемы (первое поле
— номер микролексического класса).
Существует специальный именованный класс с фиксированным именем
Escaped symbols, который определяет множество символов, игнорируемых
сканером (если это необходимо); в нем также зафиксирован специальный
символ '' (два апострофа подряд), обозначающий конец входного потока литер
(аналог Eof).
Описания именованных классов, включая Escaped symbols, должны
следовать за списком микролексических классов. Микролексические классы не
должны пересекаться. Все перечисленные в предложении Lexical classes
именованные классы и только они должны быть определены (в любом
порядке). Никакой класс, кроме специального класса Escaped symbols, не
может быть пустым.
140
Это можно видеть в примере из разд.1.3.
141
Нумерация элементов класса начинается с единицы.
224
Пример:
MICROLEXICS
Lexical classes : 'A' , 'B' , 'C' , 'a' .. 'c' , blank , '[' , ' " ' , " ' " , digit,
Escaped symbols , Eof.
blank : #32.
digit : '0' .. '9'.
Eof : '' {Два подряд идущий апострофа}.
Escaped symbols : #10 , #13 , '*' .
В приведенном примере описана микролексика, состоящая из 13 классов, из
которых четыре (blank, digit, Eof и Escaped symbols) — именованные, а
остальные ('A', 'B', 'C', 'a', 'b', 'c' , '[', ' " ' и "'") — литеральные. Класс blank
имеет один элемент (пробел), класс ‘digit’ имеет 10 элементов, класс Eof имеет
один элемент, а класс Escaped symbols — три элемента, причем первые два есть
коды перевода строки и возврата каретки. Поскольку элементы классов
нумеруются от 1, то, например, '2' в классе ‘digit’ имеет номер 3.
8.6. ОПИСАНИЕ ЛЕКСИКИ
Раздел описания лексики используется в том случае, если для реализации
специфицируемой трансляции в качестве сканера используется процессор, а не
транслитератор. Тогда после заголовка раздела описания лексики следует
указать имя спецификации трансляции, реализуемой этим сканером.
Синтаксис
LEXICS DECLARATION : 'LEXICS' , ':', SPECIFICATION NAME.
SPECIFICATION NAME : TAG.
Пример:
LEXICS : GenLex
Такое описание лексики использовано в спецификации генераторов Алгола 68
(см. разд. 6.4). Под именем GenLex числится спецификация сканера для
анализатора генераторов.
8.7. ОПИСАНИЕ СИНТАКСИСА
Раздел описания синтаксиса является источником информации для
построения управляющей таблицы конечного или сплайнового процессора,
реализующего специфицируемую трансляцию.
Синтаксис
SYNTAX DECLARATION : [ 'SYNTAX'; 'PRODUCTIVE SYNTAX'],
NONTERMINALS LIST,
[ AUXILIARY NOTIONS LIST ],
[ TERMINALS LIST ],
[ FORWARD PASS SEMANTICS LIST ],
[ BACKWARD PASS SEMANTICS LIST ],
[ FORWARD PASS RESOLVERS LIST ],
[ BACKWARD PASS RESOLVERS LIST ],
RULES .
225
Описание синтаксиса входного языка специфицируемой трансляции
представляется в виде RBNF-грамматики, которая состоит из алфавитов и
правил. Этот раздел должен начинаться с ключевого слова SYNTAX — в случае
анализирующей грамматики, или PRODUCTIVE SYNTAX — в случае, когда
грамматика порождающая. Далее следуют алфавиты грамматики:
алфавит нетерминалов,
алфавит вспомогательных понятий,
алфавит терминалов,
алфавит семантик прямого просмотра,
алфавит резольверов прямого просмотра,
алфавит семантик обратного просмотра,
алфавит резольверов обратного просмотра.
Обязательным является только алфавит нетерминалов, и он должен быть
первым. Другие алфавиты, если они существуют, могут следовать в
произвольном порядке. Алфавиты грамматики попарно не пересекаются. Это
значит, что любой символ (акроним) может находиться не более, чем в одном
из указанных списков. За алфавитами следуют правила грамматики.
Алфавит нетерминалов. Задание алфавита нeтepминaлoв oбязaтeльно, так
как в любoй гpaммaтикe имeeтcя xoтя бы oдин нeтepминaл. Первый элемент в
списке нетерминалов считается начальным нетерминалом грамматики. Этот
алфавит служит для идентификации нетерминалов, используемых в правилах
грамматики.
Синтаксис
NONTERMINALS LIST : 'Nonterminals' , ':' , NOTION # ',' , '.'.
NOTION : ACRONYM , [ SYNONYM ] .
ACRONYM : TAG .
SYNONYM : '(' , TERM , ')' .
TERM : 'Любая цепочка литер, не содержащая пробелов'.
Описание алфавита нетерминалов начинается с ключевого слова
Nonterminals, за которым следует двоеточие и элементы списка нетерминалов,
разделенные запятыми. Список элементов завершается точкой.
Каждый элемент списка нетерминалов — понятие — состоит из акронима и
необязательного синонима.
Акронимы — сокращенные обозначения нетерминалов — используются в
правилах грамматики, тогда как синонимы — развернутые понятия
грамматики
— включаются в глоссарий диагностических сообщений.
Поскольку при внесении синонимов в глоссарий диагностик пробелы
отбрасываются, рекомендуется вместо пробелов использовать символ
подчеркивания '_'. Если синоним не указывается, то в глоссарий в качестве
синонима заносится акроним.
Пример:
Nonterminals : P (ПРОГРАММА) , UI (Целое_без_знака) , DIGIT.
Здесь обозначения P, UI и DIGIT — акронимы, а ПРОГРАММА и
Целое_без_знака — синонимы. Нетерминал DIGIT синонима не имеет.
226
Алфавит вспомогательных понятий служит для идентификации
вспомогательных понятий, используемых в правилах грамматики. Описание
алфавита вспомогательных понятий вполне аналогично описанию алфавита
нетерминалов. Но существенная особенность трактовки вспомогательных
понятий состоит в том, что их вхождения в правые части правил заменяются на
определяющие их регулярные выражения во время преобразования грамматики
в эквивалентную граф-схему, которая в технологическом комплексе SYNTAX
является формой внутреннего представления грамматики. И хотя при такой
подстановке вспомогательные понятия исключаются из правил грамматики, в
граф-схеме сохраняется информация о первоначальной синтаксической
структуре предложений входного языка.
Типичный прием балансировки грамматик состоит в переносе символов из
алфавита нетерминалов в алфавит вспомогательных понятий. Как отмечалось,
это равнозначно подстановке определений вместо используемых вхождений
вспомогательных понятий
142
.
Синтаксис
AUXILIARY NOTIONS LIST : 'Auxiliary notions' , ':' , NOTION # ',' , '.'.
Другими словами, описание алфавита вспомогательных понятий начинается с
ключевой фразы Auxiliary notions, за которой следует двоеточие и список
понятий. Понятия разделяются запятыми. В конце ставится точка.
Каждое понятие состоит из акронима и необязательного синонима. В
правилах грамматики используются акронимы, тогда как синонимы служат в
качестве диагностических терминов. Отсутствующий синоним считается
равным акрониму.
Пример:
Auxiliary notions : I ( ЦЕЛОЕ) , E ( ПОРЯДОК) ,
ЧИСЛО БЕЗ ЗНАКА .
Здесь I, E, ЧИСЛО БЕЗ ЗНАКА — акронимы, ЦЕЛОЕ и ПОРЯДОК —
синонимы.
Алфавит терминалов. Список терминалов используется для задания
определенного порядка их нумерации. Если терминалы расположить в порядке
убывания частоты их встречаемости в языке, который специфицируется, то это
может ускорить трансляцию этого языка.
Задавать список терминалов необязательно. В том случае, когда он
отсутствует, нумерация, о которой шла речь, определяется текстуальным
порядком вхождения терминалов в правые части правил грамматики. Если в
данной спецификации имеется раздел описания микролексики, то
соответствующий транслитератор автоматически настраивается на нумерацию
терминалов, необходимую для анализатора, по нумерации, определяемой (явно
или неявно) в разделе описания синтаксиса.
142
Разумеется, циклические подстановки невозможны — вспомогательные понятия не
могут определяться рекурсивно.
227
Синтаксис
TERMINALS LIST : 'Terminals' , ':' , TERMINAL # ',' , '.' .
TERMINAL : " ' " , DENOTATION, " ' " ; ' " ' , DENOTATION, ' " ' .
DENOTATION : 'Любая цепочка литер' .
Описание алфавита терминалов начинается с ключевого слова Terminals, за
которым следует двоеточие и элементы списка терминалов, разделенные
запятыми. Список элементов завершается точкой. Элемент списка —
произвольная цепочка литер, заключенная в апострофы или двойные кавычки.
Пример:
Terminals : 'begin' , ':=' , "'".
Последний элемент в этом списке — апостроф в двойных кавычках.
Алфавиты семантических символов. Семантические символы
ассоциируются с некоторыми преобразованиями операционной среды,
выполняемыми на прямом или обратном просмотре челночного процессора.
Соответственно, если семантики используются, необходимо определять
алфавиты семантических символов прямого и (или) обратного просмотров.
Синтаксис
FORWARD PASS SEMANTICS LIST: 'Forward pass semantics' , ':' , TAG # ',' ,
'.' .
BACKWARD PASS SEMANTICS LIST: 'Backward pass semantics', ':', TAG # ',' ,
'.' .
Описания алфавитов семантик прямого и обратного просмотров
различаются только ключевыми фразами, с которых они начинаются: Forward
pass semantics или Backward pass semantics соответственно. Далее следует
двоеточие, элементы алфавита, разделенные запятой, и точка.
Элементы-идентификаторы используются в правых частях правил
грамматики в качестве семантик. В разделе описания операционной среды
каждый семантический символ должен быть описан как процедура без
параметров.
Примеры:
Forward pass semantics : FPInit , FPStep , FPDone .
Backward pass semantics : BPInit , BPStep , BPDone .
По этим словарям символы FPInit, FPStep, FPDone, используемые в правилах
грамматики, идентифицируются как семантики прямого просмотра, тогда как
символы BPInit, BPStep, BPDone — как семантики обратного.
Алфавиты резольверных символов. Резольверные символы ассоциируют-
ся с некоторыми предикатами, тестирующими текущее состояние операцион-
ной среды на прямом или обратном просмотре челночного процессора.
Соответственно, если резольверы используются, необходимо определять алфа-
виты резольверных символов прямого и (или) обратного просмотров.
Синтаксис
FORWARD PASS RESOLVERS LIST: 'Forward pass resolvers', ':', TAG # ',' , '.' .
BACKWARD PASS RESOLVERS LIST: 'Backward pass resolvers', ':', TAG # ',' , '.' .
228
Описания алфавитов резольверов прямого и обратного просмотров различают-
ся только ключевыми фразами, с которых они начинаются: Forward pass
resolvers или Backward pass resolvers соответственно. Далее следует двоето-
чие, элементы алфавита, разделенные запятой, и точка.
Элементы-идентификаторы используются в правых частях правил
грамматики в качестве резольверов. В разделе описания операционной среды
каждый резольверный символ должен быть описан как булевская функция без
параметров.
Примеры:
Forward pass resolvers : Small , Large , Ok .
Backward pass resolvers : Short , Long .
Символы Small , Large и Ok, используемые в правилах управляющей
грамматики, идентифицируются как резольверы прямого просмотра, а Short ,
Long — как резольверы обратного.
Правила управляющей грамматики описывают синтаксическую
структуру входного языка и способ его обработки. Если контекстные символы
не используются, грамматика описывает бесконтекстный синтаксис входного
языка. Если используются семантические символы, грамматика задает управ-
ляющую структуру, включающую обрабатывающие процедуры. Если
резольверы используются, грамматика описывает также и контекстные
условия. По крайней мере одно правило — правило для начального
нетерминала — обязательно.
Синтаксис
RULES : RULE
+
.
RULE : LEFT PART, ':' , RIGHT PART , '.'.
LEFT PART : NONTERMINAL ; AUXILIARY NOTION.
RIGHT PART : REGULAR EXPRESSION.
REGULAR EXPRESSION : OPERAND # DYADIC OPERATION .
OPERAND : ( NONTERMINAL;
AUXILIARY NOTION;
TERMINAL;
SEMANTICS;
RESOLVER;
EMPTY ;
' (' , REGULAR EXPRESSION , ')' ;
' [' , REGULAR EXPRESSION , ']') ,
MONADIC OPERATION* .
NONTERMINAL : ACRONYM { нетерминала}.
AUXILIARY NOTION : ACRONYM { впомогательного понятия}.
SEMANTICS : TAG {Семантика прямого или обратного просмотра}.
RESOLVER : TAG { Резольвер прямого или обратного просмотра }.
EMPTY : '&' .
DYADIC OPERATION : ';' {Объединение} ;
',' {Конкатенация} ;
'#' {Итерация с разделителем}.
MONADIC OPERATION : '
*
' {Итерация} ;
'
+
'
{Усеченная итерация} .
229
Правило состоит из левой и правой частей, разделенных двоеточием. В
левой части может находиться нетерминал или вспомогательное понятие, а в
правой — некоторое регулярное выражение над символами алфавитов,
определенных в данной грамматике
143
. Нетерминалы и вспомогательные
понятия, определяемые или используемые правилами, представляются своими
акронимами.
Регулярные операции в двух последних правилах перечислены по
возрастанию старшинства, причем одноместные операции итерации и
усеченной итерации имеют одинаковое и наибольшее старшинство.
8.8. ОПИСАНИЕ
ОПЕРАЦИОННОЙ СРЕДЫ
Описание семантики входного языка в спецификации трансляции
представляется разделом описания операционной среды. Этот раздел содержит
описание констант, типов, переменных, процедур и функций на языке Borland
Pascal 7.0. Реализация этих описаний составляет операционную среду, в
которой интерпретируются контекстные символы.
В операционную среду могут входить также обработчики сообщений
(интерпретаторы команд). Они определяются в разделе сообщений и служат
средством прямого обмена информацией между процессорами, входящими в
одно и то же SYNTAX-приложение (об использовании сообщений см.
разд. 7.7).
Все эти описания включаются в библиотечный модуль, который
компилируется штатным компилятором bpc. Сгенерированная DLL-
библиотека динамически присоединяется к стандартному управляющему
процессору, образуя сплайновый процессор, реализующий специфицируемую
трансляцию.
Синтаксис
ENVIRONMENT DECLARATION :
'ENVIRONMENT', ENVIRONMENT ELEMENTS,
'IMPLEMENTATION', CONTEXT SYMBOL INTERPRETATION,
['MESSAGES', COMMAND INTERPRETATION].
ENVIRONMENT
ELEMENTS : {Описания констант, типов, переменных, процедур и
функций, используемых в реализации семантик (действий, ассоциируемых с
терминалами в порождающих грамматиках) и резольверов, на базовом языке
программирования}.
CONTEXT
SYMBOL INTERPRETATION : {Описание процедур, реализующих
семантики (и действия, ассоциируемые с терминалами в порождающих грамматиках),
а также функций, реализующих резольверы, на базовом языке программирования} .
COMMAND INTERPRETATION : COMMAND INTERPRETER
+
.
COMMAND INTERPRETER : 'Message', ':', COMMAND IDENTIFIER, BODY.
COMMAND IDENTIFIER : TAG.
BODY : {Некоторая реализация обработчика команды
на базовом языке программирования }.
143
Точнее, используются терминалы, акронимы нетерминалов и вспомогательных понятий
и контекстные символы.
230
Описание семантики, если оно имеется, состоит из раздела описания
элементов операционной среды, раздела описания интерпретации контекстных
символов и необязательного раздела сообщений.
Раздел описания элементов операционной среды начинается с ключевого
слова ENVIRONMENT, за которым следует блок описаний констант, типов,
переменных, функций и процедур в полном соответствии с синтаксисом блока
языка Borland Pascal 7.0.
Раздел описания интерпретации контекстных символов начинается с
ключевого слова IMPLEMENTATION, за которым следуют описания булевых
функций без параметров, интерпретирующих резольверные символы, и
описания процедур (также без параметров) интерпретации семантических
символов. Каждый контекстный символ должен иметь соответствующую
интерпретацию. В телах этих функций и процедур можно использовать
элементы операционной среды, описанные в разделе ENVIRONMENT, а
также процедуры и функции, встроенные в подсистему процессирования.
Раздел сообщений имеется в описании операционной среды каждого
процессора, который получает сообщения от других процессоров, входящих в
состав одного и того же SYNTAX-приложения. Он начинается с ключевого
слова MESSAGES, за которым следует последовательность описаний
обработчиков сообщений.
Описание обработчика сообщения начинается ключевым словом Message, за
которым следует двоеточие, затем идентификатор сообщения, и, наконец, тело
обработчика, завершающееся точкой с запятой. Тело обработчика — то же
самое, что и тело процедуры в языке Borland Pascal 7.0. Пример использования
сообщений приведен в спецификации XGenLex (см. разд. 7.8)
Многочисленные примеры описания операционной среды на Паскале,
используемом в качестве базового языка программирования в технологическом
комплексе SYNTAX, можно найти в предыдущих главах книги.