Создание лексического анализатора с помощью программы GPLex

Материал из Вики ИТ мехмата ЮФУ
Версия от 09:30, 9 октября 2015; Admin (обсуждение | вклад) (→‎Обязательные задания (4 балла))

Перейти к: навигация, поиск

К основной странице курса

Разработка лексических анализаторов с помощью программы GPLex

GPLex - программа для автоматической генерации сканеров (лексических анализаторов)

Комплект для практического занятия скачиваем отсюда. Состав:

  • LexProjects.sln - файл решения, содержащее проект Lex1.csproj
  • Lex1.csproj - файл демонстрационного проекта для GPLex
  • gplex.exe - исполняемый файл генератора сканеров
  • mymain.cs - основная программа, содержащая создание сканера и сканирование всех лексем в файле
  • ShiftReduceParserCode.cs - файл проекта, необходимый для работы лексического анализатора
  • SimpleLex.lex - файл, содержащий правила для генерации лексического анализатора
  • generateScanner.bat - командный файл. Содержит одну команду: gplex.exe /noparser SimpleLex.lex
  • SimpleLex.cs - файл проекта, автоматически создаваемый при запуске generateScanner.bat
  • a.txt - файл программы, подаваемой на вход сгенерированному лексеру

Компиляция проекта и выполнение программы

  • Выполняем команду gplex.exe /noparser SimpleLex.lex, запустив командный файл generateScanner.bat
При этом генерируется файл SimpleLex.cs, содержащий код лексера. Ключ /noparser означает, что генерируется лексер без парсера.
  • Открываем и компилируем .sln
  • Меняем содержимое a.txt, запускаем проект и анализируем результаты

Файл ScannerHelper.cs

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

Лексема EOF должна идти первой и быть связанной с константой 0.

Группы лексем

  • EOF
  • Литеральные константы: ID, INUM, RNUM
  • Разделители, знаки операций: COLON, SEMICOLON, ASSIGN
  • Ключевые слова: BEGIN, END, CYCLE
namespace ScannerHelper
{
    public enum Tok { EOF = 0, ID, INUM, RNUM, COLON, SEMICOLON, ASSIGN, BEGIN, END, CYCLE };
}

Lex-файл SimpleLang.lex

Формат .lex-файла

Определения
%%
Правила
%%
Пользовательский код

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

Пользовательский код может находиться в секции определений, для этого его надо заключить в 

%{

%}

Код SimpleLang.lex

%using ScannerHelper;
%namespace SimpleScanner

Alpha 	[a-zA-Z_]
Digit   [0-9] 
AlphaDigit {Alpha}|{Digit}
INTNUM  {Digit}+
REALNUM {INTNUM}\.{INTNUM}
ID {Alpha}{AlphaDigit}* 

// Здесь можно делать описания типов, переменных и методов - они попадают в класс Scanner
%{
  public int LexValueInt;
  public double LexValueDouble;
%}

%%
{INTNUM} { 
  LexValueInt = int.Parse(yytext);
  return (int)Tok.INUM;
}

{REALNUM} { 
  LexValueDouble = double.Parse(yytext);
  return (int)Tok.RNUM;
}

begin { 
  return (int)Tok.BEGIN;
}

end { 
  return (int)Tok.END;
}

cycle { 
  return (int)Tok.CYCLE;
}

{ID}  { 
  return (int)Tok.ID;
}

":" { 
  return (int)Tok.COLON;
}

":=" { 
  return (int)Tok.ASSIGN;
}

";" { 
  return (int)Tok.SEMICOLON;
}

[^ \r\n] {
  LexError();
  return (int)Tok.EOF; // конец разбора
}

%%

// Здесь можно делать описания переменных и методов - они тоже попадают в класс Scanner
public void LexError()
{
  Console.WriteLine("({0},{1}): Неизвестный символ {2}", yyline, yycol, yytext);
}

public string TokToString(Tok tok)
{
  switch (tok)
  {
    case Tok.ID:
      return tok + " " + yytext;
    case Tok.INUM:
      return tok + " " + LexValueInt;
    case Tok.RNUM:
      return tok + " " + LexValueDouble;
    default:
      return tok + "";
  }
}

Комментарии к SimpleLex.lex

Секция описаний содержит строки 

%using ScannerHelper;
%namespace SimpleScanner

которые после преобразования в SimpleLex.cs перейдут в строки 

using ScannerHelper;

namespace SimpleScanner
{
  // остальной генерируемый код
}

Строки 

Alpha 	[a-zA-Z_]
Digit   [0-9] 
AlphaDigit {Alpha}|{Digit}
INTNUM  {Digit}+
REALNUM {INTNUM}\.{INTNUM}
ID {Alpha}{AlphaDigit}*

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

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

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

int yylex()

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

  • в случае лексемы целой константы в LexValueInt будем возвращать целое, соответствующее текущей лексеме,
  • в случае лексемы вещественной константы в LexValueDouble будем возвращать вещественное, соответствующее текущей лексеме

Переменная 

yytext

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

Метод 

public string TokToString(Tok tok)

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

Отдельно рассмотрим правило: 

[^ \r\n] {
  LexError();
  return (int)Tok.EOF;
}

Запись [^ \r\n] означает любые символы кроме пробела и символов перехода на новую строку. Если таковые встретятся и они не входят в другое правило (описанное выше), то это - лексическая ошибка "Неизвестный символ".

Регулярные выражения, используемые в секции определений

. один символ кроме '\n'
* ноль или более повторений
+ одно или более повторений
 ? ноль или одно повторение
[] класс символов, обозначающий любой символ внутри []
^ при использовании внутри [] обозначает отрицание. При использовании вне [] обозначает, что шаблон начинается с начала строки
\ начало esc-последовательности (например, \n)

Внутри [] можно использовать: - для задания диапазона, например [0-9] ^ в начале для задания отрицания, например [^"\n] (не кавычки и не символ перехода на новую строку)

Примеры регулярных выражений

[0-9]
[0-9]+
[0-9]*\.[0-9]+    \. здесь обозначает точку, т.к. просто . имеет другое значение
[+-]?[0-9]+
#.* комментарий, начинающийся с #, после которого идет ноль или более символов до конца строки
\"[^"\n]*["\n] кавычка, после которой идет любое количество не кавычек и не символов перехода на новую строку, после которых идет кавычка или переход на новую строку - так может задаваться литеральная строка. Здесь вне [] кавычка предваряется \, поскольку символ " имеет самостоятельный смысл; в [] кавычку можно писать без \, поскольку внутри [] кавычка не имеет самостоятельного смысла
[^ \n\t]+ любой символ, не являющийся пробелом, переходом на новую строчку, табулостопом, повторяющийся 1 или более раз
^[ \t]*\n строка из whitespace - пробелы или знаки табуляции, начинающиеся с начала строки и повторенные ноль или более раз, после которых идет символ перехода на новую строку

Класс Scanner

Класс Scanner создается в файле SimpleLex.cs, который генерируется по SimpleLex.lex-файлу

  • Основной метод - int yylex() - возвращает код следующей лексемы (токена)
  • Свойства:
string yytext - текст лексемы
int yyline - номер строки лексемы
int yycol - номер столбца лексемы
int yyleng - длина лексемы

Основная программа

using System;
using System.IO;
using SimpleScanner;
using ScannerHelper;

namespace Main
{
    class mymain
    {
        static void Main(string[] args)
        {
            // Чтобы вещественные числа распознавались и отображались в формате 3.14 (а не 3,14 как в русской Culture)
            System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US");

            var fname = @"..\..\a.txt";
            Console.WriteLine(File.ReadAllText(fname));

            Scanner scanner = new Scanner(new FileStream(fname, FileMode.Open));

            int tok = 0;
            do {
                tok = scanner.yylex();
                if (tok == (int)Tok.EOF)
                    break;
                Console.WriteLine(scanner.TokToString((Tok)tok));
            } while (true);

            Console.ReadKey();
        }
    }
}

Комментарии к программе

Лексический анализатор (сканер) содержит главный метод - yylex() - который возвращает следующую лексему, точнее, ее тип, приведенный к целому типу.

В основной программе мы в цикле вызываем метод scanner.yylex() пока не будет достигнут конец потока и выводим на экран содержимое текущего токена (лексемы)

Обязательные задания (5 баллов)

  1. Откомпилировать лексический анализатор и запустить его для правильной программы и нескольких неправильных программ
  2. Подсчитать количество, среднюю, минимальную и максимальную длину всех идентификаторов
  3. Найти сумму всех целых и сумму всех вещественных в файле

Дополнительные задания (4 балла)

1. Реализовать однострочный комментарий // (1 балл)

Однострочный комментарий можно создать так: 

DotChr [^\r\n]
OneLineCmnt  \/\/{DotChr}*

\/ означает символ /, он так пишется, поскольку значок /, написанный без \, имеет другой смысл

2. Реализовать лексему Строка в апострофах (1 балл) 

\'[^']*\'

означает "строка, заключенная в одинарные апострофы" 

[^']

означает "последовательность символов, не включающая '"

3. Реализовать многострочный комментарий { } (1 балл). Откомпилировав программу с комментарием, убедиться, что всё его содержимое пропускается.

Для реализации многострочного комментария необходимо использовать состояния лексического анализатора.

При работе лексер может переходить из состояния в состояние командой BEGIN(ИмяСостояния);

Для возврата в первоначальное состояние следует вызвать BEGIN(INITIAL);

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

Для реализации многострочного комментария:

В первой секции (до первого %%) следует задать новое состояние: 

%x COMMENT

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

"{" { 
  // переход в состояние COMMENT
  BEGIN(COMMENT);
}

<COMMENT> "}" { 
  // переход в состояние INITIAL
  BEGIN(INITIAL);
}

4. Используя состояния лексического анализатора, накопить в списке и выдать все идентификаторы, встречающиеся внутри многострочного комментария (1 балл)

Подсказка: используйте 

<COMMENT>{ID} {
  // обрабатывается ID внутри комментария
}
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Создание_лексического_анализатора_с_помощью_программы_GPLex&oldid=6092»