1. Какую роль выполняет лексический анализ в процессе компиляции?
2. Как связаны фазы лексического и синтаксического анализа?
3. Что такое таблица идентификаторов и для чего она предназначена?
4. Перечислите способы организации таблиц идентификаторов.
5. В чем заключается алгоритм бинарного поиска? Какие преимущества он дает по сравнению с простым перебором, каковы его недостатки?
6. В чем суть хеш-адресации? Что такое хеш-функции и для чего они используются?
7. Охарактеризуйте сущность, достоинства и недостатки метода цепочек.
8. Как могут быть скомбинированы различные методы организации хеш-таблиц?
9. Дайте определение конечного автомата. В чем отличие детерминированного и недетерминированного конечных автоматов?
10.Какие проблемы необходимо решить при построении сканера на основе конечного автомата?
1. Построить регулярную грамматику, порождающую язык
L = {(abb)k^| k ³ 1},
по ней построить ДС, а затем по ДС написать на языке Си лексический анализатор для этого языка.
2. Построить ДС, по которой в заданном тексте, оканчивающемся на ^, выявляются все парные комбинации <>, <= и >= и подсчитывается их общее количество.
3. Дана регулярная грамматика:
S ® A^
A ® Ab | Bb | b
B ® Aa
Определить язык, который она порождает; построить ДС; написать на языке Си лексический анализатор.
4. Пусть имеется переменная cи функция gc(), считывающая в с очередной символ анализируемой цепочки. Дана ДС с действиями:
a) Определить, что будет выдано на печать при разборе цепочки 1+101//p11+++1000/5^?
b) Написать на языке Си лексический анализатор по этой ДС.
5. Написать на языке Си лексический анализатор, выделяющий из текста вещественные числа без знака (они определены как в Паскале) и преобразующий их из символьного представления в числовое.
6. Даны две грамматики G1 и G2:
G1: S ® 0C | 1B | e G2: S ® 0D | 1B
B ® 0B | 1C | e B ® 0C | 1C
C ® 0C | 1C C ® 0D | 1D | e
D ® 0D | 1D
L1 = L(G1); L2 = L(G2).
Построить регулярную грамматику для:
a) L1ÈL2
b) L1ÇL2
Если разбор по ней оказался недетерминированным, найти эквивалентную ей грамматику, допускающую детерминированный разбор.
c) написать Р-грамматику, почти эквивалентную данной;
d) построить ДС и написать лексический анализатор на языке Си.
S ® 0S | S0 | D
D ® DD | 1A | e
A ® 0B | e
B ® 0A | 0
9. Написать лексический анализатор на языке Си по следующей грамматике:
a) S ® C^ b) S ® C^
B ® B1 | 0 | D0 C ® B1
C ® B1 | C1 B ® 0 | D0
D ® D0 | 0 D ® B1
c) S ® A0
A ® A0 | S1 | 0
10. Грамматика G определяет язык L=L1ÈL2, причем L1 ÇL2 =Æ. Написать регулярную грамматику G1, которая порождает язык L1*L2 (см. §2.4, задача 20). Для нее построить ДС и написать лексический анализатор на языке Си.
S ® 0A | 1S
A ® 0A | 1B
B ® 0B | 1B | ^
11. Даны две грамматики G1 и G2, порождающие языки L1 и L2. Построить регулярные грамматики для
a) L1 È L2
b) L1 Ç L2
c) L1 * L2 (см. §2.4, задача 20)
G1: S ® 0B | 1S G2: S ® B^
B ® 0C | 1B | e A ® B1 | 0
C ® 0B | 1S B ® A1 | C1 | B0 | 1
C ® A0 | B1
Для грамматики b) построить ДС и написать лексический анализатор на языке Си.
12. По данной грамматике G1 построить регулярную грамматику G2 для языка L1* L1 (см. §2.4, задача 20), где L1 = L(G1); по грамматике G2 – постоить ДС и лексический анализатор на языке Си.
a) L = {w^ | w Î {0,1}* , где за каждой 1 непосредственно следует 0};
b) L = {1w1^ | w Î {0,1}+ , где между вхождениями 1 нечетное количество 0};
по ней построить ДС, а по ДС написать на языке Си лексический анализатор.
14. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" :
например, ..--. .- ...- ^. Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.
В данной главе рассматривается сущность и задачи синтаксического и семантического анализа. На примере модельного паскалеподобного языка (М-языка) демонстрируется построение синтаксического анализатора методом рекурсивного спуска с синтаксически-управляемым контролем контекстных условий. Приводятся примеры программ на языке Си, в которых реализованы излагаемые в этой главе алгоритмы.
