Формализмы синтаксического анализа и грамматики
Восстановление грамматической структуры предложений машинным способом: формализмы грамматики, описывающие допустимые структуры, и алгоритмы, которые их вычисляют, от деревьев составляющих до графов зависимостей.
Definition
Синтаксический анализ — это вычислительное присвоение грамматической структуры входной строке в соответствии с грамматикой; формализмы грамматики — это системы, используемые для определения того, какие структуры являются допустимыми.
Scope
Охватывает синтаксический анализ в компьютерной лингвистике — бесконтекстный анализ составляющих и его вероятностные и табличные алгоритмы, анализ зависимостей, основные формализмы грамматики, выходящие за рамки простых бесконтекстных грамматик, и задачи пометки последовательностей (такие как пометка частей речи), которые предшествуют синтаксическому анализу. Исключает семантическую интерпретацию, которая рассматривается в вычислительной семантике, и базовую теорию автоматов, рассматриваемую в основах.
Sub-topics
Core questions
- Как предложению может быть эффективно присвоено синтаксическое дерево или граф зависимостей?
- Какие формализмы грамматики адекватно описывают синтаксис естественного языка?
- Как вероятности помогают разрешить неоднозначность среди множества возможных вариантов синтаксического анализа?
- Как пометка и сегментация поддерживают полный синтаксический анализ?
Key concepts
- анализ составляющих
- анализ зависимостей
- бесконтекстная грамматика
- табличный синтаксический анализ
- вероятностная грамматика
- пометка частей речи
- древесный банк
- структурная неоднозначность
Key theories
- Табличный синтаксический анализ
- Алгоритмы динамического программирования, такие как CKY и Эрли, которые вычисляют все возможные анализы предложения за полиномиальное время, повторно используя общие под-анализы.
- Вероятностные бесконтекстные грамматики
- Присвоение вероятностей правилам грамматики, чтобы можно было выбрать наиболее вероятный вариант синтаксического анализа, что решает проблему повсеместной структурной неоднозначности естественного языка.
History
Ранний синтаксический анализ основывался на грамматиках, созданных вручную, и исчерпывающем поиске; алгоритмы CKY и Эрли сделали бесконтекстный анализ эффективным. Выпуск древесных банков в 1990-х годах позволил осуществлять вероятностный синтаксический анализ на основе данных, а в 2000-х годах анализ зависимостей вышел на первый план благодаря своей кросс-лингвистической надежности, позднее его заменили нейронные парсеры.
Debates
- Представление составляющих против представления зависимостей
- Вопрос о том, лучше ли представлять синтаксис как вложенные фразы или как помеченные отношения «глава-зависимый»; оба широко используются, при этом зависимости предпочтительны для языков со свободным порядком слов и последующих задач.
Key figures
- Jay Earley
- Joakim Nivre
- Christopher Manning
- Mitchell Marcus
Related topics
Seminal works
- manning1999
- kubler2009
- jurafsky2025
Frequently asked questions
- Почему синтаксический анализ сложен, если правила грамматики известны?
- Естественные предложения чрезвычайно неоднозначны: одна и та же строка может иметь множество допустимых структур. Поэтому синтаксический анализ должен не только находить структуры, но и ранжировать их, вот почему вероятностные и обучаемые модели имеют решающее значение.