close

Вход

Забыли?

вход по аккаунту

?

Maksimova teorija jazykov programmirovanija

код для вставкиСкачать
Министерство образования и науки российской федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ТЕОРИЯ ЯЗЫКОВ
ПРОГРАММИРОВАНИЯ
И МЕТОДЫ ТРАНСЛЯЦИИ
Методические указания
к выполнению курсовой работы
Санкт-Петербург
2011
Составитель Т. М. Максимова
Рецензент кандидат физико-математических наук, доцент В. А Костин
(Санкт-Петербургский государственный университет)
В методических указаниях приведены постановка задачи на курсовое проектирование, необходимые теоретические сведения и рекомендации по методике выполнения задания.
Предназначены для студентов специальностей 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» и 010503 «Математическое обеспечение и администрирование
информационных систем», изучающих дисциплину «Теория языков
программирования и методы трансляции».
Подготовлены кафедрой компьютерной математики и программирования и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского государственного университета аэрокосмического приборостроения.
Редактор А. В. Подчепаева
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 09.11.11. Подписано к печати 28.11.11. Формат 60×84 1/16.
Бумага офсетная. Усл. печ. л. 2,2. Тираж 150 экз. Заказ № 576.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2011
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
«СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ АНАЛИЗ СЕМАНТИКИ
ИДЕНТИФИКАТОРОВ В ТЕКСТАХ ПРОГРАММ»
В теоретическом и практическом разделах дисциплины «Теория
языков программирования и методы трансляции» рассматриваются различные методы решения задачи синтаксического анализа,
использующего формальные описания языков; лабораторный практикум предусматривает программирование некоторых алгоритмов
решения такой задачи. На этапе курсового проектирования, как заключительном в изучении этой дисциплины, предлагается усложнить задачу синтаксического анализа подключением к ней частичного анализа семантики. В этом усложненном варианте задача формулируется следующим образом.
Разработайте программу синтаксического и семантического анализа для подмножества языка программирования, определенного
вариантом задания. (Выбор подмножества языка согласуйте с преподавателем). Синтаксический разбор реализуйте с использованием детерминированного автомата с магазинной памятью. Семантические аспекты опишите грамматикой свойств. На семантический
анализ возложите проверку правомерности использования идентификаторов с точки зрения их описания.
Варианты исходных языков: Pascal, C, Java, Flex, Perl, Lisp, Prolog,
Matlab, Visual Basic, Shell.
3
НЕКОТОРЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
О СЕМАНТИЧЕСКОМ АНАЛИЗЕ
С ИСПОЛЬЗОВАНИЕМ ГРАММАТИКИ СВОЙСТВ
Описывающая синтаксис языка контекстно-свободная грамматика (КС-грамматика) может использоваться не только для синтаксического анализа текста, но и для управления процессом его трансляции, если снабдить ее семантическими правилами, учитывающими контекстно-зависимые свойства языка. Такое приписывание
семантических правил может быть выполнено в рамках так называемой атрибутной грамматики [1]. Атрибутной грамматикой называют КС-грамматику, символы которой связаны с атрибутами, описывающими контекстно-несвободные аспекты языка. Связывание
выполняется в контексте порождающих правил КС-грамматики.
С помощью атрибутов информация может передаваться как от символа левой части правила к символам правой части правила (такие
атрибуты называются наследуемыми), так и в обратном направлении: от символов правой части правила к символу левой части правила (такие атрибуты называются синтезируемыми). Во втором случае
способ определения синтезируемого атрибута может быть зафиксирован с помощью функции, заданной для всех правил КС-грамматики.
А именно: правилу вида A:: = X1…Xn, имеющему номер i, ставится
в соответствие функция μi(x1, …, xn), аргументами которой являются атрибуты символов X1, …, Xn правой части правила, а значением – атрибут символа A левой части правила. В литературе [2] описан один из частных видов атрибутной грамматики с синтезируемыми атрибутами, названный грамматикой свойств. Функция μ грамматики свойств задается в табличной форме.
Инструмент грамматики свойств, как и любой атрибутной грамматики, позволяет во время выполнения синтаксического разбора производить некоторые действия семантического анализа. Одним из наиболее эффектных применений этого инструмента является анализ соответствий описаний и использований символьных имен, идентификаторов. Такие соответствия, очевидно, представляют собой контекстнонесвободные свойства языка, т.е. не могут быть описаны только
средствами КС-грамматик. Для решения этой задачи с использованием грамматики свойств в процессе синтаксического разбора с каждой
вершиной дерева разбора следует связать таблицу атрибутов – свойств
идентификаторов. (Запись таблицы содержит, как минимум, два поля: поле идентификатора и поле свойства идентификатора). Если по
окончании восходящего разбора с корнем дерева (аксиомой граммати4
ки) связалась таблица, содержащая только свойства из заранее определенного множества допустимых свойств, разобранный текст можно считать семантически корректным. Вывод о семантической некорректности текста может быть сделан в двух ситуациях:
таблица свойств не может быть построена для внутренней вершины дерева разбора в силу некорректности последовательности
таблиц, связанных с непосредственными потомками этой вершины
(значение функции μ от аргументов-атрибутов символов правой части правила не определено);
таблица свойств, связанная с корнем дерева разбора, содержит
свойства, не принадлежащие множеству допустимых свойств.
Грамматика свойств [2] задается восьмеркой компонент: G(V, T,
P, S, ϑ, ϑ0, φ, μ), где (V, T, P, S) – КС-грамматика (V – множество нетерминальных символов, T – множество терминальных символов,
P – множество порождающих правил, S – аксиома); ϑ – множество
свойств; ϑ0 – нейтральное свойство (ϑ0 ∈ ϑ); φ – множество допустимых свойств (φ ⊆ ϑ); μ – функция, определяющая отображение из
P×ϑ* в ϑ (A* – множество слов, составленных из символов алфавита
A, и пустая строка).
С помощью функции μ определяется свойство, связываемое с внутренней вершиной дерева разбора, в зависимости от свойств потомков этой вершины. Значения μ(p, ℓ) задаются таблично для каждого p ∈ P. При этом длина строки ℓ свойств равна длине правой части правила p, сама строка ℓ является строкой свойств, связанных
с символами правой части этого правила; значение функции равно свойству, связываемому с нетерминалом левой части правила p,
и таблица, соответствующая правилу p, содержит только такие
строки ℓ, для которых значение μ(p, ℓ) определено.
Пусть грамматика, описывающая некоторый язык, в частности,
содержит правила:
i) <описания>::=вещественное <список имен>
ii) <список имен>::=<список имен>,идентификатор
iii) <список имен>::=идентификатор
Словом идентификатор здесь обозначен терминальный для данной грамматики символ, представляющий собой код лексемы (токен) типа «идентификатор», которая распознается на этапе лексического анализа.
Пусть, например, идентификатор в таблицах имен, связываемых
с вершинами дерева разбора, может приобретать свойства ϑ:
0) нейтральное свойство (не имеет никакого отношения к символу вершины дерева);
5
1) упоминается здесь;
2) появляется в списке имен;
3) объявляется переменной вещественного типа.
Будем теперь руководствоваться этим списком для задания
значений атрибутов: они будут определяться своими номерами
в списке. Это означает, что в виде своих номеров будут храниться свойства идентификаторов в таблицах свойств, и в виде номеров свойств будут представлены значения аргумента ℓ и значения
функции μ.
Функция μ для приведенных трех правил грамматики может
быть задана следующими тремя таблицами:
ℓ
μ(i, ℓ)
00
0
02
3
ℓ
μ(ii, ℓ)
000
0
200
2
001
2
ℓ
μ(iii, ℓ)
0
0
1
2
Длина строк ℓ в таблице для μ(i,ℓ) равна двум, поскольку правая
часть правила i состоит из двух символов. Первый из этих символов является терминалом (вещественное), с которым не может быть
связано никакое свойство, кроме нейтрального, никакого идентификатора. Этим объясняются значения 0 в первых разрядах строк ℓ
для таблицы μ(i, ℓ). Второй разряд соответствует нетерминальному
символу <список имен>, и он может иметь значения 2 или 0, в зависимости от того, был ли замечен идентификатор в списке имен.
Если был замечен (строка 02), то с нетерминалом левой части правила (<описания>) следует связать новое свойство идентификатора:
объявляется переменной вещественного типа. Это свойство имеет
номер 3, который и стал значением функции μ(i,02).
6
ÇÈÁʹÆÁØ<¸º>
º½Ñ½Éʺ½ÅÅƽ<¸º>ÊÈÁÊÇÃÁžÆ<¸º>
ÊÈÁÊÇÃÁžÆ<¸º> <BC>º<¸º>
¸<¸º>
Рис. 1. Дерево разбора с таблицами свойств
Таблицы для μ(ii, ℓ) и для μ(iii, ℓ) показывают, каким образом
идентификатор может появиться в списке имен (приобрести свойство 2). Следует особо отметить, что значение функции μ(ii, ℓ) для
строки ℓ = 201 не определено. Это означает, что идентификатору не
разрешено появляться в списке имен два и более раз.
Примером правильной строки, с точки зрения вышеприведенных правил, может быть (из соображений наглядности примера
терминалы идентификатор изобразим в виде двух разных лексемидентификаторов):
вещественное а,в
На рис. 1 приведено дерево разбора этой строки с таблицами
свойств, приписанными вершинам дерева.
Поскольку синтезируемыми атрибутами информация передается
от правой части правила к левой, ими удобно пользоваться при выполнении восходящего разбора. Алгоритм типа «сдвиг-приведение» [3]
восходящего разбора можно взять за основу синтаксически управляемой трансляции. Записи стека, с которым работает такой алгоритм,
следует дополнить полями со значениями атрибутов. Для грамматики свойств такое поле может, например, содержать ссылку на таблицу свойств. Выполнение операции приведения (замены правой части
правила, размещенной в верхней части стека, на нетерминал левой
части этого правила) должно сопровождаться вычислением значения
функции μ для этого правила и занесением вычисленного значения
в таблицу свойств в качестве атрибута нетерминала, на который заменена правая часть правила, если только это значение не оказалось
нейтральным свойством. Процессу неявного построения дерева, приведенного на рис. 1, алгоритмом «сдвиг-приведение» соответствует
следующая последовательность состояний стека (рис. 2).
Еще одним примером синтаксически правильной, с точки зрения
рассматриваемой КС-грамматики, строкой является строка веще7
ʽ»Á¼
º½Ñ½Éʺ½ÅÅƽ <>
ÊÈÁÊÇÃÁžÆ
º½Ñ½Éʺ½ÅÅƽ
º
ÊÈÁÊÇÃÁžÆ
º½Ñ½Éʺ½ÅÅƽ
ÇÈÁʹÆÁØ
ʽ»Á¼
<¸>
<>
¸
º½Ñ½Éʺ½ÅÅƽ ÈÉÁ»¾½¾ÆÁ¾
<¹>
<>ÈÇÈɹ»ÁÄÌJJJ
<>ʽ»Á¼
ÊÈÁÊÇÃÁÅ¾Æ <¸>
º½Ñ½Éʺ½ÅÅƽ <>
<º>ÈÉÁ»¾½¾ÆÁ¾
<>
<¸>ÈÇÈɹ»ÁÄÌJJ
<>
ÊÈÁÊÇÃÁžÆ
º½Ñ½Éʺ½ÅÅƽ
ÈÉÁ»¾½¾ÆÁ¾
<¸º>ÈÇÈɹ»ÁÄÌJ
<>
<¸º>
Рис. 2. Последовательность состояний стека при восходящем разборе
ственное а,a. Для нее можно построить дерево разбора, аналогичное
приведенному на рис.1, а процесс ее разбора можно проиллюстрировать схемой, аналогичной схеме, приведенной на рис. 2. Однако
в момент выполнения операции приведения по правилу ii попытка
вычислить значение функции μ(ii,ℓ) для строки ℓ = 201 свойств идентификатора a позволит обнаружить семантическую ошибку, заключающуюся в повторном описании этого идентификатора.
ПРИМЕР ФОРМАЛЬНОГО ОПИСАНИЯ
СИНТАКСИСА И СЕМАНТИКИ ЯЗЫКА
Неформальное описание языка
Некий язык иллюстраций позволяет описывать операции над
двумя типами данных: строковыми и логическими. Над строковыми данными может быть выполнена операция конкатенации, обозначаемая словом conc, и операция сравнения, обозначаемая словом eq. Над логическими данными также может быть выполнена
операция сравнения (eq). Операнды могут быть константами или
переменными. Строковая константа изображается строкой печатных символов, заключенной в двойные кавычки. Логическая константа изображается словом true или словом false. Для обозначения
8
переменной используется идентификатор – последовательность латинских букв и арабских цифр, начинающаяся с буквы. Переменные приобретают значения в результате выполнения присвоения,
которое изображается знаком =. Текст программы состоит из двух
разделов: раздела объявлений переменных и раздела операторов.
В конце текста программы ставится точка. Раздел объявлений предваряется заголовком declaration, а раздел операторов – заголовком
implementation. В разделе объявлений перечисляются используемые переменные с указанием их типов: строковый тип указывается словом string, логический тип – словом boolean. Переменные, относящиеся к одному типу, могут быть перечислены через запятую,
а объявления переменных разных типов должны быть перечислены
через точку с запятой. Раздел операторов содержит последовательность операторов присваивания. Каждый оператор заканчивается
точкой с запятой, слева от операции присвоения содержит переменную, а справа – строковое или логическое выражение. Строковое
выражение может содержать произвольное количество двуместных
операций conc. При этом подразумевается, что выполняться они будут в порядке слева направо. Результат выполнения операции eq является логическим, и логическое выражение может содержать произвольное количество этих операций, выполняемых в порядке слева направо. Тип переменной в левой части оператора должен совпадать с типом выражения в правой части оператора.
Список семантических ошибок, подлежащих обнаружению
1. Использование необъявленного идентификатора.
2. Двойное объявление идентификатора.
3. Использование переменной не в соответствии с объявлением.
Описание грамматики свойств
В разделах «Неформальное описание языка» и «Список ошибок,
подлежащих обнаружению», можно сказать, сформулировано задание на конструирование грамматики свойств. Приступая к его исполнению, прежде всего, составим список свойств идентификатора, которые понадобятся для анализа семантики идентификаторов
в программе.
Свойства идентификатора (компонента ϑ):
0) нейтральное свойство (ϑ0);
1) появляется в списке имен или в операторе;
2) объявляется строковой переменной;
9
3) объявляется логической переменной;
4) используется как строковая переменная;
5) используется как логическая переменная.
Множество ϕ допустимых свойств – {0}.
Формализуем теперь описание языка в виде правил грамматики
и снабдим эти правила таблицами функции μ.
Правила P КС-грамматики и функция μ
1) <программа>::=declaration<объявления>implementation<исполнения>.
Правило описывает общую структуру программы: два раздела
(объявлений и операторов), в конце текста – точка. Идентификатору разрешено появиться в разделе объявлений со свойством 2 или
со свойством 3. Если он в этом разделе обнаружен, то ему разрешено появиться и в разделе операторов со свойством 4 или со свойством 5, соответственно. В таблице это следует зафиксировать нулевым (нейтральным) значением функции для аргументов-строк
02040 и 03050, что и будет означать использование переменной
в соответствии с описанием. Поскольку искать описанные, но не используемые, переменные в задании не требуется, функция μ должна иметь нулевое значение и для аргументов 02000 и 03000.
ℓ
μ(1, ℓ)
00000
02000
03000
02040
03050
0
0
0
0
0
2) <объявления>::=<объявления>;<объявление>
Рекурсивное правило указывает на то, что раздел объявлений
может содержать произвольное количество компонент, перечисленных через точку с запятой. Идентификатор в этом разделе может
быть объявлен строковой переменной (свойство 2) или логической
переменной (свойство 3). С этим своим свойством он и должен переходить в таблицу, связанную с нетерминалом <объявления> левой
части правила, о чем должны свидетельствовать соответствующие
значения функции μ. Идентификатору не разрешено более одного
раза появляться в разделе объявлений, поэтому значения 202, 203,
302, и 303 аргумента ℓ в таблицу включать не следует.
10
ℓ
μ(2, ℓ)
000
200
300
002
003
0
2
3
2
3
3) <объявления>::=<объявление>
Раздел объявлений может состоять из одной компоненты. Таблица для функции μ в этом случае должна быть аналогична таблице,
приписанной правилу 2, но иметь меньший размер.
ℓ
μ(3, ℓ)
0
0
2
2
3
3
4)<объявление>::=string<список имен>
Из этого правила следует, что компонента объявлений объявляет список идентификаторов переменными строкового типа, если
предваряет этот список словом string. Идентификатор, появившийся
в таком списке (свойство 1), приобретает новое свойство: 2 – объявлен
переменной строкового типа, на что и должна указать функция μ.
ℓ
μ(4, ℓ)
00
0
01
2
5) <объявление>::=boolean<список имен>
Это правило аналогично правилу 4, отличаясь от него словом
boolean в первой позиции правой части. Соответственно, функция
μ от аргумента 01 должна быть равна 3, поскольку идентификатор,
появившийся в списке имен, в этом случае становится логической
переменной.
ℓ
μ(5, ℓ)
00
0
01
3
11
6) <список имен>::=<список имен>,идентификатор
Из рекурсивного правила следует, что после описателя string или
boolean можно перечислить через запятую несколько идентификаторов. Свойство 1, зафиксированное для идентификатора в таблицах,
связанных с символами правой части правила, переходит и в таблицу, связанную с символом <список имен> левой части правила. Для
аргумента 101 значение функции μ определять не следует, поскольку
в одном списке имен все идентификаторы должны быть различными.
ℓ
μ(6, ℓ)
000
001
100
0
1
1
7) <список имен>::=идентификатор
Список имен может состоять из одного идентификатора. В этом
случае он также попадает в таблицу для <список имен> со свойством 1.
ℓ
μ(7, ℓ)
0
0
1
1
8) <исполнения>::=<исполнения>;<оператор>
В соответствии с рекурсивным правилом в раздел операторов
можно включить произвольное количество операторов, используя
в качестве разделителя точку с запятой. Идентификатор может появиться в операторах только как строковая переменная (свойство
4) или только как логическая переменная (свойство 5). С таким же
свойством он должен попасть в таблицу для нетерминала <исполнения> левой части правила, на что и указывают соответствующие
значения функции μ.
12
ℓ
μ(8, ℓ)
000
0
400
4
500
5
004
4
005
5
404
4
505
5
9) <исполнения>::=<оператор>
Раздел операторов может состоять из одного оператора. Таблица функции μ для этого правила аналогична предыдущей, но имеет
меньший размер.
ℓ
μ(9, ℓ)
0
0
4
4
5
5
10) <оператор>::=идентификатор=<строковое выражение>
Правило описывает синтаксис оператора присваивания. Таблица
функции μ для этого правила должна зафиксировать следующую ситуацию. При обнаружении одного и того же идентификатора слева и
справа от знака =, его свойство, связываемое с символом <оператор>
левой части правила, должно быть свойством 4, если он используется
в строковом выражении в качестве строковой переменной.
ℓ
μ(10, ℓ)
000
100
004
104
0
4
4
4
11) <оператор>::=идентификатор=<логическое выражение>
Еще одно правило, относящееся к синтаксису оператора присваивания, предполагает использование логического выражения справа от операции присвоения. Таблицу функции μ для этого случая
следует определить аналогично тому, как это сделано для правила
10, но с учетом того, что в логическом выражении могут участвовать
строковые переменные. Поэтому функцию следует определить для
аргумента 004. Однако строковой переменной нельзя присвоить логическое значение. Поэтому для аргумента 104, в отличие от предыдущей таблицы, функцию определять не следует.
ℓ
μ(11, ℓ)
000
100
005
105
004
0
5
5
5
4
13
12) <строковое выражение>::=<строковое выражение>conc<строковый операнд>
В соответствии с этим правилом строковое выражение может
содержать произвольное количество двуместных операций conc.
Идентификатор в строковом выражении может появиться многократно, но только со свойством 4.
ℓ
μ(12, ℓ)
000
0
400
4
004
4
404
4
13) <строковое выражение>::=<строковый операнд>
Строковое выражение может состоять из одного операнда. Если этим операндом является идентификатор, о котором уже известно, что он используется как строковая переменная (свойство
4), то с этим же свойством он должен быть включен в таблицу,
связываемую с нетерминалом <строковое выражение> левой части правила.
ℓ
μ(13, ℓ)
0
0
4
4
14) <строковый операнд>::=идентификатор
Строковый операнд может быть строковой переменной. Если
контекст использования идентификатора позволяет сделать такой
вывод, то идентификатор должен приобрести новое свойство: 4.
ℓ
μ(14, ℓ)
0
0
1
4
Заметим, впрочем, что распознать идентификатор как строковый операнд с помощью используемой нами технологии удастся
только в том случае, если строковое выражение с этим идентификатором содержит хотя бы одну операцию conc. Это значит, что семантическую ошибку в операторе вида: A=B; где A – логическая пере14
менная, а B – строковая (или наоборот), грамматика свойств обнаружить не позволит.
15) <строковый операнд>::=строка
Строковый операнд может быть константой. С константой не может быть связано никакое свойство никакого идентификатора, кроме нейтрального. Поэтому таблица для функции μ должна состоять
из единственной строки для аргумента 0 со значением 0.
ℓ
μ(15, ℓ)
0
0
16) <логическое выражение>::=<логическое выражение1>eq<терм>
Логическое выражение может содержать строки, над которыми выполняются операции eq сравнения. Это правило, описывающее логическое выражение через нетерминал <логическое выражение1>, подразумевает именно такую структуру этого выражения.
Идентификатор в таком логическом выражении может использоваться только как строковая переменная, и значения функции μ
должны сохранять это его свойство в таблице для нетерминала <логическое выражение> левой части правила.
ℓ
μ(16, ℓ)
000
0
400
4
404
4
004
4
17) <логическое выражение>::=<логическое выражение2>
Второй вариант логического выражения предполагает использование в нем идентификаторов только в качестве логических переменных, а значит – со свойством 5.
ℓ
μ(17, ℓ)
0
0
5
5
18) <логическое выражение1>::=<логическое выражение1>eq<терм>
Логическое выражение первого вида может содержать произвольное количество операций eq сравнения строк. Операнды опера15
ции eq сравнения строк обозначим нетерминалом <терм> для того,
чтобы иметь возможность установить более высокий, по отношению
к операции eq, приоритет операции conc.
ℓ
μ(18, ℓ)
000
0
400
4
404
4
004
4
19) <логическое выражение1>::=<терм>
В соответствии с этим правилом логическое выражение первого
вида может содержать один терм.
ℓ
μ(19, ℓ)
0
0
4
4
20) <терм>::=<терм>conc<строковый операнд>
Рекурсивное правило позволяет включать в терм произвольное
количество операций conc над строками. Эти строки могут быть
представлены идентификаторами, используемыми в качестве строковых переменных.
ℓ
μ(20, ℓ)
000
0
400
4
404
4
004
4
21) <терм>::=<строковый операнд>
Терм может состоять из единственного строкового операнда: константы или переменной. Во втором случае используется идентификатор со свойством 4.
16
ℓ
μ(21, ℓ)
0
0
4
4
22) <логическое выражение2>::=<логическое выражение2>eq
<логический операнд>
Рекурсивное правило для логического выражения второго вида
допускает произвольное количество операций eq сравнения логических операндов. Идентификатор в таких выражениях может использоваться только как логическая переменная – со свойством 5.
ℓ
μ(22, ℓ)
000
0
500
5
505
5
005
5
23) <логическое выражение2>::=<логический операнд>
Логическое выражение может состоять из единственного логического операнда. Если этим операндом является идентификатор,
о котором уже известно, что он используется как логическая переменная (свойство 5), то с этим же свойством он должен быть включен в таблицу, связываемую с нетерминалом <логическое выражение2>.
ℓ
μ(23, ℓ)
0
0
5
5
24) <логический операнд>::=идентификатор
К этому правилу может быть сделан комментарий, аналогичный
комментарию к правилу 14. Логический операнд может быть логической переменной. Если контекст использования идентификатора
позволяет сделать такой вывод, то идентификатор должен приобрести новое свойство: 5.
ℓ
μ(24, ℓ)
0
0
1
5
Справедливым также остается и замечание, относящееся к контексту использования идентификатора. В данном случае этот контекст обязательно должен содержать операцию сравнения с логической константой.
17
25) <логический операнд>::=true|false
Правило учитывает выражения, в которых логические операнды представлены константами. Таблица функции μ в этом случае
фиксирует только нейтральное свойство.
ℓ
μ(25, ℓ)
0
0
<программа> – аксиома (компонента S)
Тестовый пример
Вход (программа на языке иллюстраций):
declaration
string A,B;
boolean C,D;
implementation
A=”string1”;
B=”string2”;
C=A conc “2” eq B conc “1”;
D=A conc B.
Выход (результат анализа с помощью грамматики свойств):
Семантическая ошибка: использование переменной D не в соответствии с объявлением.
Комментарии к тестовому примеру
При разборе текста из вышеприведенного тестового примера в соответствии с правилами 5 и 3, с нетерминалом <объявления> будет связана таблица [A:2,B:2,C:3,D:3]. (Будем упоминать в таблицах
только идентификаторы со свойствами, отличными от нейтрального). В результате приведения по правилу 10 с нетерминалом <оператор> левой части этого правила будет связана следующая таблица свойств: [D:4,A:4,B:4]. С таким же свойством идентификатор D
попадет в таблицу, связываемую с нетерминалом <исполнения>
в результате операции приведения по правилу 8. Таким образом,
для определения функции μ(1,ℓ), относящейся к идентификатору D,
будет получена строка свойств: ℓ = 03040, отсутствующая в таблице, что и означает наличие семантической ошибки в разобранном тексте.
18
НЕКОТОРЫЕ ПРАКТИЧЕСКИЕ РЕКОМЕНДАЦИИ
Общие рекомендации
Схема «сдвиг-приведение» может найти конкретное воплощение, например, в виде LR(1)-разбора или разбора с использованием
отношений предшествования, предполагающих построение модели
синтаксического анализатора в виде детерминированного автомата
с магазинной памятью [1]. Краткие сведения о построении и функционировании этих моделей приведены в приложении. Программная реализация какой-либо из них в курсовой работе может быть
выполнена самостоятельно или с помощью каких-либо средств автоматизации построения синтаксических анализаторов. К таким
средствам относятся, в частности, утилиты Flex и Bison, возможное
применение которых описано в следующем разделе.
Построение грамматики свойств, а точнее – ее четырех последних компонент, следует начать с определения списка семантических
ошибок, которые планируется обнаруживать. Опираясь на такой
список, затем можно зафиксировать множество ϑ свойств, приобретаемых анализируемым объектом (идентификатором), и множество φ допустимых свойств, т. е. таких, которыми может обладать
анализируемый объект по окончании восходящего разбора.
Следует заметить, что аппарат атрибутной грамматики не всесилен даже в решении частной задачи анализа семантики идентификаторов. Так, с помощью грамматики свойств невозможно
проследить соответствие формальных и фактических параметров
процедур и функций в общем случае и нельзя полностью проконтролировать описания типа «структура» или «класс». Тестовые
примеры, приведенные в приложении, тем не менее, предлагают проведение такого контроля. Для его реализации придется
связывать с идентификаторами данные более сложной структуры, чем просто номер свойства. По-видимому, это должны быть
данные о взаимосвязях идентификаторов (например, имен классов или структур и имен их компонент). Объявление переменных типа «структура» или «класс» можно считать объявлениями составных идентификаторов (составленных из имен компонент структуры или класса с префиксом – именем переменной),
для которых также необходимо формировать таблицы свойств
с целью анализа корректности их использования. Что же касается имен процедур и функций, такими дополнительным данными
могут быть, например, связанные с этими именами списки типов
19
параметров. Впрочем, в учебной задаче допустимо ограничить
сложность анализируемых конструкций (например, зафиксировав длину списка параметров).
Рекомендации по использованию Flex-Bison
в курсовом проектировании
Использование утилит Flex-Bison избавляет от необходимости
самостоятельно программировать автоматные модели для лексического и синтаксического анализов. Напомним, что утилита Flex
на основании описания лексем в виде регулярных выражений генерирует программную реализацию конечного автомата, принимающего такие лексемы, а утилита Bison – программную реализацию
LR(1)-автомата, принимающего язык, описанный правилами грамматики [4]. Программная реализация автоматной модели включает
в себя как управляющую таблицу, так и алгоритм анализа с использованием этой таблицы и, в случае LR(1)-модели, с использованием стека разбора. Таким образом, программисту остается лишь сосредоточить внимание на описании синтаксиса языка и семантических подпрограмм, которые, по заданию на курсовое проектирование, должны дополнить LR(1)-грамматику синтезируемыми атрибутами.
Атрибуты в рассматриваемой задаче должны содержать информацию о семантике используемых идентификаторов, представленную таблицами свойств идентификаторов. Доступ к такой таблице
свойств, связанной с символом грамматики, должно обеспечивать
внутреннее представление этого символа грамматики (то, на что
можно ссылаться через $i и yylval). Пусть, например, одна строка
динамической таблицы свойств описывается структурой:
struct line{// запись таблицы свойств
char *identifier;
char property;
line *next;
};
Тогда внутреннее представление символа грамматики целесообразно описать в виде:
union {
line *table;
}
Тот факт, что table будет типом внутренних представлений терминальных и нетерминальных символов грамматики, следует ука20
зать во входном потоке Bison с помощью директив token и type, соответственно.
При выполнении лексического анализа обнаружение идентификатора в анализируемом тексте должно сопровождаться созданием
внутреннего представления этой лексемы в виде записи типа line
с указателем на нее в переменной yylval и формированием ее кода
(токена). Так для вышеприведенного фрагмента описания языка
в виде правил с номерами i) – iii) и соответствующих таблиц
свойств идентификаторов описание действий во входном потоке Flex, сопровождающих обнаружение идентификатора, может
быть таким:
{Identifier} {yylval.table=new line;
yylval.table->identifier = new char[strlen(yytext)+1];
strcpy(yylval.table->identifier,yytext);
yylval.table->property=’1’;
yylval.table->next=NULL;
return AP_Identifier_KW;
}
Описание сделано в предположении, что регулярное выражение, описывающее лексему-идентификатор, поименовано Identifier,
а AP_Identifier_KW является символьным обозначением токена
этой лексемы.
В результате выполнения таких действий, в частности, в поле identifier сформированной записи будет помещен сам идентификатор, а в поле property – номер его свойства (1 – «упоминается
здесь»).
Поскольку с терминалами «вещественное» и «,» не должны связываться таблицы свойств идентификаторов, обнаружения этих лексем могут сопровождаться, например, следующими действиями:
{Real}
{yylval.table=NULL;
return AP_Real_KW;
}
{Comma}
{yylval.table=NULL;
return AP_Comma_KW;
}
В этом описании Real и Comma – имена регулярных выражений, описывающих лексемы «вещественное» и «,», соответственно,
а AP_Real_KW и AP_Comma_KW – символьные обозначения токенов этих лексем.
Таблицы свойств, связываемые с нетерминальными символами, формируются в виде внутренних представлений этих символов
21
на этапе синтаксического анализа. Семантическая подпрограмма, приписанная какому-либо правилу грамматики, должна сформировать таблицу свойств, которая будет связана с нетерминалом
левой части этого правила. Доступ к формируемой таблице удобно
выполнять через переменную $$, предназначенную для хранения
внутреннего представления нетерминала левой части правила, и,
следовательно, в рассматриваемом примере имеющую тип line *. Доступ же к таблицам свойств, связанным с символами правой части
правила, как терминальным, так и нетерминальным, удобно выполнять через переменные с именами $i, где i – номер символа правой части правила (символы нумеруются в порядке слева направо,
начиная с 1).
Выполняя операцию приведения по какому-либо правилу, процедура LR(1)-разбора удаляет из стека разбора правую часть правила и помещает в стек разбора левую часть правила. Поэтому в семантической подпрограмме, приписанной какому-либо правилу,
после формирования таблицы по указателю $$ следует предусмотреть освобождение памяти, отведенной ранее таблицам для символов правой части правила по указателям $i (i = 1..n, где n – длина
правой части правила).
Запишем вышерассмотренное правило номер i) в несколько ином
виде, с учетом допустимых обозначений во входном потоке Bison:
i) <descriptions>::=вещественное <namelist>
Описание действий, сопровождающих операцию приведения по
этому правилу, в терминологии Bison может быть, например, таким:
descriptions : AP_Real_KW namelist {$$=NULL; line *p=$2;
//alltable – массив таблиц для символов правой части правила:
//терминала AP_Real_KW и нетерминала descriptions
alltable[0]=NULL; alltable[1]=$2;
//формирование таблицы для нетерминала descriptions
while(p)
{if(!keytest(p->identifier,$$))
tablewrite(p->identifier,mcompute(p->identifier,alltable,1),$$);
p=p->next;
}
//освобождение памяти, занимаемой таблицей для нетерминала
//namelist
p=$2;line *pp;
while(p)
{delete [strlen(p->identifier)+1] p->identifier;
22
pp=p->next; delete p; p=pp;
}
//вывод таблицы, связанной с нетерминалом descriptions
p=$$;
while(p)
{cout<<p->identifier<<’ ‘<<p->property<<’\n’;
p=p->next;
}};
Описание предполагает наличие функций:
bool keytest(char*key,line*t) – проверка наличия в таблице t записи с идентификатором key;
void tablewrite(char*key,char m,line*t) – занесение в таблицу t новой записи с идентификатором key и свойством m;
char mcompute(char*key,line*alltable,N) – вычисление значения
функции μ для идентификатора key по исходным таблицам alltable,
связанным с символами правой части правила номер N.
Табличное определение функции μ целесообразно задать глобальной константой.
При программном анализе строки вещественное а,в , проиллюстрированном рис.1 и рис.2, вывод таблицы, связанной с нетерминалом descriptions, изобразит текст:
a3
b3
Заметим, впрочем, что в задании на курсовую работу построение таблицы свойств идентификаторов для аксиомы грамматики не
является самоцелью. Содержание таблицы, если ее удалось построить, должно быть проанализировано на предмет принадлежности
всех вошедших в нее свойств множеству допустимых. И на основании этого анализа следует сделать вывод о корректности разобранного текста.
23
СОДЕРЖАНИЕ ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ
Введение
1. Постановка задачи
2. Описание исходного языка
3. Детерминированная автоматная модель синтаксического анализатора
4. Грамматика свойств
5. Структура разработанной программы
6. Результаты тестирования
7. Руководство пользователя
Заключение
Библиографический список
Приложение
Перечисленные разделы должны содержать следующую информацию:
Введение – описание задач, которые возлагаются на синтаксический и семантический анализ в работе транслятора, а также общую характеристику исходного языка, выбранного по варианту задания, и области его применения.
Постановка задачи – текст задания, конкретизированный указанием исходного языка и словесным описанием выбранного подмножества этого языка.
Описание исходного языка – регулярную грамматику, описывающую лексемы языка, и КС-грамматику, описывающую синтаксис
языка.
Детерминированная автоматная модель синтаксического
анализатора – описание автоматных моделей, выбранных для реализации лексического и синтаксического анализов.
Грамматика свойств – компоненты ϑ, ϑ0, φ, μ , дополняющие
построенную КС-грамматику до грамматики свойств.
Структура разработанной программы – обобщенное описание спроектированной программы с указанием ее основных блоков,
функций и их взаимосвязей.
Результаты тестирования – несколько тестов, на которых
была проверена работа спроектированной программы, в виде
входных текстов, предъявленных программе, и текстов ее ответных реакций.
24
Руководство пользователя – инструкцию по подготовке исходных данных, запуску программы и интерпретации ее сообщений.
Заключение – критический анализ проделанной работы с указанием ее достоинств и, возможно, недостатков.
Библиографический список – список использованной литературы (на которую в основном тексте полагается делать ссылки).
Приложение – исходный текст спроектированной программы.
25
Библиографический список
1. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты: пер. с англ. М.: Издательский дом «Вильямс»,
2003. 768 с.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция: пер. с англ. М.: Мир, 1978.
488 с.
3. Хантер Р. Проектирование и конструирование компиляторов:
пер. с англ. М.: Финансы и статистика, 1984. 232 с.
4. Бржезовский А. В., Максимова Т. М., Янкелевич А. А. Теория
языков программирования и методы трансляции. Средства автоматизации построения синтаксических анализаторов: методические
указания к выполнению лабораторных работ № 1, 2. СПб.: СПбГУАП,
2006. 36 с.
5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин: пер. с англ. М.: Мир, 1975. 544 с.
26
ПРИЛОЖЕНИЕ 1
Синтаксический анализ с использованием
детерминированного автомата с магазинной памятью
Детерминированный автомат с магазинной памятью может использоваться в качестве распознавателя некоторых частных видов
КС-языков. (КС-язык – это язык, который может быть описан КСграмматикой, а КС-грамматика, по классификации Хомского, – это
грамматика, правила которой в левой части содержат по одному нетерминалу, а в правой – произвольные строки терминалов, нетерминалов или пустые строки). Структура такого распознавателя приведена на рис. П1.
Управляющая таблица содержит в своих клетках команды, которые должен выполнить автомат. Координаты клетки, из которой следует выбрать очередную команду, определяются содержанием вершины стека (координата строки) и обозреваемым на входной ленте символом анализируемой строки (координата столбца).
Управляющая таблица автомата, реализующего алгоритм типа
«сдвиг-приведение», естественно, содержит команды типа «сдвиг»
и типа «приведение», а также две команды завершения работы алгоритма: успешное завершение синтаксического разбора входной
строки и обнаружение синтаксической ошибки во входной строке.
LR(1)-грамматика и грамматика предшествования являются частными видами КС-грамматик, для которых может быть построен детерминированный автомат, реализующий алгоритм типа «сдвигприведение».
LR(1)-реализация алгоритма «сдвиг-приведение»
В заголовки строк управляющей таблицы LR(1)-автомата выносятся индексы его внутренних состояний, а в заголовки строк –
все терминальные и нетерминальные символы грамматики, а так
»ÎǽƹØľÆ˹
¬Èɹ»ÄØ×Ò¹Ø
˹ºÄÁϹ
Ê˾Ã
Рис. П1. Структура детерминированного распознавателя КС-языков
27
же маркер конца входной строки. Записи стека содержат два поля:
поле символа и поле внутреннего состояния. Содержание поля состояния верхней записи стека определяет текущее внутреннее состояние автомата и, следовательно, координату строки управляющей таблицы, из которой должна быть выбрана очередная команда. Перед началом работы распознавателя в стек следует поместить
запись, содержащую индекс начального состояния в поле состояния. Команда типа «сдвиг» должна указывать, в какое внутреннее состояние переходит автомат одновременно с чтением символа
из входной ленты. В результате выполнения этой команды курсор
входной ленты перемещается на один символ влево, а стек пополняется записью с прочитанным из ленты символом в поле символа
и индексом внутреннего состояния, указанного в команде, в поле
состояния. Команда типа «приведение» должна указывать правило
грамматики, например, в виде его номера, по которому следует выполнить приведение. В результате выполнения этой команды из стека удаляются записи, соответствующие правой части правила, по
которому делается приведение, и подготавливается имитация установки курсора входной ленты на нетерминальный символ левой части этого правила. По команде «допуск» разбор считается успешно
завершенным. По команде «ошибка» разбор также прекращается,
но входная строка объявляется синтаксически неверной.
Для вышеприведенного фрагмента грамматики с правилами i) – iii)
управляющая таблица LR(1)-автомата может быть такой.
<описания>
1
2
3
<список
имен>
допуск
вещественное
,
идентификатор
маркер
конца
сдвиг2
сдвиг3
сдвиг6
сдвиг4
4
приведение i
сдвиг5
5
приведение ii
приведение ii
6
приведение iii
приведение iii
Таблица построена в предположении, что нетерминал <описания> является начальным символом фрагмента грамматики (его
аксиомой). Числами 1–6 в таблице обозначены внутренние состоя28
ния автомата, при этом состояние 1 является начальным. Соответственно, в командах типа «сдвиг» этими числами указываются внутренние состояния, в которые должен переходить автомат, выполняя такие команды. Команды типа «приведение» снабжены номерами правил, по которым следует выполнять приведение. Пустые
клетки таблицы считаются содержащими команду «ошибка».
Разбор строки вещественное а,в с использованием приведенной
таблицы получится несколько более длинным, чем на рис. 2, поскольку в этом случае попадание нетерминального символа в стек
оказывается возможным только при выполнении команды типа
«сдвиг». Процесс разбора удлинится на некоторое количество таких операций имитации чтения из входной ленты нетерминального
символа и занесения его в стек.
В записях стека на рис. П2 содержание полей символа и внутреннего состояния указаны через запятую. Символом Λ обозначена пустая строка. Так запись Λ,1 означает, что поле символа пусто, а в поле внутреннего состояния находится индекс 1.
Для того чтобы построить управляющую таблицу для LR(1)автомата, нужно определить множество его внутренних состояний.
ʽ»Á¼
ʽ»Á¼
ÈÉÁ»¾½¾ÆÁ¾
JJJ
¸
º½Ñ½Éʺ½ÅÅƽ
º½Ñ½Éʺ½ÅÅƽ
Λ
Λ
ʽ»Á¼
ʽ»Á¼
ʽ»Á¼
ÊÈÁÊÇÃ
ÊÈÁÊÇÃ
ÁžÆ
ÁžÆ
º½Ñ½Éʺ½ÅÅƽ
º½Ñ½Éʺ½ÅÅƽ
º½Ñ½Éʺ½ÅÅƽ
Λ
Λ
Λ
º
ÈÉÁ»¾½¾ÆÁ¾JJ
ʽ»Á¼
ÊÈÁÊÇÃÁžÆ
ÊÈÁÊÇÃ
ÁžÆ
º½Ñ½Éʺ½ÅÅƽ
º½Ñ½Éʺ½ÅÅƽ
º½Ñ½Éʺ½ÅÅƽ
Λ
Λ
Λ
ÈÉÁ»¾½¾ÆÁ¾J
½ÇÈÌÊÃ
Λ
Λ
Рис. П2. Последовательность состояний стека при LR(1)-разборе
29
Внутренние состояния автомата ставятся в соответствие позициям
правых частей правил LR(1)-грамматики в результате так называемой разметки этих правил.
В простейшем случае разметка выполняется следующим образом.
1. Индексы внутренних состояний следует поместить между соседними символами, перед первым символом (в начальную позицию) и после последнего символа (в конечную позицию) правой части каждого правила.
2. В начальные позиции всех правых частей правил для аксиомы
следует поместить индекс начального состояния автомата.
3. Если в процессе разметки индекс какого-либо состояния оказался перед нетерминальным символом, его следует распространить на начальные позиции всех правых частей правил для этого
нетерминального символа.
4. Если в процессе разметки в двух или более правилах слева от
одного и того же символа оказался один и тот же индекс внутреннего состояния, то в этих правилах и справа от этого символа следует
поместить одинаковые индексы.
Рассмотренная в этом разделе LR(1)-таблица была построена на
основе такой разметки правил грамматики:
i) <описания>::= 1 вещественное 2 <список имен> 3
ii) <список имен>::= 2 <список имен> 3 , 4 идентификатор 5
iii) <список имен>::= 2 идентификатор 6
Для разметки понадобилось шесть различных индексов. Следовательно, у автомата должно быть шесть внутренних состояний.
Заполнение таблицы с использованием разметки выполняется
по следующим правилам.
1. Команда «сдвиг k» помещается в клетку таблицы с координатами (j,символ), если позиция слева от символа отмечена индексом
k, а позиция справа от символа – индексом j.
2. Команда «приведение m» помещается в клетку таблицы с координатами (n,символ), если конечная позиция правой части m-го
правила грамматики отмечена индексом n, а символ является
символом-следователем для нетерминала левой части m-го правила
грамматики, т. е. может следовать за этим нетерминалом в какойлибо сентенциальной форме. (Сентенциальной формой называются
аксиома и все строки нетерминальных и терминальных символов,
которые из нее выводятся).
3. Команда «допуск» помещается в клетку таблицы с координатами (l,аксиома), где l – индекс начального внутреннего состояния
автомата.
30
4. После заполнения таблицы по правилам 1–3 в клетки, оставшиеся пустыми, помещается команда «ошибка».
В результате применения этих правил к размеченному фрагменту грамматики и получается вышеприведенная управляющая таблица LR(1)-автомата.
Восходящий разбор
с использованием грамматики простого предшествования
Управляющая таблица автоматного распознавателя, построенного по грамматике простого предшествования, представляет собой квадратную матрицу отношений простого предшествования
для всех терминальных и нетерминальных символов грамматики. Отношения предшествования определяются для пар символов грамматики, которые могут оказаться соседними в какойлибо сентенциальной форме. Конкретные значения отношений
(< , > , =) указывают на возможное положение двух соседних
символов относительно основы. Основой называется правая часть
правила, которая в текущей сентенциальной форме подлежит замене левой частью правила на очередном шаге восходящего разбора. Другими словами, основа – это такая подстрока текущей
сентенциальной формы, по отношению к которой на очередном
шаге алгоритма типа «сдвиг-приведение» следует выполнить
операцию «приведение».
Отношение < предполагает, что первый из пары соседних символов находится непосредственно слева от основы, а второй принадлежит ей и является ее первым символом. Отношение > предполагает, что первый из пары соседних символов принадлежит основе и является ее последним символом, а второй находится непосредственно справа от основы. Отношение = предполагает, что оба соседних
символа находятся внутри основы. Таким образом, если рассматривать символы отношения предшествования в качестве команд
управляющей таблицы автоматного распознавателя, реализующего алгоритм типа «сдвиг-приведение», символы < и = должны считаться обозначением команды «сдвиг», а символ > – команды «приведение». Клетки таблицы с такими координатами-символами, для
которых отношение предшествования не определено, должны считаться содержащими команду «ошибка», поскольку неопределенность отношения предшествования для пары символов грамматики
означает, что такая пара символов не может появиться ни в какой
сентенциальной форме.
31
Во фрагменте грамматики с правилами i) – iii) отношения простого предшествования не для всех пар символов оказываются единственными. Преобразуем грамматику к виду:
i) <описания>::=вещественное <А>
ii) <список имен>::=<список имен>,идентификатор
iii) <список имен>::=идентификатор
iv) <А>::=<список имен>
Для символов грамматики с правилами i) – iv) имеют место отношения простого предшествования, зафиксированные в матрице:
<описания>
<список
имен>
<А>
вещественное
идентификатор
маркер
правого
конца
>
<описания>
<список
имен>
<А>
=
>
>
<
вещественное
,
идентификатор
маркер левого конца
,
=
<
=
>
<
>
<
Выполним еще раз разбор строки вещественное а,в теперь уже
с учетом отношений предшествования. Возможность использования
матрицы отношений предшествования в качестве управляющей таблицы в автоматном распознавателе со структурой, изображенной на
рис. 3, можно сказать, обусловлена следующим утверждением [5].
Единственной основой любой сентенциальной формы грамматики простого предшествования является такая самая левая подстрока si…sj этой формы, для символов которой определены отношения
простого предшествования:
si–1 < si = si+1 = … = sj–1 = sj > sj+1.
Воспользуемся этой удобной формой для иллюстрации процесса
восходящего разбора без явного изображения стека. Маркеры левого и правого концов строки обозначим символом $.
$ < вещественное < а > ,в$ → приведение по правилу iii
32
$ < вещественное < <список имен> = , = в > $ → приведение
по правилу ii
$ < вещественное < <список имен> > $ → приведение по правилу iv
$ < вещественное = <А> > $ → приведение по правилу i
$ < <описания> > $ → успешное завершение разбора.
В заключение прокомментируем процесс заполнения матрицы
отношений простого предшествования. Эти отношения определяются в результате анализа правил грамматики.
Если символы A и B стоят рядом в правой части какого-либо правила грамматики, то для них определено отношение простого предшествования = : A = B. Например: <список имен> = , .
Если символы A и W стоят рядом в правой части какого-либо
правила грамматики и символ W является нетерминальным, то
A < B для всех символов B, с которых могут начинаться строки, выводимые из W. Например:
вещественное < <список имен> и вещественное < идентификатор , поскольку есть правило с правой частью вещественное <А>,
а строки, выводимые из <А>, могут начинаться с символа <список
имен> и символа идентификатор.
Если символы W и B стоят рядом в правой части какого-либо
правила грамматики и символ W является нетерминальным, а символ B – терминальным, то A > B для всех символов A, на которые
могут заканчиваться строки, выводимые из W. Например: идентификатор > , ,поскольку есть правило с фрагментом правой части
<список имен> , и все строки, выводимые из нетерминала <список имен>, заканчиваются символом идентификатор.
33
ПРИЛОЖЕНИЕ 2
Примеры тестов для вариантов задания
на курсовую работу
1. Исходный язык – подмножество Pascal
Вход:
program p;
procedure f1(a:boolean);
var z:character;
begin
z:=’a’;
if a then z:=z+1
else z:=z-1;
end;
begin
f1(false);
end.
Выход:
Семантическая ошибка: z – использование идентификатора не в
соответствии с типом
2. Исходный язык – подмножество C
Вход:
int i,j;
void f1(char i)
{ if(i) f1(i--);
else return;
}
void main()
{ bool a=false;
f1(true); i=1;
f1(10);
f1(“1.3”);
}
Выход:
Семантическая ошибка: f1 – использование идентификатора не
в соответствии с типом
34
3. Исходный язык – подмножество Java
Вход:
class Point { int x, у;
public static void main(String args[]) {
Point p = new Point();
р.х = 10;
p.у = 20;
p.z = 30;
System.out.println(«x = « + р.x + « у = « + p.y + « z = « + p. z);
}}
Выход:
Семантическая ошибка: р.z – использование необъявленного
идентификатора
4. Исходный язык – подмножество Flex
Вход:
letter [a-z]
digit [0-9]
identifier {letter}({letter}|{digit})*
%%
{identifier} {cout<<”идентификатор”<<yytext; return ID_token;}
{semicolon} {cout<<”точка с запятой”<<yytext; return S_token;}
%%
Выход:
Семантическая ошибка: semicolon – использование необъявленного идентификатора
5. Исходный язык – подмножество Perl
Вход:
my $var=’a’;
print “$var=’$var’\n”;
sub1();
sub sub1{
$var=’b’;
my $lvar=’c’;
print “$lvar=’$lvar’\n”;
sub2();
print “$var=’$var’\n”;
}
sub sub2{
print “$var=’$var’\n”;
35
$var=’d’;
print “$lvar=’$lvar’\n”;
}
Выход:
Семантическая ошибка: $lvar – использование необъявленного
идентификатора
6. Исходный язык – подмножество Lisp
Вход:
(defun list1(x y)
(cons x (cons y nil)))
(setq list1 ‘a)
(list1 list1 ‘b)
(list1 a list1)
Выход:
Семантическая ошибка: a – использование необъявленного идентификатора
7. Исходный язык – подмножество Prolog
Вход:
domains
int=integer*
predicates
ord(int)
clauses
ord([A]).
ord([A,B|C]):-A>C,ord([B|C]).
Выход:
Семантическая ошибка: C – использование идентификатора не в
соответствии с типом
8. Исходный язык – подмножество Matlab
Вход:
function[]=main()
r=5; x0=3; y0=-3;
circle(r,x0,y0);
circle(r)
function[]=circle(r,x0,y0)
if(nargin<3), y0=0;end
if(nargin<2), x0=0;end
t=0:pi/64:2*pi;
36
x=x0+r*cos(t);
y=y+r*sin(t);
plot(x,y), axis equal, grid on, hold on
xlabel(‘x’), ylabel(‘y’), title(‘circle’)
Выход:
Семантическая ошибка: y – использование необъявленного идентификатора
9. Исходный язык – подмножество Visual Basic
Вход:
Dim Result As Date
Sub MultiplyEm(Value1 As Single, Value2 As Single)
Result =Value1*Value2
End Sub
Sub TestProc()
Dim V1 As Single, V2 As Single
V1=5
V2=7
MultiplyEm (V1, V2)
End Sub
Выход:
Семантическая ошибка: Result – использование идентификатора
не в соответствии с описанием
10. Исходный язык – подмножество Shell
Вход:
for i in *
do
echo $j
done
Выход:
Семантическая ошибка: j – использование необъявленного идентификатора
37
ПРИЛОЖЕНИЕ 3
График выполнения курсовой работы
№ этапа
Содержание этапа
1
Выполнение лабораторной работы
«Средства автоматизации построения синтаксических анализаторов»
Ознакомление с исходным языком,
подготовка тестовых примеров
Подготовка формального описания
синтаксиса исходного языка
Разработка грамматики свойств
Разработка программной реализации
Тестирование программы
Подготовка пояснительной записки
Защита курсовой работы
2
3
4
5
6
7
8
38
№ недели
отчетности
Рейтинг
2
5
4
10
6
7
10
10
11
13
14
16
15
5
5
40
Содержание
Задание на курсовую работу «Синтаксически управляемый анализ семантики идентификаторов в текстах программ»....................................................................... Некоторые теоретические сведения о семантическом анализе с использованием грамматики свойст....................... Пример формального описания синтаксиса и семантики
языка......................................................................... Неформальное описание языка.................................. Список семантических ошибок, подлежащих обнаружению.............................................................. Описание грамматики свойств................................... Тестовый пример. .................................................... Комментарии к тестовому примеру............................. Некоторые практические рекомендации......................... Общие рекомендации................................................ Рекомендации по использованию Flex-Bison в курсовом
проектировании................................................. Содержание пояснительной записки............................... Библиографический список........................................... Приложение 1............................................................. Синтаксический анализ с использованием детерминированного автомата с магазинной памятью............ LR(1)-реализация алгоритма «сдвиг-приведение»......... Восходящий разбор с использованием грамматики простого предшествования....................................... Приложение 2............................................................. Примеры тестов для вариантов задания на курсовую
работу.............................................................. Приложение 3............................................................. График выполнения курсовой работы......................... 3
4
8
8
9
9
18
18
19
19
20
24
26
27
27
27
31
34
34
38
38
39
Документ
Категория
Без категории
Просмотров
2
Размер файла
656 Кб
Теги
maksimov, programmirovania, jazykov, teorija
1/--страниц
Пожаловаться на содержимое документа