Файл: Обзор языков программирования высокого уровня ( ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ ).pdf

При составлении таблицы каждому элементу языка сопоставляется тип соответствующей лексемы. Некоторые базовые элементы объединены в один тип (осуществляют схожие функции и имеют одинаковый приоритет).

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

В основе лексических анализаторов лежат автоматные грамматики.

Грамматикой G называется четверка (S, VN, ST, R), где S - начальный символ грамматики, VN - множество нетерминальных символов, ST - множество терминальных символов, R - множество правил грамматики [4].

Каждое правило грамматики в общем случае записывается в виде а^в, где а, в - произвольные цепочки, составленные из терминальных и нетер­минальных символов грамматики.

Автоматной называется грамматика, все правила которой имеют вид: А^аВ, а, где A, B - нетерминальные символы, а - терминальный символ [1].

Правила Л^ а называют заключительными(терминальными) правилами.

Автоматная грамматика для целочисленных констант имеет вид:

S^0S|1S|...|9S|0|1|...|9

Автоматная грамматика для идентификаторов имеет вид:

S^aA|bA|...|zA

S > 0A|1A|...|9A|0|1|...|9|aA|bA|...|zA|a|b|...|z

Построение собственного лексического анализатора для цепочки

с предусловием на языке Java

В качестве анализируемого выражения возьмем цепочку следующего вида: while ((a<n) and (b<k) ){

sum=sum+a;

a=a+1;

b=b+20;

^}

В качестве алфавита выступают буквы латинского алфавита, цифры, другие значащие символы (+, <, =, ;, (, ), {, }) и незначащие символы (пробел, табуляция, перевод строки)

Составим таблицы лексем и идентификаторов, которые будет использоваться лексическим анализатором при трансформации исходной программы в цепочку токенов (см. таблицы 2-6). Сам лексический анализатор будем реализовывать как анализатор автоматного языка.

Составим автоматную грамматику для идентификаторов и констант (символом '^Л' обозначен символ конца строки). При ее построении будем считать, что символом '*' обозначены все символы, не являющиеся цифрами, символом '~' - пробел, символом '0' - все кроме букв и цифр, символом 'ц' - все символы, кроме фигурных скобок. После перехода в состояние Fx, автомат сбрасывается и переходит в состояние S.

S- S

S—aA|bA|...|zA A—aA|bA|...|zA A-0A|1A|...|9A A - 0F1.4

S-0B|1B|...|9B

B-0B|1B|...|9B

B -*R

Грамматики для операций и отношений:

S - R -R A;

Грамматики для специальных символов:

S-|(F₃| )F3

Грамматика для последовательностей незначащих символов:

S—#32S|...|#10S|#13SP

Грамматика для выражений, находящихся в фигурных скобках (включая их):

S-{S'

S' -uS'

S'-}S

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

Автомат завершает работу при считывании символа Л

S^^Al'in, здесь fin - состояние, в котором считывается последняя лексема.

Таблица 2.

Тип 1- служебные слова

Таблица 3.

Тип 2 - операции и отношения

Таблица 4.

Тип 3 - специальные символы

Таблица 5.

Тип 4 - идентификаторы

Таблица 6.

Тип 5 - числовые константы

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

<1,1>,<3,2>,<3,2>,<4,1>,<2,1>,<4,2>,<3,3>,<1,2>,<3,2>,<4,3>,<2,1>,<4,4>,< 3,3>,<3,3>,<3,4>,<4,5>,<2,2>,<4,5>,<2,3>,<4,1>,<3,1>,<4,1>,<2,2>,<4,1>,<2,3>,< 5,1>,<3,1>,<4,3>,<2,2>,<4,3>,<2,3>,<5,2>,<3,1>,<3,5> - здесь у пары <i,j> число i означает номер типа, число j - номер лексемы в типе.

Создадим конечный детерминированный автомат, распознающий цепочки, являющиеся лексемами вышеприведенных типов. Конечными состояниями автомата будут являться F_1j4, F₂, F₃, F5(здесь индекс конечного состояния означает нахождение считанной лексеме в соответствующей таблице лексем), т. е. попадание в состояние F3 означает, что считан специальный символ из таблицы 3 и т. д. Лексемы из таблиц 1 и 4(служебные слова и идентификаторы) объединены в одно финальное состояние с целью уменьшения размера автомата и упрощения программистской задачи. Заметим, что конец считывания происходит только при считывании одного лишнего символа.

Представим детерминированный конечный автомат, предназначенный для лексического анализа вышеприведенного примера.

Рисунок 23. Конечный автомат в виде графа

На представленном рисунке Err - состояние ошибки, в которое автомат попадает при неописанном символе, в Err ведут стрелки со всех состояний.

Код программы лексического анализатора

char GetNextChar();

void ReturnLiter(char c);

void AddToBuf(char c);

bool IsNumber(char c);

void IsLetter(char c);

int BufIntendKey(int &Type);

int BufOper(int &Type);

int BufSpec(int &Type);

int BufNum(int &Type);

enume State {S,S1,A,B,fin} T;

int StepNextChar (int &Type) {

char c;

State T=S;

do{

c=GetNextChar();

switch(T){

case S: if((c==' ')||(c=='\t')||(c=='\r')||(c=='\n')) break; if(c=='{') {T=S1;break;}

if(c=='^A') return 0;

AddToBuf (c);

if(IsLetter(c)) {T=A; break;}

if((c=='=')||(c=='+') ||(c=='<')) return BufOper (Type); if((c==';') ||(c=='(')||(c==')')) return BufSpec (Type); if(IsNumber(c)) {T=A; break;}

return -1;

case A:if(IsNumber(c)|| IsLetter(c)) { AddToBuf (c);break;} else {ReturnLiter(c);return BufIntendKey (Type);} case B:if(IsNumber(c)){

AddToBuf (c);

break;

}

ReturnLiter(c);

return BufNum (Type);

}

} while true;

^}

int LexicalAnalyzer (int &Type) {

int Type;

int N;

do{

N=StepNextChar(Type);

if(N=<0) return N;

AddToOutSeq(N,T);

} while true;

^}

ЗАКЛЮЧЕНИЕ

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

Первая глава работы носит теоретический характер, описывая общее понятие языков программирования, их историю развития, которая прошла несколько этапов:

• машинные коды;
• ассемблеры;
• алгоритмические языки;
• процедурные языки;
• объектно-ориентированные языки.

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

• низкого уровня:
  • машинно-зависимые – представляют собой команды, записанные непосредственно на языке конкретного процессора;
  • машинно-ориентированные – команды, записанные на языке близком к процессору в виде буквенных обозначений;
• высокого уровня – машинно-независимые языки, имитирующие естественный человеческий язык;
• сверхвысокого уровня – еще один вид машинно-независимых языков программирования. Команды таких языков исполняются на абстрактных машинах, при этом доступ к памяти полностью скрыт.

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

Существует несколько способов записи алгоритмов:

• словесное описание;
• построчная запись;
• блок-схема;
• запись на языке программирования.

Во второй главе описаны основные операторы языка программирования Паскаль:

• оператор присваивания – реализует запись значения выражения в переменную;
• операторы ввода-вывода - служат для обмена данными между программой и внешними устройствами. Так, например, можно ввести данные с клавиатуры, из файла, вывести данные на экран или в файл;
• операторы перехода – в языке Паскаль принято выделять два вида переходов – условный и безусловный. При этом в первом случае также возможно два варианта – полное и неполное ветвление;
• операторы выбора – используются в тех случаях, когда нелогично использование условных операторов. Это объясняется наличием нескольких возможных вариантов выбора;
• операторы цикла – Паскаль, как и любой другой язык программирования высокого уровня, содержит три вида циклов:
  • цикл с предусловием;
  • цикл с постусловием;
  • цикл с параметром.

Описание данных операторов сопровождается примерами, демонстрирующими решение простых задач.