Diploma_All

2.4.5 Синтаксический анализ

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

Грамматика входного файла GPPG основана на языке YACC:

Объявления

%%

Правила трансляции

%%

С#-подпрограммы поддержки

Объявления. В GPPG-программе в разделе объявлений размещаются обычные объявления С#, ограниченные %{ и %}. Код, помещенный между этими скобками будет включен в класс Parser. Директива %using в разделе объявлений включает в код парсера объявление используемого пространства имен. Также в этом разделе указываются токены (%token), семантический тип данных (%valuetype) а также другие объявление, такие как стартовые символы (%start).

Правила трансляции. В этой части спецификации GPPG после первой пары %% размещаются правила трансляции. Каждое правило состоит из продукции грамматики и связанных семантических действий. Множество продукций, в GPPG записываются следующим образом:

<Левая часть> : <Alt 1> { Семантическое действие 1 } | <Alt 2> { Семантическое действие 2 }

. . .

| <Alt n> { Семантическое действие n }

В продукциях GPPG отдельный символ в одинарных кавычках 'с' представляет терминальный символ с, а строка из букв и цифр, не взятая в кавычки и не объявленная как токен, считается нетерминалом. Альтернативные правые части продукций разделяются вертикальной чертой, а за каждой продукцией с ее альтернативами и семантическими действиями ставится точка с запятой. Первая левая часть считается стартовым символом.

Семантические действия GPPG представляют собой последовательности инструкций С#. В них могут использоваться специальные символы: $$ представ-

ляет значение атрибута, связанного с нетерминалом в левой части, а $i — значе-

ние, связанное с i-м грамматическим символом (терминалом или нетерминалом)

41

справа. Семантическое действие выполняется при свертке связанной с ним продукции, так что обычно семантическое действие вычисляет $$ по $i.

Раздел подпрограмм поддержки. Здесь описываются вспомогательные классы и методы. Если GPPG используется как самостоятельная программа (без участия GPLEX), то обязательно определение функции Main() и специального ме-

тода yylex(). Другие функции, такие как подпрограммы обработки ошибок, могут быть добавлены при необходимости.

Ниже приводится текст входного файла GPPG netlist_parser.y, определяющий правила трансляции файла в формате SPICE, содержащего объявления МОП-транзисторов:

%{

private List<SpiceElement> _elements = new List<SpiceElement>();

public SpiceElement[] SpiceElements

{

get { return _elements.ToArray(); }

}

%}

%using NetListAnalyzer %valuetype string

%start list

%token NAME M_NODES MODEL_NAME PARAMS

42

element.ModelName = modelName.TrimStart(); element.Pins = nodes.TrimStart().Split(' '); element.Params = parameters.TrimStart().

Split(' ');

_elements.Add(element);

}

;

%%

В разделе объявлений объявляется список для хранения найденных SPICEэлементов, команда включить использование пространства имен NetListAnalyzer, в котором содержится определение класса SpiceElement, а также указание использовать в качестве семантического типа строку. Помимо этого объявляются токены NAME M_NODES MODEL_NAME PARAMS, которые используются

GPLEX ({name} yylval = yytext; return (int)Tokens.NAME;), и

стартовый символ.

В правилах трансляции указывается, что когда встречается конструкция, характерная для объявления МОП-транзистора, нужно создать новый объект типа

SpiceElement, с именем NAME, узами M_NODES, моделью MODEL_NAME и

парметрами PARAMS (символ $1 отвечает за атрибут токена NAME, $2 за атрибут токена M_NODES и т.д.) и поместить его в список найденных элементов.

Запустив GPPG командой

gppg.exe /gplex netlist_parser.y > Parser.cs,

где Parser.cs — имя файла, куда записывается сгенерированный код, а netlist_parser.y – имя файла с грамматикой языка SPICE на языке YACC, получим набор классов, позволяющих осуществить синтаксический анализ входного файла.

Далее необходимо указать классу Parser класс Scanner, используемый для анализа входного потока данных и возвращающего найденные токены. Для этого включим оба сгенерированных файла в проект (папка Parser) и создадим метод для анализа входного файла:

public SpiceElement[] ParseFile(string fileName)

{

Parser parser = new Parser();

MemoryStream mStream = PrepareFile(fileName);

43

parser.scanner = new Scanner(mStream); parser.Trace = true;

parser.Parse();

mStream.Close();

return parser.SpiceElements;

}

Метод PrepareFile(fileName) открывает файл для анализа на чтение и удаляет из текста двойные пробелы и убирает из текста переносы строк, характерные для SPICE (с использованием символа «+»). Метод возвращает подготовленный таким образом текст в виде потока в памяти, пригодного для дальнейшего синтаксического анализа классом Parser.

Далее, найденные элементы уже в виде объектов передаются методу построения иерархии.

44

2 . 5 З а к л ю ч е н и е

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

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

Разработанное приложение отвечает поставленным требованиям эффективности и переносимости, просто в поддержке и установке, имеет дружественный

кпользователю интерфейс.

45

3 Глава 3

Технологический раздел

Платформа .NET.

Генератор лексических анализаторов GPLEX. Генератор синтаксических анализаторов GPPG.

Дипломант: Транченко Д. В. Консультант: Кривсун Е. В.

46

3 . 1 Платформа . NET

Microsoft .NET — это новая платформа для разработки программного обеспечения, построенная на верхнем слое операционной системы. На развитие технологии .NET оказали влияние другие технологические достижения, в частности расширяемый язык разметки XML, платформа Java, a также модель компонент-

ных объектов Microsoft (Component Object Model — COM).

Платформа .NET предоставляет:

●устойчивую общеязыковую среду выполнения CLR (Common Language Runtime), которая входит в состав данной платформы;

●средства разработки приложений на любом из многих языков программирования, поддерживаемых платформой .NET;

●лежащую в основе открытой модели программирования огромную библиотеку классов .NET Framework, содержащую многократно используемый код;

●поддержку сетевой инфраструктуры, построенной на верхнем слое стандартов Интернет, вследствие чего обеспечивается высокий уровень взаимодействия между приложениями;

●поддержку нового промышленного стандарта, а именно технологии веб-служб, которая предоставляет новый механизм создания распределенных приложений, по сути являясь распространением технологии создания приложений на базе компонентов на сферу Интернет;

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

●мощные инструментальные средства разработки.

3.1.1 Каркас .NET Framework

Современный стиль программирования предполагает многократное использование кода, содержащегося в библиотеках. Объектно-ориентированные языки программирования облегчают создание библиотек классов. Получающиеся в результате библиотеки являются гибкими, им присущ высокий уровень абстракции. Эти библиотеки могут быть расширены путем добавления новых классов, а

47

также путем образования новых классов на основе уже существующих. При этом новые классы наследуют функциональность существующих классов.

Вкаркасе .NET Framework представлено более 2500 классов, содержащих повторно используемый код. Эти классы доступны в любом языке программирования, который поддерживается платформой. Библиотека классов .NET Framework является расширяемой. На основе уже существующих базовых классов можно создать новые производные классы, причем производные классы могут быть реализованы на совершенно другом языке программирования.

Всостав библиотеки классов .NET Framework входят классы, которые используются при разработке Windows-приложений, веб-приложений, а также приложений с базами данных. В библиотеке классов .NET Framework имеются также классы, обеспечивающие взаимодействие с языком XML, с моделью компонентных объектов Microsoft (COM) и с любой платформой, поддерживающей интерфейс 32-разрядных Windows-приложений (Win32 API).

Втаблице 3.1 представлены пространства имен платформы .NET, которые содержат основные классы, использованные при создании программного модуля,

атакже кратко описано их назначение.

48

3.1.2 Общеязыковая среда выполнения CLR (Common Language Runtime)

Среда выполнения предоставляет необходимые службы во время выполнения приложении. Традиционно каждой среде программирования соответствует своя среда выполнения. В качестве примера среды выполнения могут служить стандартная библиотека языка С, библиотека базовых классов Microsoft (MFC), среда выполнения языка Visual Basic, а также виртуальная машина Java (Java Virtual Machine). Среда выполнения платформы .NET получила название общеязыковой среды выполнения CLR.

Общеязыковая среда выполнения CLR предоставляет в распоряжение .NETкода ряд служб (включая и библиотеку классов .NET Framework, которая размещается на верхнем слое CLR). Для того чтобы воспользоваться этими службами, .NET-код должен иметь предсказуемое поведение и, к тому же, быть понятным общеязыковой среде выполнения CLR. Например, для того чтобы среда выполнения могла осуществить проверку границ массивов, все массивы в

.NET имеют идентичный формат. Требования типовой безопасности могут налагать на .NET-код и другие ограничения.

Ограничения, которые накладываются на .NET-код, определяются общей системой типов (Common Type System, CTS), а также ее реализацией в промежуточном языке IL, разработанном корпорацией Microsoft (Microsoft Intermediate Language — MSIL, или просто IL). Общей системой типов определены типы и операции, которые могут использоваться кодом, работающим в общеязыковой среде выполнения CLR. Так, именно общей системой типов (CTS) на используемые типы накладывается ограничение единичного наследования реализации. Код на промежуточном языке MSIL компилируется во внутренний (собственный) код платформы.

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

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

49

Память для управляемых данных распределяется и освобождается автоматически. Такое автоматическое освобождение занимаемой памяти называется сборкой мусора (garbage collection). Сборка мусора решает все проблемы утечки памяти и им подобные.

Общеязыковую среду выполнения CLR можно представить себе как инфра-

структуру универсального языка CLI (Common Language Infrastructure), допол-

ненную библиотеками базовых классов FCL (Framework Class Libraries). Библиотека базовых классов FCL поддерживает фундаментальные типы об-

щей системы типов CTS, а именно: ввод/вывод файлов, строки и форматирование. Поскольку общеязыковая среда выполнения CLR зависит от используемой платформы, в ней используются модели управления процессами и памятью базовой операционной системы.

3.1.3 Верифицируемый код

Управляемый код может быть проверен на предмет типовой безопасности. Код, удовлетворяющий требованиям типовой безопасности, разрушить не так легко. Например, структуры данных или другие приложения, которые находятся в памяти, не могут быть повреждены в результате перезаписи буфера. Политику безопасности можно применить к коду, удовлетворяющему требованиям типовой безопасности. Например, доступ к некоторым файлам или средствам пользовательского интерфейса может быть разрешен или запрещен. Выполнение кода, происхождение которого неизвестно, можно запретить.

Однако, не все приложения, для работы которых требуется общеязыковая среда выполнения CLR, обязаны удовлетворять требованиям типовой безопасности. В частности, такая ситуация реализуется для приложений, написанных на C++. Управляемый код, написанный на C++, может использовать возможности, предоставляемые общеязыковой средой выполнения CLR, например, сборку мусора. Но так как на C++ может быть создан и неуправляемый код, то нет никаких гарантий относительно того, что приложение, написанное на C++, будет удовлетворять требованиям типовой безопасности. В управляемом коде, написанном на C++, нельзя выполнять арифметические операции над управляемыми указателями, или приводить тип управляемого указателя к неуправляемому. Поэтому управляемый код, написанный на C++, можно проверить на безопасность.

50