Теория вычислительных процессов

Факультет дистанционного обучения

Томский государственный университет

систем управления и радиоэлектроники (ТУСУР)

Кафедра автоматизированных систем управления

Лабораторная работа № 1

по дисциплине «Теория вычислительных процессов»

Выполнил:

студент ФДО ТУСУР

гр.:

специальности

г. Стрежевой

2012г

Содержание

Содержание             

1.              Задание             

1.1 Входные данные             

1.2 Выходные данные             

2. Краткая теория             

3. Результаты работы программы             

4. Выводы             

Список литературы             

Приложение.             

1.      Задание

Необходимо разработать программу для анализа описания переменных.

1.1 Входные данные

На вход программы подается текстовый файл с именем INPUT.TXT, содержащий только описания переменных на языке Pascal. Например, содержание текстового файла может быть следующим:

var a, b, c: real;

d: array [1..6, 6..9] of integer;

s1: string;

s2: string[10];

То есть описание переменных начинается с ключевого слова «var», далее следуют списки имен переменных с указанием типа. В список типов необходимо включить наиболее часто используемые базовые типы. Тип может быть также массивом (в т.ч. многомерным) или строкой. У массива нижняя граница индекса не должна быть меньше верхней. Строка не может быть длиннее 255 символов.

Имя переменной — это последовательность букв и цифр, начинающаяся с буквы. Под буквами понимаются большие и малые буквы латинского алфавита (a…z, A…Z) и подчеркивание (_). Большинство современных компиляторов не имеют ограничений по длине имен переменных, однако значащими считаются только первые N символов (число N зависит от конкретного компилятора). Например, если N = 8, то переменные a1234567 и a12345678 рассматриваются компиляторами как идентичные, хотя обе записи являются синтаксически верными. Значение числа N можно выбрать любое (N ≥ 1), но обычно это 8, 16, 32 и т.д.

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

- пробелы (код ASCII — 32 или $20 в шестнадцатеричном виде);

- переводы строк и возвраты кареток (коды ASCII — 10 ($0A) и 13 ($0D) соответственно);

- табуляции (код ASCII — 9 или $09).

Для указания символа по его коду в языке Pascal используется знак «#». Либо для этих целей можно использовать функцию CHR (см. ее описание в файле справки компилятора языка Pascal). При указании букв A…F в шестнадцатеричных числах можно использовать как большие, так и малые буквы. Так, для проверки символа ch на возврат каретки можно написать

if ch = #13 …

или

if ch = #$0D …

или же

if ch = chr(13) …

1.2 Выходные данные

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

              1.              Сообщение о том, что описание корректное.

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

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

2. Краткая теория                       

Для реализации программ был выбран язык программирования Pascal.

Для реализации алгоритма выбран цикл «case» -  здесь сыграла проблема с поиском начала объявления - ключевого слова "var" и последующим переходом к  описанию   переменных. Выбран вариант с построчной обработкой файла.

.

3. Результаты работы программы  

var a, b, c: real;

d: array [1..6, 6..9] of integer;

s1: string;

s2: string[10];

Ошибок не обнаружено

var

a, b, c: real; d: array [1..6, 6..9] of integer;

s1: string;

s2: string[10];

f: array of real;

f4:array [1..1] of real;

F4:string[255];

Переменная с таким именем уже определена - "F4"

В позиции: 7:1

4. Выводы

В среде Pascal была создана программа, которая определяет правильно ли описаны переменные языка паскаль во входном файле input.txt

Список литературы                  

1.         Калайда В.Т. Теория вычислительных процессов и структур: Учеб. пособие. — Томск: ТМЦДО, 2007. — 269 с.

2.         Ахо А., Ульяман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — 612 с.

3.         Ханкер Р. Проектирование и конструирование компиляторов. — М.: Финансы и статистика, 1984 — 230 с.

4.         Райуорд-Смит В. Дж. Теория формальных языков. Вводный курс. — М.: Радио и связь, 1988. — 128 с.

5.         Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. — М.: Мир, 1979. — 656 с.

Приложение.

Листинг программы:    

program varible_3;

var input:text;

    line,position,err_line,err_pos:integer; //строка и позиция

    err_name:string;

    is_error:boolean=false;

    lines:array of string; //обрабатываемая строка

    startP,endP:string; //Начало и конец массива

    Prev_Pos:byte;

    name:array of string;

    name_nmb:integer;

    unexp_end:boolean=false;

    is_array:boolean=false;

    aft_str:boolean=false;

    aft_dots:boolean=false;

    temp_str:string;

    j:integer;

    var_str:string;

const

      //Предыдущий символ

  SEMICOLON        = 1;    //разделитель - ";" или ",". Т.е. кончилось объявление предыдущей переменной.

  STR              = 2;    //переменная

  COLON            = 3;    // ":" или "OF"

  ARRAY_P          = 4;

  BRECKET_1        = 5;    // "[" или ".." или ","

  BRECKET_2        = 6;

  VAR_TYPE         = 8;

  NUMERIC          = 9;

  N = 8;

function separator(sep:char):boolean;

begin

  separator:=(sep = #32) or (sep=#9);

end;

function symb(smb:char):boolean;

begin

  symb := ((smb>='A') and (smb<='Z')) or ((smb>='a') and (smb<='z'));

end;

function get_str:string;

begin

  temp_str:='';

  while symb(lines[line][position]) do

    begin

      temp_str:=temp_str+lines[line][position];

      position:=position+1;

    end;

  get_str:=temp_str;

end;

function check(chkstr:string):boolean;

var i:integer;

    dots_str:string;

    keyword:array [1..6] of string;

label else_p_colon,

      else_p_num,

      else_p_brecket_1,

      else_p_brecket_2;

begin

    while separator(lines[line][position]) do

      begin

          position:=position+1;   //Вычитается ниже

          if lines[line][position]=#9 then err_pos:=err_pos+4-1; //плюс количество смволов в табуляции(обычно 4 или 8) и минус уже прибавленную до этого позицию

      end;

    if (lines[line][position]=#13) or

       (lines[line][position]=#10) or

       (lines[line][position]=#0)then

      begin

        check:=true;

        exit;

     end;

    case prev_pos of

      SEMICOLON:

                begin

                  unexp_end:=false;

                  keyword[1]:='STRING';

                  keyword[2]:='INTEGER';

                  keyword[3]:='REAL';

                  keyword[4]:='ARRAY';

                  keyword[5]:='OF';

                  keyword[6]:='VAR';

                  if (symb(lines[line][position])) or (lines[line][position]='_') then   //Если в теущий знак может быть началом перменной

                    begin

                      name_nmb:=name_nmb+1;   //Увеличиваем счетчик имен пермеменных

                      setlength(name,name_nmb+1); //расширяем массив имен

                      while (symb(lines[line][position])) or

                            (lines[line][position]='_') or

                            ((lines[line][position]>='0') and (lines[line][position]<='9')) do

                        begin

                          name[name_nmb]:=name[name_nmb]+lines[line][position];

                          position:=position+1;

                        end;

                      for i:=1 to 6 do

                          if UpperCase(name[name_nmb])=keyword[i] then

                            begin

                              err_name:='Переменная не может быть ключевым словом - '+'"'+name[name_nmb]+'"';

                              err_line:=line;

                              err_pos:=err_pos+position -(length(name[name_nmb]));//Вроде так...

                              check:=false;

                              exit;

                            end;

                      delete(name[name_nmb],N+1,length(name[name_nmb])); //Значимыми являются только первые N символов - удаляем все, лишнее

for i:=1 to name_nmb-1 do         //Проверяем нет объявлена ли переменная ранее. Можно обойтись и без вспомогательного массива. Но в этом случае алгоритм будет сложнее, а одна переменная типа string все равно понадобится.

for i:=1 to line do if (pos(name,lines[i])<>0) and (pos(name,lines[i])<>(position-(name_pos-1))) then //выводим ошибку;

if UpperCase(name[name_nmb]) = UpperCase(name[i]) then  //Имена перменных не чувствительны к регистру

                            begin     //Выводим ошибку

                              err_name:='Переменная с таким именем уже определена - '+'"'+name[name_nmb]+'"';

                              err_line:=line;

                              err_pos:=err_pos+position -(length(name[name_nmb]));                              check:=false;

                              exit;

                            end;

                      prev_pos:=STR;

                      check(lines[line]);

                      exit;

                    end;

                  else

                    begin

                      err_line:=line;

                      err_pos:=err_pos+position;

err_name:='Переменная не может начинаться с символа: '+'"'+lines[err_line][err_pos]+'"';

                      check:=false;

                      exit;

                    end;

                end;

      STR      :

                begin

                  if lines[line][position] = ',' then

                    begin

                      unexp_end:=true;

                      prev_pos:=SEMICOLON;

                      position:=position+1;

                      check(lines[line]);

                      exit;

                    end

                  else

                    if lines[line][position] = ':' then 

                      begin

                        prev_pos:=COLON;

                        position:=position+1;

                        check(lines[line]);

                        exit;

                      end

                  else     //ошибка

                    begin

                      err_line:=line;