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

__NOTOC__
[[Страница_курса_"Методы_построения_компиляторов"| К основной странице курса]]

===Разработка лексических анализаторов с помощью программы GPLex===
GPLex - программа для автоматической генерации сканеров (лексических анализаторов)

Комплект для практического занятия [http://pascalabc.net/downloads/CompilerConstruction/GPLexProject.zip скачиваем отсюда]. Состав:
*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
<source lang="Csharp">
namespace ScannerHelper
{
    public enum Tok { EOF = 0, ID, INUM, RNUM, COLON, SEMICOLON, ASSIGN, BEGIN, END, CYCLE };
}</source>

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

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

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

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

<source lang="Csharp">%{

%}</source>

====Код SimpleLang.lex====
<source lang="csharp">%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 + "";
  }
}</source>

====Комментарии к SimpleLex.lex====
Секция описаний содержит строки

<source lang="Csharp">%using ScannerHelper;
%namespace SimpleScanner
</source>

которые после преобразования в SimpleLex.cs перейдут в строки 
<source lang="Csharp">
using ScannerHelper;

namespace SimpleScanner
{
  // остальной генерируемый код
}
</source>
Строки
<source lang="Csharp">Alpha 	[a-zA-Z_]
Digit   [0-9] 
AlphaDigit {Alpha}|{Digit}
INTNUM  {Digit}+
REALNUM {INTNUM}\.{INTNUM}
ID {Alpha}{AlphaDigit}*</source> 
в секции описаний определяют так называемые '''классы символов''', которыми можно пользоваться при определении других классов символов и в секции правил.

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

В семантических действиях в основном мы возвращаем целое значение для функции
<source lang="Csharp">int yylex()
</source>
и, возможно, выполняем другие действия. В качестве целого значения будем возвращать тип лексемы Tok, приведенный к целому типу.
Дополнительные семантические действия проделаем в следующих случаях: 
* в случае лексемы целой константы в LexValueInt будем возвращать целое, соответствующее текущей лексеме, 
* в случае лексемы вещественной константы в LexValueDouble будем возвращать вещественное, соответствующее текущей лексеме

Переменная

<source lang="Csharp">yytext</source>
используемая в коде, является стандартным полем класса Scanner и представляет собой текстовое представление текущей лексемы.

Метод

<source lang="Csharp">public string TokToString(Tok tok)</source>

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

Отдельно рассмотрим правило: 
<source lang="Csharp">
[^ \r\n] {
  LexError();
  return (int)Tok.EOF;
}</source>
Запись [^ \r\n] означает любые символы кроме пробела и символов перехода на новую строку. Если таковые встретятся и они не входят в другое правило (описанное выше), то это - лексическая ошибка "Неизвестный символ".

==== Регулярные выражения, используемые в секции определений====
{| style="background:#DDDDDD"
 |- 
 | style="width:25px" | .
 | один символ кроме '\n'
 |-
 | *
 | ноль или более повторений
 |-
 | +
 | одно или более повторений
 |-
 | ?
 | ноль или одно повторение
 |-
 | []
 | класс символов, обозначающий любой символ внутри []
 |-
 | ^
 | при использовании внутри [] обозначает отрицание. При использовании вне [] обозначает, что шаблон начинается с начала строки
 |-
 | \
 | начало esc-последовательности (например, \n)
 |}

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

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

{|- 
 | style="width:50px"| <tt>[0-9]</tt>
 | 
 |-
 | <tt>[0-9]+</tt>
 | 
 |-
 | <tt>[0-9]*\.[0-9]+ &nbsp;&nbsp;</tt>
 | \. здесь обозначает точку, т.к. просто . имеет другое значение
 |-
 | <tt>[+-]?[0-9]+</tt>
 | 
 |-
 | <tt>#.*</tt>
 | комментарий, начинающийся с #, после которого идет ноль или более символов до конца строки
 |-
 | <tt>\"[^"\n]*["\n]</tt>
 | кавычка, после которой идет любое количество не кавычек и не символов перехода на новую строку, после которых идет кавычка или переход на новую строку - так может задаваться литеральная строка. Здесь вне [] кавычка предваряется \, поскольку символ " имеет самостоятельный смысл; в [] кавычку можно писать без \, поскольку внутри [] кавычка не имеет самостоятельного смысла
 |-
 | <tt>[^ \n\t]+</tt>
 | любой символ, не являющийся пробелом, переходом на новую строчку, табулостопом, повторяющийся 1 или более раз
 |-
 | <tt>^[ \t]*\n</tt>
 | строка из whitespace - пробелы или знаки табуляции, начинающиеся с начала строки и повторенные ноль или более раз, после которых идет символ перехода на новую строку
 |}

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

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

=== Основная программа===
<source lang="Csharp">
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();
        }
    }
}</source>

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

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

===Обязательные задания (5 баллов)===
#Откомпилировать лексический анализатор и запустить его для правильной программы и нескольких неправильных программ
#Подсчитать количество, среднюю, минимальную и максимальную длину всех идентификаторов
#Найти сумму всех целых и сумму всех вещественных в файле

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

Однострочный комментарий можно создать так:
<source lang="csharp">DotChr [^\r\n]
OneLineCmnt  \/\/{DotChr}*
</source>
\/ означает символ /, он так пишется, поскольку значок /, написанный без \, имеет другой смысл

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

<source lang="csharp">\'[^']*\'</source> 
означает "строка, заключенная в одинарные апострофы"

<source lang="csharp">[^']</source> 
означает "последовательность символов, не включающая '"

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

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

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

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

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

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

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

<source lang="csharp">%x COMMENT</source>

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

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

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

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

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

<source lang="csharp">
<COMMENT>{ID} {
  // обрабатывается ID внутри комментария
}</source>