Занятие 3 по курсу МПК — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Обязательные задания)
 
(не показано 75 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
__NOTOC__
 
__NOTOC__
[[http://it.mmcs.sfedu.ru/wiki/%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0_%D0%BA%D1%83%D1%80%D1%81%D0%B0_%22%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%22 К странице курса]]
+
[[Страница_курса_"Методы_построения_компиляторов"| К основной странице курса]]
  
*GPLex - генератор сканеров (лексических анализаторов)
+
===Разработка лексических анализаторов с помощью программы GPLex===
*GPPG - генератор парсеров (синтаксических анализаторов)
+
GPLex - программа для автоматической генерации сканеров (лексических анализаторов)
  
===Комплект GPLex+GPPG для разработки парсеров и сканеров===
+
Комплект для практического занятия [http://pascalabc.net/downloads/CompilerConstruction/GPLexProject.zip скачиваем отсюда]. Состав:
Комплект для практического занятия [http://pascalabc.net/downloads/CompilerConstruction/GPPG_Pack.zip скачиваем отсюда]. Состав:
 
 
*LexProjects.sln - файл решения, содержащее проект Lex1.csproj
 
*LexProjects.sln - файл решения, содержащее проект Lex1.csproj
 
*Lex1.csproj - файл демонстрационного проекта для GPLex
 
*Lex1.csproj - файл демонстрационного проекта для GPLex
 
*gplex.exe - исполняемый файл генератора сканеров
 
*gplex.exe - исполняемый файл генератора сканеров
*gppg.exe - исполняемый файл генератора парсеров (он нам понадобится на следующем занятии)
 
*ShiftReduceParser.dll - внешняя сборка, необходимая для работы сгенерированного компилятора
 
*gplexx.frame - файл, включаемый в генерируемый файл лексического анализатора
 
 
*mymain.cs - основная программа, содержащая создание сканера и сканирование всех лексем в файле
 
*mymain.cs - основная программа, содержащая создание сканера и сканирование всех лексем в файле
*my.lex - файл, содержащий правила для генерации лексического анализатора
+
*ShiftReduceParserCode.cs - файл проекта, необходимый для работы лексического анализатора
 +
*'''SimpleLex.lex''' - файл, содержащий правила для генерации лексического анализатора
 +
*generateScanner.bat - командный файл. Содержит одну команду: gplex.exe /noparser SimpleLex.lex
 +
*SimpleLex.cs - файл проекта, автоматически создаваемый при запуске generateScanner.bat
 
*a.txt - файл программы, подаваемой на вход сгенерированному лексеру
 
*a.txt - файл программы, подаваемой на вход сгенерированному лексеру
  
===Компиляция проекта===
+
===Компиляция проекта и выполнение программы===
*Выполняем команду gplex.exe /noparser my.lex
+
*Выполняем команду gplex.exe /noparser SimpleLex.lex, запустив командный файл generateScanner.bat
:При этом генерируется файл my.cs, содержащий код лексера. Ключ /noparser означает, что генерируется лексер без парсера.
+
:При этом генерируется файл SimpleLex.cs, содержащий код лексера. Ключ /noparser означает, что генерируется лексер без парсера.
 
*Открываем и компилируем .sln
 
*Открываем и компилируем .sln
 +
*Меняем содержимое a.txt, запускаем проект и анализируем результаты
  
===Формат .lex-файла===
+
===Файл ScannerHelper.cs ===
  
Определения
+
Вспомогательный файл для сканера. Содержит глобальные определения.
%%
+
В данном случае ScannerHelper.cs содержит перечислимый тип Tok, содержащий виды лексем, возвращаемых нашим сканером.
Правила
+
 
%%
+
Лексема EOF должна идти первой и быть связанной с константой 0.
Пользовательский код
 
  
Пользовательский код содержит описания полей и методов, включаемых в генерируемый класс Scanner.
+
====Группы лексем====
 +
* 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-файл имеет вид:
+
===Lex-файл SimpleLang.lex ===
  
<source lang="csharp">%namespace LexScanner
+
<source lang="csharp">%using ScannerHelper;
 +
%namespace SimpleScanner
  
Alpha [a-zA-Z]
+
Alpha [a-zA-Z_]
INTNUM  [0-9]+
+
Digit  [0-9]  
 +
AlphaDigit {Alpha}|{Digit}
 +
INTNUM  {Digit}+
 
REALNUM {INTNUM}\.{INTNUM}
 
REALNUM {INTNUM}\.{INTNUM}
ID {Alpha}+
+
ID {Alpha}{AlphaDigit}*
 +
 
 +
// Здесь можно делать описания типов, переменных и методов - они попадают в класс Scanner
 +
%{
 +
  public int LexValueInt;
 +
  public double LexValueDouble;
 +
%}
  
 
%%
 
%%
 
 
{INTNUM} {  
 
{INTNUM} {  
   Console.WriteLine("IntNum "+yytext);
+
   LexValueInt = int.Parse(yytext);
 +
  return (int)Tok.INUM;
 
}
 
}
  
 
{REALNUM} {  
 
{REALNUM} {  
   Console.WriteLine("RealNum   "+yytext);
+
   LexValueDouble = double.Parse(yytext);
 +
   return (int)Tok.RNUM;
 
}
 
}
  
 
begin {  
 
begin {  
   Console.WriteLine("Key: begin");  
+
   return (int)Tok.BEGIN;
 
}
 
}
  
 
end {  
 
end {  
   Console.WriteLine("Key: end");
+
   return (int)Tok.END;
 +
}
 +
 
 +
cycle {
 +
  return (int)Tok.CYCLE;
 
}
 
}
  
 
{ID}  {  
 
{ID}  {  
   Console.WriteLine("ID "+yytext);
+
   return (int)Tok.ID;
 +
}
 +
 
 +
":" {
 +
  return (int)Tok.COLON;
 +
}
 +
 
 +
":=" {
 +
  return (int)Tok.ASSIGN;
 +
}
 +
 
 +
";" {
 +
  return (int)Tok.SEMICOLON;
 
}
 
}
  
 
%%
 
%%
  
// Здесь можно делать описания переменных и методов - они попадают в класс Scanner
+
// Здесь можно делать описания переменных и методов - они тоже попадают в класс Scanner
 
public int Sum = 0;</source>
 
public int Sum = 0;</source>
 +
 +
====Формат .lex-файла====
 +
 +
Определения
 +
%%
 +
Правила
 +
%%
 +
Пользовательский код
 +
 +
Пользовательский код содержит описания полей и методов, включаемых в генерируемый класс Scanner.
 +
 +
Пользовательский код может находиться в секции определений, для этого его надо заключить в
 +
 +
<source lang="Csharp">%{
 +
 +
%}</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 и представляет собой текстовое представление текущей лексемы.
 +
 +
==== Регулярные выражения, используемые в секции определений====
 +
{| 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===
* Основной метод - int yylex() - возвращает номер следующей лексемы (токена)
+
Класс Scanner создается в файле SimpleLex.cs, который генерируется по SimpleLex.lex-файлу
* Свойства
+
 
 +
* Основной метод - int yylex() - возвращает код следующей лексемы (токена)
 +
* Свойства:
 
  string yytext - текст лексемы
 
  string yytext - текст лексемы
 
  int yyline - номер строки лексемы
 
  int yyline - номер строки лексемы
Строка 76: Строка 225:
 
  int yyleng - длина лексемы
 
  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();
 +
 
 +
                Console.Write((Tok)tok + " ");
 +
 
 +
                if ((Tok)tok == Tok.INUM)
 +
                    Console.WriteLine(scanner.LexValueInt);
 +
                else if ((Tok)tok == Tok.RNUM)
 +
                    Console.WriteLine(scanner.LexValueDouble);
 +
                else if ((Tok)tok == Tok.ID)
 +
                    Console.WriteLine(scanner.yytext);
 +
                else Console.WriteLine();
 +
 
 +
            } while (tok != (int)Tok.EOF);
 +
 
 +
            Console.ReadKey();
 +
        }
 +
    }
 +
}</source>
 +
 
 +
==== Комментарии к программе ====
 +
Лексический анализатор (сканер) содержит главный метод - yylex() - который возвращает следующую лексему, точнее, ее тип, приведенный к целому типу.
 +
 
 +
В основной программе мы в цикле вызываем метод scanner.yylex() пока не будет достигнут конец потока
 +
 
 +
===Обязательные задания===
 
#Откомпилировать лексический анализатор и запустить его для файла a.txt
 
#Откомпилировать лексический анализатор и запустить его для файла a.txt
#Сделать имя файла, обрабатываемого лексическим анализатором, параметром командной строки
 
 
#Подсчитать количество, среднюю, минимальную и максимальную длину всех идентификаторов
 
#Подсчитать количество, среднюю, минимальную и максимальную длину всех идентификаторов
 
#Найти сумму всех целых и сумму всех вещественных в файле
 
#Найти сумму всех целых и сумму всех вещественных в файле
 +
 +
===Дополнительные задания===
 
#Дана программа, в которой встречаются ключевые слова begin end. Определить, правильно ли они расставлены
 
#Дана программа, в которой встречаются ключевые слова begin end. Определить, правильно ли они расставлены
 
#По данному тексту слов составить таблицу
 
#По данному тексту слов составить таблицу
 
  слово  список его вхождений в текст в формате (строка,столбец), (строка,столбец)
 
  слово  список его вхождений в текст в формате (строка,столбец), (строка,столбец)

Текущая версия на 13:09, 16 августа 2014

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

Разработка лексических анализаторов с помощью программы 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

%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;
}

%%

// Здесь можно делать описания переменных и методов - они тоже попадают в класс Scanner
public int Sum = 0;

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

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

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

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

%{

%}

Комментарии к 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 и представляет собой текстовое представление текущей лексемы.

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

. один символ кроме '\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();

                Console.Write((Tok)tok + " ");

                if ((Tok)tok == Tok.INUM)
                    Console.WriteLine(scanner.LexValueInt);
                else if ((Tok)tok == Tok.RNUM)
                    Console.WriteLine(scanner.LexValueDouble);
                else if ((Tok)tok == Tok.ID)
                    Console.WriteLine(scanner.yytext);
                else Console.WriteLine();

            } while (tok != (int)Tok.EOF);

            Console.ReadKey();
        }
    }
}

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

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

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

Обязательные задания

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

Дополнительные задания

  1. Дана программа, в которой встречаются ключевые слова begin end. Определить, правильно ли они расставлены
  2. По данному тексту слов составить таблицу
слово   список его вхождений в текст в формате (строка,столбец), (строка,столбец)