Разработка и отладка формальных грамматик
Разработка и отладка обобщенных автоматов, формальных грамматик, реализация синтаксического анализа, а также решение практических вопросов проектирования программных продуктов. Отладка разработанной грамматики для метода параллельного предшествования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 25.11.2010 |
| Размер файла | 559,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
**** Страница 3 ****
0000000000 0000000001 1111111111 1111111111
8888888889 9999999990 0000000001 1111111112
1234567890 1234567890 1234567890 1234567890
+----------+----------+----------+----------+
1 Empty |XXX> X | | | |
2 Set | | | | |
3 Let | | | | |
4 Static | | | | |
5 Private | | | | |
6 Public | | | | |
7 Dim | | | | |
8 As_String |XXX> X> | > | | |
9 As_Boolean |XXX> X> | > | | |
10 As_Integer |XXX> X> | > | | |
+----------+----------+----------+----------+
11 As_Single |XXX> X> | > | | |
12 As_Byte |XXX> X> | > | | |
13 As_Variant |XXX> X> | > | | |
14 As_Date |XXX> X> | > | | |
15 By | | | | |
16 ident |XXX> X=< =| ><< == | | X >|
17 , | <= | |<= | |
18 Property | < |<= | | |
19 PropertyEnd |XXX> X | | | |
20 Const |XXX> X> | > | | X >|
+----------+----------+----------+----------+
21 RegCloseKey | | X > |= | |
22 Lib | | = | | |
23 Func_Declare | | | | |
24 date |XXX> X | | | |
25 bool |XXX> X | | | |
26 one | | | | |
27 two | | | | |
28 three | | | | |
29 [ | | =| | |
30 ] | = | | | |
+----------+----------+----------+----------+
31 string |XXX> X | | | |
32 MsgBox | | |<= | |
33 = | | | < <<< | << = |
34 InputBox | | |<= | |
35 ( | | | <=<<< <=|<<< |
36 ) |XXX> X | > | | X >|
37 ^ | | | < = | |
38 * | | | < = | |
39 \ | | | < = | |
40 mod | | | < = | |
+----------+----------+----------+----------+
41 - | | | < <<= | |
42 True | | | | |
43 False | | | | |
44 Not | | | < | = |
45 Xor | | | < | = |
46 And | | | < | = |
47 Eqv | | | < | <<= |
48 == | | | X XXX | X> |
49 >= | | | X XXX | X> |
50 <= | | | X XXX | X> |
+----------+----------+----------+----------+
51 <> | | | X XXX | X> |
52 > | | | X XXX | X> |
53 < | | | X XXX | X> |
54 Select_Case | | | | |
55 Case | | = | | |
56 Case_Else |<<< < | = | | |
57 End_Select | | | | |
58 While | | | < <<< | |
59 Went |XXX> X | | | |
60 goto | | | < <<< | |
+----------+----------+----------+----------+
61 Len | | |= | |
62 CSng | | | < <<< | = |
63 IsNothing | | | | |
64 *FS* | | | | |
65 E |XXX> X | | | |
66 Body |XXX> X | | | |
67 fProp |XXX> X | | | |
68 DeclareApi |XXX> X | | | |
69 DeclareArray |XXX> X | | | |
70 InputPerem |XXX> X | | | |
+----------+----------+----------+----------+
71 PrintMessage |XXX> X | | | |
72 DeclareJavn |XXX> X | | | |
73 DeclareSuffix |XXX> X | | | |
74 OperIs |XXX> X | | | |
75 OperPr |XXX> X | | | |
76 WWCycle |XXX> X | | | |
77 OperCSng |XXX> X | | | |
78 OperLen |XXX> X | | | |
79 OperIsEmpty |XXX> X | | | |
80 OperRegCloseKey |XXX> X | | | |
+----------+----------+----------+----------+
81 Goto |XXX> X | | | |
82 Body1 |XXX> X | | | |
83 zBody1 |<<<= < | | | |
84 zamBody |XXX> X | | | |
85 Action | | | | |
86 Access | | | | |
87 Ptype |XXX> X> | > | | |
88 OutPrm | > | | | |
89 z1OutPrm | > | | | |
90 z2OutPrm | = | | | |
+----------+----------+----------+----------+
91 PBody |XXX X | > | | |
92 zPBody |<<< < | = | | |
93 zBody | | | | |
94 BiblName | | | | |
95 Const1 |<<< <> | = | | |
96 ApiFName | | < = | | |
97 ApiParam | > | | | |
98 ApiBody | = | | | |
99 Suffix |XXX> X | | | |
100 Dimension | | | | |
+----------+----------+----------+----------+
101 Str |XXX> X | | | |
102 Msg |XXX> X | | | |
103 AV3 |XXX> X | > | | X >|
104 zamAV | | | | |
105 AV |XXX> X | > | | X >|
106 AV2 |XXX> X | > | | X >|
107 AV1 |XXX> X | > | | X >|
108 zamAV1 |XXX> X | > | | X >|
109 BV3 | | | | |
110 zamBV | | | | |
+----------+----------+----------+----------+
111 BV | | | | |
112 BV2 | | | | |
113 BV1 | | | | |
114 zamBV1 | | | | |
115 Compare | | | X XXX | X> |
116 AVX | | | | < =|
117 zAV |XXX> X | | | X >|
118 AVY |XXX> X | | | |
119 IsBody |XXX> X | | | |
120 zCompare | | | < <<< | <= |
+----------+----------+----------+----------+
121 Choice | | | | |
122 CaseDeclare | | | | |
123 z1AV | | | | < =|
124 z2AV |<<< < | = | | |
125 z3AV |XXX> X | | | |
126 z4AV |XXX> X | | | |
+----------+----------+----------+----------+
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ИСХОДНОЙ ГРАММАТИКИ.
**** Страница 4 ****
111111
222222
123456
+------+
1 Empty |X> |
2 Set | |
3 Let | |
4 Static | |
5 Private | |
6 Public | |
7 Dim | |
8 As_String |X> |
9 As_Boolean |X> |
10 As_Integer |X> |
+------+
11 As_Single |X> |
12 As_Byte |X> |
13 As_Variant |X> |
14 As_Date |X> |
15 By | |
16 ident |X> |
17 , | |
18 Property | |
19 PropertyEnd |X> |
20 Const |X> |
+------+
21 RegCloseKey | |
22 Lib | |
23 Func_Declare | |
24 date |X> |
25 bool |X> |
26 one | |
27 two | |
28 three | |
29 [ | |
30 ] | |
+------+
31 string |X> |
32 MsgBox | |
33 = | = |
34 InputBox | |
35 ( | |
36 ) |X> |
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> |
60 goto | =|
+------+
61 Len | |
62 CSng | |
63 IsNothing | |
64 *FS* | |
65 E |X> |
66 Body |X> |
67 fProp |X> |
68 DeclareApi |X> |
69 DeclareArray |X> |
70 InputPerem |X> |
+------+
71 PrintMessage |X> |
72 DeclareJavn |X> |
73 DeclareSuffix |X> |
74 OperIs |X> |
75 OperPr |X> |
76 WWCycle |X> |
77 OperCSng |X> |
78 OperLen |X> |
79 OperIsEmpty |X> |
80 OperRegCloseKey |X> |
+------+
81 Goto |X> |
82 Body1 |X> |
83 zBody1 | |
84 zamBody |X> |
85 Action | |
86 Access | |
87 Ptype |X> |
88 OutPrm | |
89 z1OutPrm | |
90 z2OutPrm | |
+------+
91 PBody | |
92 zPBody | |
93 zBody |<= |
94 BiblName | |
95 Const1 | |
96 ApiFName | |
97 ApiParam | |
98 ApiBody | |
99 Suffix |X> |
100 Dimension | |
+------+
101 Str |X> |
102 Msg |X> |
103 AV3 |X> |
104 zamAV | |
105 AV |X> |
106 AV2 |X> |
107 AV1 |X> |
108 zamAV1 |X> |
109 BV3 | |
110 zamBV | |
+------+
111 BV | |
112 BV2 | |
113 BV1 | |
114 zamBV1 | |
115 Compare | > |
116 AVX | |
117 zAV |X> |
118 AVY |X> |
119 IsBody |X> |
120 zCompare | = |
+------+
121 Choice | |
122 CaseDeclare | |
123 z1AV | |
124 z2AV | |
125 z3AV |X> |
126 z4AV |X> |
+------+
2.3 Синтаксическое дерево для тестовой цепочки
На листе А1
3. Разработка сканера
Лексический анализ
Основная задача лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, то есть выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться ("\" в конце строки внутри "...").
Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова - это некоторое конечное подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического.
Для осуществления двух дальнейших фаз анализа лексический анализатор выдает информацию двух типов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализатора, работающего вслед за синтаксическим, существенна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.).
Таким образом, общая схема работы лексического анализатора такова. Сначала выделяется отдельная лексема (при этом, возможно, используются символы- разделители). Ключевые слова распознаются явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых слов.
Если выделенная лексема является ограничителем, то этот ограничитель (точнее, некоторый его признак) выдается как результат лексического анализа. Если выделенная лексема является ключевым словом, то выдается признак соответствующего ключевого слова. Если выделенная лексема является идентификатором - выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно.
Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либо праволинейная грамматика. Все три формализма (конечных автоматов, регулярных выражений и праволинейных грамматик) имеют одинаковую выразительную мощность. В частности, по регулярному выражению или праволинейной грамматике можно сконструировать конечный автомат, распознающий тот же язык.
Конечные автоматы
Регулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы. Недетерминированный конечный автомат (НКА) - по определению есть пятерка M = (Q, T, D, q0, F), где
1. Q - конечное множество состояний,
2. T - конечное множество допустимых входных символов (входной алфавит),
3. D - функция переходов (отображающая множество во множество подмножеств множества Q), определяющая поведение управляющего устройства,
4. - начальное состояние управляющего устройства,
5. - множество заключительных состояний.
Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо
Пусть G = (N, T, P, S) - КС-грамматика. Введем несколько важных понятий и определений.
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S* u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определим правосторонний вывод. Обозначим шаги левого (правого) вывода l (r).
Упорядоченным графом называется пара (V,E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ... , (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершинуv2, и т.д.
Упорядоченным помеченным деревом называется упорядоченный граф (V,E), основой которого является дерево и для которого определена функция f : V F (функция разметки) для некоторого множества F.
Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:
(1) корень дерева D помечен S;
(2) каждый лист помечен либо , либо e;
(3) каждая внутренняя вершина помечена нетерминалом ;
(4) если X - нетерминал, которым помечена внутренняя вершина и X1, ... , Xn - метки ее прямых потомков в указанном порядке, то X X1 ... Xk - правило из множества P;
(5) Цепочка, составленная из выписанных слева направо меток листьев, равна w.
Процесс определения принадлежности данной строки языку, порождаемому данной грамматикой, и, в случае указанной принадлежности, построение дерева разбора для этой строки, называется синтаксическим анализом. Можно говорить о восстановлении дерева вывода (в частности, правостороннего или левостороннего) для строки, принадлежащей языку. По восстановленному выводу можно строить дерево разбора.
Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.
Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что для некоторой цепочки R существует вывод A + A. автомат обобщенный формальный грамматика предшествование
Организация таблиц символов
В процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов. Как правило, информация о каждом объекте состоит из двух основных элементов: имени объекта и описания объекта. Информация об объектах программы должна быть организована таким образом, чтобы поиск ее был по возможности быстрее, а требуемая память по возможности меньше.
Кроме того, со стороны языка программирования могут быть дополнительные требования к организации информации. Имена могут иметь определенную область видимости. Например, поле записи должно быть уникально в пределах структуры (или уровня структуры), но может совпадать с именем объекта вне записи (или другого уровня записи). В то же время имя поля может открываться оператором присоединения, и тогда может возникнуть конфликт имен (или неоднозначность в трактовке имени). Если язык имеет блочную структуру, то необходимо обеспечить такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости, а во-вторых - эффективно освобождать память при выходе из блока. В некоторых языках (например, Аде) одновременно (в одном блоке) могут быть видимы несколько объектов с одним именем, в других такая ситуация недопустима.
Некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные деревья и реализацию блочной структуры.
Формальное определение лексем и структуру таблиц сканера
Определение состава лексических единиц языка
Лексическая единица --> конст¦идентифик¦Property | MsgBox | InputBox | Select..Case| While ..Went| Len|CSng|IsEmpty| |not | xor | and | eqv |mod| - | * | \ | ^ | ( | ) | { | } .
Табл.1. Лексемы языка
|
Обозначение лексемы |
Смысл лексемы |
|
|
идентифик |
Идентификатор (integer%, single!) |
|
|
MsgBox |
Вывод на экран диалоговое окно,содержащее сообщение |
|
|
InputBox |
Вывод на экран диалоговое окно,содержащее сообщение и поле ввода |
|
|
Select..Case |
Условой оператор |
|
|
While ..Went |
Цикл |
|
|
Len |
Функция длины стролки |
|
|
CSn |
Возвращает символы из строки |
|
|
IsEmpty |
Проверка на заполнение |
|
|
Dim |
Объявление переменных |
|
|
оп.прис. |
Операция присвания |
|
|
GoTo |
Безусловый переход |
|
|
not |
Логическое «НЕ» |
|
|
eqv |
Логическое «Эквивалетно» |
|
|
xor |
Логическое « НЕ - ИЛИ » |
|
|
and |
Логическое «И» |
|
|
- |
Арифметические операции вычитания |
|
|
\ ,*,mod |
Арифметические операция деления и умножения |
|
|
^ |
Арифметическая операция возведения в степень |
|
|
( |
Открывающая скобка |
|
|
) |
Закрывающая скобка |
Разработка Баз Данных сканера
Табл.2. Таблица однолитерных терминальных символов
|
ТТС1 |
||||
|
0 |
“а” “z” “A” “Z” “а” “я” “А” “Я” |
Буквы |
Б |
|
|
25 |
||||
|
26 |
||||
|
51 |
||||
|
52 |
||||
|
85 |
||||
|
86 118 |
||||
|
119 128 |
"0" "9" |
Цифры |
Ц |
|
|
129 |
"mod" |
Цел. деление |
"mod" |
|
|
130 |
“-“ |
Вычитание |
"-" |
|
|
131 |
"\" |
Деление на цело |
"\" |
|
|
132 |
"*" |
Умножение |
"*" |
|
|
133 |
"^" |
Возведение в степень |
"^" |
|
|
134 |
"<" |
Меньше |
"<" |
|
|
135 |
">" |
Больше |
">" |
|
|
136 |
"=" |
Равно |
"=" |
|
|
137 |
"%" |
Суффикс Integer |
"%" |
|
|
139 |
"(" |
Открывающая cкобка |
"(" |
|
|
140 |
")" |
Закрывающая скобка |
")" |
|
|
141 |
"." |
Точка |
"." |
|
|
142 |
Недопустимый символ |
x |
||
|
143 |
Конец файла |
k |
Табл.3. Таблица ключевых слов
|
ТКС |
||
|
Private |
0 |
|
|
Public |
1 |
|
|
Static |
2 |
|
|
As |
3 |
|
|
Const |
4 |
|
|
Dim |
5 |
|
|
Property |
6 |
|
|
Select |
7 |
|
|
Case |
8 |
|
|
While |
9 |
|
|
Went |
10 |
|
|
Next |
11 |
|
|
End |
12 |
Табл.4. Таблица классификации текущиих литер
|
KTL |
||
|
б |
0 |
|
|
р |
1 |
|
|
"mod" |
2 |
|
|
"-" |
3 |
|
|
"\" |
4 |
|
|
"*" |
5 |
|
|
"^" |
6 |
|
|
"<" |
7 |
|
|
">" |
8 |
|
|
"=" |
9 |
|
|
"%" |
10 |
|
|
"!" |
11 |
|
|
"(" |
12 |
|
|
")" |
13 |
|
|
"." |
14 |
|
|
"x" |
15 |
|
|
"k" |
16 |
Табл.5. Таблица типов лексических едини
|
TLE |
||
|
идентифик |
0 |
|
|
+ |
1 |
|
|
- |
2 |
|
|
\ |
3 |
|
|
* |
4 |
|
|
^ |
5 |
|
|
( |
6 |
|
|
) |
7 |
|
|
< |
8 |
|
|
> |
9 |
|
|
= |
10 |
|
|
Фукции (MsgBox,InputBox, Len|CSng|IsEmpty) |
11 |
|
|
Логические операции( not,xor,and,eqv) |
12 |
|
|
Ключевые слова |
13 |
|
|
Тип данных |
14 |
|
|
Кнопка |
15 |
Табл.6. Таблица функцией и процедуры
|
ТФП |
||
|
MsgBox |
0 |
|
|
InputBox |
1 |
|
|
Len |
2 |
|
|
CSng |
3 |
|
|
IsEmpty |
4 |
Табл.7. Таблица логорических операцией
|
ТЛО |
||
|
not |
0 |
|
|
or |
1 |
|
|
and |
2 |
|
|
eqv |
3 |
Табл.8. Таблица типов данных
|
ТТД |
|||
|
Тип |
адрес |
Длина(байт) |
|
|
Boolean |
0 |
2 |
|
|
Byte |
1 |
1 |
|
|
Date |
2 |
8 |
|
|
Integer |
3 |
2 |
|
|
Single |
4 |
4 |
|
|
String |
5 |
Табл.9. Таблица Buttons (кнопок)
|
ТВ |
||
|
VbOKOnly |
0 |
|
|
VbOKCancel |
1 |
|
|
VbAboutRetryIgnore |
2 |
|
|
VbYesNoCancel |
3 |
|
|
VbYesNo |
4 |
|
|
VbRetryCacel |
5 |
|
|
VbCritical |
6 |
|
|
VbQuestion |
7 |
|
|
VbExclamation |
8 |
|
|
VbInformation |
9 |
|
|
VbDefaultButton1 |
10 |
|
|
VbDefaultButton2 |
11 |
|
|
VbDefaultButton3 |
12 |
|
|
VbDefaultButton4 |
13 |
|
|
VbApplicationModal |
14 |
|
|
VbSystemModal |
15 |
Табл.11. Таблица идентификаторов
|
ТИ |
||||||
|
Идентификатор |
Атрибуты |
Адрес идентиф. |
||||
|
Тип |
Точка |
Точность представления |
Основание системы исчисления |
|||
Табл.12. Таблица констант
|
ТК |
|||||
|
Константа |
Атрибуты |
||||
|
Тип |
Точка |
Точность представления |
Основание системы исчисления |
||
Табл.13. Таблица стандартных символов
|
ТСС |
||
|
TLE |
ALE |
|
Табл.14. Таблица двулитерных терминальных символов
|
ТТС2 |
|||
|
<= |
Меньше / равно |
<= |
|
|
>= |
Больше / равно |
>= |
Каждый тип лексических единиц описываем с помощью автоматной грамматики и для каждой грамматики составляем эквивалентный ей конечный автомат.
идентификаторы , ключевые слова , логические операторы
S = бА .
А = бА !"%"A1! e.
A1 = е .
е = "( " ! "+" ! "\" ! "^" ! ")" ! "=" ! "<" ! ">" .
Рис.4.2.1. Идентификаторы , ключевые слова , логические операторы
+,-
S = "+" U1 ! "-" U1 .
U1 = e3 .
e3 = б ! "%"!"! ".
рис.4.2.2. +,-
\ , *,mod
S = "\"U1 ! "*"U1 .
U1 = e3 .
e3 = б! "%"! "!".
рис.4.2.3. \,*,mod
^
S = "^"U1 .
U1 = e3 .
e3 = б! "%"! "!".
Размещено на http://www.allbest.ru/
рис.4.2.4. ^
=
S = "="O3 .
O3 = e3 .
e3 = б! "%"! "!".
рис.4.2.5.=
<
S = "<" O1 .
O1 = ">"O4 ! "="O4 ! e3 .
O4 = e3 .
e3 = б! "%"! "!".
рис.4.2.6. <
>
S = ">"O2 .
O2 = "="O5 ! e3 .
O5 = e3 .
e3 = б! "%"! "!".
рис.4.2.7. >
(
S = "("K1 .
K1 = e2 .
e2 = б! "%"!"!"! "(" .
Размещено на http://www.allbest.ru/
рис.4.2.8. (
)
S = ")"K2 .
K2 = e .
е = " " ! "+" ! "-" ! "*" ! "\" ! "^" ! ")" ! "=" ! "<" ! ">" .
Размещено на http://www.allbest.ru/
рис.4.2.9. (
3.1 Схема обобщенного конечного автомата
Рис 4.2.10 Схема обобщенного конечного автомата.
3.2 Семантические действия сканера
TIP - определение типа лексической единицы;
VKL - включение очередной литеры в лексему;
CLL - считывание новой литеры из текущей позиции;
PODGOT - подготовка сканера к работе.
ZAPTAB - процедура , которая иницирует строку LE некоторых таблиц
OUT - формирование очередной записи в ТСС.
Poisk - фукция поиска
Проектирование сканера включало в себя определение типа лексем, составление формальных грамматик и конечных автоматов для каждого типа лексических единиц, построение обобщенного конечного автомата сканера, дополненного семантическими предложениями.
3.3 Таблицы сканера для тестовой цепочки
Property Get Myfunc(X, Y)
Dim Z As Integer
If Y <> 0 Then
Z = X\Y-10^X
Else
MsgBox ( “Error” , BUTTON_OK , “Error” )
End Property
Табл.14 Таблица индентификаторов ТИ
|
ИД |
Тип |
Точка |
Точность |
Основани |
Адрес |
|
|
X |
0 |
Integer |
2 |
0 |
||
|
Y |
0 |
Integer |
2 |
1 |
||
|
Z |
0 |
Integer |
- |
14 |
||
|
Myfunc |
0 |
Fix |
- |
3 |
||
|
Integer |
12 |
Fix |
- |
3 |
||
|
String |
12 |
Fix |
- |
5 |
Табл.15 Таблица констант ТК
|
Константа |
Тип |
Точка |
Точность |
Основание |
|
|
10 |
Дес_конст |
Нет |
10 |
Табл. 16 Таблица стандартных символов TCC
|
TLE |
ALE |
|
|
11 |
0 |
|
|
11 |
6 |
|
|
0 |
28 |
|
|
4 |
137 |
|
|
5 |
138 |
|
|
11 |
5 |
|
|
0 |
0 |
|
|
11 |
3 |
|
|
12 |
3 |
|
|
0 |
1 |
|
|
11 |
3 |
|
|
12 |
3 |
|
|
0 |
24 |
|
|
11 |
3 |
|
|
12 |
5 |
|
|
0 |
0 |
|
|
TLE |
ALE |
|
|
8 |
134 |
|
|
0 |
125 |
|
|
0 |
1 |
|
|
8 |
134 |
|
|
0 |
124 |
|
|
11 |
7 |
|
|
0 |
0 |
|
|
6 |
133 |
|
|
0 |
1 |
|
|
11 |
8 |
|
|
0 |
24 |
|
|
8 |
134 |
|
|
0 |
0 |
|
|
11 |
9 |
|
|
11 |
7 |
|
|
0 |
0 |
|
|
TLE |
ALE |
|
|
8 |
134 |
|
|
0 |
1 |
|
|
11 |
8 |
|
|
0 |
24 |
|
|
8 |
134 |
|
|
0 |
1 |
|
|
11 |
12 |
|
|
11 |
7 |
|
|
11 |
12 |
|
|
11 |
7 |
|
|
9 |
0 |
|
|
0 |
24 |
|
|
13 |
9 |
|
|
0 |
15 |
|
|
11 |
12 |
|
|
11 |
6 |
На приведенном примере была продемонстрирована работа сканера с заполнением соответствующих таблиц.
4. Синтаксический анализ
Синтаксический анализ - это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Например, известно, что для любой контекстно - свободной грамматики может быть построен анализатор, сложность которого не превышает O(n3) для входной строки длины n, но в большинстве случаев по заданному языку программирования мы можем построить такую грамматику, которая позволит сконструировать и более быстрый анализатор. Анализаторы реально используемых языков обычно имеют линейную сложность; это достигается, например, за счет просмотра исходной программы слева направо с заглядыванием вперед на один терминальный символ (лексический класс).
Вход синтаксического анализатора - последовательность лексических и таблицы, например, таблица внешних представлений, которые являются выходом лексического анализатора.
Выход синтаксического анализатора - дерево разбора и таблицы, например, таблица идентификаторов и таблица типов, которые являются входом для следующего просмотра компилятора (например, это может быть просмотр, осуществляющий контроль типов).
Отметим, что совсем необязательно, чтобы фазы лексичекого и синтаксического анализа выделялись в отдельные просмотры. Обычно эти фазы взаимодействуют друг с другом на одном просмотре. Основной фазой такого просмотра считается фаза синтаксического анализа, при этом синтаксический анализатор обращается к лексическому анализатору каждый раз, когда у него появляется потребность в очередном терминальном символе.
4.1 Разработка алгоритма синтаксического анализатора
Схема алгоритма синтаксического анализатора
На листе А1
Описание обозначений
X# - массив символов входной цепочки, знак # - он сигнализирует об окончании цепочки.
MP - матрица предшествования.
P - массив правил.
ST - стек, с помощью которого определяется хвост основы.
ST1 - стек, с помощью которого определяется голова основы.
NTL - номер текущей литеры.
TL - текущая литера.
OSN - строка, в которой накапливаются основы.
NOSN - количество символов в строке OSN.
? - правая часть некоторого правила.
A - нетерминал, на который заменяется основа.
REZ - результат (1\0).
ST.push(“#”) - включает элемент в стек.
ST.top() - доступ к вершине стека.
ST.pop() - доступ к вершине стека и исключение элемента из вершины.
ST.nst() - возвращает количество элементов в стеке.
4.2 Разбор тестовой цепочки входного языка
Для фрагмента”X\Y-10^X” выполним разбор
Puc 5.1.1. Синтаксическое дерево
Таблица 17: Таблица синтаксического анализа параллельного предшествования
|
№ |
Сентенциальная форма |
Простые фразы |
|
|
1 |
#While A>C A=(C*2)\(A*3) MSGBOX work, continue WENT# |
A, C, 2, 3, >, work, continue |
|
|
2 |
#WHILE z1AV zCompare z2AV ident=(ident*const)\(ident*const)MSGBOX string, string WENT# |
Ident, const, string |
|
|
3 |
#WHILE z1AV zCompare z2AV ident=(AV3 * AV3)\(AV3*AV3) MSGBOX str, str WENT# |
AV3, str |
|
|
4 |
#WHILE z1AV zCompare z2AV ident=(AV2 * AV2)\(AV2*AV2) MSGBOX str, msg WENT# |
AV2, str “,” msg |
|
|
5 |
#WHILE z1AV zCompare z2AV ident=(AV1 * AV2)\(AV1*AV2) MSGBOX msg WENT# |
AV1*AV2, MSGBOX msg |
|
|
6 |
#WHILE z1AV zCompare z2AV ident=(AV1)\(AV1) PrintMessage WENT# |
AV1, PrintMessage |
|
|
7 |
#WHILE z1AV zCompare z2AV ident=(AV)\(AV) Body WENT# |
AV, Body |
|
|
8 |
#WHILE z1AV zCompare z2AV ident=(zamAV)\(zamAV) zamBody WENT# |
(zamAV) |
|
|
9 |
#WHILE z1AV zCompare z2AV ident=AV3\AV3 zamBody WENT# |
AV3 |
|
|
10 |
#WHILE z1AV zCompare z2AV ident=AV2\AV2 zamBody WENT# |
AV2 |
|
|
11 |
#WHILE z1AV zCompare z2AV ident=AV1\AV2 zamBody WENT# |
AV1\AV2 |
|
|
12 |
#WHILE z1AV zCompare z2AV ident=AV1 zamBody WENT# |
AV1 |
|
|
13 |
#WHILE z1AV zCompare z2AV ident=AV zamBody WENT# |
AV |
|
|
14 |
#WHILE z1AV zCompare z2AV ident=z3AV zamBody WENT# |
ident=z3AV |
|
|
#WHILE z1AV zCompare z2AV operPR zamBody WENT# |
OperPR |
||
|
16 |
#WHILE z1AV zCompare z2AV Body zamBody WENT# |
Body |
|
|
17 |
#WHILE z1AV zCompare z2AV Body1 zamBody WENT# |
Body1 |
|
|
18 |
#WHILE z1AV zCompare z2AV zBody1 zamBody WENT# |
zBody1 zamBody |
|
|
19 |
#WHILE z1AV zCompare z2AV Body1 WENT# |
Body1 |
|
|
20 |
#WHILE z1AV zCompare z2AV Body WENT# |
Body |
|
|
21 |
#WHILE z1AV zCompare z2AV zBody WENT# |
WHILE z1AV zCompare z2AV zBody WENT |
|
|
22 |
#Body# |
Успех!!!!!111 |
В ходе выполнения данной цепочки был осуществлен синтаксический анализ выражения методом параллельного предшествования. В результате была получена таблица, в которой наглядно отображены шаги синтаксического анализа.
Заключение
В ходе выполнения данной курсовой работы была разработана контекстно-свободная грамматика для языка, нарисовано синтаксическое дерево тестового примера для проверки правильности разработанной грамматики. Выполнилась отладка разработанной грамматики для метода параллельного предшествования, разрешены конфликтов отношений предшествования между символами и получена бесконфликтная грамматика. В курсовой работе определены лексемы, структура таблиц сканера, с помощью автоматных грамматик, построился обобщенный конечный автомат. А также разработана схема алгоритма, построилась подробная таблица синтаксического анализа.
Литературные источники, использованные при разработке
1. Ахо А., Лам М., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструментарий.- К.: Изд. Дом "Вильямс", 2 издание, 2008. - 1184с.
2. Ахо А., Сетхи Р., Ульман Дж . Компиляторы: Принципы, технологии, инструменты.- К.: Изд. Дом "Вильямс", 2001. - 694 с.
3. Компаниец Р.С. Системное программирование. Основы построения трансляторов.- СПб.: БХВ-Петербург, 2001. - 254 с.
4 Костельцев И.П. Построение интерпретаторов и компиляторов. Использование Bizon, Jacc, Zubr.- СПб.: БХВ-Петербург, 2001. - 286 с.
5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин.- М.: Мир, 1975. - 546 с.
6. Ахо А., Ульман Дж . Теория синтаксического анализа, перевода и компиляции.Том2. Компиляция - М.: Мир , 1978. - 580 с. (Электронная копия - http://ihtik.lib.ru/)
7. V. Aho, R. Sethi, J. D. Ullman. Compilers: Principles, Technique, Tools.- Addison Webley Publ. Company, 1986. - 720 p.
8. Хантер р. Основные концепции компиляторов.: Пер. с англ. - М.: Издательский дом“Вильямс”, 2002.
9. William A. Barrett, Rodney M. Bates, David A. Qustafson, John D. Couch. Compiler Construction.and Practice. Second Edition, Galgotia Publications pvt ltd. New Delhi, 1990. - 504 p.
10. V. Aho, J. D. Ullman. Principles of Compiler Design. - Narosa Publishing House, New Delhi,1990. - 612 p.
Размещено на Allbest.ru
Подобные документы
Разработка формальной грамматики для выражений, содержащих: логические и арифметические операции, константы, идентификаторы, знаки отношений и т.д., ее отладка в соответствии с требованиями метода параллельного предшествования. Разработка сканера.
контрольная работа [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
