Содержание
- 2. Распознающие автоматы Входная очередь Устройство управления с конечной памятью Вспомогательная память Линейная последовательность символов из Σ.
- 3. Конечный автомат Входная очередь Устройство управления с конечной памятью Недетерминированный конечный автомат – пятерка объектов: К=(Q,
- 4. Конечные преобразователи Входная очередь Устройство управления с конечной памятью Выходная очередь Такт работы конечного преобразователя –
- 5. Регулярный перевод Формализация такта КП как отношения ├ на множестве конфигураций: Для всех q∈Q, а∈Σ, х∈Σ
- 6. Пример конечного преобразователя: распознавание действительных чисел М={(q0, q1, q2, q3, q4), {d, .}, {1, 2, 3},
- 7. Конфигурация МП-автомата (q, х, Z): q∈Q – состояние УУ х ∈ Σ* - необработанная часть входной
- 8. Пример: МП-автомат для распознавания симметричных цепочек P = ({q0, q1, q2}, {a, b}, {Z, a, b},
- 9. Расширенный МП-автомат Лемма: Если (q, w, A) ├n (q’, ε, ε), то (q, w, Aα) ├
- 10. Преобразователи с магазинной памятью Входная очередь Устройство управления с конечной памятью Z α Z0 стек Выходная
- 11. Размеченный вывод цепочек в КС-грамматике Грамматика: (1) (2) (3) (4) (5) (6) Предложение: i+i*i Левый вывод:
- 12. Дерево вывода Упорядоченное дерево, каждый узел которого помечен символом из , называется деревом вывода в КС-грамматике
- 13. Определение разбора Цепочка для КС-грамматики разобрана, если известно её дерево вывода. Пусть заданы КС-грамматика G, правила
- 14. Эквивалентность КС-грамматик и МП-автоматов Пусть G=(N,Σ, P, S) – КС-грамматика, P =({q}, Σ, ΣᵕN, δ, q,
- 15. Пример: МП-автомат для скобочных выражений Грамматика: G=({E, T, M}, {i, +, *, (, )}, {E→E+T, E→T,
- 16. Пример: разбор цепочки i*(i+i) (q, i*(i+i), E)├ (q, i*(i+i), T)├ (q, i*(i+i), T*M) ├ (q, i*(i+i),
- 17. Восходящий синтаксический анализ (свертка слева) Правый вывод цепочки i+i*i: E=>(1) E+T=>(3) E+T*P=>(5) E+T*i =>(4) E+P*i=>(5) E+i*i=>(2)
- 19. Скачать презентацию