ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ Рейн Т. С. Программная реализация лексического анализатора

Задача определения языка Как определить используемый язык ? Определение должно быть удобным, т. е.: Определение должно быть конечным Должен существовать алгоритм, за конечное число шагов проверяющий принадлежность некоторой входной цепочки языку Наиболее распространенные формализмы для задания языков : грамматики, Регулярные выражения, конечные и магазинные автоматы, машины Тьюринга

Определение грамматики Грамматика определяется путем задания следующих компонент : Терминальные символы ( алфавит ) Нетерминальные символы ( иногда также называемые понятия ) Правила вывода Начальный символ Кроме того, необходимо определить набор правил вывода вида αβ, с помощью которых строятся все цепочки языка.

Если А есть алфавит, то A* обозначает множество всех строк ( включая пустую строку ε ), составленных из символов, входящих в А. A+ определяет множество всех строк, составленных из символов, входящих в А, но без пустой строки. Нетерминалы обозначаются прописными буквами, а терминалы – строчными. Определение грамматики

Грамматика G определяется как следующая четверка : G = (V_T, V_N, P, S), где V_T – конечное множество терминальных символов ; V_N – не пересекающееся с V_T конечное множество нетерминальных символов ; P – конечный набор порождающих правил вида ( α, β ), где α V +, β V * S – начальный символ, где N Определение грамматики

Грамматикой, порождающей язык {0^n 1^n | n0}, является G_0: G_0= ({0,1}, {S}, P, S), где P = {S 0S1, S ε }. Грамматика, порождающая язык {a^m b^n | m,n 0}. Такая грамматика имеет вид G1= ({a,b}, {S,A, B}, P, S), где набор правил определяется следующим образом : P = {S AB, A aA, A ε, B bB, B ε }. Грамматики. Пример

Свойства грамматик Различные грамматики могут порождать один и тот же язык. Такие грамматики называются эквивалентными Левые части правил могут содержать другие нетерминалы ( помимо определяемого ) По соглашению, можно объединять несколько правил с одинаковой левой частью, записывая правые части через символ '|' (" или ")

Конечные автоматы Конечный автомат – это пятерка : M = (Q, Σ, δ, q0, F), где Q – конечное множество состояний Σ – конечное множество допустимых входных символов δ – функция перехода q0 из Q – начальное состояние F – множество заключительных состояний

Детерминированные конечные автоматы Автомат называется детерминированным, если множество δ (q, a) содержит не более одного состояния для любых q, a. Если δ (q, a) всегда содержит ровно одно состояние, то автомат называется полностью определенным. Цепочка w допускается автоматом M, если существует последовательность шагов, приводящая нас по этой цепочке в заключительное состояние автомата Язык распознается конечным автоматом, если им распознается каждое слово языка

Детерминированные конечные автоматы КА, распознающий язык (aa*|bb*)КА, распознающий язык (a|b)*abb

Недетерминированные КА Любому недетерминированному автомату соответствует детерминированный автомат, определяющий тот же самый язык, причем известен метод конструирования эквивалентного конечного автомата Классы языков, задаваемых недетерминированными и детерминированными конечными автоматами, совпадают

Пример Программный код демонстрирует моделирование конечного автомата ( предполагается, что входная лента заканчивается символом end_of_file): q = q0; c = GetChar(); while (c != eof) { q = move (q, c); c = GetChar(); } if (q is in F) return "yes"; else return "no";

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

Задача лексического анализатора Задача лексического анализа – разбиение исходной программы на лексемы Типичные лексические классы : Ключевые слова (if, switch, for…) Идентификаторы Строковые литералы Числовые константы Каждому подмножеству сопоставляется некоторое число, называемое идентификатором лексического класса (token) или, короче, лексическим классом.

Токен

Класс токена #include using namespace std; class CToken { private: E_TOKEN_TYPES _Type;//тип лексемы string _Text;//текст лексемы public: E_TOKEN_TYPES Type(void)const {return _Type;} string Text(void)const {return _Text;} CToken(void); CToken(const CToken&); CToken(E_TOKEN_TYPES, const string&); };

Тип Примеры Тип Примеры Зарезервиров анные слова int, end Операторы +, ~, = Целые константы 10, 100 Строковые константы «I think it is» Переменные answ, num Функции Write(), Char() Разделители «,», «;» Неидентифиц ированный E_TOKEN_TYPES – характеризует тип лексхемы

enum E_TOKEN_TYPES { ttResWord = 0, //ключевое (зарезервированное) слово ttOperator, //оператор ttStrConstant, //строковая константа ttIntConstant, //числовая константа ttVariable, //переменная ttFunction, //функция ttDevider, //разделитель ttUnknown //тип не определен, либо не известен };

Конструкторы класса CToken::CToken(void): _Type(ttUnknown) {}; CToken::CToken(const CToken& other): _Type(other._Type), _Text(other._Text) {}; CToken::CToken(E_TOKEN_TYPES type, const string& text): _Type(type), _Text(text) {};

Пример Рассмотрим оператор языка Pascal const pi = ; Этот оператор состоит из следующих лексем : с onst – лексический класс Const_LC pi – лексический класс Identifier_LC = – лексический класс Relation_LC – лексический класс Number_LC ; – лексический класс Semicolon_LC

Работа лексического анализатора вход -> пока не обработаны все данные : формировать очередной токен -> помещать его в буфер токенов формирование очередного токена : выделение очередной лексемы из входных данных -> определение ее типа -> помещение типа и текста лексемы в объект токена

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

Интерфейс ЛА typedef vector TokensArray; class CLexer { private: string _Operators, //операторы _Deviders; //разделители TokensArray _TokensBuffer; //токены, полученные при последнем //ЛА текста unsigned _OffSet; //позиция в текущем лексируемом тексте //возвращает очередной токен из передаваемого текста CToken SkanToken(const string&); public: const TokensArray& GetTokens(void)const {return _TokensBuffer;} void SaveTokens(ostream& os)const; //разбивает передаваемый текст на массив токенов bool Lex(const string&); };

ЛА различных языков программирования Особенности некоторых языков могут существенно затруднять лексический анализ : Фиксированный формат программы ( Фортран, PL/I, Кобол ) Трактовка пробела как незначащего символа ( Фортран, Алгол 68) – Использование ключевых слов какидентификаторов (PL/I)

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

Таблица представлений Простейший вид таблицы представлений – это массив указателей на строки Однако этот массив должен иметь возможность расширения и быстрого поиска Поэтому распространена другая форма организации таблицы представлений – в виде набора хэшированных списков

Использование грамматик для лексического анализа Лексические свойства языков обычно носят достаточно регулярную структуру, поэтому для задания правил лексического анализа можно использовать ( праволинейные ) грамматики : letter => 'a'..'z' | 'A'..'Z' | '_' digit => '0'..'9' ident => letter | letter tail tail => letter | digit | letter tail | digit tail Однако на практике чаще используется эквивалентный праволинейным грамматикам механизм регулярных выражений

Регулярные выражения Регулярное выражение над алфавитом А может быть задано с помощью следующих правил : Пустое множество и множество, состоящее только из пустой строки, являются регулярными выражениями Любой одиночный символ а из А является регулярным выражением Для любых регулярных выражений P и Q следующие множества также являются регулярными выражениями : PQ (Q следует за P) P|Q (P или Q) P* ( нуль или более экземпляров P)

Регулярные выражения. Пример Регулярное выражение 1(0+1)*1+1 представляет множество цепочек, начинающихся и заканчивающихся символом 1 Регулярные выражения эквивалентны праволинейным грамматикам. Таким образом, регулярным выражениям также соответствует естественный класс распознавателей в виде конечных автоматов.

Алгоритм построения ЛА по РВ анализ первого символа ( буква или символ подчеркивания ?) продвижение вперед по исходной строке, покуда мы встречаем буквы, цифры или символ подчеркивания проверка, не является ли разобранный идентификатор ключевым словом ? если это действительно ключевое слово, то выдается соответствующий лексический класс ( ключевое слово ), вместе с привязкой к исходному тексту и точным значением ключевого слова если это не ключевое слово, то это идентификатор, который и выдается вместе с привязкой к исходному тексту и его именем.

Забегание вперед при ЛА В некоторых случаях может потребоваться заглядывание вперед для точного определения текущей лексемы Для этого используется выражение A/B, которое выдает лексический класс А только в том случае, если за ним следует В В качестве примера рассмотрим разбор переменных, начинающихся с DO в Фортране

ПРИМЕР ЛА

Пример разработки ЛА Пусть некоторый язык программирования включает в себя директиву using, функцию main(), описание переменных, констант, массива переменной длины, операторов присваивания, арифметические операции.

Пример кода на формальном языке using System.Text; /* многострочный комменатрий */ public class TestClass { public uint a, b = 35, i; public bool c, d; public const long int e = 9L; public uint Main(Param1, Param2) { read(a, b); for(i = 0; i < 10; i = i + 1) { write(a, b, c, d, e); a = b - (c + 2L); d *= e - 2; e /= 123; break; }; for(i = 0; i < 10; i *= 2) { continue; } }

Разбор кода Директива using позволяет в текущем пространстве имен использовать типы данных, определенные в другом пространстве имен. Синтаксис : using System.Text; В данном случае лексема using является ключевым словом. С помощью ключевого слова class определяются классы. Например : public class TestClass { // Определение полей и методов класса } Ключевое слово public определяет уровень доступности класса.

Поля класса определяются как переменные : public class TestClass { public uint a, b = 35, i; public bool c, d; public const long int e = 9L; } Для каждого поля прописывается модификатор доступа (public) и тип поля. Методы класса определяются так же, как и обычные функции : public class TestClass { public int Main(Param1, Param2) { } }

Как и для полей класса, для методов задается модификатор доступа и тип возвращаемого значения метода. Тело метода класса согласно учебному языку может содержать : определение цикла со счетчиком : for ( ; ; ) { } вызовы процедур : write ( ); read ( ); операторы присваивания : a = ; d *= ; F /= ; арифметические выражения, содержащие бинарные операции : a = b - (c + d);

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

Грамматики Синтаксис идентификаторов определяется праволинейной регулярной грамматикой : -> L ( 1) -> L ( 2) -> D ( 3) -> е ( 4) где L - буква множества (A..Z), D - цифра множества (0..9), е - пустая цепочка или символ окончания лексемы. Целые константы записываются арабскими цифрами. Праволинейная грамматика целого числа : + |- н н | е

Конечный автомат Заданная грамматика может бать реализована автоматом со следующими состояниями : S - состояние ожидания первого символа лексемы ; I - состояние ожидания символов идентификаторов : буквы, цифры ; С - состояние ожидания символов целой части числа ; E - состояние ошибки ; R - состояние допуска лексемы. Автомат переходит в допустимое состояние R из состояния I для идентификаторов и из состояния C для чисел.

Регулярные грамматики Регулярная грамматика для заданных условий записи лексем задается следующими множествами : Р : [P1, P2, …,P4] – множество правил ; G: [S, I, C, E, R] – множество состояний, где S – начальный символ ; [0..9, A..Z, «–», «#», «(», «)», «*», «,», «.», «/», «:», «;», «{«, «}», «+», «=»] – множество входных символов, из них разделительные символы и уникальные лексемы [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»].

Символы пробел и табуляции означают конец лексемы. Эти символы не является лексемой и требуют выполнения операции « СДВИГ » над входной строкой. По символу пробел автомат допускает лексему и переходит в начальное состояние анализа следующего символа входной строки автомата. Символы : «–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=» являются одновременно разделительными знаками и началом следующей лексемы, даже если перед ними нет символа конца лексемы. Операция « СДВИГ » после этих символов не требуется, автомат допускает лексему и переходит в начальное состояние для анализа этих же символов.

Таблица переходов LDe SIESНач. состояние IIIR EОшибка RДопустить

Зарезервированные слова Идентификация служебных слов реализуется автоматом распознавателя. Множество служебных слов : BREAK CLASS CONST CONTINUE LONG INT BOOL FOR UINT PUBLIC READ USING WRITE.

Управляющая таблица При составлении таблицы использовались следующие обозначения : первым символом указывается состояние, в которое переходит автомат при поступлении соответствующего символа ; символ «+» означает добавление входного символа к лексеме ; символ «>>» означает сдвиг входной строки на один символ.

Управляющая таблица SpacesLetters Digits Symbols SS, >>I, +, >> C, +, >> R, +, >> CRE C, +, >> R IRI, +, >> R EОшибка RS, Допустить Spaces – множество символов пробела (сам пробел и знак табуляции); Letters – множество букв латинского алфавита [A..Z, « _ » ]; Digits – множество арабских цифр [0..9]; Symbols – множество разделительных символов [ «–», « # », « ( », « ) », « * », «, », « / », « : », « ; », « { «, « } », « + », « = » ].

Синтаксис ЛА Грамматика целевого символа : ( 1) -> using ( 2) -> public ( 3) -> ; ( 4) -> e

Синтаксис ЛА Грамматика описания using: ( 5) -> ID ( 6) ->. ( 7) -> e

Синтаксис ЛА Грамматика описания класса : ( 8) -> class ID { } ( 9) -> public (10) -> ; (11) -> e

Синтаксис ЛА Грамматика описания определения полей и методов класса : (12) -> uint (13) -> bool (14) -> const long int (15) -> ID (16) -> ( ) { } (17) ->, (18) -> = (19) -> e (20) -> ID (21) ->, (22) -> = (23) -> e

Синтаксис ЛА Грамматика описания списка операторов : (24) -> (25) -> ; (26) -> e Грамматика описания операторов : (27) -> for ( ID = ; ; ID ) { } (28) -> break (29) -> continue (30) -> write ( ) (31) -> read ( ) (32) -> ID (33) -> = (34) -> * = (35) -> / =

Синтаксис ЛА Грамматика описания арифметического выражения : (36) -> ( ) (37) -> ID (38) -> NUM (39) -> + (40) -> - (41) -> e Грамматика описания условия : (42) -> ( ) (43) -> (44) -> > (45) -> (46) -> = = (47) -> e