Теория языков программирования и методы трансляции Романенко В.В. - презентация

1 Теория языков программирования и методы трансляции Романенко В.В.

2 Факультет дистанционного обучения ТУСУР Предварительные сведения Множества Атом a. Множество A. a A A = {a 1, a 2, …, a n } B A, B A #A = n, # = 0

3 Факультет дистанционного обучения ТУСУР Предварительные сведения Операции на множествах Предикат: A = {a | условие} Объединение A B = {x | x A или x B} Пересечение A B = {x | x A и x B} Разность A–B = {x | x A и x B} Декартово произведение A B = {(a, b) | a A и b B} и т.д.

4 Факультет дистанционного обучения ТУСУР Предварительные сведения Отношения на множествах (a, b) R или aRb A B, a A, b B Пример: {(a, b) | a < b} или a < b (aLb) Обратное отношение R –1 : {(b, a) | (a, b) R} Свойства: рефлексивность – aRa; симметричность – aRb bRa; транзитивность – aRb и bRс aRс. Степень отношения: aR 1 b aRb, aR i b для i > 1 aRc и cR i–1 b, c A.

5 Факультет дистанционного обучения ТУСУР Предварительные сведения Отношения на множествах Транзитивное замыкание: аR + b Рефлексивное и транзитивное замыкание: аR * b 1) aR * a для всех a A; 2) аR * b, если аR + b.

6 Факультет дистанционного обучения ТУСУР Предварительные сведения Цепочки Σ – алфавит Символ – элемент алфавита Цепочки состоят из символов алфавита e – пустая цепочка Длина цепочки: |abc|=3, |e|=0

7 Факультет дистанционного обучения ТУСУР Предварительные сведения Языки L – язык, L Σ * Общая задача перевода: Пусть – входной алфавит, а – выходной алфавит. Переводом (или трансляцией) с языка L 1 * на L 2 * называется отображение f: L 1 L 2.

8 Факультет дистанционного обучения ТУСУР Предварительные сведения Методы перевода (трансляции): Конечные автоматы (КА, ДКА, ДМПА); Регулярные выражения; Грамматики (КС-грамматики).

9 Факультет дистанционного обучения ТУСУР Конечные автоматы ДМП-автомат (ДМПА) – это семерка P = (Q, Σ, Γ, δ, q 0, Z 0, F), где: Q – конечное множество символов состояния, представляющих всевозможные состояния управляющего устройства; Σ – конечный входной алфавит; Γ – конечный алфавит магазинных символов; δ – функция, переходов, отображение множества Q (Σ {e} { }) Γ во множество Q Γ * ; q 0 Q – начальное состояние управляющего устройства; Z 0 Γ – символ, находящийся в магазине в начальный момент (начальный символ); F Q – множество заключительных состояний.

10 Факультет дистанционного обучения ТУСУР Конечные автоматы Конфигурацией ДМП-автомата P называется тройка (q, w, α) Q Σ * Γ *, где: q – текущее состояние устройства; w – неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана; α – содержимое магазина; самый левый символ цепочки α считается верхним символом магазина; если α = e, то магазин считается пустым. Здесь « » – специальный маркер, обозначающий конец входной цепочки. На входе ДМПА находится символ « », если вся входная цепочка прочитана (w = e).

11 Факультет дистанционного обучения ТУСУР Конечные автоматы

12 Факультет дистанционного обучения ТУСУР Конечные автоматы

13 Факультет дистанционного обучения ТУСУР Конечные автоматы Представление функции переходов ДКА и ДМПА в виде графа: q q'q' (a, Z, ) q q'q' a q q'q' a q q'q' q'' (e, Z', Z')

14 Факультет дистанционного обучения ТУСУР Конечные автоматы Представление функции переходов ДМПА в виде таблицы: (a 1, Z 1 )(a 2, Z 2 )(a 3, Z 3 )… q0q0 δ(q 0, a 1, Z 1 )δ(q 0, a 2, Z 2 )δ(q 0, a 3, Z 3 )… q1q1 δ(q 1, a 1, Z 1 )δ(q 1, a 2, Z 2 )δ(q 1, a 3, Z 3 )… q2q2 δ(q 2, a 1, Z 1 )δ(q 2, a 2, Z 2 )δ(q 2, a 3, Z 3 )… …………… (a, Z)(e, Z') (, Z') q (q', ) ERROR q'ERROR(q'', Z')ERROR q''ERROR HALT (a, Z) (, Z') q (q', ) ERROR q'ERRORHALT

15 Факультет дистанционного обучения ТУСУР Конечные автоматы Представление функции переходов ДКА в виде таблицы: Включение действий в синтаксис: Для ДМПА: δ(q, a, Z) = (q',, A ); Для ДКА: δ(q, a) = (q', A ). a1a1 a2a2 … q0q0 δ(q 0, a 1 )δ(q 0, a 2 )… δ(q 0, ) q1q1 δ(q 1, a 1 )δ(q 1, a 2 )… δ(q 1, ) q2q2 δ(q 2, a 1 )δ(q 2, a 2 )… δ(q 2, ) ……………

16 Факультет дистанционного обучения ТУСУР Конечные автоматы Алгоритм разбора ДМПА: 1. q := q 0, M := Z 0, k := Ищем δ(q, a, Z) (a = a k, M = Zβ или a = a k, Z = e или a = e, M = Zβ). Если такая ячейка не найдена, то ошибка в позиции k. Если таких ячеек несколько – значит, таблица переходов построена неверно. 3. Если δ(q, a, Z) = (q',, A ), то: 3.1. Если A e и A, то выполнить действие A q := q' M := β Если a e, то k := k Если δ(q, a, Z) = HALT, то разбор успешно завершен. 5. Если δ(q, a, Z) = ERROR, то ошибка в позиции k.

17 Факультет дистанционного обучения ТУСУР Конечные автоматы Алгоритм разбора ДКА: 1. q := q 0, k := Ищем δ(q, a) (a = a k ). Если такая ячейка не найдена, то ошибка в позиции k. Если таких ячеек несколько – значит, таблица переходов построена неверно. 3. Если δ(q, a) = (q', A ), то: 3.1. Если A e и A, то выполнить действие A q := q' k := k Если δ(q, a) = HALT, то разбор успешно завершен. 5. Если δ(q, a) = ERROR, то ошибка в позиции k.

18 Факультет дистанционного обучения ТУСУР Конечные автоматы Пример 1. Рассмотрим язык L, описывающий число с фиксированной точкой. Такое число может начинаться со знака «+» или «–», далее следует мантисса числа. Разные языки программирования допускают различные формы записи мантиссы, в общем случае они могут быть следующими: «N.M», «N.», «.M», «N», где N – целая, а M – дробная часть числа. В принципе, оба этих числа имеют одинаковый формат – это последовательность из одной и более цифр в диапазоне от 0 до 9. + –.0-9 q0q0 q1q1 q2q2 q3q3 q1q1 q2q2 q3q3 q2q2 q4q4 q3q3 q4q4 q3q3 HALT q4q4 q4q4

19 Факультет дистанционного обучения ТУСУР Конечные автоматы Граф переходов:

20 Факультет дистанционного обучения ТУСУР Конечные автоматы Получили ДКА M = (Q, Σ, δ, q 0, F), где: Q = {q 0, q 1, q 2, q 3, q 4 }; Σ = {+, –,., 0-9}; δ(Q Σ) = {{q 1, q 2, q 3, ERROR}, {ERROR, q 2, q 3, ERROR}, {ERROR, ERROR, q 5, ERROR}, {ERROR, q 4, q 3, HALT}, {ERROR, ERROR, q 4, HALT}}; F = {q 3, q 4 }. Примеры цепочек: правильная – «–15.2 »; неправильная – «.2. ».

21 Факультет дистанционного обучения ТУСУР Конечные автоматы Ограничение количества значащих цифр: A 1 – инициализация счетчика значащих цифр значением 1 (count := 1); A 2 – увеличение счетчика значащих цифр на 1 (count := count + 1) и проверка: если count > N, где N – максимальное количество значащих цифр, то перевести ДКА в состояние ERROR. + –.0-9 q0q0 q 1, q 2, q 3, A 1 q1q1 q 2, q 3, A 1 q2q2 q 4, A 1 q3q3 q 4, q 3, A 2 HALT q4q4 q 4, A 2 HALT

22 Факультет дистанционного обучения ТУСУР Конечные автоматы Пример 2. Пусть язык L описывает идентификатор, заключенный в произвольное количество скобок, от нуля до бесконечности (например, «xyz», «(((abc)))» и т.п.). Скобки должны быть парными, т.е. каждой открывающей скобки должна соответствовать закрывающая. Идентификатор начинается с буквы или подчеркивания («_a-zA-Z»), далее идут буквы, цифры и подчеркивания. (, e_a-zA-Z, e0-9, e), ( e,, q0q0 q 0, (q 1, e q1q1 q 2, eq 3, e q2q2 q 2, eq 3, e q3q3 HALT

23 Факультет дистанционного обучения ТУСУР Конечные автоматы Граф переходов: q0q0 q1q1 (, e, ( _a-zA-Z, e, e 0-9, e, e q2q2 _a-zA-Z, e, e ), (, e q3q3 e,, e ), (, e (, e_a-zA-Z, e0-9, e), (, q0q0 q 0, (q 1, e q1q1 q 2, eHALT q2q2 q 2, eHALT

24 Факультет дистанционного обучения ТУСУР Конечные автоматы Получили ДМПА P = (Q, Σ, Γ, δ, q 0, Z 0, F), где: Q = {q 0, q 1, q 2 }; Σ = {(, ), _, a-z, A-Z, 0-9}; Γ = {(}; δ(Q (Σ {e} { }) Γ) = {{(q 0, «(»), (q 1, e), ERROR, ERROR, ERROR}, {ERROR, (q 1, e), (q 1, e), (q 2, e), HALT}, {ERROR, ERROR, ERROR, (q 2, e), HALT}}; Z 0 = e; F = {q 1, q 2 }. Примеры цепочек: правильная – «((a123)) »; неправильные – «(x)) », «() ».

25 Факультет дистанционного обучения ТУСУР Конечные автоматы Пример 3. Пусть язык L описывает вложенные операторы языка Pascal «begin end;». Учитывая, что необходимо проверять их парность, используем ДМПА с посимвольным разбором (табл. 3.13). Операторы отделяются друг от друга разделительными символами (пробелами, табуляциями, знаками возврата каретки и перехода на новую строку) в произвольном количестве, но не менее одного (в таблице обозначены символом подчеркивания). Также пробелы могут окружать знак «;». Разбор по лексемам: begin, eend, b«;», e, q0q0 q 0, bq 1, e HALT q1q1 q 0, e

26 Факультет дистанционного обучения ТУСУР Конечные автоматы Разбор по символам: b, ee, bg, ei, en, ed, e«;», e_, e, q0q0 q 1, bq 6, e q 0, eHALT q1q1 q 2, b q2q2 q 3, e q3q3 q 4, e q4q4 q 5, e q5q5 q 0, e q6q6 q 7, e q7q7 q 8, e q8q8 q 0, eq 8, e

27 Факультет дистанционного обучения ТУСУР Конечные автоматы Включение действий: Буфер buf := ''. A 1 – если buf '', то buf := a k, иначе ERROR. A 2 – buf := buf + a k. A 3 – если buf 'end', то buf := '', иначе ERROR. A 4 – если buf 'end', то A 5, затем A 3, иначе ERROR. A 5 : если… а) buf 'begin', то M b и buf := ''; б) buf 'end' и top(M) = b, то M b, иначе ERROR. {b, e, g, i, n, d}, e«;», e_, e, q0q0 q 1, e, A 1 q 0, e, A 3 q 0, e, HALT q1q1 q 1, e, A 2 q 0, e, A 4 q 0, e, A 5

28 Факультет дистанционного обучения ТУСУР Регулярные выражения Регулярные выражения: 1) – регулярное выражение, обозначающее регулярное множество ; 2) e – регулярное выражение, обозначающее регулярное множество {e}; 3) если a Σ, то a – регулярное выражение, обозначающее регулярное множество {a}; 4) если p и q – регулярные выражения, обозначающие регулярные множества P и Q, то а) (p+q) – регулярное выражение, обозначающее P Q; б) pq – регулярное выражение, обозначающее PQ; в) p * – регулярное выражение, обозначающее P * ; 5) ничто другое не является регулярным выражением. Приоритет – итерация, конкатенация, объединение.

29 Факультет дистанционного обучения ТУСУР Регулярные выражения Леммы, обозначающие основные алгебраические свойства РВ: α + β = β + α * = e α + (β + γ) = (α + β) + γ α(βγ) = (αβ)γ α(β + γ) = αβ + αγ (α + β)γ = αγ + βγ αe = eα = α α = α = α+α * = α * (α * ) * = α * α+α = α α+ = α

30 Факультет дистанционного обучения ТУСУР Регулярные выражения Объединение: x = a+b, y = c+d x X = {a, b}, y Y = {c, d} x + y X Y = {a, b, c, d} Конкатенация: xy XY = {ac, ad, bc, bd} к(и+о)т {к}{и, о}{т} = {кит, кот} или к(и+о)т = кит + кот {кит, кот} Итерация: x = a, x * X * = {e, a, aa, aaa, …} Т.е. x * = e + x + xx + xxx + …

31 Факультет дистанционного обучения ТУСУР Регулярные выражения Итерация конкатенации и объединения: (xy) * = e + xy + xyxy + xyxyxy + … (x + y) * = e + (x + y) + (x + y)(x + y) + (x + y)(x + y)(x + y) + … = = e + x + xx + xy + yx + yy + xxx + … Приоритет: x + yz {x, yz} (x + y)z {xz, yz} x + y * {e, x, y, yy, yyy, yyyy, …} x * + y * {e, x, y, xx, yy, xxx, yyy, xxxx, yyyy, …} (x + y) * {e, x, y, xx, xy, yx, yy, xxx, …} (xy) * {e, xy, xyxy, …} xy * {x, xy, xyy, xyyy, …}

32 Факультет дистанционного обучения ТУСУР Регулярные выражения Системы уравнений с регулярными коэффициентами: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1n X n X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2n X n …………………………………………………… X n = α n0 + α n1 X 1 + α n2 X 2 + … + α nn X n Алгортм решения изложен в учебном пособии. Решением линейного уравнения X = αX + β является X = α * (β + γ) Наименьшая неподвижная точка – X = α * β.

33 Факультет дистанционного обучения ТУСУР Регулярные выражения Применение регулярных уравнений: для описания языков в различных трансляторах и интерпретаторах; как основа для систем искусственного интеллекта (в частности баз знаний и экспертных систем), хотя чаще в этой области применяются контекстно-зависимые грамматики; в поисковых системах (типа Google и Yandex) при составлении запросов; при поиске и замене текста в различных программных продуктах, например, в диалоге «Поиск и замена» Visual Studio, в аналогичном диалоге программы Microsoft Word и т.д.; в программировании, и особенно web-программировании (при поиске, замене, обработке текста и т.п.); и т.д.

34 Факультет дистанционного обучения ТУСУР Регулярные выражения Преобразование ДКА в РВ: 1. полагаем все коэффициенты α ij := ; 2. если имеется функция переходов δ(X i, a) = X j, a Σ, то коэффициент α ij объединить с a: α ij := α ij + a; 3. если состояние X i является конечным (X i F или δ(X i, ) = HALT), то α i0 := e. Для числа с фиксированной точкой: q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4

35 Факультет дистанционного обучения ТУСУР Регулярные выражения Решение: q 0 = sq 1 + pq 2 + dq 3 = s(pdd * + dd * (pd * + e)) + pdd * + dd * (pd * + e) Получили РВ s(pdd * + dd * (pd * + e)) + pdd * + dd * (pd * + e) = = (s + e)(pdd * + dd * (pd * + e)) = (s + e)(pd + + d + pd * + d + ) q0q0 q1q1 s q2q2 q3q3 pd pd q4q4 d d d q5q5 p d

36 Факультет дистанционного обучения ТУСУР Регулярные выражения Сопоставление РВ и графов переходов ДКА: q0q0 a + b q1q1 q2q2 ab q0q0 ab q1q1 q2q2 a b q0q0 a a*a*

37 Факультет дистанционного обучения ТУСУР Регулярные выражения Сопоставление РВ и графов переходов ДКА: q0q0 (a + e)b q1q1 q2q2 ab q0q0 ab(cab) * q1q1 q2q2 a b q0q0 a (a + b) * q1q1 a q0q0 a aa * = a + q0q0 (ab) + q1q1 q2q2 a b a q0q0 e + (a + b)c * q1q1 ab c b c b

38 Факультет дистанционного обучения ТУСУР Грамматики Грамматикой называется четверка G = (N, Σ, P, S), где N – конечное множество нетерминальных символов или нетерминалов; Σ – непересекающееся с N конечное множество терминальных символов (терминалов); P – конечное подмножество множества (N Σ) * N(N Σ) * (N Σ) *, (α, β) P или α β P; S – начальный (стартовый, исходный) символ. L(G) – язык L, задаваемый грамматикой G.

39 Факультет дистанционного обучения ТУСУР Грамматики Грамматика G называется: праволинейной, если P N (Σ + N Σ * ), т.е. каждое правило из P имеет вид A xB, A x, или A e, x Σ + ; контекстно-свободной (или бесконтекстной), если P N (N Σ) *, т.е. каждое правило из P имеет вид A α, где A N, α (N Σ) * ; контекстно-зависимой (или неукорачивающей), если каждое правило из P имеет вид α β, |α| |β|, α (N Σ) * N(N Σ) *, β (N Σ) +.

40 Факультет дистанционного обучения ТУСУР Грамматики Нормальная форма Хомского: 1) A BC, где A, B, C принадлежит N; 2) A a, где a Σ; 3) S e, если e L(G), причем S не встречается в правых частях правил. Нормальная форма Грейбаха: нет e-правил и каждое правило из P, отличное от S e, имеет вид A aα, где a Σ, α N *.

41 Факультет дистанционного обучения ТУСУР LL(k)-грамматики Обозначения в написании LL(k)-грамматики означают: L – строки разбираются слева направо; L – используются выводы из левых частей правил к правым; k – варианты порождающего правила выбираются с помощью предварительного просмотра k символов.

42 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Множество терминальных символов- предшественников: a S(α) α * aβ, где a – терминал или пустая цепочка, а Σ {e}; α и β – произвольные цепочка терминалов и/или нетерминалов, α, β (N Σ) * ; S(α) – множество символов-предшественников цепочки α.

43 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Пусть α = X 1 X 2 …X n, где X i N Σ {e}. Тогда

44 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Множество терминальных последующих символов: a F(A) αAβ * αAaγ, где: a – терминал или признак конца цепочки, а Σ { }; α, β и γ – произвольные цепочки терминалов и/или нетерминалов, α, β, γ (N Σ) * ; А – нетерминал, A N; F(A) – множество последующих символов для нетерминала A.

45 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Пусть B αAβ. Тогда

46 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Множество направляющих символов:

47 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Таблица разбора: declare 1 TABLE, 2 terminals LIST, 2 jump int, 2 accept bool, 2 stack bool, 2 return bool, 2 error bool; declare 1 LIST, 2 term string, 2 next pointer;

48 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Построение таблицы: M L = {i | (X i α) P}, M R = {j | (A αX j ) P},

49 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Построение таблицы:

50 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Построение таблицы:

51 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Разбор цепочки по таблице: 1. Положить i := 1 (разбор начинается с первой строки таблицы). 2. Положить k := 1 (разбор идет слева направо, начиная с первого символа цепочки). 3. M 0 (поместить в стек значение 0). 4. Если a k terminals i, то: 4.1. Если accept i = true, то k := k + 1 (перейти к следующему символу входной цепочки) Если stack i = true, то M i (поместить в стек номер текущей строки таблицы разбора).

52 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Разбор цепочки по таблице: 4.3. Если return i = true, то: M i; Если i = 0, то перейти на шаг 6; i := i + 1; Вернуться на шаг Если jump i 0, то: i := jump i ; Вернуться на шаг 4.

53 Факультет дистанционного обучения ТУСУР LL(1)-грамматики Разбор цепочки по таблице: 5. Иначе если error i = false, то у правила есть еще одна альтернатива и нужно просто перейти к следующей строке таблицы разбора: 5.1. i := i + 1; 5.2. Вернуться на шаг В противном случае разбор окончен. Если при этом стек M пуст, а a k =, то разбор завершен успешно. Иначе цепочка содержит синтаксическую ошибку и k – позиция этой ошибки.

54 Факультет дистанционного обучения ТУСУР Описание LL(1)-грамматики Даны правила грамматики: E T E E + T E E e T F T T * F T T e F ( E ) F x Они описывают математические выражения, состоящие из операндов (обозначены терминалом x), операций сложения и умножения, а также скобок.

55 Факультет дистанционного обучения ТУСУР Разметка LL(1)-грамматики Выполним маркировку символов грамматики: E 1 T 2 E 3 E T 7 E 8 E 5 e 9 T 10 F 11 T 12 T 13 * 15 F 16 T 17 T 14 e 18 F 19 ( 21 E 22 ) 23 F 20 x 24

56 Факультет дистанционного обучения ТУСУР Нахождение множеств символов- предшественников Найдём для данной грамматики G = (N, Σ, P, S) множества символов- предшественников S(A) для всех нетерминалов A N, стоящих в левых частях правил: S(E 1 ) = {(, x} S(E 4 ) = {+} S(E 5 ) = {e} S(T 10 ) = {(, x} S(T 13 ) = {*} S(T 14 ) = {e} S(F 19 ) = {(} S(F 20 ) = {x}

57 Факультет дистанционного обучения ТУСУР Для поиска множеств символов-предшественников для нетерминалов в правых частях правил используем частный случай приведённой выше формулы: Таким образом, S(E) = S(E 1 ) = {(, x} S(E) = S(E 4 ) S(E 5 ) = {+, e} S(T) = S(T 10 ) = {(, x} S(T) = S(T 13 ) S(T 14 ) = {*, e} S(F) = S(F 19 ) S(F 20 ) = {(, x} S(E 1 ) = {(, x} S(E 4 ) = {+} S(E 5 ) = {e} S(T 10 ) = {(, x} S(T 13 ) = {*} S(T 14 ) = {e} S(F 19 ) = {(} S(F 20 ) = {x} Нахождение множеств символов- предшественников

58 Факультет дистанционного обучения ТУСУР Нахождение множеств последующих символов Найдём для данной грамматики G = (N, Σ, P, S) множества последующих символов F(A) для всех нетерминалов A N грамматики: F(E) = {, )} F(T) = {, +, )} F(F) = {, +, *, )}

59 Факультет дистанционного обучения ТУСУР Множества направляющих символов для левых частей правил ищутся по формуле Последовательно получаем: 1) e S(E 1 ), поэтому T(E 1 ) = S(E 1 ) – {e} = {(, x}; 2) e S(E 4 ), поэтому T(E 4 ) = S(E 4 ) – {e} = {+}; 3) e S(E 5 ), поэтому T(E 5 ) = (S(E 5 ) – {e}) F(E) = {, )}; 4) e S(T 10 ), поэтому T(T 10 ) = S(T 10 ) – {e} = {(, x}; 5) e S(T 13 ), поэтому T(T 13 ) = S(T 13 ) – {e} = {*}; 6) e S(T 14 ), поэтому T(T 14 ) = (S(T 14 ) – {e}) F(T) = {, +, )}; 7) e S(F 19 ), поэтому T(F 19 ) = S(F 19 ) – {e} = {(}; 8) e S(F 20 ), поэтому T(F 20 ) = S(F 20 ) – {e} = {x}. F(E) = {, )} F(T) = {, +, )} F(F) = {, +, *, )} Нахождение множеств направляющих символов S(E 1 ) = {(, x} S(E 4 ) = {+} S(E 5 ) = {e} S(T 10 ) = {(, x} S(T 13 ) = {*} S(T 14 ) = {e} S(F 19 ) = {(} S(F 20 ) = {x}

60 Факультет дистанционного обучения ТУСУР Нахождение множеств направляющих символов Окончательно имеем: S(A)S(A)F(A)F(A)T(A)T(A) E T E (, x, ) (, x E + T E +, ) + E e e, ) T F T (, x, +, ) (, x T * F T *, +, ) * T e E, +, ) F ( E ) (, +, *, ) ( F xxx

61 Факультет дистанционного обучения ТУСУР iXterminalsjumpacceptstackreturnerror 1E(, x2 2T 10 true 3E +, ), 4 4E+6 false 5E ), true 7T(, x10 true 8E +, ), 4 9e ), 0 true 10T(, x11 F(, x19 true 12T +, *, ), 13 T*15 false 14T +, ), 18 15**16true 16F(, x19 true 17T +, *, ), 13 18e +, ), 0 true 19F(21 false 20FX24 21((22true 22E(, x1 true 23))0true 24xx0true Построение таблицы разбора Построим таблицу разбора:

62 Факультет дистанционного обучения ТУСУР Связь LL(1)-грамматики и ДКА Если имеется функция переходов δ ДКА M = (Q, Σ, δ, q 0, F), можно построить соответствующую ей праволинейную грамматику G = (Q, Σ, P, q 0 ). Т.е. нетерминалами этой грамматики являются состояния ДКА (N = Q), алфавиты совпадают, а стартовым символом является q 0. Правила грамматики P формируются следующим образом: 1. если имеется функция переходов δ(X i, a) = X j, a Σ, то добавить в грамматику правило X i a X j ; 2. если состояние X i является конечным (X i F или δ(X i, ) = HALT), то добавить в грамматику правило X i e.

63 Факультет дистанционного обучения ТУСУР Спасибо за внимание!