Разработка и отладка формальных грамматик
Разработка и отладка обобщенных автоматов, формальных грамматик, реализация синтаксического анализа, а также решение практических вопросов проектирования программных продуктов. Отладка разработанной грамматики для метода параллельного предшествования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 25.11.2010 |
| Размер файла | 559,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Разработка и отладка формальных грамматик
Пояснительная записка к курсовой работе
по дисциплине
"Теория трансляции"
СПОТТ.073-01 81 01
Листов 52
Одесса ОНПУ 2010
Аннотация
Задачей данной курсовой работы является закрепление, систематизация, углубление и развитие теоретических и практических знаний, полученных в процессе изучения дисциплины «Теория трансляции», а именно применение на практике таких навыков как разработка формальных грамматик, обобщенных автоматов, отладка грамматик, реализация синтаксического анализа а также приобретение практических навыков самостоятельного творческого решения общетеоретических, практических и методических вопросов проектирования программных продуктов.
Основная цель курсовой работы состоит в изучении и анализе вопросов, связанных со специальными аспектами изученной дисциплины, совершенствовании общетеоретической подготовки, а также самостоятельной разработке программных продуктов.
В процессе курсовой работы приобретаются навыки к использованию специальной научно-технической литературы и документации, справочников, ГОСТов и других методических материалов.
Выполнение курсовой работы определяет общетеоретическую и специальную подготовку студента и служит необходимой базой для выполнения завершающего этапа обучения в ВУЗе - дипломного проектирования.
Содержание
Аннотация
Листинг Задания
Введение
1. Назначение и область применения
2. Технические характеристики
2.1 Разработка грамматики
2.2 Разрешение конфликтов
2.3 Синтаксическое дерево для тестовой цепочки
3. Разработка сканера
3.1 Схема обобщенного конечного автомата
3.2 Семантические действия сканера
3.3 Таблицы сканера для тестовой цепочки
4. Синтаксический анализ
4.1 Разработка алгоритма синтаксического анализатора
4.2 Разбор тестовой цепочки входного языка
Заключение
Литературные источники, использованные при разработке
Листинг Задания
Одесский национальный политехнический университет
Кафедра системного программного обеспечения
Группа АС-073
Студент Довганюк Дмитрий Сергеевич
Дата : 24.02.2010 18:22:20
Дисциплина "Теория трансляции "
Курсовая работа
"Разработка и отладка формальных грамматик "
Задание
1. Разработать контекстно-свободную грамматику для языка, который допускает использование:
1.1 Процедур Property.
1.2 Явное объявление следующих типов переменных: Variant, Byte, Single, Integer, Boolean, String
1.3 Оператор объявления API функций.
1.4 Описание типа переменных с помощью суффикса: Date, Boolean
1.5 Массивы переменного размера с максимальной размерностью 3
1.6 Операторы ввода/вывода MsgBox, InputBox.
1.7 Арифметические операции: * - \ mod ^
1.8 Логические операции: Not, And, Xor, Eqv.
1.9 Операции сравнения.
1.10 Условные операторы типа Select Case
1.11 Оператор цикла типа While...Went
1.12 Оператор присваивания
1.13 Оператор безусловного перехода
1.14 Следующие функции: Len,, CSng, IsEmpty, RegCloseKey.
2. Для проверки правильности разработанной грамматики для тестового примера нарисуйте синтаксическое дерево. В случае необходимости модифицируйте исходную грамматику.
3. Определите лексемы. Опишите их с помощью автоматных грамматик, постройте обобщенный конечный автомат. Определите семантические действия сканера. Определите структуру таблиц сканера и заполните их для тестового примера.
4. Выполните отладку разработанной грамматики для метода параллельного предшествования. Укажите символы, между которыми существуют конфликты отношений предшествования. Отладку проиллюстрируйте синтаксическими деревьями.
5. Выполните синтаксический анализ тестового примера заданным методом синтаксического анализа. Разработайте схему алгоритма. Постройте подробную таблицу синтаксического анализа.
Введение
Транслямтор -- программа, которая принимает на вход программу на одном языке (он в этом случае называется исходный язык, а программа -- исходный код), и преобразует её в программу, написанную на другом языке (соответственно, целевой язык и объектный код).
В качестве целевого языка наиболее часто выступают машинный код, Ассемблер и байт-код, так как они наиболее удобны (с точки зрения производительности) для последующего исполнения.
Наиболее часто встречаются две разновидности трансляторов:
Компиляторы -- выдают результат в виде исполняемого файла (в данном случае считаем, что компоновка входит в компиляцию). Этот файл:
· транслируется один раз -- может быть запущен самостоятельно
· не требует для работы наличия на машине создавшего его транслятора
Интерпретаторы -- исполняют программу после разбора (в этом случае в роли объектного кода выступает внутреннее представление программы интерпретатором). Исполняется она построчно. В данном случае программа
· транслируется (интерпретируется) при каждом запуске (если объектный код кешируется, возможны варианты)
· требует для исполнения наличия на машине интерпретатора и исходного кода
Алфавиты, цепочки и языки
Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа
Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один символ.
Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.
Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.
Представление языков
Процедура - это конечная последовательность инструкций, которые могут быть механически выполнены. Примером может служить машинная программа. Процедура, которая всегда заканчивается, называется алгоритмом.
Один из способов представления языка - дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит в том, чтобы дать процедуру, которая останавливается с ответом "да" для цепочек, принадлежащих языку, и либо останавливается с ответом "нет", либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык.
Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка.
Если мы можем распознать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то мы можем и генерировать язык, поскольку мы можем систематически генерировать все цепочки из , проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Но если процедура не всегда заканчивается при проверке цепочки, мы не сдвинемся дальше первой цепочки, на которой процедура не заканчивается. Эту проблему можно обойти, организовав проверку таким образом, чтобы процедура никогда не продолжала проверять одну цепочку бесконечно. Для этого введем следующую конструкцию.
Предположим, что V имеет p символов. Мы можем рассматривать цепочки из как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в "числовом" порядке для цепочек одинаковой длины.
1. Назначение и область применения
Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Сегодня только очень малая часть программного обеспечения, требующая особой эффективности, разрабатывается с помощью ассемблеров. В настоящее время имеет применение довольно много языков программирования. Наряду с традиционными языками, такими, например, как Фортран, широкое распространение получили так называемые "универсальные" языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ.
Для ряда названных языков имеется довольно много реализаций. Так, на рынке программного обеспечения представлены десятки реализаций языков Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC.
С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Наряду с возникновением новых архитектур, совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным параметрам. Это можно проиллюстрировать на примере микропроцессора Intel-80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, 68040.
В рамках традиционных последовательных машин развивается большое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC- архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.
Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом архитектуры (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными компьютерами (например, на основе микропроцессора I-860). Естественно, для каждой из новых машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов
2. Технические характеристики
Разработать контекстно-свободную грамматику для языка
Грамматики
Для нас наибольший интерес представляет одна из систем генерации языков - грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примером может служить способ описания синтаксиса языков программирования при помощи БНФ - формы Бэкуса-Наура.
Определение. Грамматика - это четверка G = (N,T,P,S), где
(1) N - алфавит нетерминальных символов;
(2) T - алфавит терминальных символов,
(3) P - конечное множество правил вида
, где (1)
(4) - начальный знак (или аксиома) грамматики.
Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из и, наконец, малые греческие буквы для обозначения цепочек из .
Определим на множестве бинарное отношение выводимости следующим образом: если , то для всех
(2)
Если , то говорят, что цепочка непосредственно выводима из .
Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения , а также его степень (обозначаемые соответственно , и ). Если , то говорят, что цепочка выводима (нетривиально выводима, выводима за k шагов) из .
Если , то существует последовательность шагов
где и (3) Последовательность цепочек в этом случае называют выводом из
Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа.
Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, то есть
(3)
Грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык, то есть
(4)
Типы грамматик и их свойства
Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.
Определение. Пусть дана грамматика G = (N, T, P, S). Тогда
· если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой общего вида.
· если каждое правило грамматики имеет вид , где (5) , то ее называют грамматикой типа 1, или конкретной грамматикой.
· если каждое правило грамматики имеет вид , где (6) , то ее называют грамматикой типа 2, или контекстно-свободной
· если каждое правило грамматики имеет вид либо , либо , где (7) ,то ее называют грамматикой типа 3, или автоматической граматикой.
2.1 Разработка грамматики
Разработаем грамматику, которая согласно заданию содержит:
- процедуры Property;
- явное объявление следующих типов переменных: String переменного размера, Single, Integer, Date, Object;
- оператор объявления функций;
- описание типа переменных с помощью суффикса: Currency, Double;
- массивы переменного размера с максимальной размерностью 3;
- операторы ввода/вывода MsgBox, InputBox;
- арифметические операции: * \ + - ^ ;
- логические операции: Not, Or, Xor, Imp;
- операции сравнения;
- условные операторы типа Select Case;
- оператор цикла типа Do...While c постусловием;
- оператор присваивания; - оператор безусловного перехода;
- следующие функции: UCase, CLng, IsNothing,RegOpenKeyEx.
Разработанная грамматика имеет вид:
E = "Empty" .
Body = fProp !
DeclareApi !
DeclareArray !
InputPerem !
PrintMessage !
DeclareJavn !
DeclareSuffix !
OperIs !
OperPr !
WWCycle !
OperCSng !
OperLen !
OperIsEmpty !
OperRegCloseKey !
Goto !
elLabel !
elTextBox !
elCommandButton !
elCheckBox !
elpictureBox !
elImage !
Body1 !
E .
Body1 = Body1 Body !
Body .
Action = "Set" !
"Let" .
Access="Static" !
"Private" !
"Public" !
"Dim" !
E .
Ptype = "As_String" !
"As_Boolean" !
"As_Integer" !
"As_Single" !
"As_Byte" !
"As_Variant" !
"As_Date" .
OutPrm = "By" "ident" Ptype "," OutPrm !
"By" "ident" Ptype .
PBody = Action "ident" OutPrm Ptype .
fProp = Access "Property" PBody Body "PropertyEnd" .
DeclareJavn = Access "ident" Ptype .
BiblName = "Const" .
ApiFName = "RegCloseKey" .
ApiParam = "Const" .
ApiBody = BiblName "Lib" ApiFName ApiParam .
DeclareApi = Access "Func_Declare" "ident" ApiBody Ptype .
Suffix = "date" !
"bool" .
DeclareSuffix = Access "ident" Suffix .
Dimension = "one" !
"two" !
"three" .
DeclareArray = Access "ident" "[" Dimension "]" Ptype .
Str = "string" .
Msg = Str "," Msg !
Str .
PrintMessage = "MsgBox" Msg .
InputPerem = "ident" "=" "InputBox" Msg .
AV3 = "Const" !
"ident" !
"(" AV ")" .
AV2 = AV3 "^" AV2 !
AV3 .
AV1= AV1 "*"AV2 !
AV1 "\"ArifmV2 !
AV1 "mod" AV2 !
AV2 .
AV = AV "-" AV1 !
AV1 .
BV3 = "True" !
"False" !
"(" BV ")" .
BV2 = "Not" BV2 !
BV3 .
BV1 = BV1 "Xor" BV2 !
BV1 "And" BV2 !
BV2 .
BV = BV "Eqv" BV1 !
BV1 .
Compare = "==" !
">=" !
"<=" !
"<>" !
">" !
"<" .
AVX = AV .
AVY = AV .
IsBody = AVX Compare AVY .
OperIs = "ident" "=" IsBody .
Choice = "Select_Case" "ident" .
CaseDeclare = Choice "Case" "Const" Body CaseDeclare !
"Case_Else" Body "End_Select" .
WWCycle = "While" AV Compare AV Body "Went" .
OperPr = "ident" "=" AV .
Goto = "goto" AV .
OperLen = "ident" "=" "Len" Str .
OperCSng = "ident" "=" "CSng" AV .
OperIsEmpty = "ident" "=" "IsNothing" "ident" .
OperRegCloseKey = "ident" "=" "RegCloseKey" Str .
Eog
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
**** Страница 1 ****
0000000000 0000000000 0000000000 0000000000
0000000001 1111111112 2222222223 3333333334
1234567890 1234567890 1234567890 1234567890
+----------+----------+----------+----------+
1 Empty |X XXXX | 4 >> | > | X |
2 Set | | > | | |
3 Let | | > | | |
4 Static | | > > | > | |
5 Private | | > > | > | |
6 Public | | > > | > | |
7 Dim | | > > | > | |
8 As_String |X XXXXXXX|XXXX X> > | | X |
9 As_Boolean |X XXXXXXX|XXXX X> > | | X |
10 As_Integer |X XXXXXXX|XXXX X> > | | X |
+----------+----------+----------+----------+
11 As_Single |X XXXXXXX|XXXX X> > | | X |
12 As_Byte |X XXXXXXX|XXXX X> > | | X |
13 As_Variant |X XXXXXXX|XXXX X> > | | X |
14 As_Date |X XXXXXXX|XXXX X> > | | X |
15 By | | = | | |
16 ident |X XXXX<<<|<<<<<X ><| << = | X= >>>>>|
17 , | | < | |< |
18 Property | << | | | |
19 PropertyEnd |X XXXX | X > | | X |
20 Const |5 5555XXX|XXXX 5 > | > | 5 >>>>>|
+----------+----------+----------+----------+
21 RegCloseKey | | X| |< |
22 Lib | | |< | |
23 Func_Declare | | = | | |
24 date |X XXXX | X > | | X |
25 bool |X XXXX | X > | | X |
26 one | | | >| |
27 two | | | >| |
28 three | | | >| |
29 [ | | | <<< | |
30 ] | <<<|<<<< | | |
+----------+----------+----------+----------+
31 string |X XXXX | X> > | | X |
32 MsgBox | | | |< |
33 = | | < <|= | =< |
34 InputBox | | | |< |
35 ( | | < <| | < |
36 ) |X XXXX | X > | | X >>>>>|
37 ^ | | < <| | < |
38 * | | < <| | < |
39 \ | | < <| | < |
40 mod | | < <| | < |
+----------+----------+----------+----------+
41 - | | < <| | < |
42 True | | | | > |
43 False | | | | > |
44 Not | | | | < |
45 Xor | | | | < |
46 And | | | | < |
47 Eqv | | | | < |
48 == | | X X| | X |
49 >= | | X X| | X |
50 <= | | X X| | X |
+----------+----------+----------+----------+
51 <> | | X X| | X |
52 > | | X X| | X |
53 < | | X X| | X |
54 Select_Case | | = | | |
55 Case | | =| | |
56 Case_Else |< <<<< | < | | < |
57 End_Select | | | | |
58 While | | < <| | < |
59 Went |X XXXX | X > | | X |
60 goto | | < <| | < |
+----------+----------+----------+----------+
61 Len | | | |< |
62 CSng | | < <| | < |
63 IsNothing | | = | | |
64 *FS* | | | | |
65 E |X XXXX | 4 >> | > | X |
66 Body |X XXXX | X 2 | | X |
67 fProp |X XXXX | X > | | X |
68 DeclareApi |X XXXX | X > | | X |
69 DeclareArray |X XXXX | X > | | X |
70 InputPerem |X XXXX | X > | | X |
+----------+----------+----------+----------+
71 PrintMessage |X XXXX | X > | | X |
72 DeclareJavn |X XXXX | X > | | X |
73 DeclareSuffix |X XXXX | X > | | X |
74 OperIs |X XXXX | X > | | X |
75 OperPr |X XXXX | X > | | X |
76 WWCycle |X XXXX | X > | | X |
77 OperCSng |X XXXX | X > | | X |
78 OperLen |X XXXX | X > | | X |
79 OperIsEmpty |X XXXX | X > | | X |
80 OperRegCloseKey |X XXXX | X > | | X |
+----------+----------+----------+----------+
81 Goto |X XXXX | X > | | X |
82 Body1 |5 5555 | 5 > | | 5 |
83 Action | | = | | |
84 Access | | = = | = | |
85 Ptype |X XXXXXXX|XXXX X= > | | X |
86 OutPrm | 555|5555 | | |
87 PBody |< <<<< | < | | < |
88 BiblName | | | = | |
89 ApiFName | | <| | |
90 ApiParam | XXX|XXXX | | |
+----------+----------+----------+----------+
91 ApiBody | <<<|<<<< | | |
92 Suffix |X XXXX | X > | | X |
93 Dimension | | | =| |
94 Str |X XXXX | X= > | | X |
95 Msg |X XXXX | X > | | X |
96 AV3 |X XXXX | X > | | X >=>>>|
97 AV |5 5555 | 5 > | | 5 = |
98 AV2 |X XXXX | X > | | X > >>>|
99 AV1 |X XXXX | X > | | X > ===|
100 BV3 | | | | > |
+----------+----------+----------+----------+
101 BV | | | | = |
102 BV2 | | | | > |
103 BV1 | | | | > |
104 Compare | | < <| | < |
105 AVX | | | | |
106 AVY |X XXXX | X > | | X |
107 IsBody |X XXXX | X > | | X |
108 Choice | | | | |
109 CaseDeclare | | | | |
+----------+----------+----------+----------+
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
**** Страница 2 ****
0000000000 0000000000 0000000000 0000000000
4444444445 5555555556 6666666667 7777777778
1234567890 1234567890 1234567890 1234567890
+----------+----------+----------+----------+
1 Empty | | X X>X>X| X4XXXX|XXXXXXXXXX|
2 Set | | | | |
3 Let | | | | |
4 Static | | | | |
5 Private | | | | |
6 Public | | | | |
7 Dim | | | | |
8 As_String | | X X>X>X| X4XXXX|XXXXXXXXXX|
9 As_Boolean | | X X>X>X| X4XXXX|XXXXXXXXXX|
10 As_Integer | | X X>X>X| X4XXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
11 As_Single | | X X>X>X| X4XXXX|XXXXXXXXXX|
12 As_Byte | | X X>X>X| X4XXXX|XXXXXXXXXX|
13 As_Variant | | X X>X>X| X4XXXX|XXXXXXXXXX|
14 As_Date | | X X>X>X| X4XXXX|XXXXXXXXXX|
15 By | | | | |
16 ident |> XXX|XXXX>X>X>X| X4XXXX|XXXXXXXXXX|
17 , | | | | |
18 Property | | | | |
19 PropertyEnd | | X X>X>X| X4XXXX|XXXXXXXXXX|
20 Const |> XXX|XXXX X>5>5| 5B5555|5555555555|
+----------+----------+----------+----------+
21 RegCloseKey | | | | |
22 Lib | | | | |
23 Func_Declare | | | | |
24 date | | X X>X>X| X4XXXX|XXXXXXXXXX|
25 bool | | X X>X>X| X4XXXX|XXXXXXXXXX|
26 one | | | | |
27 two | | | | |
28 three | | | | |
29 [ | | | | |
30 ] | | | | |
+----------+----------+----------+----------+
31 string | | X X>X>X| X4XXXX|XXXXXXXXXX|
32 MsgBox | | | | |
33 = | | |=== | |
34 InputBox | | | | |
35 ( | <<< | | | |
36 ) |> >>>XXX|XXXX X>X>X| X4XXXX|XXXXXXXXXX|
37 ^ | | | | |
38 * | | | | |
39 \ | | | | |
40 mod | | | | |
+----------+----------+----------+----------+
41 - | | | | |
42 True | >>> | | | |
43 False | >>> | | | |
44 Not | <<< | | | |
45 Xor | <<< | | | |
46 And | <<< | | | |
47 Eqv | <<< | | | |
48 == | | | | |
49 >= | | | | |
50 <= | | | | |
+----------+----------+----------+----------+
51 <> | | | | |
52 > | | | | |
53 < | | | | |
54 Select_Case | | | | |
55 Case | | | | |
56 Case_Else | | < <| <1<<<<|<<<<<<<<<<|
57 End_Select | | | | |
58 While | | | | |
59 Went | | X X>X>X| X4XXXX|XXXXXXXXXX|
60 goto | | | | |
+----------+----------+----------+----------+
61 Len | | | | |
62 CSng | | | | |
63 IsNothing | | | | |
64 *FS* | | | | |
65 E | | X X>X>X| X4XXXX|XXXXXXXXXX|
66 Body | | 5 52X2X| X4XXXX|XXXXXXXXXX|
67 fProp | | X X>X>X| X4XXXX|XXXXXXXXXX|
68 DeclareApi | | X X>X>X| X4XXXX|XXXXXXXXXX|
69 DeclareArray | | X X>X>X| X4XXXX|XXXXXXXXXX|
70 InputPerem | | X X>X>X| X4XXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
71 PrintMessage | | X X>X>X| X4XXXX|XXXXXXXXXX|
72 DeclareJavn | | X X>X>X| X4XXXX|XXXXXXXXXX|
73 DeclareSuffix | | X X>X>X| X4XXXX|XXXXXXXXXX|
74 OperIs | | X X>X>X| X4XXXX|XXXXXXXXXX|
75 OperPr | | X X>X>X| X4XXXX|XXXXXXXXXX|
76 WWCycle | | X X>X>X| X4XXXX|XXXXXXXXXX|
77 OperCSng | | X X>X>X| X4XXXX|XXXXXXXXXX|
78 OperLen | | X X>X>X| X4XXXX|XXXXXXXXXX|
79 OperIsEmpty | | X X>X>X| X4XXXX|XXXXXXXXXX|
80 OperRegCloseKey | | X X>X>X| X4XXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
81 Goto | | X X>X>X| X4XXXX|XXXXXXXXXX|
82 Body1 | | X X>5>5| 5B5555|5555555555|
83 Action | | | | |
84 Access | | | | |
85 Ptype | | X X>X>X| X4XXXX|XXXXXXXXXX|
86 OutPrm | | | | |
87 PBody | | < <| <1<<<<|<<<<<<<<<<|
88 BiblName | | | | |
89 ApiFName | | | | |
90 ApiParam | | | | |
+----------+----------+----------+----------+
91 ApiBody | | | | |
92 Suffix | | X X>X>X| X4XXXX|XXXXXXXXXX|
93 Dimension | | | | |
94 Str | | X X>X>X| X4XXXX|XXXXXXXXXX|
95 Msg | | X X>X>X| X4XXXX|XXXXXXXXXX|
96 AV3 |> XXX|XXXX X>X>X| X4XXXX|XXXXXXXXXX|
97 AV |= 555|555X X>5>5| 5B5555|5555555555|
98 AV2 |> XXX|XXXX X>X>X| X4XXXX|XXXXXXXXXX|
99 AV1 |> XXX|XXXX X>X>X| X4XXXX|XXXXXXXXXX|
100 BV3 | >>> | | | |
+----------+----------+----------+----------+
101 BV | = | | | |
102 BV2 | >>> | | | |
103 BV1 | ==> | | | |
104 Compare | | | | |
105 AVX | <<<|<<< | | |
106 AVY | | X X>X>X| X4XXXX|XXXXXXXXXX|
107 IsBody | | X X>X>X| X4XXXX|XXXXXXXXXX|
108 Choice | | = | | |
109 CaseDeclare | | | | |
+----------+----------+----------+----------+
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
**** Страница 3 ****
0000000000 0000000001 111111111
8888888889 9999999990 000000000
1234567890 1234567890 123456789
+----------+----------+---------+
1 Empty |XX X | | X>|
2 Set | | | |
3 Let | | | |
4 Static | | | |
5 Private | | | |
6 Public | | | |
7 Dim | | | |
8 As_String |XX X> | | X>|
9 As_Boolean |XX X> | | X>|
10 As_Integer |XX X> | | X>|
+----------+----------+---------+
11 As_Single |XX X> | | X>|
12 As_Byte |XX X> | | X>|
13 As_Variant |XX X> | | X>|
14 As_Date |XX X> | | X>|
15 By | | | |
16 ident |XX X== < |== | > X>|
17 , | = | <= | |
18 Property | < = | | |
19 PropertyEnd |XX X | | X>|
20 Const |55 5> | | > X>|
+----------+----------+---------+
21 RegCloseKey | >| = | |
22 Lib | = | | |
23 Func_Declare | | | |
24 date |XX X | | X>|
25 bool |XX X | | X>|
26 one | | | |
27 two | | | |
28 three | | | |
29 [ | | = | |
30 ] | = | | |
+----------+----------+---------+
31 string |XX X | | X>|
32 MsgBox | | <= | |
33 = | | <1<< | < = |
34 InputBox | | <= | |
35 ( | | <1<<<|1<< |
36 ) |XX X | | > X>|
37 ^ | | < = | |
38 * | | < = | |
39 \ | | < = | |
40 mod | | < = | |
+----------+----------+---------+
41 - | | < <1 | |
42 True | | | |
43 False | | | |
44 Not | | <| = |
45 Xor | | <| = |
46 And | | <| = |
47 Eqv | | <| <1 |
48 == | | X4XX | > |
49 >= | | X4XX | > |
50 <= | | X4XX | > |
+----------+----------+---------+
51 <> | | X4XX | > |
52 > | | X4XX | > |
53 < | | X4XX | > |
54 Select_Case | | | |
55 Case | | | |
56 Case_Else |<< < | | |
57 End_Select | | | |
58 While | | <1<< | |
59 Went |XX X | | X>|
60 goto | | <1<< | |
+----------+----------+---------+
61 Len | | = | |
62 CSng | | <1<< | |
63 IsNothing | | | |
64 *FS* | | | |
65 E |XX X | | X>|
66 Body |XX X | | 52|
67 fProp |XX X | | X>|
68 DeclareApi |XX X | | X>|
69 DeclareArray |XX X | | X>|
70 InputPerem |XX X | | X>|
+----------+----------+---------+
71 PrintMessage |XX X | | X>|
72 DeclareJavn |XX X | | X>|
73 DeclareSuffix |XX X | | X>|
74 OperIs |XX X | | X>|
75 OperPr |XX X | | X>|
76 WWCycle |XX X | | X>|
77 OperCSng |XX X | | X>|
78 OperLen |XX X | | X>|
79 OperIsEmpty |XX X | | X>|
80 OperRegCloseKey |XX X | | X>|
+----------+----------+---------+
81 Goto |XX X | | X>|
82 Body1 |55 5 | | X>|
83 Action | | | |
84 Access | | | |
85 Ptype |XX X> | | X>|
86 OutPrm | 2 | | |
87 PBody |<< < | | |
88 BiblName | | | |
89 ApiFName | =| | |
90 ApiParam | > | | |
+----------+----------+---------+
91 ApiBody | = | | |
92 Suffix |XX X | | X>|
93 Dimension | | | |
94 Str |XX X | | X>|
95 Msg |XX X | | X>|
96 AV3 |XX X | | > X>|
97 AV |55 5 | | 2 X>|
98 AV2 |XX X | | > X>|
99 AV1 |XX X | | > X>|
100 BV3 | | | |
+----------+----------+---------+
101 BV | | | |
102 BV2 | | | |
103 BV1 | | | |
104 Compare | | <1<< | = |
105 AVX | | | = |
106 AVY |XX X | | X>|
107 IsBody |XX X | | X>|
108 Choice | | | |
109 CaseDeclare | | | |
+----------+----------+---------+
**** ПРИМЕЧАНИЯ ****
* строка 1, столбец 16 : 4 - конфликт типа >,X
* строка 1, столбец 66 : 4 - конфликт типа >,X
* строка 8, столбец 66 : 4 - конфликт типа >,X
* строка 9, столбец 66 : 4 - конфликт типа >,X
* строка 10, столбец 66 : 4 - конфликт типа >,X
* строка 11, столбец 66 : 4 - конфликт типа >,X
* строка 12, столбец 66 : 4 - конфликт типа >,X
* строка 13, столбец 66 : 4 - конфликт типа >,X
* строка 14, столбец 66 : 4 - конфликт типа >,X
* строка 16, столбец 66 : 4 - конфликт типа >,X
* строка 19, столбец 66 : 4 - конфликт типа >,X
* строка 20, столбец 1 : 5 - конфликт типа <,X
* строка 20, столбец 4 : 5 - конфликт типа <,X
* строка 20, столбец 5 : 5 - конфликт типа <,X
* строка 20, столбец 6 : 5 - конфликт типа <,X
* строка 20, столбец 7 : 5 - конфликт типа <,X
* строка 20, столбец 16 : 5 - конфликт типа <,X
* строка 20, столбец 32 : 5 - конфликт типа <,X
* строка 20, столбец 58 : 5 - конфликт типа <,X
* строка 20, столбец 60 : 5 - конфликт типа <,X
* строка 20, столбец 65 : 5 - конфликт типа <,X
* строка 20, столбец 66 : B - конфликт типа =,<,X,>
* строка 20, столбец 67 : 5 - конфликт типа <,X
* строка 20, столбец 68 : 5 - конфликт типа <,X
* строка 20, столбец 69 : 5 - конфликт типа <,X
* строка 20, столбец 70 : 5 - конфликт типа <,X
* строка 20, столбец 71 : 5 - конфликт типа <,X
* строка 20, столбец 72 : 5 - конфликт типа <,X
* строка 20, столбец 73 : 5 - конфликт типа <,X
* строка 20, столбец 74 : 5 - конфликт типа <,X
* строка 20, столбец 75 : 5 - конфликт типа <,X
* строка 20, столбец 76 : 5 - конфликт типа <,X
* строка 20, столбец 77 : 5 - конфликт типа <,X
* строка 20, столбец 78 : 5 - конфликт типа <,X
* строка 20, столбец 79 : 5 - конфликт типа <,X
* строка 20, столбец 80 : 5 - конфликт типа <,X
* строка 20, столбец 81 : 5 - конфликт типа <,X
* строка 20, столбец 82 : 5 - конфликт типа <,X
* строка 20, столбец 84 : 5 - конфликт типа <,X
* строка 24, столбец 66 : 4 - конфликт типа >,X
* строка 25, столбец 66 : 4 - конфликт типа >,X
* строка 31, столбец 66 : 4 - конфликт типа >,X
* строка 33, столбец 97 : 1 - конфликт типа =,<
* строка 35, столбец 97 : 1 - конфликт типа =,<
* строка 35, столбец 101 : 1 - конфликт типа =,<
* строка 36, столбец 66 : 4 - конфликт типа >,X
* строка 41, столбец 99 : 1 - конфликт типа =,<
* строка 47, столбец 103 : 1 - конфликт типа =,<
* строка 48, столбец 97 : 4 - конфликт типа >,X
* строка 49, столбец 97 : 4 - конфликт типа >,X
* строка 50, столбец 97 : 4 - конфликт типа >,X
* строка 51, столбец 97 : 4 - конфликт типа >,X
* строка 52, столбец 97 : 4 - конфликт типа >,X
* строка 53, столбец 97 : 4 - конфликт типа >,X
* строка 56, столбец 66 : 1 - конфликт типа =,<
* строка 58, столбец 97 : 1 - конфликт типа =,<
* строка 59, столбец 66 : 4 - конфликт типа >,X
* строка 60, столбец 97 : 1 - конфликт типа =,<
* строка 62, столбец 97 : 1 - конфликт типа =,<
* строка 65, столбец 16 : 4 - конфликт типа >,X
* строка 65, столбец 66 : 4 - конфликт типа >,X
* строка 66, столбец 19 : 2 - конфликт типа =,>
* строка 66, столбец 54 : 5 - конфликт типа <,X
* строка 66, столбец 56 : 5 - конфликт типа <,X
* строка 66, столбец 57 : 2 - конфликт типа =,>
* строка 66, столбец 59 : 2 - конфликт типа =,>
* строка 66, столбец 66 : 4 - конфликт типа >,X
* строка 66, столбец 108 : 5 - конфликт типа <,X
* строка 66, столбец 109 : 2 - конфликт типа =,>
* строка 67, столбец 66 : 4 - конфликт типа >,X
* строка 68, столбец 66 : 4 - конфликт типа >,X
* строка 69, столбец 66 : 4 - конфликт типа >,X
* строка 70, столбец 66 : 4 - конфликт типа >,X
* строка 71, столбец 66 : 4 - конфликт типа >,X
* строка 72, столбец 66 : 4 - конфликт типа >,X
* строка 73, столбец 66 : 4 - конфликт типа >,X
* строка 74, столбец 66 : 4 - конфликт типа >,X
* строка 75, столбец 66 : 4 - конфликт типа >,X
* строка 76, столбец 66 : 4 - конфликт типа >,X
* строка 77, столбец 66 : 4 - конфликт типа >,X
* строка 78, столбец 66 : 4 - конфликт типа >,X
* строка 79, столбец 66 : 4 - конфликт типа >,X
* строка 80, столбец 66 : 4 - конфликт типа >,X
* строка 81, столбец 66 : 4 - конфликт типа >,X
* строка 82, столбец 1 : 5 - конфликт типа <,X
* строка 82, столбец 4 : 5 - конфликт типа <,X
* строка 82, столбец 5 : 5 - конфликт типа <,X
* строка 82, столбец 6 : 5 - конфликт типа <,X
* строка 82, столбец 7 : 5 - конфликт типа <,X
* строка 82, столбец 16 : 5 - конфликт типа <,X
* строка 82, столбец 32 : 5 - конфликт типа <,X
* строка 82, столбец 58 : 5 - конфликт типа <,X
* строка 82, столбец 60 : 5 - конфликт типа <,X
* строка 82, столбец 65 : 5 - конфликт типа <,X
* строка 82, столбец 66 : B - конфликт типа =,<,X,>
* строка 82, столбец 67 : 5 - конфликт типа <,X
* строка 82, столбец 68 : 5 - конфликт типа <,X
* строка 82, столбец 69 : 5 - конфликт типа <,X
* строка 82, столбец 70 : 5 - конфликт типа <,X
* строка 82, столбец 71 : 5 - конфликт типа <,X
* строка 82, столбец 72 : 5 - конфликт типа <,X
* строка 82, столбец 73 : 5 - конфликт типа <,X
* строка 82, столбец 74 : 5 - конфликт типа <,X
* строка 82, столбец 75 : 5 - конфликт типа <,X
* строка 82, столбец 76 : 5 - конфликт типа <,X
* строка 82, столбец 77 : 5 - конфликт типа <,X
* строка 82, столбец 78 : 5 - конфликт типа <,X
* строка 82, столбец 79 : 5 - конфликт типа <,X
* строка 82, столбец 80 : 5 - конфликт типа <,X
* строка 82, столбец 81 : 5 - конфликт типа <,X
* строка 82, столбец 82 : 5 - конфликт типа <,X
* строка 82, столбец 84 : 5 - конфликт типа <,X
* строка 85, столбец 66 : 4 - конфликт типа >,X
* строка 86, столбец 8 : 5 - конфликт типа <,X
* строка 86, столбец 9 : 5 - конфликт типа <,X
* строка 86, столбец 10 : 5 - конфликт типа <,X
* строка 86, столбец 11 : 5 - конфликт типа <,X
* строка 86, столбец 12 : 5 - конфликт типа <,X
* строка 86, столбец 13 : 5 - конфликт типа <,X
* строка 86, столбец 14 : 5 - конфликт типа <,X
* строка 86, столбец 85 : 2 - конфликт типа =,>
* строка 87, столбец 66 : 1 - конфликт типа =,<
* строка 92, столбец 66 : 4 - конфликт типа >,X
* строка 94, столбец 66 : 4 - конфликт типа >,X
* строка 95, столбец 66 : 4 - конфликт типа >,X
* строка 96, столбец 66 : 4 - конфликт типа >,X
* строка 97, столбец 1 : 5 - конфликт типа <,X
* строка 97, столбец 4 : 5 - конфликт типа <,X
* строка 97, столбец 5 : 5 - конфликт типа <,X
* строка 97, столбец 6 : 5 - конфликт типа <,X
* строка 97, столбец 7 : 5 - конфликт типа <,X
* строка 97, столбец 16 : 5 - конфликт типа <,X
* строка 97, столбец 32 : 5 - конфликт типа <,X
* строка 97, столбец 48 : 5 - конфликт типа <,X
* строка 97, столбец 49 : 5 - конфликт типа <,X
* строка 97, столбец 50 : 5 - конфликт типа <,X
* строка 97, столбец 51 : 5 - конфликт типа <,X
* строка 97, столбец 52 : 5 - конфликт типа <,X
* строка 97, столбец 53 : 5 - конфликт типа <,X
* строка 97, столбец 58 : 5 - конфликт типа <,X
* строка 97, столбец 60 : 5 - конфликт типа <,X
* строка 97, столбец 65 : 5 - конфликт типа <,X
* строка 97, столбец 66 : B - конфликт типа =,<,X,>
* строка 97, столбец 67 : 5 - конфликт типа <,X
* строка 97, столбец 68 : 5 - конфликт типа <,X
* строка 97, столбец 69 : 5 - конфликт типа <,X
* строка 97, столбец 70 : 5 - конфликт типа <,X
* строка 97, столбец 71 : 5 - конфликт типа <,X
* строка 97, столбец 72 : 5 - конфликт типа <,X
* строка 97, столбец 73 : 5 - конфликт типа <,X
* строка 97, столбец 74 : 5 - конфликт типа <,X
* строка 97, столбец 75 : 5 - конфликт типа <,X
* строка 97, столбец 76 : 5 - конфликт типа <,X
* строка 97, столбец 77 : 5 - конфликт типа <,X
* строка 97, столбец 78 : 5 - конфликт типа <,X
* строка 97, столбец 79 : 5 - конфликт типа <,X
* строка 97, столбец 80 : 5 - конфликт типа <,X
* строка 97, столбец 81 : 5 - конфликт типа <,X
* строка 97, столбец 82 : 5 - конфликт типа <,X
* строка 97, столбец 84 : 5 - конфликт типа <,X
* строка 97, столбец 104 : 2 - конфликт типа =,>
* строка 98, столбец 66 : 4 - конфликт типа >,X
* строка 99, столбец 66 : 4 - конфликт типа >,X
* строка 104, столбец 97 : 1 - конфликт типа =,<
* строка 106, столбец 66 : 4 - конфликт типа >,X
* строка 107, столбец 66 : 4 - конфликт типа >,X
Общее количество конфликтов : 166
2.2 Разрешение конфликтов
В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.
Для разрешения конфликтов применяеться отладка грамматики. При этом за счет расширения грамматики стараються избежать неоднозначных веток порождающих конфликты.
Грамматика называеться бескофликтной когда она не содержит ни одного конфликта предшествования
2.2.1 Конфликт типа =,<
и полученная новая грамматика
ArifmV1 "mod" AV2 !
AV2 .
AV = AV "-" ZamArf1 !
AV1 .
ZamArf1 = AV1 .
Аналогично разрешим остальные конфликты типа =,<
2.2.2 Конфликт типа =,>
WWCycle = "While" AV Compare AV Body "Went" .
…
AVX = AV .
AVY = AV .
IsBody = AVX Compare AVY .
WWCycle = "While" ArifmV Compare ZamArf Body "Went" .
…
ZamArf = AV
AVX = AV .
AVY = AV .
IsBody = AVX Compare AVY .
Отлаженная грамматика
E = "Empty" .
Body = fProp !
DeclareApi !
DeclareArray !
InputPerem !
PrintMessage !
DeclareJavn !
DeclareSuffix !
OperIs !
OperPr !
WWCycle !
OperCSng !
OperLen !
OperIsEmpty !
OperRegCloseKey !
Goto !
elLabel !
elTextBox !
elCommandButton !
elCheckBox !
elpictureBox !
elImage !
Body1 !
E .
zBody1 = Body1 .
Body1 = zBody1 zamBody !
Body .
zamBody = Body .
Action = "Set" !
"Let" .
Access="Static" !
"Private" !
"Public" !
"Dim" !
E .
Ptype = "As_String" !
"As_Boolean" !
"As_Integer" !
"As_Single" !
"As_Byte" !
"As_Variant" !
"As_Date" .
OutPrm = "By" "ident" Ptype "," z1OutPrm !
"By" "ident" Ptype .
z1OutPrm = OutPrm .
z2OutPrm = OutPrm .
PBody = Action "ident" z2OutPrm Ptype .
fProp = Access "Property" zPBody zBody "PropertyEnd" .
zPBody = PBody .
DeclareJavn = Access "ident" Ptype .
BiblName = Const1 .
Const1 = "Const" .
ApiFName = "RegCloseKey" .
ApiParam = Const1 .
ApiBody = BiblName "Lib" ApiFName ApiParam .
DeclareApi = Access "Func_Declare" "ident" ApiBody Ptype .
Suffix = "date" !
"bool" .
DeclareSuffix = Access "ident" Suffix .
Dimension = "one" !
"two" !
"three" .
DeclareArray = Access "ident" "[" Dimension "]" Ptype .
Str = "string" .
Msg = Str "," Msg !
Str .
PrintMessage = "MsgBox" Msg .
InputPerem = "ident" "=" "InputBox" Msg .
AV3 = "Const" !
"ident" !
"(" zamAV ")" .
zamAV = AV .
AV2 = AV3 "^" AV2 !
AV3 .
AV1= AV1 "*"AV2 !
AV1 "\"AV2 !
AV1 "mod" AV2 !
AV2 .
AV = AV "-" zamAV1 !
AV1 .
zamAV1 = AV1 .
BV3 = "True" !
"False" !
"(" zamBV ")" .
zamBV = BV .
BV2 = "Not" BV2 !
BV3 .
BV1 = BV1 "Xor" BV2 !
BV1 "And" BV2 !
BV2 .
BV = BV "Eqv" zamBV1 !
BV1 .
zamBV1 = BV1 .
Compare = "==" !
">=" !
"<=" !
"<>" !
">" !
"<" .
AVX = zAV .
AVY = zAV .
IsBody = AVX zCompare AVY .
zCompare = Compare .
OperIs = "ident" "=" IsBody .
Choice = "Select_Case" "ident" .
CaseDeclare = Choice "Case" Const1 zBody CaseDeclare !
"Case_Else" zBody "End_Select" .
WWCycle = "While" z1AV zCompare z2AV zBody "Went" .
zBody = Body .
OperPr = "ident" "=" z3AV .
Goto = "goto" z4AV .
zAV = AV .
z1AV = AV .
z2AV = AV .
z3AV = AV .
z4AV = AV .
OperLen = "ident" "=" "Len" Str .
OperCSng = "ident" "=" "CSng" zAV .
OperIsEmpty = "ident" "=" "IsNothing" "ident" .
OperRegCloseKey = "ident" "=" "RegCloseKey" Str .
Eog
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
**** Страница 1 ****
0000000000 0000000000 0000000000 0000000000
0000000001 1111111112 2222222223 3333333334
1234567890 1234567890 1234567890 1234567890
+----------+----------+----------+----------+
1 Empty |X XXXX | > >> | > | X |
2 Set | | > | | |
3 Let | | > | | |
4 Static | | > > | > | |
5 Private | | > > | > | |
6 Public | | > > | > | |
7 Dim | | > > | > | |
8 As_String |X XXXXXXX|XXXX X> > | | X |
9 As_Boolean |X XXXXXXX|XXXX X> > | | X |
10 As_Integer |X XXXXXXX|XXXX X> > | | X |
+----------+----------+----------+----------+
11 As_Single |X XXXXXXX|XXXX X> > | | X |
12 As_Byte |X XXXXXXX|XXXX X> > | | X |
13 As_Variant |X XXXXXXX|XXXX X> > | | X |
14 As_Date |X XXXXXXX|XXXX X> > | | X |
15 By | | = | | |
16 ident |X XXXX<<<|<<<<<X ><| << = | X= >>>>>|
17 , | | < | |< |
18 Property | << | | | |
19 PropertyEnd |X XXXX | X > | | X |
20 Const |X XXXXXXX|XXXX X > | > | X >>>>>|
+----------+----------+----------+----------+
21 RegCloseKey | | X| |< |
22 Lib | | |< | |
23 Func_Declare | | = | | |
24 date |X XXXX | X > | | X |
25 bool |X XXXX | X > | | X |
26 one | | | >| |
27 two | | | >| |
28 three | | | >| |
29 [ | | | <<< | |
30 ] | <<<|<<<< | | |
+----------+----------+----------+----------+
31 string |X XXXX | X> > | | X |
32 MsgBox | | | |< |
33 = | | < <|= | =< |
34 InputBox | | | |< |
35 ( | | < <| | < |
36 ) |X XXXX | X > | | X >>>>>|
37 ^ | | < <| | < |
38 * | | < <| | < |
39 \ | | < <| | < |
40 mod | | < <| | < |
+----------+----------+----------+----------+
41 - | | < <| | < |
42 True | | | | > |
43 False | | | | > |
44 Not | | | | < |
45 Xor | | | | < |
46 And | | | | < |
47 Eqv | | | | < |
48 == | | X X| | X |
49 >= | | X X| | X |
50 <= | | X X| | X |
+----------+----------+----------+----------+
51 <> | | X X| | X |
52 > | | X X| | X |
53 < | | X X| | X |
54 Select_Case | | = | | |
55 Case | | <| | |
56 Case_Else |< <<<< | < | | < |
57 End_Select | | | | |
58 While | | < <| | < |
59 Went |X XXXX | X > | | X |
60 goto | | < <| | < |
+----------+----------+----------+----------+
61 Len | | | |< |
62 CSng | | < <| | < |
63 IsNothing | | = | | |
64 *FS* | | | | |
65 E |X XXXX | > >> | > | X |
66 Body |X XXXX | X > | | X |
67 fProp |X XXXX | X > | | X |
68 DeclareApi |X XXXX | X > | | X |
69 DeclareArray |X XXXX | X > | | X |
70 InputPerem |X XXXX | X > | | X |
+----------+----------+----------+----------+
71 PrintMessage |X XXXX | X > | | X |
72 DeclareJavn |X XXXX | X > | | X |
73 DeclareSuffix |X XXXX | X > | | X |
74 OperIs |X XXXX | X > | | X |
75 OperPr |X XXXX | X > | | X |
76 WWCycle |X XXXX | X > | | X |
77 OperCSng |X XXXX | X > | | X |
78 OperLen |X XXXX | X > | | X |
79 OperIsEmpty |X XXXX | X > | | X |
80 OperRegCloseKey |X XXXX | X > | | X |
+----------+----------+----------+----------+
81 Goto |X XXXX | X > | | X |
82 Body1 |X XXXX | X > | | X |
83 zBody1 |< <<<< | < | | < |
84 zamBody |X XXXX | X > | | X |
85 Action | | = | | |
86 Access | | = = | = | |
87 Ptype |X XXXXXXX|XXXX X= > | | X |
88 OutPrm | XXX|XXXX | | |
89 z1OutPrm | XXX|XXXX | | |
90 z2OutPrm | <<<|<<<< | | |
+----------+----------+----------+----------+
91 PBody |X XXXX | X | | X |
92 zPBody |< <<<< | < | | < |
93 zBody | | = | | |
94 BiblName | | | = | |
95 Const1 |< <<<<XXX|XXXX < | > | < |
96 ApiFName | | <| | |
97 ApiParam | XXX|XXXX | | |
98 ApiBody | <<<|<<<< | | |
99 Suffix |X XXXX | X > | | X |
100 Dimension | | | =| |
+----------+----------+----------+----------+
101 Str |X XXXX | X= > | | X |
102 Msg |X XXXX | X > | | X |
103 AV3 |X XXXX | X > | | X >=>>>|
104 zamAV | | | | = |
105 AV |X XXXX | X > | | X > |
106 AV2 |X XXXX | X > | | X > >>>|
107 AV1 |X XXXX | X > | | X > ===|
108 zamAV1 |X XXXX | X > | | X > |
109 BV3 | | | | > |
110 zamBV | | | | = |
+----------+----------+----------+----------+
111 BV | | | | > |
112 BV2 | | | | > |
113 BV1 | | | | > |
114 zamBV1 | | | | > |
115 Compare | | X X| | X |
116 AVX | | | | |
117 zAV |X XXXX | X > | | X |
118 AVY |X XXXX | X > | | X |
119 IsBody |X XXXX | X > | | X |
120 zCompare | | < <| | < |
+----------+----------+----------+----------+
121 Choice | | | | |
122 CaseDeclare | | | | |
123 z1AV | | | | |
124 z2AV |< <<<< | < | | < |
125 z3AV |X XXXX | X > | | X |
126 z4AV |X XXXX | X > | | X |
+----------+----------+----------+----------+
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
**** Страница 2 ****
0000000000 0000000000 0000000000 0000000000
4444444445 5555555556 6666666667 7777777778
1234567890 1234567890 1234567890 1234567890
+----------+----------+----------+----------+
1 Empty | | X X>X>X| XXXXXX|XXXXXXXXXX|
2 Set | | | | |
3 Let | | | | |
4 Static | | | | |
5 Private | | | | |
6 Public | | | | |
7 Dim | | | | |
8 As_String | | X X>X>X| XXXXXX|XXXXXXXXXX|
9 As_Boolean | | X X>X>X| XXXXXX|XXXXXXXXXX|
10 As_Integer | | X X>X>X| XXXXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
11 As_Single | | X X>X>X| XXXXXX|XXXXXXXXXX|
12 As_Byte | | X X>X>X| XXXXXX|XXXXXXXXXX|
13 As_Variant | | X X>X>X| XXXXXX|XXXXXXXXXX|
14 As_Date | | X X>X>X| XXXXXX|XXXXXXXXXX|
15 By | | | | |
16 ident |> XXX|XXXX>X>X>X| XXXXXX|XXXXXXXXXX|
17 , | | | | |
18 Property | | | | |
19 PropertyEnd | | X X>X>X| XXXXXX|XXXXXXXXXX|
20 Const |> XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
21 RegCloseKey | | | | |
22 Lib | | | | |
23 Func_Declare | | | | |
24 date | | X X>X>X| XXXXXX|XXXXXXXXXX|
25 bool | | X X>X>X| XXXXXX|XXXXXXXXXX|
26 one | | | | |
27 two | | | | |
28 three | | | | |
29 [ | | | | |
30 ] | | | | |
+----------+----------+----------+----------+
31 string | | X X>X>X| XXXXXX|XXXXXXXXXX|
32 MsgBox | | | | |
33 = | | |=== | |
34 InputBox | | | | |
35 ( | <<< | | | |
36 ) |> >>>XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
37 ^ | | | | |
38 * | | | | |
39 \ | | | | |
40 mod | | | | |
+----------+----------+----------+----------+
41 - | | | | |
42 True | >>> | | | |
43 False | >>> | | | |
44 Not | <<< | | | |
45 Xor | <<< | | | |
46 And | <<< | | | |
47 Eqv | <<< | | | |
48 == | | | | |
49 >= | | | | |
50 <= | | | | |
+----------+----------+----------+----------+
51 <> | | | | |
52 > | | | | |
53 < | | | | |
54 Select_Case | | | | |
55 Case | | | | |
56 Case_Else | | < <| <<<<<<|<<<<<<<<<<|
57 End_Select | | | | |
58 While | | | | |
59 Went | | X X>X>X| XXXXXX|XXXXXXXXXX|
60 goto | | | | |
+----------+----------+----------+----------+
61 Len | | | | |
62 CSng | | | | |
63 IsNothing | | | | |
64 *FS* | | | | |
65 E | | X X>X>X| XXXXXX|XXXXXXXXXX|
66 Body | | X X>X>X| XXXXXX|XXXXXXXXXX|
67 fProp | | X X>X>X| XXXXXX|XXXXXXXXXX|
68 DeclareApi | | X X>X>X| XXXXXX|XXXXXXXXXX|
69 DeclareArray | | X X>X>X| XXXXXX|XXXXXXXXXX|
70 InputPerem | | X X>X>X| XXXXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
71 PrintMessage | | X X>X>X| XXXXXX|XXXXXXXXXX|
72 DeclareJavn | | X X>X>X| XXXXXX|XXXXXXXXXX|
73 DeclareSuffix | | X X>X>X| XXXXXX|XXXXXXXXXX|
74 OperIs | | X X>X>X| XXXXXX|XXXXXXXXXX|
75 OperPr | | X X>X>X| XXXXXX|XXXXXXXXXX|
76 WWCycle | | X X>X>X| XXXXXX|XXXXXXXXXX|
77 OperCSng | | X X>X>X| XXXXXX|XXXXXXXXXX|
78 OperLen | | X X>X>X| XXXXXX|XXXXXXXXXX|
79 OperIsEmpty | | X X>X>X| XXXXXX|XXXXXXXXXX|
80 OperRegCloseKey | | X X>X>X| XXXXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
81 Goto | | X X>X>X| XXXXXX|XXXXXXXXXX|
82 Body1 | | X X>X>X| XXXXXX|XXXXXXXXXX|
83 zBody1 | | < <| <<<<<<|<<<<<<<<<<|
84 zamBody | | X X>X>X| XXXXXX|XXXXXXXXXX|
85 Action | | | | |
86 Access | | | | |
87 Ptype | | X X>X>X| XXXXXX|XXXXXXXXXX|
88 OutPrm | | | | |
89 z1OutPrm | | | | |
90 z2OutPrm | | | | |
+----------+----------+----------+----------+
91 PBody | | X X| XXXXXX|XXXXXXXXXX|
92 zPBody | | < <| <<<<<<|<<<<<<<<<<|
93 zBody | | < <= = | | |
94 BiblName | | | | |
95 Const1 | | < <| <<<<<<|<<<<<<<<<<|
96 ApiFName | | | | |
97 ApiParam | | | | |
98 ApiBody | | | | |
99 Suffix | | X X>X>X| XXXXXX|XXXXXXXXXX|
100 Dimension | | | | |
+----------+----------+----------+----------+
101 Str | | X X>X>X| XXXXXX|XXXXXXXXXX|
102 Msg | | X X>X>X| XXXXXX|XXXXXXXXXX|
103 AV3 |> XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
104 zamAV | | | | |
105 AV |= XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
106 AV2 |> XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
107 AV1 |> XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
108 zamAV1 |> XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
109 BV3 | >>> | | | |
110 zamBV | | | | |
+----------+----------+----------+----------+
111 BV | = | | | |
112 BV2 | >>> | | | |
113 BV1 | ==> | | | |
114 zamBV1 | > | | | |
115 Compare | | | | |
116 AVX | <<<|<<< | | |
117 zAV | XXX|XXXX X>X>X| XXXXXX|XXXXXXXXXX|
118 AVY | | X X>X>X| XXXXXX|XXXXXXXXXX|
119 IsBody | | X X>X>X| XXXXXX|XXXXXXXXXX|
120 zCompare | | | | |
+----------+----------+----------+----------+
121 Choice | | = | | |
122 CaseDeclare | | | | |
123 z1AV | <<<|<<< | | |
124 z2AV | | < <| <<<<<<|<<<<<<<<<<|
125 z3AV | | X X>X>X| XXXXXX|XXXXXXXXXX|
126 z4AV | | X X>X>X| XXXXXX|XXXXXXXXXX|
+----------+----------+----------+----------+
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
Подобные документы
Разработка формальной грамматики для выражений, содержащих: логические и арифметические операции, константы, идентификаторы, знаки отношений и т.д., ее отладка в соответствии с требованиями метода параллельного предшествования. Разработка сканера.
контрольная работа [45,8 K], добавлен 24.09.2010Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Основные понятия теории грамматик простого и операторного предшествования, алгоритмы синтаксического разбора предложения для классов КС-грамматик; разработка дерева вывода для грамматики входного языка в форме Бэкуса-Наура с указанием шагов построения.
лабораторная работа [28,0 K], добавлен 24.07.2012Модели параллельного программирования; отладка параллельных программ. Реализация экспериментальной версии системы сравнительной отладки Fortran-OpenMP программ: получение, сбор и запись трассы, инструментарий программ, используемый формат файлов трассы.
дипломная работа [92,8 K], добавлен 17.10.2013Содержательная и формальная (математическая) постановка задачи. Разработка алгоритма решения задачи. Структуры программы и алгоритмы программных модулей, их описание. Решение задачи на конкретном примере. Разработка системы тестов и отладка программы.
курсовая работа [882,1 K], добавлен 24.11.2014Роль информационных технологий в быту. Теоретические аспекты формальных грамматик и их преобразование, алфавит нетерминалов. Распознаватель для преобразованной грамматики и реализация его в виде программы для проверки текстовых файлов и вводимых цепочек.
курсовая работа [129,4 K], добавлен 15.06.2009Применение правил грамматики. Синтаксический анализатор, нис- и восходящий разбор, полный перебор правил подстановки. Классификация грамматик по Хомскому. Определение языков с помощью автоматов. Форма Бекуса-Наура описания синтаксиса формальных языков.
лекция [270,1 K], добавлен 19.10.2014Отладка - процесс обнаружения, устранения синтаксических и семантических ошибок. Точки отслеживания (трассировки). Выполнение отладки в режиме останова. Мониторинг содержимого переменных. Пошаговое выполнение кода. Разработка тестов для отладки программы.
презентация [743,6 K], добавлен 09.12.2013Тестирование и отладка программного обеспечения: понятие, принципы, этапы, цели и задачи. Тестирование методом сандвича как компромисс между восходящим и нисходящим подходами. Сущность метода "белого и черного ящика", отладки программного обеспечения.
курсовая работа [36,9 K], добавлен 21.07.2012Основные стадии разработки, принципы тестирования и отладка программного модуля "VFS". Особенности проектирования на языке UML. Методы "грубой силы" и их применение при отладке программы. Вредные факторы, присутствующие на рабочем месте программиста.
дипломная работа [827,0 K], добавлен 07.03.2012
