Нисходящий синтаксический анализ — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно-свободной грамматикой. Это класс алгоритмов грамматического анализа, где правила формальной грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Контекстно-свободная грамматика — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала.
В информатике лексический анализ — процесс аналитического разбора входной последовательности символов на распознанные группы — лексемы, с целью получения на выходе идентифицированных последовательностей, называемых «токенами». В простых случаях понятия «лексема» и «токен» идентичны, но более сложные токенизаторы дополнительно классифицируют лексемы по различным типам. Лексический анализ используется в компиляторах и интерпретаторах исходного кода языков программирования, и в различных парсерах слов естественных языков.
yacc — компьютерная программа, служащая стандартным генератором синтаксических анализаторов (парсеров) в Unix-системах. Название является акронимом «Yet Another Compiler Compiler». Yacc генерирует парсер на основе аналитической грамматики, описанной в нотации BNF или контекстно-свободной грамматики. На выходе yacc выдаётся код парсера на языке программирования Си.
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.
Абстрактное синтаксическое дерево — конечное помеченное ориентированное дерево, в котором внутренние вершины сопоставлены (помечены) с операторами языка программирования, а листья — с соответствующими операндами. Таким образом, листья являются пустыми операторами и представляют только переменные и константы.
LR-анализатор (англ. LR parser) — синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и производит наиболее правую (Right) продукцию контекстно-свободной грамматики. Используется также термин LR(k)-анализатор, где k выражает количество непрочитанных символов предпросмотра во входном потоке, на основании которых принимаются решения при анализе. Обычно k равно 1 и часто опускается.
Грамматика, построенная на определённых предложениях — это способ построения грамматики в логических языках программирования, например, Пролог. DC-грамматика обычно ассоциируется с Прологом, но и другие языки, например, Mercury, также могут использовать DC-грамматику. Словосочетание «определенные предложения» используется в названии потому, что эта грамматика основывается на дизъюнкте Хорна в логике первого порядка.
В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом. Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.
Стохастическая контекстно-свободная грамматика — контекстно-свободная грамматика, в которой каждому правилу вывода соответствует вероятность. Вероятность вывода определяется как произведение вероятностей используемых в нём правил вывода, таким образом, некоторые выводы лучше соответствуют стохастической грамматике, чем другие. СКС-грамматики расширяют КС-грамматики так же, как скрытые марковские модели расширяют регулярные грамматики. СКС-грамматики широко применяются в науке: от обработки естественных языков до изучения молекул РНК. СКС-грамматики являются особой формой взвешенных контекстно-свободных грамматик.
Грамматика, разбирающая выражение (РВ-грамматика) — тип аналитической формальной грамматики, описывающей формальный язык в терминах набора правил для распознавания строк языка. Грамматика, разбирающая выражение, в сущности, представляет собой синтаксический анализатор рекурсивного спуска в чисто схематической форме, которая выражает только синтаксис и не зависит от конкретной реализации или применения синтаксического анализатора. Грамматики, разбирающие выражение, похожи на регулярные выражения и на контекстно-свободные грамматики (КС-грамматики) в нотации Бэкуса-Наура, но имеют отличную от них интерпретацию.
Грамматика ван Вейнгаардена — это двухуровневая грамматика, которая предоставляет способ определения потенциально бесконечных грамматик через конечное число правил. Формализм был изобретён Адрианом ван Вейнгаарденом для определения некоторых синтаксических ограничений, которые ранее должны были формулироваться на естественных языках, несмотря на свою принципиально синтаксическую сущность. Типичными применениями являются обработка рода и числа в естественных языках и правильное формулирование идентификаторов в языках программирования.
GLR-парсер — в информатике расширенный алгоритм LR-парсера, предназначенный для разбора по недетерминированным и неоднозначным грамматикам. Впервые описанный Масару Томита в 1984 году, его также называют «параллельным парсером».
Алгори́тм Э́рли — алгоритм синтаксического анализа предложения по контекстно-свободной грамматике, основанный на методе динамического программирования. В отличие от алгоритма Кока — Янгера — Касами, который требует приведения грамматики к нормальной форме Хомского, алгоритм Эрли привлекателен тем, что не накладывает ограничений на используемую для анализа контекстно-свободную грамматику. Кроме того, Алгоритм Кока — Янгера — Касами работает по принципу «снизу-вверх», то есть строит возможные деревья разбора предложения начиная с вершины. В отличие от него Алгоритм Эрли реализует стратегию вывода «слева-направо».
Грамматика сложения деревьев — это формальная грамматика, придуманная Аравиндом Джоши. Эта грамматика обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы. Таким образом грамматика определяет правила замены узлов дерева на поддеревья.
Индукция грамматики — процедура машинного обучения, которая восстанавливает формальную грамматику языка на основе набора наблюдений (примеров) с известной принадлежностью этому языку. В результате процедуры строится модель наблюдаемых объектов в виде набора правил вывода или порождающих правил, конечного автомата или автомата другого вида. В более общем смысле, грамматический вывод — это одно из направлений машинного обучения, в котором пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья, графы.
