6 Праволинейные грамматики КС грамматики
Праволинейная контекстно-свободная (КС) грамматика — это грамматика, в которой все правила имеют вид A→a|aB, где a — терминальные символы, а A,B — нетерминальные. Пример праволинейной грамматики: ﹤описание﹥«﹤тип﹥﹤идентификатор﹥﹤список переменных﹥; ﹤список переменных﹥«,﹤идентификатор﹥﹤список переменных﹥ ﹤список переменных﹥«e int a, b, c, i, j, k;. По любой праволинейной грамматике может быть построена эквивалентная ей автоматная грамматика. Также известно, что праволинейные грамматики соответствуют регулярным автоматам, и множества, допускаемые этими моделями, совпадают. 00:05 Введение в контекстно-свободные грамматики 01:15 Доказательство теоремы 02:51 Индукция по выводу 05:25 Доказательство базы 07:03 Переход и индукционный переход 10:00 Доказательство теоремы 11:09 Вопросы и обсуждение 14:00 Переход к контекстно-свободным грамматикам 16:54 Раскрытие и дерево вывода 20:08 Левостороннее и правостороннее дерево вывода 22:15 Синтаксический анализатор 26:06 Виды парсеров 27:44 Однозначная грамматика 30:41 Существенно неоднозначные языки 33:25 Замкнутость языков 36:35 Нормальная форма Хомского 37:41 Введение в порождающие грамматики 38:20 Правила нормальной формы Хомского 39:49 Алгоритм приведения к нормальной форме Хомского 42:16 Удаление не порождающих символов 48:46 Удаление недостижимых символов 51:16 Проверка отсутствия не порождающих символов 56:49 Введение в теорию графов 59:33 Алгоритм нахождения не порождающих символов 01:01:16 Удаление длинных смешанных правил 01:04:29 Работа с длинными правилами 01:07:08 Построение грамматики 01:10:06 Доказательство корректности грамматики 01:15:39 Индукция по длине вывода 01:16:16 Варианты переходов 01:17:37 Доказательство 01:18:21 Заключение
Праволинейная контекстно-свободная (КС) грамматика — это грамматика, в которой все правила имеют вид A→a|aB, где a — терминальные символы, а A,B — нетерминальные. Пример праволинейной грамматики: ﹤описание﹥«﹤тип﹥﹤идентификатор﹥﹤список переменных﹥; ﹤список переменных﹥«,﹤идентификатор﹥﹤список переменных﹥ ﹤список переменных﹥«e int a, b, c, i, j, k;. По любой праволинейной грамматике может быть построена эквивалентная ей автоматная грамматика. Также известно, что праволинейные грамматики соответствуют регулярным автоматам, и множества, допускаемые этими моделями, совпадают. 00:05 Введение в контекстно-свободные грамматики 01:15 Доказательство теоремы 02:51 Индукция по выводу 05:25 Доказательство базы 07:03 Переход и индукционный переход 10:00 Доказательство теоремы 11:09 Вопросы и обсуждение 14:00 Переход к контекстно-свободным грамматикам 16:54 Раскрытие и дерево вывода 20:08 Левостороннее и правостороннее дерево вывода 22:15 Синтаксический анализатор 26:06 Виды парсеров 27:44 Однозначная грамматика 30:41 Существенно неоднозначные языки 33:25 Замкнутость языков 36:35 Нормальная форма Хомского 37:41 Введение в порождающие грамматики 38:20 Правила нормальной формы Хомского 39:49 Алгоритм приведения к нормальной форме Хомского 42:16 Удаление не порождающих символов 48:46 Удаление недостижимых символов 51:16 Проверка отсутствия не порождающих символов 56:49 Введение в теорию графов 59:33 Алгоритм нахождения не порождающих символов 01:01:16 Удаление длинных смешанных правил 01:04:29 Работа с длинными правилами 01:07:08 Построение грамматики 01:10:06 Доказательство корректности грамматики 01:15:39 Индукция по длине вывода 01:16:16 Варианты переходов 01:17:37 Доказательство 01:18:21 Заключение