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