Системное программирование

Задачи по системному программированию. Компиляторы, синтаксические анализаторы.

Регулярные выражения

Задано регулярное выражение r = (a|b|c)*bc.
Входной алфавит ∑= {a, b, c}.
Написать программу, распознающую строки, соответствующие данному регулярному выражению.
(Соответствуют: abbbabcbbcabc, bc, abc, bbbc, abcbc, cbc, aabbccbc. Не соответствуют: abccba, bca, abcbcc).
Использовать теории регулярных выражений и конечных автоматов (КА):
1. Для заданного регулярного выражения построить соответствующий ему КА;
2. Если автомат, полученный в предыдущем пункте, недетерминированный, то преобразовать его в ДКА;
3. Используя ДКА, написать программу-распознаватель.

Ключевые слова: 
регулярное выражение, детерминированный конечный автомат.

Нисходящий анализ. Предикативный анализатор.

Для заданной КС-грамматики написать синтаксический анализатор, реализующий метод рекурсивного спуска без откатов. Результатом работы синтаксического анализатора должно быть левое порождение входной строки, представленное списком правил грамматики, использованных в процессе порождения.

Ключевые слова: 
синтаксический анализатор, метод рекурсивного спуска без отката, контекстно-свободная грамматика, левая рекурсия, факторизация

Недетерминированные конечные автоматы. Поисковая система

search.jpg

Написать программу, осуществляющую поиск множества ключевых слов {beta, begin, green} в текстовом файле. Результатом работы программы должен быть список найденных слов и номера позиций этих слов в тексте. Символ новой строки не учитывать при подсчете позиции слова.

Ключевые слова: 
регулярные выражения, недетерминированные конечные автоматы, поисковая система

Калькулятор

Калькулятор.
Произвести синтаксический анализ строки, задающей математическое выражение, содержащее скобки, операции умножения, деления, вычитания, суммирования, тригонометрические функции и условный оператор. Вычислить результат.

Ключевые слова: 
калькулятор, математическое выражение, функция, синтаксический анализ
Синдикация материалов