В некоторых случаях КС-грамматика может содержать недостижимые и бесплодные символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.
Символ x Î (VT È VN) называется недостижимымв грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.
Алгоритм удаления недостижимых символов:
На входе имеется КС-грамматика G = (VT, VN, P, S).
На выходе получаем КС-грамматику G’ = (VT’, VN’, P’, S), не содержащую недостижимых символов, для которой L(G) = L(G’).
Рекурсивно строим множества V0, V1, ...
Шаг 1. V0 = {S}; i = 1.
Шаг 2. Vi = {x | x Î (VT È VN), в P есть A ® axb и A Î Vi-1} È Vi-1.
Шаг 3. Если Vi ¹ Vi-1, то i := i+1 и переходим к шагу 2;
иначе VN’=Vi Ç VN; VT’ = Vi Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).
Символ A Î VN называется бесплоднымв грамматике G =(VT, VN, P, S), если множество { a Î VT* | A Þ a} пусто.
Алгоритм удаления бесплодных символов:
На входе имеется КС-грамматика G = (VT, VN, P, S).
На выходе получаем КС-грамматику G’ = (VT, VN’, P’, S), не содержащую бесплодных символов, для которой L(G) = L(G’).
Рекурсивно строим множества N0, N1, ...
Шаг 1. N0 = Æ, i = 1.
Шаг 2. Ni = {A | (A ® a) Î P и a Î (Ni-1 È VT)*} È Ni-1.
Шаг 3. Если Ni ¹ Ni-1, то i := i+1 и переходим к шагу 2;
иначе VN’ = Ni; P’ состоит из правил множества P, содержащих только символы из VN’ È VT; G’ = (VT, VN’, P’, S).
КС-грамматика G называетсяприведенной, если в ней нет недостижимых и бесплодных символов.
Алгоритм приведения грамматики:
1) обнаруживаются и удаляются все бесплодные нетерминалы;
2) обнаруживаются и удаляются все недостижимые символы.
Удаление символов сопровождается удалением правил вывода, содержащих эти символы.
Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.
Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.
Замечание:если при описании грамматики указаны только правила вывода Р, то будем считать, что большие латинские буквы обозначают нетерминальные символы, S - цель грамматики, все остальные символы - терминальные.
1. Дана грамматика. Построить вывод заданной цепочки.
1) S ® T | T+S | T-S 2) S ® aSBC | abC
T ® F | F*T CB ® BC
F ® a | b bB ® bb
Цепочка a-b*a+b . bC ® bc
cC ® cc
Цепочка aaabbbccc .
2. Построить все сентенциальные формы для грамматики с правилами:
S ® A+B | B+A
A ® a
B ® b
3. Какой язык порождается грамматикой с правилами:
1) S ® APA 2) S ® aQb | e
P ® + | - Q ® cSc
A ® a | b
3) S ® 1B 4) S ® A | SA | SB
B ® B0 | 1 A ® a
B ® b
4. Построить грамматику, порождающую язык :
1) L = {an bm | n, m ³ 1};
2) L = {acbcgc | a, b, g - любые цепочки из a и b};
3) L = {a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n ³ 1};
4) L = {an bm | n ¹ m ; n, m ³ 0};
5) L = {цепочки из 0 и 1 с неравным числом 0 и 1};
6) L = {aa | a Î {a,b}+};
7) L = {w | w Î {0,1}+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей};
8) L = {(a2m bm)n | m ³ 1, n ³ 0};
9) L = {^ | n ³ 1};
10) L = {| n ³ 1};
11) L = {| n ³ 1}.
5. К какому типу по Хомскому относится грамматика с правилами:
1) S ® a | Ba 2) S ® Ab
B ® Bb | b A ® Aa | ba
3) S ® 0A1 | 01 4) S ® AB
0A ® 00A1 AB ® BA
A ® 01 A ® a
B ® b
6. Эквивалентны ли грамматики с правилами :
1) S ® AB и S ® AS | SB | AB
A ® a | Aa A ® a
B ® b | Bb B ® b
2) S ® aSL | aL и S ® aSBc | abc
L ® Kc cB ® Bc
cK ® Kc bB ® bb
K ® b
7. Построить КС-грамматику, эквивалентную грамматике с правилами:
1) S ® aAb 2) S ® AB | ABS
aA ® aaAb AB ® BA
A ® e BA ® AB
A ® a
B ® b
8. Построить регулярную грамматику, эквивалентную грамматике с правилами:
1) S ® A | AS 2) S ® A.A
A ® a | bb A ® B | BA
B ® 0 | 1
9. Доказать, что грамматика с правилами:
S ® aSBC | abC
CB ® BC
bB ® bb
bC ® bc
cC ® cc
порождает язык L = {an bn cn | n ³ 1}.
Для этого показать, что в данной грамматике выводится любая цепочка вида an bn cn(n ³ 1) и не выводятся никакие другие цепочки.
10. Дана грамматика с правилами:
1) S ® S0 | S1 | D0 | D1 2) S ® if B then S | B = E
D ® H. E ® B | B + E
H ® 0 | 1 | H0 | H1 B ® a | b
Построить восходящим и нисходящим методами дерево вывода для цепочки:
1) 10.1001
2) if a then b = a+b+b
11. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.
S ® P^
P ® 1P1 | 0P0 | T
T ® 021 | 120R
R1 ® 0R
R0 ® 1
R^® 1^
12. Построить регулярную грамматику, порождающую цепочки в алфавите {a, b}, в которых символ a не встречается два раза подряд.
13. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.
L = {a2n bm c2k | m=n+k, m>1}.
14. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, ( , ), ^ }. Сбалансированную цепочку a определим рекуррентно: цепочка a сбалансирована, если
1) a не содержит скобок;
2) a = (a1) или a= a1 a2, где a1 и a2 сбалансированы.
15. Написать КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa в этой грамматике.
L = {an cbm can | n, m>0}.
16. Написать КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 в этой грамматике.
L = {1n 0m 1p | n+p>m; n, p, m>0}.
17. Дана грамматика G. Определить ее тип; язык, порождаемый этой грамматикой; тип языка.
G: S ® 0A1
0A ® 00A1
A ® e
18. Дан язык L = {13n+2 0n | n³0}. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.
19. Привести пример грамматики, все правила которой имеют вид A ® Bt, либо A ® tB, либо A ® t, для которой не существует эквивалентной регулярной грамматики.
20. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для
1) L1ÈL2;
2) L1 * L2;
3) L1*
Замечание:L =L1 * L2 - это конкатенация языков L1 и L2 то есть L = { ab | a Î L1, b Î L2}; L = L1* - это итерация языка L1, то есть объединение {e} È L1 È L1*L1 È L1*L1*L1 È ...
21. Написать КС-грамматику для
L={wi 2 wi+1R | i Î N, wi=(i)2 - двоичное представление числа i,
wR - обращение цепочки w}.
Написать КС-грамматику для языка L* (см. задачу 20).
22. Показать, что грамматика
E ® E+E | E*E | (E) | i
неоднозначна. Как описать этот же язык с помощью однозначной грамматики?
23. Показать, что наличие в КС-грамматике правил вида
1) A ® AA | a
2) A ® AaA | b
3) A ® aA | Ab | g,
где a,b,g Î (VTÈVN)*, A Î VN, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?
24. Показать, что грамматика G неоднозначна.
G: S ® abC | aB
B ® bc
bC ® bc
25. Дана КС-грамматика G={VT, VN, P, S}.
Предложить алгоритм построения множества X={A Î VN | A Þ e}.
26. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).
28. Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет получить ответ о принадлежности любой цепочки языку. Если число шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачивающей грамматикой, легко распознаваем.
29. Доказать, что любой конечный язык, в который не входит пустая цепочка, является регулярным языком.
30. Доказать, что нециклическая КС-грамматика порождает конечный язык. Нетерминальный символ A Î VN - циклический, если в грамматике существует A Þ x1 A x2 . КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ.
31. Показать, что условие цикличности грамматики (см. задачу 30) не является достаточным условием бесконечности порождаемого этой грамматикой языка.
32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен. Циклический символ называется эффективным, если A Þ aAb, где |aAb| > 1; иначе циклический символ называется фиктивным.
Практически во всех трансляторах (и в компиляторах, и в интерпретаторах) в том или ином виде присутствует большая часть перечисленных далее процессов: лексический анализ; синтаксический анализ; семантический анализ; генерация внутреннего представления программы; оптимизация; генерация объектного модуля. В конкретных компиляторах порядок этих процессов может быть несколько иным, некоторые из них могут объединяться в одну фазу, другие могут выполняться в течение всего процесса компиляции. В интерпретаторах и при смешанной стратегии трансляции некоторые этапы могут вообще отсутствовать.
В данной главе рассматриваются некоторые методы, используемые для построения лексических анализаторов, а именно, подробно излагаются сущность и особенности применения конечных автоматов и регулярных грамматик. Рассматриваемые алгоритмы и методы иллюстрируются на примере модельного паскалеподобного языка (М-языка). Все алгоритмы записаны на языке Си.
P ® program D1; B^
D1 ® var D {;D}
D ® I {,I}: [ int| bool ]
B ® begin S {;S} end
S ® I := E | if E then S else S | while E do S | B | read (I) | write (E)
E ® E1 [ = | < | > | != ] E1
E1 ® T {[ + | - | or ] T}
T ® F {[ * | / | and ] F}
F ® I | N | L | not F | (E)
L ® true | false
I ® C | IC | IR
N ® R | NR
C ® a | b | ... | z | A | B | ... |Z
R ® 0 | 1 | 2 | ... | 9
Замечание:
a) запись вида {a} означает итерацию цепочки a, то есть в порождаемой цепочке в этом месте может находиться либо e, либо a, либо aa, либо aaa, и так далее.
b) запись вида [ a | b ] означает, что в порождаемой цепочке в этом месте может находиться либо a, либо b.
c) P - цель грамматики; символ ^ - маркер конца текста программы.
Условимся, что:
- любое имя, используемое в программе, должно быть описано и только один раз;
- в операторе присваивания типы переменной и выражения должны совпадать;
- в условном операторе и в операторе цикла в качестве условия возможно только логическое выражение;
- операнды операции отношения должны быть целочисленными;
- тип выражения и совместимость типов операндов в выражении определяются по обычным правилам; старшинство операций задано синтаксисом;
- в любом месте программы, кроме идентификаторов, служебных слов и чисел, может находиться произвольное число пробелов и комментариев вида {< любые символы, кроме} и ^ >};
- true, false, read и write - служебные слова (их нельзя переопределять, как стандартные идентификаторы Паскаля);
- сохраняется паскалевское правило о разделителях между идентификаторами, числами и служебными словами.
^ | n ³ 1};
| n ³ 1};
| n ³ 1}.