Темы

Теория формальных языков

Formal Language Theory · 65 статей

  1. Иерархия формальных грамматик по Чомски

    Иерархия Чомского: классы формальных грамматик в лингвистике и информатике. Описание языков, синтаксис, типы грамматик и их включение друг в друга.

    #1320 · 1 мин чтения

  2. Контекстно-зависимые грамматики: определение и свойства

    Контекстно-зависимые грамматики: определение, свойства и место в иерархии Хомского. Более мощные, чем контекстно-свободные, но менее – неограниченные.

    #1363 · 5 мин чтения

  3. Контекстно-зависимые языки: определение и свойства

    Контекстно-зависимые языки: определение, свойства и связь с машиной Тьюринга с линейно ограниченной памятью. Тип 1 иерархии Хомского. Теория формальных языков.

    #1364 · 1 мин чтения

  4. Контекстно-свободные грамматики: определение и применение

    Контекстно-свободная грамматика (КСГ): определение, правила вывода и отличие от контекстно-зависимых грамматик. Теория формальных языков и грамматик.

    #1492 · 5 мин чтения

  5. Контекстно-свободные языки и грамматики

    Контекстно-свободные языки (КСЯ): определение, грамматики, автоматы с магазинной памятью. Применение в программировании и парсинге. Теория формальных языков.

    #1519 · 3 мин чтения

  6. Алгоритм Earley для синтаксического анализа контекстно-свободных языков

    Парсер Эрли: алгоритм разбора контекстно-свободных языков. Динамическое программирование, лингвистика, кубическая сложность. Эффективный разбор!

    #2239 · 3 мин чтения

  7. Конечные автоматы: математическая модель вычислений

    Конечный автомат: мат. модель вычислений. Определение, типы (детерминированные и недетерминированные), состояния, переходы и применение в информатике.

    #2584 · 6 мин чтения

  8. Формальные языки: определение и применение

    Формальные языки: определение, грамматика и применение в математике, логике и программировании. Основы синтаксиса и структуры языков.

    #2587 · 7 мин чтения

  9. LALR-парсеры: теория и применение

    LALR-парсер: что это такое? Разбор текста в структурированное представление для компиляторов. Упрощенная версия LR-парсера, разработанная Фрэнком ДеРемером.

    #4339 · 3 мин чтения

  10. LR-парсеры: принципы и разновидности

    LR-парсеры: анализ языков программирования в компьютерной науке. Типы (SLR, LALR, LR(1), GLR) и генерация из формальных грамматик. Быстрая обработка!

    #4346 · 13 мин чтения

  11. Регулярные выражения: история и применение

    Регулярные выражения (regex): что это такое? Паттерны для поиска и замены текста, валидации данных. История, теория и применение в программировании.

    #6207 · 26 мин чтения

  12. Регулярные языки: теория и обобщения

    Регулярные языки в теории формальных языков: определение, примеры (грамматики 3 типа, конечные автоматы). Не регулярные языки и их свойства.

    #6208 · 2 мин чтения

  13. Проблема высоты звезды в теории формальных языков

    Проблема высоты звезды в теории формальных языков: можно ли выразить все регулярные языки выражениями с ограниченной вложенностью Kleene star? Исследование и примеры.

    #6718 · 2 мин чтения

  14. Yacc: Генератор парсеров и его потомки

    Yacc: генератор парсеров для Unix. Создает LALR-парсеры из грамматик (BNF). Альтернатива – Bison (GNU). История, разработка и применение Yacc.

    #8178 · 2 мин чтения

  15. Bison: Генератор парсеров, совместимый с Yacc

    Bison: генератор парсеров, совместимый с Yacc. Создает переносимые LALR(1), LR, GLR парсеры на C/C++/D/Java. Flex для лексического анализа.

    #12435 · 3 мин чтения

  16. Алгоритм Кока-Янгера-Касами для синтаксического анализа контекстно-свободных грамматик

    Алгоритм CYK (Кока-Янгера-Касами) – эффективный метод синтаксического анализа контекстно-свободных грамматик. Динамическое программирование, CNF.

    #12627 · 4 мин чтения

  17. LL-парсеры: теория, типы и применение.

    LL-парсеры: разбор контекстно-свободных языков сверху вниз. LL(k) грамматики и парсеры с k символами предпросмотра. Теория и применение в информатике.

    #13543 · 2 мин чтения

  18. Формализм Бэкуса-Наура для описания языков программирования

    BNF (БНФ): нотация для описания синтаксиса языков программирования и формальных языков. Разработана Backus и Naur. Применение: спецификации, учебники.

    #14608 · 1 мин чтения

  19. Простые LR-парсеры: теория и реализация.

    SLR-парсер: эффективный анализ синтаксиса в программировании. Простота генерации, небольшие таблицы, высокая скорость разбора. Сравнение с LALR и LR-парсерами.

    #16179 · 3 мин чтения

  20. Расширенная форма Бэкуса — Наура: Семейство нотаций для описания грамматик

    EBNF: расширенная нотация Бэкуса-Наура для описания синтаксиса языков программирования. Варианты, преимущества, история и применение в CS.

    #16430 · 2 мин чтения

  21. Канонические и минимальные LR(1) парсеры: обзор и развитие

    Канонический LR-парсер: алгоритм синтаксического анализа языков программирования. LR(1) грамматики, преимущества и недостатки, преобразования грамматик.

    #16694 · 2 мин чтения

  22. Древесные автоматы: разновидности и свойства

    Конечные автоматы для деревьев: теория, типы (нисходящие, восходящие) и связь с регулярными языками деревьев. Автоматы для обработки древовидных структур.

    #22925 · 2 мин чтения

  23. Теория автоматов и абстрактных машин

    Теория автоматов: изучение абстрактных машин и автоматов, вычислительных задач. Связь с матлогикой. Автомат – самодействующее вычислительное устройство.

    #23889 · 4 мин чтения

  24. Лекс: Генератор лексических анализаторов UNIX

    Lex – генератор лексических анализаторов для Unix. Создает сканеры на C (и Ratfor) из описаний, часто используется с yacc. Стандарт POSIX.

    #24826 · 2 мин чтения

  25. Парсеры с таблицей: анализ неоднозначных грамматик

    Чартовый парсер: анализ неоднозначных грамматик в компьютерной лингвистике. Динамическое программирование, алгоритм Витерби, предотвращение комбинаторного взрыва.

    #24928 · 1 мин чтения

  26. Альфред Ахо: Пионер информатики и лауреат премии Тьюринга

    Альфред Ахо: канадский ученый, пионер в области языков программирования и алгоритмов. Лауреат премии Тьюринга 2020 года за вклад в компьютерные науки.

    #45232 · 3 мин чтения

  27. Моделирование структуры биомолекул с помощью контекстно-свободных грамматик.

    Формальные грамматики (PCFGs) для анализа последовательностей. Алгоритм Inside-Outside вычисляет вероятность генерации последовательности грамматикой. Лингвистика, NLP.

    #74605 · 1 мин чтения

  28. Машина Мили: Конечный автомат с выходом, зависящим от состояния и входа.

    Машина Мили: автомат с конечным числом состояний, выдающий выходные данные в зависимости от состояния и входа. Отличие от машины Мура. Теория вычислений.

    #80547 · 1 мин чтения

  29. Топ-даун парсинг: методы и современные решения

    Парсинг сверху вниз: метод анализа данных в компьютерной науке и лингвистике. LL-парсеры, формальные грамматики, построение дерева разбора.

    #81791 · 2 мин чтения

  30. Детерминированные и недетерминированные автоматы Бюхи: теория и применение.

    Детерминированные и недетерминированные автоматы Бюхи: теория, состояния, функции переходов и критерии принятия бесконечных входных данных. Автоматы Бюхи.

    #82792 · 3 мин чтения

  31. Метасинтаксис: структура и состав фраз и предложений металлнгвика

    Метасинтаксис: структура и состав фраз для описания языков программирования. BNF, EBNF, WSN, ABNF – популярные формальные метаязыки. 💻✨

    #83971 · 5 мин чтения

  32. Flex: Генератор лексических анализаторов для UNIX

    Flex – генератор лексических анализаторов для UNIX. Создает сканеры/лексеры, альтернатива lex. Используется с Yacc/Bison, основан на DFA. Бесплатный и открытый.

    #87789 · 3 мин чтения

  33. Переписывание термов и системы переписывания

    Переписывание формул в математике, логике и IT: замена подтермов, системы переписывания, редукционные системы. Недетерминированность правил.

    #94536 · 4 мин чтения

  34. Атрибутивные грамматики: Семантический анализ и преобразование синтаксических деревьев

    Атрибутивная грамматика: формальный метод добавления семантики к грамматике. Атрибуты и правила вычисления для обработки информации в синтаксическом дереве.

    #105391 · 1 мин чтения

  35. Шейла Грейбах: вклад в теорию формальных языков и вычислительную технику

    Шейла Грейбах: биография и вклад в информатику. Формальные языки, автоматы, компиляторы, нормальная форма Грейбах. Исследования в области теории вычислений.

    #113141 · 3 мин чтения

  36. Таблица переходов состояний в теории автоматов и последовательной логике

    Таблица состояний в теории автоматов: определение, применение для описания конечных автоматов и последовательной логики. Альтернатива диаграммам состояний.

    #115112 · 1 мин чтения

  37. Древесно-соседственные грамматики: формализм и свойства

    Древесно-соседняя грамматика (TAG): формализм Аравинда Джоши для лингвистического анализа. Переписывание деревьев, начальные и вспомогательные деревья.

    #117680 · 2 мин чтения

  38. Правило отступов в синтаксисе языков программирования

    Оффсайдное правило в программировании: синтаксис, основанный на отступах. Значение отступов для определения блоков кода, история и определение Ландина.

    #122929 · 4 мин чтения

  39. Неоднозначные контекстно-свободные грамматики

    Неоднозначная грамматика в информатике: определение, примеры, связь с контекстно-свободными языками и детерминированными грамматиками. Проблемы в языках программирования.

    #129201 · 3 мин чтения

  40. Детерминированные и недетерминированные конечные автоматы

    Конечные автоматы: DFA и NFA. Различия, преимущества и алгоритм преобразования NFA в эквивалентный DFA. Теория автоматов и формальные языки.

    #129933 · 3 мин чтения

  41. Парсинг снизу вверх: принципы и применение

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

    #133218 · 2 мин чтения

  42. Чередующиеся конечные автоматы: теория и сложность задач

    Конечные автоматы с чередованием (AFA): теория, типы переходов (экзистенциальные и универсальные), не детерминированные автоматы и их поведение.

    #144671 · 2 мин чтения

  43. Язык анализа сверху вниз (TDPL) и его обобщение (GTDPL)

    TDPL: формальная грамматика для анализа синтаксиса, разработанная А. Бирманом. Изучение нисходящего разбора с поддержкой ограниченного возврата. GTDPL – расширение TDPL.

    #156352 · 2 мин чтения

  44. Конечно-автомат с двумя лентами (вход, выход)

    Конечный автомат с двумя лентами: входной и выходной. FST (конечный преобразователь) отображает строки, определяя связь между символами. Более мощный, чем FSA.

    #177575 · 3 мин чтения

  45. Детерминизация конечных автоматов: метод построения подмножеств.

    Построение подмножеств: метод преобразования недетерминированного конечного автомата (НКА) в детерминированный (ДКА). Теория автоматов, алгоритмы, DFA, NFA.

    #188560 · 5 мин чтения

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

    Конечный автомат перестановки: определение, свойства и связь с p-регулярными языками в теории автоматов. Примеры и формальное описание.

    #197500 · 1 мин чтения

  47. Идентификация в пределе: формальная модель индуктивного вывода языков.

    Идентификация языка: формальная модель обучения машинному распознаванию формальных языков. Принцип обучения по примерам, бесконечный процесс индукции.

    #203885 · 5 мин чтения

  48. Парсеры на основе приоритета операторов

    Парсер с приоритетом операторов: реализация, алгоритм сортировочной станции Дейкстры, преобразование инфиксной нотации в RPN. Простота и эффективность.

    #204117 · 2 мин чтения

  49. Левая рекурсия в теории формальных языков

    Левая рекурсия в теории языков: определение, виды (прямая и косвенная), примеры. Важный концепт для контекстно-свободных грамматик и разбора языков.

    #215222 · 2 мин чтения

  50. Линейные языки: свойства и классификация

    Линейные грамматики и языки: определение, свойства и примеры. Связь с регулярными и контекстно-свободными языками. {aⁿbⁿ} как линейный язык.

    #252508 · 2 мин чтения

  51. Языки Дика и сбалансированные скобки

    Дык-слова: сбалансированные строки скобок в математике и информатике. Определение, язык Дыка, применение в парсинге выражений и формальных языках.

    #257813 · 2 мин чтения

  52. Сети переходов с расширением: анализ и применение в обработке естественного языка.

    Автомат переходов с расширением (ATN) – графовая структура для формальных языков и ИИ. Применяется в парсинге сложных предложений, расширение RTN и FSM.

    #260052 · 1 мин чтения

  53. Расширенные Аффиксные Грамматики: Теория и Применение

    Расширенные аффиксные грамматики (EAG): формализм для описания синтаксиса языков программирования и естественных языков. Разработка, парсинг, трансляция.

    #268957 · 1 мин чтения

  54. Генераторы парсеров Unix: Berkeley Yacc и его производные

    byacc: генератор парсеров Unix, совместимый с Yacc. Написан на ANSI C89, быстрее AT&T Yacc, с открытым исходным кодом и поддержкой reentrancy.

    #272864 · 3 мин чтения

  55. Лемма о накачке для регулярных языков

    Лемма о накачке для регулярных языков: свойство, определяющее регулярные языки. Описание принципа "накачки" подстрок и ограничения длины. Теория формальных языков.

    #278235 · 3 мин чтения

  56. Алгоритм преобразования инфиксной нотации в постфиксную (алгоритм сортировочной станции)

    Алгоритм сортировочной станции (Shunting Yard) – преобразование выражений из инфиксной нотации в постфиксную (RPN). Разработан Э. Дейкстрой, основан на стеке.

    #331814 · 2 мин чтения

  57. Лемма о накачке для контекстно-свободных языков

    Лемма о выкачивании для контекстно-свободных языков: свойство, используемое для доказательства не-контекстно-свободности языка. Обобщение леммы для регулярных языков.

    #368325 · 1 мин чтения

  58. Сканерless-парсеры: токенизация и синтаксический анализ в одном шаге

    Сканерless-парсing: токенизация и синтаксический анализ за один шаг. Оптимизация грамматик языков, примеры (TeX, Raku). Сложность отладки.

    #371540 · 2 мин чтения

  59. Программирование на основе автоматов

    Программирование на основе автоматов: парадигма, моделирующая программу как автомат (конечный или сложный). Четкое разделение времени на шаги, единая точка входа.

    #380657 · 4 мин чтения

  60. Детерминированные автоматы с магазинной памятью: теория и свойства

    Детерминированный автомат с магазинной памятью (ДПМА): теория, определение, языки, распознаваемые ДПМА. Переходы, стек, операции над стеком.

    #416903 · 2 мин чтения

  61. Двунаправленные конечные автоматы: теория и свойства

    Двунаправленный конечный автомат: теория автоматов, определение, свойства и эквивалентность однонаправленным ДКА. Машина Тьюринга без рабочей ленты.

    #423078 · 3 мин чтения

  62. Индукция грамматик: методы и подходы в машинном обучении.

    Индукция грамматик в машинном обучении: обучение формальным грамматикам из данных. Алгоритмы для конечных автоматов, контекстно-свободных грамматик и др.

    #439325 · 4 мин чтения

  63. Матричные грамматики: свойства и классы языков

    Матричная грамматика: формальная грамматика с последовательными продукциями. Применение происходит строго по порядку, матрицами. Описание и принципы работы.

    #453591 · 1 мин чтения

  64. Выразительная сила формальных языков

    Экспрессивность языка программирования: что это такое? Узнайте, как выразительность влияет на возможности представления идей и эффективность вычислений.

    #455208 · 3 мин чтения

  65. Unrestricted grammar

    #466442 · 2 мин чтения