Применение правил грамматики. Синтаксический анализатор, нис- и восходящий разбор, полный перебор правил подстановки. Классификация грамматик по Хомскому. Определение языков с помощью автоматов. Форма Бекуса-Наура описания синтаксиса формальных языков.
Аннотация к работе
элементы теории языков лекция 24План лекции Описание синтаксиса языков БНФ , РБНФ, синтаксические диаграммы Формальные грамматики Классификация грамматик по Хомскому Распознавание языков Синтаксический анализатор, нис-и восходящий разбор, полный перебор правил подстановки Определение языков с помощью АВТОМАТОВФОРМА Бекуса-Наура описания синтаксиса формальных языков Джон Бекус (John Backus , 1924-2007) Руководил созданием первого компилятора для языка Фортран Питер Наур (Peter Naur , 1925 ) Один из создателей языка Алгол "Backus Normal Form"Форма Бекуса-Наура описания синтаксиса формальных языков Описание синтаксиса языков программирования Терминальные символы Нетерминальные символы Правила вида ::= | | . . ::= | "("" ) "| Пример БНФ № 3 Опишите БНФ при помощи БНФРАСШИРЕННАЯ БНФ [] Необязательная последовательность символов {} Повторение последовательности СИМВОЛОВГРАММАТИКИ Формальный язык - это произвольное множество цепочек, составленных из символов некоторого конечного алфавита Произвольное - бесконечное, конечное или пустое Грамматика - это конечное описание формального ЯЗЫКАОПРЕДЕЛЕНИЕ грамматики Грамматика - это набор из четырех элементов Множество терминальных символов Алфавит языка Множество нетерминальных символов Вспомогательные символы, не входящие в описываемый язык Множество правил вида ЛЧ-> ПЧ, где ЛЧ - послед. терминалов и нетерминалов, содержащая >= 1 нетерминал ПЧ - любая последовательность нетерминалов Стартовый нетерминал СПРИМЕНЕНИЕ правил грамматики Цепочка Ц2 получается из цепочки Ц1 применением правила ЛЧ-> ПЧ, если Ц1 имеет вид х ЛЧ у, а Ц2 имеет вид х ПЧ у Пример Цепочка АААВВВ получается из ААВВ применением правила АВ-> ААВВВЫВОД в грамматике Вывод цепочки Ц - это последовательность цепочек, состоящих из терминалов и нетерминалов, вида С, ...