Синтаксический анализ , синтаксический анализ или синтаксический анализ — это процесс анализа строки символов , будь то на естественном языке , компьютерных языках или структурах данных , в соответствии с правилами формальной грамматики . Термин « синтаксический анализ» происходит от латинского pars ( orationis ), что означает часть (речи) . [1]
Термин имеет несколько разные значения в разных отраслях лингвистики и компьютерных наук . Традиционный синтаксический анализ предложений часто выполняется как метод понимания точного значения предложения или слова, иногда с помощью таких устройств, как диаграммы предложений . Обычно он подчеркивает важность грамматических подразделений, таких как подлежащее и сказуемое .
В компьютерной лингвистике этот термин используется для обозначения формального анализа компьютером предложения или другой строки слов на ее составляющие, в результате чего получается дерево разбора, показывающее их синтаксическую связь друг с другом, которое также может содержать семантическую информацию. [ необходима цитата ] Некоторые алгоритмы синтаксического анализа генерируют лес разбора или список деревьев разбора из строки, которая является синтаксически неоднозначной . [2]
Этот термин также используется в психолингвистике при описании понимания языка. В этом контексте синтаксический анализ относится к способу, которым люди анализируют предложение или фразу (в устной речи или тексте) «с точки зрения грамматических составляющих, определения частей речи, синтаксических отношений и т. д.» [1] Этот термин особенно распространен при обсуждении того, какие языковые сигналы помогают говорящим интерпретировать предложения типа «садовая дорожка» .
В компьютерной науке этот термин используется в анализе компьютерных языков , ссылаясь на синтаксический анализ входного кода на его составные части с целью облегчения написания компиляторов и интерпретаторов . Этот термин также может использоваться для описания разделения или разбиения.
Традиционное грамматическое упражнение по синтаксическому анализу, иногда называемое анализом предложения , включает в себя разбиение текста на его составные части речи с объяснением формы, функции и синтаксических отношений каждой части. [3] Это определяется в значительной степени из изучения спряжений и склонений языка , которые могут быть довольно сложными для сильно флективных языков. Чтобы разобрать фразу, такую как «man bites dog», необходимо отметить, что единственное число существительного «man» является подлежащим предложения, глагол «bites» является третьим лицом единственного числа настоящего времени глагола «to bite», а единственное число существительного «dog» является дополнением предложения . Иногда для указания связи между элементами в предложении используются такие методы, как диаграммы предложений .
Раньше синтаксический анализ был центральным в преподавании грамматики во всем англоязычном мире и широко рассматривался как основа для использования и понимания письменного языка. Однако общее обучение таким методам больше не актуально. [ необходима цитата ]
В некоторых системах машинного перевода и обработки естественного языка письменные тексты на человеческих языках анализируются компьютерными программами. [4] Человеческие предложения нелегко анализируются программами, поскольку в структуре человеческого языка существует существенная двусмысленность , использование которого заключается в передаче смысла (или семантики ) среди потенциально неограниченного диапазона возможностей, но только некоторые из них уместны в конкретном случае. [5] Таким образом, высказывание «Человек кусает собаку» по сравнению с «Собака кусает человека» является определенным в одной детали, но на другом языке может выглядеть как «Человек собаку кусает» с опорой на более широкий контекст, чтобы различать эти две возможности, если бы это различие действительно имело значение. Трудно подготовить формальные правила для описания неформального поведения, даже если ясно, что некоторые правила соблюдаются. [ необходима цитата ]
Для анализа данных естественного языка исследователи должны сначала договориться о грамматике , которая будет использоваться. Выбор синтаксиса зависит как от лингвистических , так и от вычислительных соображений; например, некоторые системы анализа используют лексическую функциональную грамматику , но в целом анализ грамматик этого типа, как известно, является NP-полным . Грамматика структуры фраз, управляемая головой, — это еще один лингвистический формализм, который был популярен в сообществе анализа, но другие исследовательские усилия были сосредоточены на менее сложных формализмах, таких как тот, который используется в Penn Treebank . Поверхностный анализ направлен на поиск только границ основных компонентов, таких как именные группы. Еще одна популярная стратегия избежания лингвистических противоречий — анализ грамматики зависимостей .
Большинство современных парсеров являются по крайней мере частично статистическими; то есть они полагаются на корпус обучающих данных, которые уже были аннотированы (разобраны вручную). Этот подход позволяет системе собирать информацию о частоте, с которой различные конструкции встречаются в определенных контекстах. (См. машинное обучение .) Используемые подходы включают простые PCFG (вероятностные контекстно-свободные грамматики), [6] максимальную энтропию , [7] и нейронные сети . [8] Большинство наиболее успешных систем используют лексическую статистику (то есть они учитывают идентичность задействованных слов, а также их часть речи ). Однако такие системы уязвимы к переобучению и требуют некоторого сглаживания для эффективности. [ необходима цитата ]
Алгоритмы синтаксического анализа для естественного языка не могут полагаться на грамматику, имеющую «хорошие» свойства, как в случае с вручную разработанными грамматиками для языков программирования. Как упоминалось ранее, некоторые грамматические формализмы очень трудно анализировать вычислительно; в общем, даже если желаемая структура не является контекстно-свободной , для выполнения первого прохода используется некое контекстно-свободное приближение к грамматике. Алгоритмы, которые используют контекстно-свободные грамматики, часто полагаются на какой-либо вариант алгоритма CYK , обычно с некоторой эвристикой для отсечения маловероятных анализов для экономии времени. (См. анализ диаграммы .) Однако некоторые системы жертвуют скоростью ради точности, используя, например, версии алгоритма сдвига-свертки с линейным временем . Несколько недавней разработкой стало повторное ранжирование синтаксического анализа, при котором синтаксический анализатор предлагает некоторое большое количество анализов, а более сложная система выбирает лучший вариант. [ требуется цитата ] В приложениях понимания естественного языка семантические синтаксические анализаторы преобразуют текст в представление его значения. [9]
В психолингвистике синтаксический анализ подразумевает не только отнесение слов к категориям (формирование онтологических идей), но и оценку смысла предложения в соответствии с правилами синтаксиса, выведенными из выводов, сделанных из каждого слова в предложении (известными как коннотация ). Обычно это происходит, когда слова слышатся или читаются.
Нейролингвистика обычно понимает синтаксический анализ как функцию рабочей памяти, то есть синтаксический анализ используется для того, чтобы держать в уме одновременно несколько частей одного предложения, все из которых легкодоступны для анализа по мере необходимости. Поскольку рабочая память человека имеет ограничения, то же самое касается и функции синтаксического анализа предложений. [10] Об этом свидетельствуют несколько различных типов синтаксически сложных предложений, которые потенциально представляют проблемы для ментального синтаксического анализа предложений.
Первый и, возможно, самый известный тип предложения, который бросает вызов синтаксическому анализу, — это предложение garden-path. Эти предложения составлены таким образом, что наиболее распространенная интерпретация предложения кажется грамматически неверной, но при дальнейшем рассмотрении эти предложения грамматически верны. Предложения garden-path трудно разбирать, потому что они содержат фразу или слово с более чем одним значением, часто их наиболее типичным значением является другая часть речи. [11] Например, в предложении «лошадь промчалась мимо амбара упала» raced изначально интерпретируется как глагол в прошедшем времени, но в этом предложении оно функционирует как часть прилагательной фразы. [12] Поскольку синтаксический анализ используется для определения частей речи, эти предложения бросают вызов синтаксическому анализу читателя.
Другой тип предложения, который трудно разобрать, — это неоднозначность присоединения, которая включает фразу, которая может потенциально изменять различные части предложения, и, следовательно, представляет собой проблему при определении синтаксической связи (например, «Мальчик увидел даму с телескопом», в котором неоднозначная фраза с телескопом может изменять слова «мальчик увидел» или «дама»). [11]
Третий тип предложений, который бросает вызов синтаксическому анализу, — это центральное встраивание, в котором фразы помещаются в центр других, аналогично сформированных фраз (например, «Крыса, которую преследовал мужчина, забежала в ловушку»). Предложения с 2 или, в самых крайних случаях, с 3 центральными встраиваниями сложны для ментального анализа, опять же из-за неоднозначности синтаксических отношений. [13]
В нейролингвистике существует множество теорий, которые направлены на описание того, как синтаксический анализ происходит в мозге. Одна из таких моделей — более традиционная генеративная модель обработки предложений, которая предполагает, что в мозге есть отдельный модуль, предназначенный для синтаксического анализа предложений, которому предшествует доступ к лексическому распознаванию и извлечению, а затем следует синтаксическая обработка, которая рассматривает один синтаксический результат синтаксического анализа, возвращаясь только для пересмотра этой синтаксической интерпретации, если обнаружена потенциальная проблема. [14] Противоположная, более современная модель предполагает, что в уме обработка предложения не является модульной или происходит в строгой последовательности. Скорее, она предполагает, что несколько различных синтаксических возможностей могут рассматриваться одновременно, поскольку лексический доступ, синтаксическая обработка и определение значения происходят в мозге параллельно. Таким образом, эти процессы интегрируются. [15]
Хотя еще многое предстоит узнать о неврологии синтаксического анализа, исследования показали, что несколько областей мозга могут играть роль в синтаксическом анализе. К ним относятся левый передний височный полюс, левая нижняя лобная извилина, левая верхняя височная извилина, левая верхняя лобная извилина, правая задняя поясная извилина и левая угловая извилина. Хотя это не было абсолютно доказано, было высказано предположение, что эти различные структуры могут благоприятствовать либо синтаксическому анализу фразовой структуры, либо синтаксическому анализу зависимой структуры, то есть различные типы синтаксического анализа могут обрабатываться разными способами, которые еще предстоит понять. [16]
Анализ дискурса изучает способы анализа использования языка и семиотических событий. Убеждающий язык можно назвать риторикой .
Парсер — это программный компонент, который принимает входные данные (обычно текст) и строит структуру данных — часто своего рода дерево синтаксического анализа , абстрактное синтаксическое дерево или другую иерархическую структуру, давая структурное представление ввода, проверяя при этом правильность синтаксиса. Парсингу могут предшествовать или следовать другие шаги, или они могут быть объединены в один шаг. Парсеру часто предшествует отдельный лексический анализатор , который создает токены из последовательности входных символов; в качестве альтернативы они могут быть объединены в парсинг без сканирования . Парсеры могут быть запрограммированы вручную или могут быть автоматически или полуавтоматически сгенерированы генератором парсеров . Парсинг дополняет шаблонизацию , которая производит форматированный вывод. Они могут применяться к разным доменам, но часто появляются вместе, например, пара scanf / printf или входные (фронтальный парсинг) и выходные (генерация бэкэнд кода) этапы компилятора .
Входные данные для парсера обычно представляют собой текст на каком-либо компьютерном языке , но также могут быть текстом на естественном языке или менее структурированными текстовыми данными, в этом случае обычно извлекаются только определенные части текста, а не строится дерево разбора. Парсеры варьируются от очень простых функций, таких как scanf , до сложных программ, таких как frontend компилятора C++ или HTML -парсер веб-браузера . Важный класс простого парсинга выполняется с использованием регулярных выражений , в которых группа регулярных выражений определяет регулярный язык , а механизм регулярных выражений автоматически генерирует парсер для этого языка, позволяя сопоставлять шаблоны и извлекать текст. В других контекстах регулярные выражения вместо этого используются до парсинга, как шаг лексического анализа, вывод которого затем используется парсером.
Использование парсеров различается в зависимости от входных данных. В случае языков данных парсер часто встречается как средство чтения файлов программы, например, чтение в тексте HTML или XML ; эти примеры являются языками разметки . В случае языков программирования парсер является компонентом компилятора или интерпретатора , который анализирует исходный код языка программирования для создания некоторой формы внутреннего представления; парсер является ключевым шагом во внешнем интерфейсе компилятора . Языки программирования, как правило, определяются в терминах детерминированной контекстно-свободной грамматики, поскольку для них можно написать быстрые и эффективные парсеры. Для компиляторов сам парсер может быть выполнен за один проход или несколько проходов — см. однопроходный компилятор и многопроходный компилятор .
Подразумеваемые недостатки однопроходного компилятора можно в значительной степени преодолеть, добавив исправления , где предусмотрено перемещение кода во время прямого прохода, и исправления применяются в обратном направлении, когда текущий сегмент программы распознан как завершенный. Примером, где такой механизм исправления был бы полезен, был бы оператор прямого GOTO, где цель GOTO неизвестна, пока сегмент программы не будет завершен. В этом случае применение исправления будет отложено до тех пор, пока цель GOTO не будет распознана. И наоборот, обратный GOTO не требует исправления, так как местоположение уже будет известно.
Контекстно-свободные грамматики ограничены в той степени, в которой они могут выразить все требования языка. Неформально, причина в том, что память такого языка ограничена. Грамматика не может запомнить наличие конструкции в произвольно длинном вводе; это необходимо для языка, в котором, например, имя должно быть объявлено до того, как на него можно будет ссылаться. Более мощные грамматики, которые могут выразить это ограничение, однако, не могут быть проанализированы эффективно. Таким образом, это общая стратегия создания расслабленного синтаксического анализатора для контекстно-свободной грамматики, которая принимает надмножество желаемых языковых конструкций (то есть принимает некоторые недопустимые конструкции); позже нежелательные конструкции могут быть отфильтрованы на этапе семантического анализа (контекстного анализа).
Например, в Python следующий код является синтаксически допустимым:
х = 1 печать ( х )Однако следующий код синтаксически допустим с точки зрения контекстно-свободной грамматики, создавая синтаксическое дерево с той же структурой, что и предыдущее, но нарушает семантическое правило, требующее инициализации переменных перед использованием:
x = 1 печать ( y )Следующий пример демонстрирует распространенный случай анализа компьютерного языка с двумя уровнями грамматики: лексическим и синтаксическим.
Первый этап — это генерация токенов, или лексический анализ , с помощью которого поток входных символов разделяется на осмысленные символы, определяемые грамматикой регулярных выражений . Например, программа-калькулятор будет рассматривать входные данные, такие как " 12 * (3 + 4)^2", и разделять их на токены 12, *, (, 3, +, 4, ), ^, 2, каждый из которых является осмысленным символом в контексте арифметического выражения. Лексер будет содержать правила, сообщающие ему, что символы *, +, ^, (и )отмечают начало нового токена, поэтому бессмысленные токены, такие как " 12*" или " (3", не будут генерироваться.
Следующий этап — разбор или синтаксический анализ, который проверяет, что токены образуют допустимое выражение. Обычно это делается со ссылкой на контекстно-свободную грамматику , которая рекурсивно определяет компоненты, которые могут составлять выражение, и порядок, в котором они должны появляться. Однако не все правила, определяющие языки программирования, могут быть выражены только контекстно-свободными грамматиками, например, валидность типов и правильное объявление идентификаторов. Эти правила могут быть формально выражены с помощью атрибутных грамматик .
Заключительная фаза — семантический разбор или анализ, который вырабатывает импликации только что проверенного выражения и предпринимает соответствующие действия. [17] В случае калькулятора или интерпретатора действие заключается в оценке выражения или программы; компилятор, с другой стороны, сгенерирует некий код. Атрибутивные грамматики также могут использоваться для определения этих действий.
Задача парсера по сути заключается в том , чтобы определить, может ли ввод быть получен из начального символа грамматики и каким образом. Это можно сделать двумя способами:
LL-парсеры и рекурсивно-спусковые парсеры являются примерами нисходящих парсеров, которые не могут вместить леворекурсивные правила производства . Хотя считалось, что простые реализации нисходящего парсинга не могут вместить прямую и косвенную левую рекурсию и могут потребовать экспоненциальной временной и пространственной сложности при разборе неоднозначных контекстно-свободных грамматик , более сложные алгоритмы для нисходящего парсинга были созданы Фростом, Хафизом и Каллаганом [20] [21] , которые вмещают неоднозначность и левую рекурсию за полиномиальное время и которые генерируют представления полиномиального размера потенциально экспоненциального числа деревьев парсинга. Их алгоритм способен производить как самые левые, так и самые правые вывода входных данных относительно заданной контекстно-свободной грамматики .
Важное различие в отношении парсеров заключается в том, генерирует ли парсер левое или правое выводное значение (см. контекстно-свободную грамматику ). Парсеры LL генерируют левое выводное значение , а парсеры LR генерируют правое выводное значение (хотя обычно в обратном порядке). [18]
НекоторыйГрафические алгоритмы синтаксического анализа были разработаны длявизуальных языков программирования.[22][23]Парсеры для визуальных языков иногда основаны награфовых грамматиках.[24]
Алгоритмы адаптивного анализа использовались для создания «саморасширяющихся» пользовательских интерфейсов на естественном языке . [25]
Простая реализация синтаксического анализатора считывает весь входной файл, выполняет промежуточное вычисление или перевод, а затем записывает весь выходной файл, как, например, многопроходные компиляторы в памяти .
Альтернативные подходы к реализации парсера:
Некоторые из известных инструментов разработки парсеров включают в себя следующее:
int v;main(){vLookahead устанавливает максимальное количество входящих токенов, которые может использовать анализатор для принятия решения о том, какое правило следует использовать. Lookahead особенно актуален для анализаторов LL , LR и LALR , где он часто явно указывается путем добавления lookahead к имени алгоритма в скобках, например, LALR(1).
Большинство языков программирования , основная цель парсеров, тщательно определены таким образом, что парсер с ограниченным просмотром вперед, как правило, один, может их разобрать, потому что парсеры с ограниченным просмотром вперед часто более эффективны. Одно важное изменение [ требуется ссылка ] в этой тенденции произошло в 1990 году, когда Теренс Парр создал ANTLR для своей докторской диссертации, генератор парсеров для эффективных парсеров LL( k ), где k — любое фиксированное значение.
LR-парсеры обычно имеют только несколько действий после просмотра каждого токена. Это сдвиг (добавление этого токена в стек для последующего сокращения), сокращение (извлечение токенов из стека и формирование синтаксической конструкции), конец, ошибка (не применяется известное правило) или конфликт (не знает, сдвигать или сокращать).
У Lookahead есть два преимущества. [ необходимо разъяснение ]
Пример: Разбор выражения 1 + 2 * 3 [ сомнительный – обсудить ]
Большинство языков программирования (за исключением нескольких, таких как APL и Smalltalk) и алгебраических формул отдают более высокий приоритет умножению, чем сложению, в этом случае правильная интерпретация примера выше — 1 + (2 * 3) . Обратите внимание, что Правило 4 выше — это семантическое правило. Можно переписать грамматику, чтобы включить это в синтаксис. Однако не все такие правила можно перевести в синтаксис.
Первоначально ввод = [1, +, 2, *, 3]
Дерево синтаксического анализа и полученный из него код неверны с точки зрения семантики языка.
Для корректного анализа без просмотра вперед есть три решения:
Сгенерированное дерево разбора является правильным и просто более эффективным [ уточнить ] [ требуется цитата ] чем не-lookahead парсеры. Это стратегия, которой следуют в парсерах LALR .
{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)