Конечный автомат. Регулярная грамматика - Помощь студентам

RocBoy-D · 26.10.2012, 22:24

Здравствуйте! Возникли проблемы с задачей: дан набор правил q0 -> aq1, q1 -> bq2, q1 -> q2, q1 -> cq2, q2 -> aq3 и др. Нужно написать программу, которая считывает количество символов в слове и выводит на экран все слова, которые удовлетворяют этим правилам. Подскажите, что нужно искать в Интернете или дайте ссылки, алгоритм или код, если кто-то решал похожую задачу. Спасибо

Abstraction · 26.10.2012, 23:03

Ну, универсальный талмуд на сей счёт - Ахо, Лам, Сети, Ульман: "Компиляторы".

Если известно, что правила описывают детерминированный автомат (т.е. правила имеют вид N1 -> tN2 либо N1 -> t, причём не существует пары с совпадающим t N1 -> tN2, N1 -> tN3), то можно построить просто по функции на нетерминал. Каждая такая функция читает один символ; если он не совпадает ни с одним из правил - сообщает об ошибке, иначе вызывает функцию, соответствующую нетерминалу из правой части правила. Если правила описывают недетерминированный автомат (то есть содержащий также описанные выше пары и/или правила вида N1 -> N2), то его можно привести к детерминированному ("Компиляторы" 3.7.1).

Можно вместо этого сворачивать выражение в дерево разбора (синтаксический анализ; "Компиляторы" 2.4.4) - это в каком-то смысле более общий метод, но он и заметно сложнее.

26.10.2012, 22:24	#1
RocBoy-D Пользователь Регистрация: 10.03.2012 Сообщений: 10	Конечный автомат. Регулярная грамматика Здравствуйте! Возникли проблемы с задачей: дан набор правил q0 -> aq1, q1 -> bq2, q1 -> q2, q1 -> cq2, q2 -> aq3 и др. Нужно написать программу, которая считывает количество символов в слове и выводит на экран все слова, которые удовлетворяют этим правилам. Подскажите, что нужно искать в Интернете или дайте ссылки, алгоритм или код, если кто-то решал похожую задачу. Спасибо

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
недетерминированный конечный автомат	CodeNOT	Общие вопросы C/C++	0	21.02.2012 15:48
Конечный автомат	maxon56	Помощь студентам	0	19.12.2011 19:32
Конечный автомат для строк	Infinite	Помощь студентам	0	25.12.2009 21:08
Я сделал конечный автомат (правильно?)	Arkuz	Общие вопросы Delphi	2	11.10.2008 15:59
Конечный автомат на Delphi	Arkuz	Общие вопросы Delphi	4	02.10.2008 23:50

26.10.2012, 23:03	#2
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	Ну, универсальный талмуд на сей счёт - Ахо, Лам, Сети, Ульман: "Компиляторы". Если известно, что правила описывают детерминированный автомат (т.е. правила имеют вид N1 -> tN2 либо N1 -> t, причём не существует пары с совпадающим t N1 -> tN2, N1 -> tN3), то можно построить просто по функции на нетерминал. Каждая такая функция читает один символ; если он не совпадает ни с одним из правил - сообщает об ошибке, иначе вызывает функцию, соответствующую нетерминалу из правой части правила. Если правила описывают недетерминированный автомат (то есть содержащий также описанные выше пары и/или правила вида N1 -> N2), то его можно привести к детерминированному ("Компиляторы" 3.7.1). Можно вместо этого сворачивать выражение в дерево разбора (синтаксический анализ; "Компиляторы" 2.4.4) - это в каком-то смысле более общий метод, но он и заметно сложнее.