OpenToken - Руководство пользователя

Содержание

• Введение
• Лексический анализ
• Введение в лексический анализ
• Шаг 1: Описание перечислимого типа для лексем
• Шаг 2: Конкретизация класса анализатора лексем
• Шаг 3: Создание распознавателя лексем для каждой лексемы
• Шаг 3.5: Создание собственного типа распознавателя лексем
• Шаг 4: Отображение распознавателей на соответствующие лексемы
• Шаг 5: Создание объекта анализатора лексем
• Использование собственного приемника входного потока (Text_Feeder)
• Использование анализатора
• Синтаксический анализ (parsing)
• Таблично-управляемый синтаксический анализ
• Шаг 1: Создание перечислимого типа для ID лексем
• Шаг 2: Конкретизация пакетов лексем
• Шаг 3: Создание лексем
• Шаг 4: Отображение ID лексем терминалов на соответствующие распознаватели и лексемы
• Шаг 5: Описание лексического анализатора
• Описание собственного приемника входного потока (Text_Feeder)
• Шаг 6: Создание грамматики
• Шаг 7: Генерация синтаксического анализатора
• Использование синтаксического анализатора
• Синтезированные атрибуты
• Собственные нетерминалы
• Описание синтаксического анализатора
• Нисходящий рекурсивный синтаксический анализ (beta)

Введение

OpenToken - это система анализа лексем (token), которая одновременно является мощной, расширяемой и простой в использовании. В отличие от традиционных средств генерации лексических/синтаксических анализаторов, при использовании OpenToken необходимо выполнить минимальный объем работы для того, чтобы получить работоспособный лексический и/или синтаксический анализатора. В большинстве случаев, задача сводится к корректному выбору необходимых компонентов и объединению их в единое целое. Лексема (token) - это последовательность символов, которая обладает общим (коллективным) смыслом. Несложно заметить, что название системы акцентирует внимание на этом, характерном для лексем, свойстве. Базовые возможности системы предусматривают средства для лексического анализа (lexical analysis), который разделяет непрерывный поток текста на отдельные лексемы, и синтаксического анализа (parsing), который группирует лексемы в грамматические фразы.

Лексический анализ

Введение в лексический анализ

В OpenToken, пакеты генерации лексического анализатора состоят из двух частей:

1. Реализация непосредственного механизма лексического анализа (OpenToken.Token.Analyzer)
2. Набор пакетов распознавателей лексем (OpenToken.Recognizer.Line_Comment, и т.д.)

В целом, создание лексического анализатора, с помощью системы OpenToken, осуществляется в 5 шагов:

1. Описать перечислимый тип для лексем.
2. Настроить класс анализатора лексем на описанный перечислимый тип для лексем.
3. Создать распознаватель лексемы для каждой лексемы.
4. Создать синтаксис, путем отображения распознавателей лексем на соответствующие лексемы.
5. Создать объект анализатора лексем, который инициализирован требуемым синтаксисом.

Последующие разделы этого документа детально ознакомят Вас с каждым из этих шагов, используя один из примеров главы 3 книги "Compilers, Principles, Techniques, & Tools" (aka: "dragon book"). Данная книга является классической работой посвященной теории построения компиляторов.

Следует заметить, что в качестве первого обсуждаемого примера, подразумевается грамматика из примера 3.6 книги "Compilers, Principles, Techniques, & Tools". Также следует заметить, что для упрощения этот пример несколько изменен. Например, терминал num расщеплен на два терминала:

integer -> (+ | -)? digit+ real -> (+ | -)? (digit | _)* digit . (digit | _)* ( (e | E) (- | +)? (digit)+ )?

Такое изменение было сделано поскольку терминал num совпадает с описанием используемым для лексем Integer и Real, которые предусмотрены в поставке OpenToken.

Шаг 1: Описание перечислимого типа для лексем

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

type Example_Token_ID is (If_ID, Then_ID, Else_ID, ID_ID, Num, Relop, Whitespace);

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

Шаг 2: Конкретизация класса анализатора лексем

Этот шаг - тривиален. Необходимо просто конкретизировать настраиваемый пакет OpenToken.Token.Enumerated, используя в качестве параметра настройки только что описанный перечислимый тип. После чего, использовать полученный в результате конкретизации пакет для конкретизации пакета OpenToken.Token.Enumerated.Analyzer:

package Example_Token is new Opentoken.Token.Enumerated (Example_Token_ID); package Tokenizer is new Example_Token.Analyzer;

Шаг 3: Создание распознавателя лексем для каждой лексемы

Каждая перечисленная лексема нуждается в наличии объекта-распознавателя. Объекты-распознаватели могут быть созданы одним из двух способов. Наиболее простым способом является использование какого-либо распознавателя из иерархии пакетов OpenToken.Recognizer.*:

If_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Opentoken.Recognizer.Keyword.Get ("if")); Then_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Opentoken.Recognizer.Keyword.Get ("then")); Else_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Opentoken.Recognizer.Keyword.Get ("else")); ID_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Opentoken.Recognizer.Identifier.Get); Num_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Opentoken.Recognizer.Real.Get); Whitesp_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Opentoken.Recognizer.Character_Set.Get (Opentoken.Recognizer.Character_Set.Standard_Whitespace) );

Показанный выше исходный код создает распознаватели лексем для:

• Ключевых слов "if", "then" и "else". Для ключевых слов, регистр символов не имеет значения. Таким образом, будут нормально распознаваться также: "IF" или "If".
• Любой идентификатор. Будет распознаваться любая последовательность символов, которая начинается с буквы и состоит только из букв, цифр и символов подчеркивания.
• Любой вещественный литерал (с фиксированной или плавающей точкой).
• Любая последовательность "пробельных" символов. Использованный Standard_Whitespace подразумевает символы пробела, табуляции и терминаторы строк.

Шаг 3.5: Создание собственного типа распознавателя лексем

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

Распознаватель является тэговым типом, который является производным от типа OpenToken.Recognizer.Instance. Необходимо расширить этот тип, предусмотрев возможность сохранения информации о состоянии и необходимость отслеживания любых допустимых для этого типа распознавателя установок. Сюда также могут быть помещены другие подпрограммы, а также информация об этом специфическом типе лексемы. В нашем примере лексема Relop не может быть распознана каким-либо распознавателем предусмотренным системой OpenToken. Таким образом, необходимо описать этот распознаватель как показано ниже (часть, которая может быть "cut-and-paste", представлена черным цветом; часть, которая является специфичной для этого распознавателя, представлена синим цветом).

with OpenToken.Recognizer; package Relop_Example_Token is type Instance is new Opentoken.Recognizer.Instance with private; --------------------------------------------------------------------------- -- Эта функция будет вызвана для создания распознавателя лексемы. -- Следует заметить, что это простой распознаватель, поэтому -- у функции Get отсутствуют какие-либо параметры. --------------------------------------------------------------------------- function Get return Instance; private type State_ID is (First_Char, Equal_or_Greater, Equal, Done); type Instance is new Opentoken.Recognizer.Instance with record State : State_ID := First_Char; end record; --------------------------------------------------------------------------- -- Эта процедура будет вызвана в самом начале анализа новой строки-кандидата. -- Лексема "The_Token" нуждается в очистке ее состояния (если оно существует). --------------------------------------------------------------------------- procedure Clear (The_Token : in out Instance); --------------------------------------------------------------------------- -- Эта процедура будет вызвана для осуществления последующего анализа -- лексемы на основе последующего символа Next_Char. --------------------------------------------------------------------------- procedure Analyze (The_Token : in out Instance; Next_Char : in Character; Verdict : out Opentoken.Recognizer.Analysis_Verdict); end Relop_Example_Token;

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

Чтобы помочь избежать несуразиц при именовании состояний следует придерживаться следующего стандарта рекомендуемого автором системы OpenToken:

• Первое и последнее состояния должны быть соответственно именованы как First_Char и Done.
• Промежуточные состояния именуются в соответствии с ожиданием распознавания текущей части лексемы, но не в соответствии с элементами лексемы, которые уже распознаны.

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

Результатом совпадения будет служить одно из значений перечислимого типа OpenToken.Recognizer.Analysis_Verdict. Значение Matches индицирует, что принятая с момента последнего вызова процедуры Clear строка полностью квалифицирована как лексема. Значение So_Far_So_Good индицирует, что строка, в ее текущем состоянии, не соответствует лексеме, но последующее совпадение с лексемой возможно и зависит от последующих принимаемых символов. Следует заметить, что при получении в качестве результата сравнения значения Matches, после вызова процедуры Analize, вполне возможно получить результат So_Far_So_Good, при последующем вызове этой процедуры. Это зависит от описания (структуры) лексемы. Результат сравнения Failed несколько отличается. Он должен быть выдан для индикации того, что строка не является допустимой лексемой, и что строка никогда не будет соответствовать указанной лексеме, вне зависимости от числа принятых символов. В случае выдачи результата Failed, необходимо также осуществить установку распознавателя в состояние Done.

package body Relop_Example_Token is --------------------------------------------------------------------------- -- Эта процедура будет вызвана в самом начале анализа новой строки-кандидата. -- Лексема "The_Token" нуждается в очистке ее состояния (если оно существует). --------------------------------------------------------------------------- procedure Clear (The_Token : in out Instance) is begin The_Token.State := First_Char; end Clear; --------------------------------------------------------------------------- -- Эта функция будет вызвана для создания распознавателя лексемы Relop. --------------------------------------------------------------------------- function Get return Instance is begin return (Report => True, State => First_Char); end Get; -------------------------------------------------------------------------- -- Эта процедура будет вызвана для осуществления последующего анализа -- лексемы на основе последующего символа Next_Char. --------------------------------------------------------------------------- procedure Analyze (The_Token : in out Instance; Next_Char : in Character; Verdict : out Opentoken.Recognizer.Analysis_Verdict) is begin case The_Token.State is when First_Char => -- если первый символ '<', '=', или '>', то совпадение case Next_Char is when '<' => Verdict := Opentoken.Recognizer.Matches; The_Token.State := Equal_Or_Greater; when '>' => Verdict := Opentoken.Recognizer.Matches; The_Token.State := Equal; when '=' => Verdict := Opentoken.Recognizer.Matches; The_Token.State := Done; when others => Verdict := Opentoken.Recognizer.Failed; The_Token.State := Done; end case; when Equal_Or_Greater => -- если следующий символ '>' или '=', то совпадение case Next_Char is when '>' | '=' => Verdict := Opentoken.Recognizer.Matches; The_Token.State := Done; when others => Verdict := Opentoken.Recognizer.Failed; The_Token.State := Done; end case; when Equal => -- если следующий символ '=', то совпадение if Next_Char = '=' then Verdict := Opentoken.Recognizer.Matches; The_Token.State := Done; else Verdict := Opentoken.Recognizer.Failed; The_Token.State := Done; end if; when Done => Verdict := Opentoken.Recognizer.Failed; end case; end Analyze; end Relop_Example_Token;

Теперь осталось создать экземпляр объекта распознавателя нового типа. Это осуществляется так же как и в случае распознавателя тип которого предопределен в системе OpenToken:

Relop_Recognizer : constant Tokenizer.Recognizable_Token := Tokenizer.Get (Relop_Example_Token.Get);

Шаг 4: Отображение распознавателей на соответствующие лексемы

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

Syntax : constant Tokenizer.Syntax := (If_ID => If_Recognizer, Then_ID => Then_Recognizer, Else_ID => Else_Recognizer, ID_ID => ID_Recognizer, Num => Num_Recognizer, Relop => Relop_Recognizer, Whitespace => Whitesp_Recognizer );

Для некоторого упрощения, можно легко скомбинировать шаги 3 и 4 в один шаг. Например, следующим образом:

Syntax : constant Tokenizer.Syntax := (If_ID => Tokenizer.Get (Opentoken.Recognizer.Keyword.Get ("if")), Then_ID => Tokenizer.Get (Opentoken.Recognizer.Keyword.Get ("then")), Else_ID => Tokenizer.Get (Opentoken.Recognizer.Keyword.Get ("else")), ID_ID => Tokenizer.Get (Opentoken.Recognizer.Identifier.Get), Int => Tokenizer.Get (Opentoken.Recognizer.Integer.Get), Real => Tokenizer.Get (Opentoken.Recognizer.Real.Get), Relop => Tokenizer.Get (Relop_Example_Token.Get), Whitespace => Tokenizer.Get (Opentoken.Recognizer.Character_Set.Get (Opentoken.Recognizer.Character_Set.Standard_Whitespace)) );

Шаг 5: Создание объекта анализатора лексем

Теперь можно создать, собственно, анализатор лексем. Для этого необходимо описать экземпляр объекта типа Tokenizer.Instance (также как и ранее подразумевая, что Tokenizer является именем анализатора, который был получен в результате конкретизации на шаге 2), и инициализировать его с помощью вызова Tokenizer.Initialize. При осуществлении вызова Tokenizer.Initialize, следует указать как параметр объект синтаксиса, который был получен на шаге 4.

Analyzer : Tokenizer.Instance := Tokenizer.Initialize (Syntax);

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

Использование собственного приемника входного потока (Text_Feeder)

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

File : aliased Ada.Text_IO.File_Type; Feeder : aliased OpenToken.Text_Feeder.Text_IO.Instance := OpenToken.Text_Feeder.Text_IO.Create (File'Unchecked_Access); Analyzer : Tokenizer.Instance := Tokenizer.Initialize (Language_Syntax => Syntax, Feeder => Feeder'Access);

Приемник входного текстового потока является тэговым типом OpenToken.Text_Feeder.Instance'Class. Он обладает примитивной (переопределяемой) подпрограммой с именем Get, которая осуществляет заполнение строки символами. Всякий раз, когда в процессе обработки входного потока анализатор нуждается в приеме последующих символов, он осуществляет вызов подпрограммы Get. Если приемник входного потока не указан, то, по умолчанию, будет использован приемник входного потока, который читает входной поток с текущего файла ввода.

При необходимости изменить файл из которого осуществляется ввод приемником входного потока по умолчанию, можно непосредственно модифицировать Tokenizer.Input_Feeder, или изменить текущий файл ввода Text_IO следующим образом:

Ada.Text_IO.Set_Input (File); Tokenizer.Input_Feeder := OpenToken.Text_Feeder.Text_IO.Create;

или, независимо от текущего файла ввода Text_IO:

Tokenizer.Input_Feeder := OpenToken.Text_Feeder.Text_IO.Create (File'Unchecked_Access);

При необходимости изменить приемник входного текстового потока непосредственно в процессе анализа, можно использовать подпрограмму Set_Text_Feeder:

Tokenizer.Set_Text_Feeder (Analyzer => Analyzer, Feeder => My_New_Text_Feeder);

В заключение, для случаев когда необходимо использовать приемник входного потока, который не основан на файлах Text_IO, существуют приемники входного потока представленные иерархией пакетов OpenToken.Text_Feeder.*. Если ни один из них не соответствует требованиям решаемой задачи, можно описать тип, производный от типа OpenToken.Text_Feeder.Instance, и переопределить для него подпрограмму Get.

Использование анализатора

Для использования полученного вышеописанным образом анализатора лексем необходимо для обнаружения каждой лексемы осуществлять вызов Tokenizer.Find_Next Tokenizer.ID будет возвращать код идентификации (ID) каждой обнаруженной лексемы. Tokenizer.Lexeme возвращает фактическую строку распознанной лексемы.

Полный исходный текст, который использован в данном обсуждении, а также пример входного файла, распологается в подкаталоге Examples/ASU_Example_3_6. Для сборки этого примера в среде компилятора GNAT, необходимо выполнить команду "make" в этом подкаталоге (для других компиляторов: необходимо обратиться к описанию процесса сборки программы в документации на используемый компилятор). После завершения выполнения команды "make", необходимо запустить полученную программу "asu_example_3_6". В результате должен быть выдан следующий список распознанных лексем:

Found IF_ID Found ID_ID Found RELOP Found ID_ID Found THEN_ID Found ELSE_ID Found RELOP Found REAL Found RELOP Found INT

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

Синтаксический анализ (parsing)

Система OpenToken обладает возможностями синтаксического анализа. Для OpenToken, традиционным методом синтаксического анализа является таблично-управляемый синтаксический анализ, который основан на дополнительном перечислении "нетерминальных" лексем, и иерархии пакетов OpenToken.Production.

Более новым методом синтаксического анализа системы является метод нисходящего рекурсивного разбора. Этот метод основан на использовании перечисленных лексем, а также не-перечисленных лексем из иерархии OpenToken.Token.

Таблично-управляемый синтаксический анализ

Пакеты системы OpenToken, которые обеспечивают возможности таблично-управляемого синтаксического анализа, составляют четыре основные части:

1. пакеты лексического анализатора
2. синтаксический анализатор
3. лексемы
4. список правил вывода (productions); иначе - грамматика

Для построения синтаксического анализатора в системе OpenToken необходимо выполнить пять основных шагов:

1. создать перечислимый тип в котором указаны все необходимые лексемы
2. специфицировать необходимые лексемы, используя перечисление идентификаторов (ID) лексем и объектов лексем
3. создать лексический анализатор
4. описать грамматику, для указания смысла совокупностей лексем
5. генерация синтаксического анализатора для требуемой грамматики

При рассмотрении примеров в этом случае, подразумевается грамматика из примера 4.46 книги "Compilers, Principles, Techniques, & Tools":

S' -> S S -> L = R | R L -> * R | id R -> L

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

Шаг 1: Создание перечислимого типа для ID лексем

Этот шаг осуществляется также как было описано ранее. Однако, в данном случае необходимо указать ID не только для тех лексем, которые будут непосредственно присутствовать во входном потоке (т.е. "терминалы"), но и указать ID для лексем, которые будут созданы синтаксическим анализатором (т.е. "нетерминалы"). При этом, ID для лексем-терминалов должны быть указаны перед ID для лексем-нетерминалов (причина такого соглашения будет понятна несколько позже).

type Token_IDs is (Asterix_ID, ID_ID, Equals_ID, EOF_ID, Whitespace_ID, S_ID, L_ID, R_ID, S_Prime_ID);

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

Шаг 2: Конкретизация пакетов лексем

Этот шаг во многом подобен шагу 2, который рассматривался при обсуждении построения лексического анализатора ранее, за исключением того, что теперь необходимо конкретизировать несколько большее число настраиваемых пакетов. Вначале необходимо конкретизировать настраиваемый пакет OpenToken.Token.Enumerated с помощью перечислимого типа лексем. Затем, необходимо использовать этот пакет для конкретизации настраиваемого пакета OpenToken.Token.Enumerated.Analyzer. Можете заметить, что пакет анализатора обладает параметром настройки, и может показаться странным, что этот параметр не был упомянут ранее. Этот параметр служит для того, чтобы указать анализатору последний перечисленный терминал. Анализатор не заботится о нетерминалах, поскольку они не могут быть непосредственно обнаружены во входном потоке.

package Master_Token is new OpenToken.Token.Enumerated (Token_IDs); package Tokenizer is new Master_Token.Analyzer (Whitespace_ID);

Далее, конкретизированные пакеты лексем необходимо использовать для создания пакета списка лексем, который используется для создания правил вывода (productions). Этот пакет также используется для конкретизации настраиваемого пакета OpenToken.Token.Nonterminal.

package Token_List is new Master_Token.List; package Nonterminal is new Master_Token.Nonterminal (Token_List);

Далее, необходимо обеспечить доступ к пакетам, которые позволяют создать грамматику (Grammar). Конкретизация пакета OpenToken.Production осуществляется с помощью корневого пакета лексем, корневого пакета нетерминалов и пакета списка лексем. После этого необходимо осуществить конкретизацию его дочернего пакета .List:

package Production is new OpenToken.Production (Master_Token, Token_List, Nonterminal); package Production_List is new Production.List;

Далее, осуществляется конкретизация корневого пакета в иерархии синтаксического анализатора с помощью пакета списка правил вывода и пакета анализатора. А затем создается пакет синтаксического анализатора:

package Parser is new Production.Parser (Production_List, Tokenizer); package LALR_Parser is new Parser.LALR;

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

-- это обеспечивает возможность использования инфиксных -- знаков операций для встроенных правил вывода use type Token_List.Instance; use type Production.Right_Hand_Side; use type Production.Instance; use type Production_List.Instance;

Шаг 3: Создание лексем

Далее необходимо описать переменные лексем для всех лексем, которые будут появляться в правилах вывода. Лексемы о которых не выдается сообщений, такие как лексема Whitespace данного примера, могут быть легко созданы на последующем шаге "на лету". Терминалы должны быть описаны как объекты, производные от Master_Token.Instance. Нетерминалы должны быть описаны как объекты, производные от Nonterminal.Instance.

Asterix : aliased Master_Token.Class := Master_Token.Get (Asterix_ID); ID : aliased Master_Token.Class := Master_Token.Get (ID_ID); Equals : aliased Master_Token.Class := Master_Token.Get (Equals_ID); EOF : aliased Master_Token.Class := Master_Token.Get (EOF_ID); S : aliased Nonterminal.Class := Nonterminal.Get (S_ID); L : aliased Nonterminal.Class := Nonterminal.Get (L_ID); R : aliased Nonterminal.Class := Nonterminal.Get (R_ID); S_Prime : aliased Nonterminal.Class := Nonterminal.Get (S_Prime_ID);

Шаг 4: Отображение ID лексем терминалов на соответствующие распознаватели и лексемы

Теперь объект типа Tokenizer.Syntax должен быть инициализирован. Этот объект будет отображать ID лексем терминалов на соответствующие распознаватели и объекты лексем. Подпрограмма Tokenizer.Get создает структуру (называемую Recognizable_Token), которая может быть присвоена внутри элемента синтаксического анализатора для создания отображения.

Дополнительно, соществует специальная версия подпрограммы Get, которая обладает параметром New_Token. Эта форма может быть использована для создания отображения без первоначального создания объекта лексемы. Это может быть полезным для лексемы о которых не выдается сообщений (таких как лексема Whitespace данного примера), которые не являются частью грамматики. В этом случае Master_Token.Instance будет распределяться динамически, и присваиваться внутри отображения.

Syntax : constant Tokenizer.Syntax := (Asterix_ID => Tokenizer.Get (Recognizer => OpenToken.Recognizer.Keyword.Get ("*"), New_Token => Asterix), ID_ID => Tokenizer.Get (Recognizer => OpenToken.Recognizer.Keyword.Get ("id"), New_Token => ID), Equals_ID => Tokenizer.Get (Recognizer => OpenToken.Recognizer.Keyword.Get ("="), New_Token => Equals), EOF_ID => Tokenizer.Get (Recognizer => OpenToken.Recognizer.End_Of_File.Get, New_Token => EOF), Whitespace_ID => Tokenizer.Get (OpenToken.Recognizer.Character_Set.Get (OpenToken.Recognizer.Character_Set.Standard_Whitespace)) );

Шаг 5: Описание лексического анализатора

Описание собственного приемника входного потока (Text_Feeder)

В этом случае можно использовать приемник входного потока, который связан со своим собственным файлом, а не Ada.Text_IO.Current_Input. Для осуществления этого, сначала надо описать экземпляр объекта (косвенно доступный, т.е. aliased), который будет служить как файл для Text_IO.Open и Text_IO.Close. Затем, описать OpenToken.Text_Feeder.Text_IO.Instance. После, инициализировать приемник входного потока с помощью подпрограммы Create, используя файловый объект как File_Ptr:

Input_File : aliased Ada.Text_IO.File_Type; Feeder : aliased OpenToken.Text_Feeder.Text_IO.Instance := OpenToken.Text_Feeder.Text_IO.Create (Input_File'Unchecked_Access);

Теперь, для создания, собственно, анализатора, необходимо создать экземпляр объекта типа Tokenizer.Instance, и инициализировать его требуемым синтаксисом и приемником входного потока. Это не сложно:

Analyzer : Tokenizer.Instance := Tokenizer.Initialize (Syntax, Feeder'Access);

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

Шаг 6: Создание грамматики

Грамматика - это нотация описывающая взаимосвязи, которые установлены между лексемами языка. Другим способом представления грамматики является описание языка в терминах его лексем.

В системе OpenToken грамматика создается с помощью типа OpenToken.Production.List.Instance, что является серией правил вывода (productions), которые связаны воедино с помощью знаков операции and.

Таким образом, необходимо уточнить: что такое правило вывода (production)? Правило вывода - это отношение со знаком операции <= между лексемой-нетерминалом в левой части отношения и списком лексем в правой части отношения (и, возможно, подпрограмм синтеза атрибутов). Список лексем, в правой части отношения, строится с помощью знака операции &, а подпрограммы синтеза атрибутов могут быть указаны с помощью знака операции +. Следует заметить, что в этом контексте знак операции <= обладает смыслом "является производным из" ("is derived from"), что подразумевает отсутствие каких-либо действий когда одна часть отношения меньше или равна другой части отношения.

Идея заключается в том, что нетерминал в левой части отношения первого правила вывода (production) символизирует язык в целом. Лексемы в правой части этого правила вывода представляют лексемы, которые могут составлять язык (иначе, лексемы в которые этот язык можно декомпозировать). В этом списке, для каждой лексемы, которая является нетерминалом (производная от Nonterminal.Instance), может присутствовать одно или более правил вывода для описания из каких лексем состоит данный нетерминал. Некоторые из этих лексем также могут быть нетерминалами. В таком случае может возникнуть необходимость в большом числе правил вывода, которые будут описывать какие лексемы производны и из чего. В итоге, все нетерминалы должны быть каким-либо образом производны (выведены) из серий нетерминалов. Также, является важным, что лексема в левой части первого правила вывода (отношения) не появляется в каком-либо другом правиле вывода. Кроме того, в зависимости от применения синтаксического анализатора, могут существовать дополнительные ограничения налагаемые на грамматику языка. Например, многие синтаксические анализаторы не могут обрабатывать двусмысленные грамматики.

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

Ниже показано описание грамматики для обсуждаемого примера языка. Для сравнения, пример также содержит текстуальное описание, которое представлено в книге "Compilers, Principles, Techniques, & Tools":

-------------------------------------------------------------------------- -- Описание грамматики Grammar. Текст примера в книге имеет следующий вид: -- -- S' -> S -- S -> L = R | R -- L -> * R | id -- R -> L -- Grammar : constant Production_List.Instance := S_Prime <= S & EOF and S <= L & Equals & R and S <= R and L <= Asterix & R + Nonterminal.Synthesize_Self and L <= ID + Nonterminal.Synthesize_Self and R <= L;

Шаг 7: Генерация синтаксического анализатора

После описания грамматики, можно использовать это описание для генерации синтаксического анализатора. Для данного примера будет использоваться синтаксический анализатор типа LALR(1), который может быть получен с помощью OpenToken.Production.Parser.LALR. Для этого необходимо описать объект этого типа и инициализировать его путем вызова функции Generate с указанием требуемой грамматики и анализатора лексем:

-- Экземпляр синтаксического анализатора LALR. Test_Parser : LALR_Parser.Instance := LALR_Parser.Generate (Grammar => Grammar, Analyzer => Analyzer );

Использование синтаксического анализатора

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

Test_File_Name : constant String := "Example.txt"; begin Ada.Text_IO.Put ("Parsing file " & Test_File_Name & "..."); Ada.Text_IO.Flush; Ada.Text_IO.Open (File => Input_File, Name => Test_File_Name, Mode => Ada.Text_IO.In_File ); LALR_Parser.Parse (Test_Parser);

Синтезированные атрибуты

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

Если обратить внимание на один из пакетов Token.Nonterminal, то можно заметить внутри него некоторые примитивные операции со словом "synthesize". Одна из этих подпрограмм будет диспетчеризована в случае распознавания лексемы. Ее задача состоит в том, чтобы инициализировать нетерминал, основываясь на ее входных параметрах, которые обычно являются списком лексем. Всякий раз при совпадении правой части правила вывода будет осуществляться обработка, которую называют "свертка" ("reduction"). Этот процесс вызывает удаление в правой части правила вывода всех лексем, которые совпали, и создание лексемы-нетерминала тип которой соответствует левой части правила вывода. Стандартная лексема-нетерминал Nonterminal является теговым типом с единственным полем - ID лексемы. Однако, для лексем можно создавать производные типы с дополнительными полями, называемых на компиляторном жаргоне атрибутами. Такие атрибуты могут хранить полезную информацию, такую как численные значения, указатели в таблицу символов, объектный код и т.д.

При возникновении свертки правила вывода, осуществляется вызов указанной подпрограммы синтеза с перечнем обнаруженных лексем в правой части отношения. Если при описании правила вывода подпрограмма синтеза не указана, осуществляется вызов подпрограммы OpenToken.Token.Nonterminal.Synthesize_Default. Подпрограмма Synthesize_Default осуществляет диспетчеризацию вызова подпрограммы Default_Synthesize для указанного типа. Если Default_Synthesize не переопределена, она, в свою очередь, осуществляет диспетчеризацию вызова подпрограммы Synthesize_By_Copying для указанного типа, передавая ей первую из указанных в правой части отношения лексему. Таким образом, по умолчанию, нетерминалы создаются как копии первых лексем, из списка указанных лексем в правой части правила вывода. Однако, такое поведение по умолчанию на одном из уровней может быть переопределено, или может быть явно указан другой метод обработки. Это важно понимать, поскольку при решении задачи может возникнуть необходимость явного переопределения некоторых синтезирующих действий на уровне грамматики. Попытка использовать подпрограмму Synthesize_By_Copying, которая задана по умолчанию, приведет к ошибке нарушения ограничения (constraint error), если исходная лексема не принадлежит к классу целевой лексемы.

Чтобы продемонстрировать как работают описанные выше механизмы, следует рассмотреть более сложный пример из книги "Compilers, Principles, Techniques, & Tools". Пример 5.10, из этой книги, демонстрирует работу простого настольного калькулятора. Такой калькулятор способен выполнять сложение, вычитание, умножение и деление, а также обрабатывать скобки (для ассоциации).

Собственные нетерминалы

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

generic with package Token is new OpenToken.Token (<>); with package Token_List is new Token.List; with package Nonterminal is new Token.Nonterminal (Token_List); with package Integer_Literal is new Token.Integer_Literal; package Simple_Integer_Token is type Instance is new Nonterminal.Instance with private; subtype Class is Instance'Class; type Handle is access all Class;

Каждый нетерминал нуждается в конструкторе для создания начальной лексемы для всей грамматики.

function Get (ID : in Token.Token_ID; Value : in Integer := 0) return Instance'Class;

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

function Value (Subject : in Instance) return Integer; procedure Synthesize_By_Copying (New_Token : out Instance; Source : in Token.Instance'Class; To_ID : in Token.Token_ID);

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

Add_Integers : constant Nonterminal.Synthesize; Multiply_Integers : constant Nonterminal.Synthesize; Synthesize_Second : constant Nonterminal.Synthesize;

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

private type Instance is new Nonterminal.Instance with record Value : Integer; end record;

Также необходимо описать фактические подпрограммы синтеза атрибутов на которые ссылаются константы. Поскольку они будут указаны посредством объектов ссылающихся на подпрограммы, профиль их параметров должен быть идентичен профилю параметров Nonterminal.Synthesize. Следует заметить, что поскольку эти подпрограммы оперируют объектами Nonterminal.Class, они (подпрограммы) не будут диспетчеризованными (эта проблема будет рассмотрена несколько позже).

procedure Synthesize_Add (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Token.Token_ID); procedure Synthesize_Multiply (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Token.Token_ID); procedure Synthesize_From_Second_Argument (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Token.Token_ID); Add_Integers : constant Nonterminal.Synthesize := Synthesize_Add'Access; Multiply_Integers : constant Nonterminal.Synthesize := Synthesize_Multiply'Access; Synthesize_Second : constant Nonterminal.Synthesize := Synthesize_From_Second_Argument'Access;

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

package body Simple_Integer_Token is function Get (ID : in Token.Token_ID; Value : in Integer := 0) return Instance'Class is begin return Instance'Class (Instance'(Nonterminal.Instance (Nonterminal.Get (ID)) with Value => Value)); end Get; function Value (Subject : in Instance) return Integer is begin return Subject.Value; end Value;

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

procedure Synthesize_By_Copying (New_Token : out Instance; Source : in Token.Instance'Class; To_ID : in Token.Token_ID) is begin if Source in Integer_Literal.Class then New_Token := (Nonterminal.Instance (Nonterminal.Get (To_ID)) with Value => Integer_Literal.Value (Integer_Literal.Class (Source))); elsif Source in Class then New_Token := (Nonterminal.Instance (Nonterminal.Get(To_ID)) with Value => Instance (Source).Value); else Ada.Exceptions.Raise_Exception (Nonterminal.Invalid_Synth_Argument'Identity, "Token " & Token.Token_ID'Image (To_ID) & " cannot be synthesized " & "solely from a " & Token.Token_ID'Image (Token.ID (Source)) & "."); end if; end Synthesize_By_Copying;

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

Подпрограммы требуют наличия описателей первой, второй и третьей лексем в исходном списке. Это достигается использованием итератора списка из пакета Token_List (OpenToken.Token.List). Первая лексема будет указана для подпрограммы Initial_Iterator. Последующие лексемы списка могут быть достигнуты с помощью использования процедуры Next_Token.

Если Source не принадлежит типу Instance, то присваивание приведет к исключению Constraint_Error. Это исключение будет перехвачено и вместо него будет возбуждено исключение Invalid_Synth_Argument с информативным сообщением для отладки.

procedure Synthesize_Add (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Token.Token_ID) is Left : Token_List.List_Iterator := Token_List.Initial_Iterator (Source); Right : Token_List.List_Iterator := Token_List.Initial_Iterator (Source); begin -- переслать "Right" через третий элемент; Token_List.Next_Token (Right); Token_List.Next_Token (Right); New_Token := Class (Instance'(Token.Instance (Token.Get (To_ID)) with (Value (Class (Token_List.Token_Handle (Left).all)) + Value (Class (Token_List.Token_Handle (Right).all)) ) ) ); exception when Constraint_Error => Ada.Exceptions.Raise_Exception (Nonterminal.Invalid_Synth_Argument'Identity, "Token " & Token.Token_ID'Image (To_ID) & " cannot be synthesized " & "from a " & Token.Token_ID'Image (Token.ID (Token_List.Token_Handle (Left).all) ) & " and a " & Token.Token_ID'Image (Token.ID (Token_List.Token_Handle (Right).all) ) & "." ); end Synthesize_Add; procedure Synthesize_Multiply (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Token.Token_ID) is Left : Token_List.List_Iterator := Token_List.Initial_Iterator (Source); Right : Token_List.List_Iterator := Token_List.Initial_Iterator (Source); begin -- переслать "Right" через третий элемент; Token_List.Next_Token (Right); Token_List.Next_Token (Right); New_Token := Class (Instance' (Token.Instance(Token.Get (To_ID)) with Value => (Value (Class(Token_List.Token_Handle (Left).all)) * Value (Class(Token_List.Token_Handle (Right).all)) ) ) ); exception when Constraint_Error => Ada.Exceptions.Raise_Exception (Nonterminal.Invalid_Synth_Argument'Identity, "Token " & Token.Token_ID'Image (To_ID) & " cannot be synthesized " & "from a " & Token.Token_ID'Image (Token.ID (Token_List.Token_Handle (Left).all) ) & " and a " & Token.Token_ID'Image (Token.ID (Token_List.Token_Handle (Right).all) ) & "." ); end Synthesize_Multiply; procedure Synthesize_From_Second_Argument (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Token.Token_ID) is Second : Token_List.List_Iterator := Token_List.Initial_Iterator (Source); begin -- переслать "Second" через второй элемент; Token_List.Next_Token (Second); New_Token := Class (Instance'(Nonterminal.Instance (Nonterminal.Get (To_ID)) with Value => Class (Token_List.Token_Handle (Second).all).Value)); exception when Constraint_Error => Ada.Exceptions.Raise_Exception (Nonterminal.Invalid_Synth_Argument'Identity, "Token " & Token.Token_ID'Image (To_ID) & " cannot be synthesized " & "solely from a " & Token.Token_ID'Image (Token.ID (Token_List.Token_Handle (Second).all) ) & "."); end Synthesize_From_Second_Argument; end Simple_Integer_Token;

Описание синтаксического анализатора

На данный момент собственная лексема-нетерминал (Nonterminal) определена. Следовательно, можно приступить к описанию синтаксического анализатора. Первые несколько шагов очень подобны шагам из предыдущего примера. Предполагается, что этот пример соответствует следующему описанию грамматики из книги "Compilers, Principles, Techniques, & Tools":

L -> E print (L.val) E -> E + T E.val := E1.val + T.val E -> T T -> T * F T.val := T1.val * F.val T -> F F -> ( E ) F.val := E.val F -> digit

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

Сначала необходимо описать идентификаторы лексем (Token_ID):

type Token_IDs is (Integer_ID, Left_Paren_ID, Right_Paren_ID, Plus_Sign_ID, Multiply_ID, EOF_ID, Whitespace_ID, L_ID, E_ID, T_ID, F_ID);

Конкретизация настраиваемых пакетов осуществляется также как и в предыдущем примере, но с двумя дополнениями. При конкретизации для численных литералов используется пакет лексемы Integer_Literal из поставки OpenToken, и самостоятельно созданный пакет лексемы-нетерминала Simple_Integer_Token, которая представляет численно-значимые нетерминалы.

package Integer_Literal is new Master_Token.Integer_Literal; package Simple_Integer is new Simple_Integer_Token (Master_Token, Token_List, Nonterminal, Integer_Literal);

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

Line : String (1..1024); Line_Length : Natural; Feeder : aliased OpenToken.Text_Feeder.String.Instance;

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

procedure Print_Value (New_Token : out Nonterminal.Class; Source : in Token_List.Instance'Class; To_ID : in Master_Token.Token_ID);

Теперь эта подпрограмма синтеза описана. Грамматика описывается подобно тому как это рассматривалось ранее. Также как и в примере книги "Compilers, Principles, Techniques, & Tools", правила вывода, которые не обладают подпрограммами синтеза будут синтезироаны путем копирования атрибутов первой лексемы справа. Очевидно, что если эта лексема не принадлежит к классу лексемы в левой части правила вывода, то совершенно справедливо будет возбуждаться исключение ошибки ограничения (constraint error). Однако, в рассматриваемый пример предусматривает случай копирования Integer_Literals в Simple_Integers, путем переопределения используемой по умолчанию подпрограммы Synthesize_By_Copying для Simple_Integers. В случаях, где такое поведение не желательно, таких как правило вывода для сложения, соответствующая подпрограмма синтеза указана явно.

Grammar : constant Production_List.Instance := L <= E & EOF + Print_Value'Access and E <= E & Plus & T + Simple_Integer.Add_Integers and E <= T and T <= T & Times & F + Simple_Integer.Multiply_Integers and T <= F and F <= Left_Paren & E & Right_Paren + Simple_Integer.Synthesize_Second and F <= Int_Literal;

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

loop Ada.Text_IO.Get_Line (Line, Line_Length); exit when Line_Length = 0; OpenToken.Text_Feeder.String.Set (Feeder => Feeder, Value => Line (1..Line_Length)); LALR_Parser.Parse (Test_Parser); end loop;

Когда, при выполнении этого кода, пользователь набирает на клавиатуре:

3 * (5 + 7 * 2)

Программа выдает ответ:

57

Нисходящий рекурсивный синтаксический анализ

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

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

Такое концептуальное упрощение обеспечивает некоторую свободу благодаря которой можно взять какой-либо синтаксический анализатор и:

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

Общая последовательность действий при создании нисходящего рекурсивного синтаксического анализатора следующая:

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

В этот раз, в качестве примера подразумевается грамматика из примера 4.46 книги "Compilers, Principles, Techniques, & Tools":

S' -> S S -> L = R | R L -> * R | id R -> L

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

Шаг 1: Создание перечислимого типа для ID лексем

Этот шаг такой же как и описанный при рассмотрении лексического анализа.

type Token_IDs is (Asterix_ID, ID_ID, Equals_ID, EOF_ID, Whitespace_ID);

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

Шаг 2: Конкретизация пакетов лексем

Этот шаг такой же как и описанный при рассмотрении лексического анализа. Необходимо конкретизировать настраиваемый пакет OpenToken.Token.Enumerated, указав в качестве параметра настройки только что созданный перечислимый тип (Token_IDs). Затем, необходимо использовать полученный пакет для конкретизации настраиваемого пакета OpenToken.Token.Enumerated.Analyzer:

package Master_Token is new Opentoken.Token.Enumerated (Token_IDs); package Tokenizer is new Master_Token.Analyzer;

Шаг 3: Отображение ID лексем терминалов на соответствующие распознаватели и лексемы

Необходимо инициализировать объект типа Tokenizer.Syntax Этот объект будет отображать все ID лексем-терминалов как на распознаватели, так и на объекты этих лексем. Подпрограмма Tokenizer.Get создает структуру (называемую Recognizable_Token), которая может быть присвоена внутри синтаксического элемента анализатора для создания отображения.

Дополнительно, существует специальная версия подпрограммы Get, которая не обладает параметром New_Token. Эта форма подпрограммы может быть использована для создания отображения без предварительного создания объекта лексемы. Это избавляет от некоторой дополнительной работы, но требует некоторого дополнительного пространства динамически распределяемой памяти. Master_Token.Instance будет распределяться динамически и присваиваться внутри отображения.

Syntax : constant Tokenizer.Syntax := (Asterix_ID => Tokenizer.Get (OpenToken.Recognizer.Keyword.Get ("*")), ID_ID => Tokenizer.Get (OpenToken.Recognizer.Keyword.Get ("id")), Equals_ID => Tokenizer.Get (OpenToken.Recognizer.Keyword.Get ("=")), EOF_ID => Tokenizer.Get (OpenToken.Recognizer.End_Of_File.Get), Whitespace_ID => Tokenizer.Get (OpenToken.Recognizer.Character_Set.Get (OpenToken.Recognizer.Character_Set.Standard_Whitespace)) );

Шаг 4: Создание лексем

Далее необходимо описать обработчики для всех лексем. Терминалы могут быть присвоены непосредственно, как в синтаксисе (предполагается, что переименования будут работать также). Нетерминалы могут быть инициализированы позже, но, поскольку они будут указывать на те же объекты лексем, предварительная инициализация (т.е. в данный момент) позволяет сохранить некоторое пространство памяти. Если инициализация нетерминалов осуществляется сейчас, то может возникнуть необходимость осуществить некоторые действия над типами лексем, которые эти нетерминалы будут использовать. В более поздних шагах можно увидеть почему ниже были использованы экземпляры типа I В используемом примере именами лексем-нетерминалов (лексемы - влевой части правил вывода) являются S',S, L и R. Таким образом, описания имеют следующий вид:

S_Prime : OpenToken.Token.Handle; S : constant OpenToken.Token.Handle := new OpenToken.Token.Selection.Instance; L : constant OpenToken.Token.Handle := new OpenToken.Token.Selection.Instance; R : constant OpenToken.Token.Handle := new OpenToken.Token.Selection.Instance;

Позднее будет представлено объяснение почему для S_Prime инициализация отсутствует, а для остальных - присутствует.

Шаг 5: Описание лексического анализатора

Описание собственного приемника входного потока (Text_Feeder)

В этом случае можно использовать приемник входного потока, который связан со своим собственным файлом, а не Ada.Text_IO.Current_Input. Для осуществления этого, сначала надо описать экземпляр объекта (косвенно доступный, т.е. aliased), который будет служить как файл для Text_IO.Open и Text_IO.Close. Затем, описать OpenToken.Text_Feeder.Text_IO.Instance. После, инициализировать приемник входного потока с помощью подпрограммы Create, используя файловый объект как File_Ptr:

Input_File : aliased Ada.Text_IO.File_Type; Feeder : aliased OpenToken.Text_Feeder.Text_IO.Instance := OpenToken.Text_Feeder.Text_IO.Create (Input_File'Unchecked_Access);

Теперь, для создания, собственно, анализатора, необходимо создать экземпляр объекта типа Tokenizer.Instance, и инициализировать его требуемым синтаксисом и приемником входного потока. Это не сложно:

Analyzer : Tokenizer.Instance := Tokenizer.Initialize (Syntax, Feeder'Access);

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

Test_File_Name : constant String := "Example.txt";

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

Шаг 6: Описание лексемы верхнего уровня (лексема языка)

В рассматриваемом примере первое правило вывода (правило вывода верхнего уровня) имеет следующий вид:

S' -> S

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

Таким образом, S_Prime указывает на тот же самый объект, что и S:

S_Prime := S;

Собственно из-за этого способ создания S_Prime отличается от создания других объектов.

Шаг 7: Определение какой-либо лексемы, которая не определена на предыдущем шаге

На предыдущем шаге была использована лексема S. Правило грамматики для S имеет следующий вид:

S -> L = R | R

Следует заметить, что поскольку лексема S является лексемой верхнего уровня, то в конце правила вывода неявно существует лексема EOF. Следовательно, это можно выразить другими словами как последовательность лексем L, =, R и EOF или как последовательность лексем R и EOF. Можно было бы построить собственную лексему синтаксический анализатор которой способен это распознать. Однако, какая-либо последовательность лексем и какая-либо селекция лексемам достаточно случайны, а обработка лексем осуществляется весьма общенно. В связи с этим существуют прекомпилированные лексемы Token.Sequence и Token.Selection. Используя эти пакеты (естественно, с соответствующим указанием спецификатора "use type"), можно описать лексему S следующим образом:

S.all := OpenToken.Token.Selection.Class (OpenToken.Token.Sequence.New_Instance (L & Equals & R & EOF) or OpenToken.Token.Sequence.New_Instance (R & EOF));

Шаг 8: Определение какой-либо лексемы, которая не определена на предыдущем шаге

На предыдущем шаге были использованы лексемы-нетерминалы L и R. Определение правила вывода для лексемы L будет иметь вид:

L -> * R | id

То есть лексемой L является последовательность * и R или какой-либо id. Используя те же две предопределенные лексемы, можно получить следующее:

L.all := OpenToken.Token.Selection.Class (OpenToken.Token.Sequence.New_Instance (Asterix & R) or ID);

Шаг 9: Определение какой-либо лексемы, которая не определена на предыдущем шаге

Осталось определить единственную лексему - R. Это правило вывода имеет вид:

R -> L

Здесь также присутствует "глупая" тождественность правил вывода. В данном случае можно попробовать применить другую тактику и создать отдельную лексему R, которая является копией лексемы L:

R.all := L.all;

Использование нисходящего рекурсивного синтаксического анализатора

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

Ada.Text_IO.Open (File => Input_File, Name => Test_File_Name, Mode => Ada.Text_IO.In_File); -- Загрузка первой лексемы Tokenizer.Find_Next (Analyzer); OpenToken.Token.Parse (Match => S_Prime.all, Analyzer => Analyzer);

Это - все!

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

exception when Error : OpenToken.Token.Parse_Error => Ada.Text_IO.Put_Line ("failed at line" & Integer'Image (Tokenizer.Line (Analyzer)) & ", column" & Integer'Image (Tokenizer.Column (Analyzer)) & " due to parse exception:"); Ada.Text_IO.Put_Line (Ada.Exceptions.Exception_Information (Error));

Замечание

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