Лексический анализатор языка Java, созданный в среде Delphi

в 11:16, , рубрики: Delphi, Лексический анализатор, Программирование, Регулярные выражения, метки: , , ,
ТЗ или о чем пойдет речь

Данный пост будет, как правило, интересен студентам, так как подобное задание было получено в качестве лабораторной работы по дисциплине «Лингвистические основы информатики».
Итак, давайте же рассмотрим техническое задание подробнее. Что нам требуется? А требуется нам создать анализатор, который будет разбивать заданный текст на языке Java по классам — ключевым словам, идентификаторам, операторам, пунктуаторам (сепараторам) и т.п., и выводить результат работы в таблицу. Таблица будет содержать следующие столбцы:

  • Токен
  • Спецификатор
  • Описание
  • Позиция
  • Длинна

Напомню, что токен — это последовательности символов в лексическом анализе в информатике, соответствующий лексеме.
Спецификатор описывает к какому классу относится токен. То есть, например, для токена «boolean» в таблице выведется «Keywords».
Ну описание, позицию и длину описывать, я думаю, не стоит.
Вроде бы задание понятно. Теперь разобьем его на подзадачи.
0) Изначально я бы посоветовал изучить спецификацию языка, для которого вы будете писать анализатор. Далее нам нужно:
1) Загрузить массив данных о наших ключевых словах, операторах и пунктуаторах, так как они уникальны.
2) Распарсить заданный текст на токены и определить их классы. (Распарсить — то же самое, что и разобрать, т.е. выбрать эти элементы из текста в переменные)
3) Занести данные о токенах в массив и отсортировать его.
4) Вывести данные в таблицу.

Определимся с выбором

Каким же образом мы можем распарсить наш текст? Вообще метода 2:

  1. При помощи оператора case. Долго, нудно и не интересно. А если серьезно, то способ слишком объемен и сложен в реализации. То есть для каждого токена Вам нужно будет составить отдельное значение для переменной. Для одних только ключевых слов придется делать 52 (!) блока проверки условия. Я молчу о проверке ошибок литералов и комментариев. Вердикт — отсеиваем.
  2. И второй, более простой способ, использование регулярных выражений. Просто, быстро и удобно. Лично я использовал библиотеку RegExpr с сайта RegExpr Studio.
Этап 1. Заполняем массивы данных

Итак, нам нужно создать массивы, в которых будут наши ключевые слова, операторы, пунктуаторы и их описание. Вы можете создать уже заполненные массивы в самой программе, но я, лично, что бы не перегружать код и упростить редактирование данных, делал выгрузку из 3х файлов и буду объяснять именно на этом примере.
Создаем 3 файла. У меня это «keywords.txt», «operator.txt» и «separator.txt». Заполняем их в соответствии с их названием. Каким образом заполняем? Пишем (вставляем), например, ключевое слово и через пробел его описание. Как это выглядит?
_____________
abstract modificator
boolean type
break CTRLcycle
byte type
case selection
catch exception
char type
______________
Ну и так далее. То есть тоже самое мы делаем для операторов и сепараторов. Сделали? Отлично! Едем дальше.

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

  while not EOF(FKeyw) do
    begin
      readln(fkeyw,s);
      SetLength(KWRD,i+1);  //уведичиваем массив на 1 элемент
      KWRD[i].token:=copy(s,1,(pos(' ',s)-1)); // копируем в токен все, что до пробела
      KWRD[i].spec:=copy(s,(pos(' ',s)+1),length(s)); //а в описание все, что после
      inc(i);
   end;

, где FKeyw — файловая переменная для файла Keywords.txt, а KWRD — это массив записей для ключевых слов, объявленный, как ГЛОБАЛЬНАЯ переменная.
Аналогичным образом заполняются массивы OPRT и PNCTR. Ну по названию видно какой массив к какому файлу относится.
На этом, собственно, первый этап заканчивается.

Этап 2. Самый длинный.

Модуль RegExpr уже скачан и подключен к программе. Что дальше? А дальше мы проходим по ссылочке ниже и читаем синтаксис наших регулярных выражений, так как копировать всю информацию с этого сайта не имеет смысла.
Синтаксис регулярных выражений RegExpr

Предположим (да так оно и есть), что программа работает по нажатию на кнопку.
Теперь прописываем в разделе описания переменных для Button1Click:
r:Tregexpr;
Теперь создаем наш объект (после begin естессно):
R:=TRegExpr.Create;
Далее кидаем на форму объект RichEdit. Чем обусловлен выбор именно его, а не, например, Memo, я объясню чуть позже. Организуем выгрузку из него в строковую переменную txt, но после каждой строки будем добавлять символ #13.
for xx:=0 to richedit1.Lines.Count do
txt:=txt+richedit1.Lines[xx]+#13;

Создание регулярного выражения, в соответствии с его синтаксисом осуществляется при помощи выражения
r.Expression:='(МАСКА)';

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

 r.Expression:='([a-zA-Z_]+[a-zA-Z0-9_]*)'; //задается маска
      if r.exec(txt) then              //если такой элемент найден, то
      repeat
       begin
         ma:=r.Match[1];          //сюда записывается найденый токен
         for i:=1 to length(KWRD)-1 do
           begin
             s:=KWRD[i].token;
             if s=ma then      //если такой токен найден в массиве ключевых слов, то
               begin
                 inc(j);
                 setlength(it,j+1); 
                 it[j].token:=s;         //записать в итоговый массив сам токен
                 it[j].cl:='Keywords';   // записать в итоговый массив класс токена
                 it[j].spec:=KWRD[i].spec;  //записать описание
                 it[j].ps:=r.MatchPos[1];  //записать позицию в тексте
                 it[j].len:=r.MatchLen[1];  //записать длину
                 delete(txt, it[j].ps, it[j].len);
                 ss:='';
                 for xx:=1 to r.MatchLen[1] do
                   ss:=ss+' ';                                      //здесь произвелась замена этого токена на пробелы, 
                 insert(ss,txt,r.MatchPos[1]);         // что бы не потерять позицию при поиске следующих регулярных выражений
                 break;
               end else                                                   //если такой токен не найден в массиве, то
                if i=length(KWRD)-1 then
                  begin
                   inc(j);
                   setlength(it,j+1);                   //тут опять все записываем
                   it[j].token:=ma;
                   it[j].cl:='Identificator';
                   it[j].spec:='-//-';                        //ну а какое описание у идентификатора может быть?!
                   it[j].ps:=r.MatchPos[1];
                   it[j].len:=r.MatchLen[1];
                   delete(txt, it[j].ps, it[j].len);
                   ss:='';
                   for xx:=1 to r.MatchLen[1] do
                     ss:=ss+' ';
                   insert(ss,txt,r.MatchPos[1]);
                   break;
                 end;
            end;
         end;
      until not r.ExecNext;                            // до тех пор. пока не проверит все найденные токены

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

aa:=0;
      r.Expression:='(//)'; //находит двойной слеш
    while aa=0 do
    begin
    aa:=1;
    qqq:=0;
    if r.exec(txt) then
      repeat
         if qqq=1 then
            break;
        for ps:=r.MatchPos[1]+2 to length(txt) do
          begin
            if txt[ps]=#13 then                             //находит конец строки (помните мы добавляли? )
              begin
                ln:=(ps)-r.MatchPos[1];
                delete(txt,r.MatchPos[1],ln+1);
                ss:='';
                 for xx:=1 to ln+1 do
                   ss:=ss+' ';                                           
                 insert(ss,txt,r.MatchPos[1]);             //заменяет на пробелы
                 aa:=0;
                 qqq:=1;
                 break;
              end;
          end;
      until not r.ExecNext;
    end;

PROFIT.
Ниже привожу ПОРЯДОК нахождения токенов в программе и комментарии.

1) Находим комментарии вида /* */
2) Находим комментарии вида //
3) Находим символьные литералы вида 'С', 't', 'n' (что бы в Delphi заэкранировать апостроф надо поставить их два )
4) Находим строковые литералы вида «Строковый литерал»
5) Находим вещественные числа с экспонентой (несколько выражений)
6) Находим вещественные числа с точкой ( r.Expression:='([1-9]*[.][0-9]+[fFdD]?|[0-9]+[.][1-9]*[fFdD]?)'; );
7) Находим шестнадцатеричные числа вида 0x3AF04B ( r.Expression:='(0[xX][0-9|a-f|A-F]+[l|L]?)'; )
8) Находим двоичные числа вида 0b01001010 ( r.Expression:='([0][b][01]+)'; )
9) Находим восьмеричные числа вида 038423 ( r.Expression:='([0][0-9]+[l|L]?)'; )
10) Находим десятичные числа ( r.Expression:='([0-9]+[L|l]*)'; )
11) Находим ключевые слова и идентификаторы
12) Находим операторы (выражение длинное, но составить легко. Прост скопируйте все операторы из файла и экранируйте некоторые символы с помощью значка обратного слеша )
13) Находим сепараторы ( r.Expression:='([(){}[];.,])'; )

Ну вот и самое сложное позади. Едем дальше.

Этап 3. Сортируем массив по значению позиции

Сортировок массивов в интернете полно, так что я просто приведу код наиболее простого и эффективного способа.

 repeat
        bool:=false;
        for i:=0 to j-1 do
        begin
          if it[i].ps>it[i+1].ps then
            begin
              temp:=it[i];  //temp - переменная записи 
              it[i]:=it[i+1];
              it[i+1]:=temp;
              bool:=true;
            end;
        end;
      until not(bool);
Этап 4. Заполняем таблицу

Заполняем мы компонент StringGrid. Думаю сложностей с ним не возникнет, но код, на всякий случай, приведу.

  stringgrid1.RowCount:=j+1;
    stringgrid1.cells[0,0]:='Токен';
    stringgrid1.cells[1,0]:='Класс';
    stringgrid1.cells[2,0]:='Описание';
    stringgrid1.cells[3,0]:='Позиция';
    stringgrid1.cells[4,0]:='Длина';
    for m:=1 to length(it)-1 do
      begin
        stringgrid1.cells[0,m]:=it[m].token;
        stringgrid1.cells[1,m]:=it[m].cl;
        stringgrid1.cells[2,m]:=it[m].spec;
        stringgrid1.cells[3,m]:=inttostr(it[m].ps);
        stringgrid1.cells[4,m]:=inttostr(it[m].len);
      end;
Заключение

Что бы программа имела совсем вылизанный вид, Вам потребуется вывести в отдельное поле ошибки, связанные с незакрытыми комментариями или литералами, а так же сделать обработку ситуаций, когда в литерале будут знаки комментариев.
В качестве бонуса привожу код, который позволит Вам, щелкая по токену в таблице, выделять его в RichEdit (для чего, собственно, он нам и был нужен ).

procedure TForm1.StringGrid1SelectCell(Sender: TObject; ACol, ARow: Integer;  var CanSelect: Boolean);
  var ps,ln,k:integer;
begin
  ps:=strtoint(stringgrid1.Cells[3,Arow]);
  ln:=strtoint(stringgrid1.Cells[4,Arow]);
  richedit1.SelStart:=ps-1;
  richedit1.SelLength:=ln;
  richedit1.SetFocus;
end;

Внешний вид программы:
Лексический анализатор языка Java, созданный в среде Delphi

Удачной работы и спасибо за внимание!

Автор: WizAlx

Источник

Поделиться

* - обязательные к заполнению поля