Разбор - Parsing

Разбор , анализ синтаксиса или синтаксический анализ является процессом анализа строки из символов , либо на естественном языке , компьютерных языках или структуры данных , в соответствии с правилами в формальных грамматиках . Термин синтаксический анализ происходит от латинского pars ( orationis ), что означает часть (речи) .

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

В рамках компьютерной лингвистики этот термин используется для обозначения формального компьютерного анализа предложения или другой строки слов на его составные части, в результате чего получается дерево синтаксического анализа, показывающее их синтаксические отношения друг с другом, которое также может содержать семантическую и другую информацию ( p-значения ). Некоторые алгоритмы синтаксического анализа могут генерировать лес синтаксического анализа или список деревьев синтаксического анализа для синтаксически неоднозначного ввода.

Этот термин также используется в психолингвистике при описании понимания языка. В этом контексте синтаксический анализ относится к способу, которым люди анализируют предложение или фразу (в разговорной речи или тексте) «с точки зрения грамматических составляющих, идентифицируя части речи, синтаксические отношения и т. Д.» Этот термин особенно часто встречается при обсуждении того, какие лингвистические подсказки помогают говорящим интерпретировать предложения с тропинками .

В информатике этот термин используется при анализе компьютерных языков , имея в виду синтаксический анализ входного кода на его составные части, чтобы облегчить написание компиляторов и интерпретаторов . Этот термин также может использоваться для описания разделения или разделения.

Человеческие языки

Традиционные методы

Традиционное грамматическое упражнение по синтаксическому анализу, иногда известное как анализ предложений , включает разбиение текста на составные части речи с объяснением формы, функции и синтаксических отношений каждой части. Это определяется в значительной степени от изучения языка в спряжения и склонения , которые могут быть довольно запутанными для сильно флективных языков. Для того, чтобы разобрать фразу типа «человек укусов собаки» включает в себя , отметив , что в единственном числе существительное «человек» является предметом приговора, глагол «укусы» является третье лицо единственного из настоящего времени глагола «кусать», и существительное в единственном числе «собака» является объектом предложения. Такие приемы, как диаграммы предложений , иногда используются для обозначения взаимосвязи между элементами в предложении.

Раньше синтаксический анализ занимал центральное место в преподавании грамматики во всем англоязычном мире и широко рассматривался как основа для использования и понимания письменного языка. Однако общее обучение таким техникам больше не актуально.

Вычислительные методы

В некоторых системах машинного перевода и обработки естественного языка письменные тексты на человеческих языках анализируются компьютерными программами. Человеческие предложения нелегко анализировать программами, поскольку существует значительная неоднозначность в структуре человеческого языка, использование которого заключается в передаче значения (или семантики ) среди потенциально неограниченного диапазона возможностей, но только некоторые из них имеют отношение к конкретному случаю. Таким образом, высказывание «Человек кусает собаку» по сравнению с «Собака кусает человека» определенно по одной детали, но на другом языке может выглядеть как «Человек кусает собаку» с опорой на более широкий контекст, чтобы различать эти две возможности, если это действительно так. беспокойства. Трудно подготовить формальные правила для описания неформального поведения, хотя очевидно, что некоторые правила соблюдаются.

Чтобы проанализировать данные на естественном языке, исследователи должны сначала согласовать грамматику, которая будет использоваться. На выбор синтаксиса влияют как лингвистические, так и вычислительные проблемы; например, некоторые системы синтаксического анализа используют лексическую функциональную грамматику , но в целом известно, что синтаксический анализ грамматик этого типа является NP-полным . Грамматика структуры фраз, управляемая заголовком, - это еще один лингвистический формализм, который был популярен в сообществе синтаксического анализа, но другие исследовательские усилия были сосредоточены на менее сложных формализмах, таких как тот, который используется в Penn Treebank . Мелкий анализ направлен на поиск только границ основных составляющих, таких как словосочетания с существительными. Другой популярной стратегией избежания лингвистических противоречий является синтаксический анализ грамматики зависимостей .

Большинство современных парсеров хотя бы частично являются статистическими ; то есть они полагаются на корпус обучающих данных, которые уже были аннотированы (проанализированы вручную). Этот подход позволяет системе собирать информацию о частоте, с которой различные конструкции встречаются в определенных контекстах. (См. Машинное обучение .) Используемые подходы включают простые PCFG (вероятностные контекстно-свободные грамматики), максимальную энтропию и нейронные сети . Большинство наиболее успешных систем используют лексическую статистику (то есть они учитывают идентичность задействованных слов, а также их часть речи ). Однако такие системы уязвимы для переобучения и требуют некоторого сглаживания, чтобы быть эффективными.

Алгоритмы синтаксического анализа для естественного языка не могут полагаться на грамматику, имеющую «хорошие» свойства, как в случае грамматик, созданных вручную для языков программирования. Как упоминалось ранее, некоторые грамматические формализмы очень трудно анализировать с помощью вычислений; в общем, даже если желаемая структура не является контекстно-независимой , для выполнения первого прохода используется некоторая неконтекстная аппроксимация грамматики. Алгоритмы, использующие контекстно-свободные грамматики, часто полагаются на какой-либо вариант алгоритма CYK , обычно с некоторой эвристикой, чтобы отсечь маловероятный анализ и сэкономить время. (См. Анализ диаграммы .) Однако некоторые системы жертвуют скоростью ради точности, используя, например, линейные версии алгоритма уменьшения сдвига . Отчасти недавняя разработка заключалась в изменении ранжирования синтаксического анализа, при котором синтаксический анализатор предлагает некоторое большое количество анализов, а более сложная система выбирает лучший вариант. Семантические синтаксические анализаторы преобразуют тексты в представления их значений.

Психолингвистика

В психолингвистике синтаксический анализ включает не только присвоение слов категориям (формирование онтологических идей), но и оценку значения предложения в соответствии с правилами синтаксиса, сделанными на основе выводов, сделанных из каждого слова в предложении (известное как коннотация ). . Обычно это происходит, когда слова слышны или читаются. Следовательно, психолингвистические модели синтаксического анализа по необходимости являются инкрементными , что означает, что они создают интерпретацию по мере обработки предложения, которая обычно выражается в терминах частичной синтаксической структуры. При толковании предложений « садовая дорожка» возникает создание изначально неправильных структур .

Анализ речи

Анализ дискурса изучает способы анализа использования языка и семиотических событий. Убедительный язык можно назвать риторикой .

Компьютерные языки

Парсер

Анализатор представляет собой программный компонент , который принимает входные данные (часто текст) и строит структуру данных - часто своего рода дерево разбора , абстрактного синтаксического дерева или другой иерархической структуры, что дает структурное представление ввода при проверке правильности синтаксиса. Синтаксическому анализу могут предшествовать или следовать другие шаги, или они могут быть объединены в один шаг. Парсеру часто предшествует отдельный лексический анализатор , который создает токены из последовательности входных символов; в качестве альтернативы они могут быть объединены в синтаксическом анализе без сканирования . Синтаксические анализаторы могут быть запрограммированы вручную или могут быть автоматически или полуавтоматически сгенерированы генератором синтаксического анализатора . Синтаксический анализ является дополнением к шаблону , который производит форматированный вывод. Они могут применяться к разным доменам, но часто появляются вместе, например пара scanf / printf или этапы ввода (анализ внешнего интерфейса) и вывода (генерация внутреннего кода) компилятора.

Входными данными для синтаксического анализатора часто является текст на каком-либо компьютерном языке , но также может быть текст на естественном языке или менее структурированные текстовые данные, и в этом случае обычно извлекаются только определенные части текста, а не строится дерево синтаксического анализа. Парсеры варьируются от очень простых функций, таких как scanf , до сложных программ, таких как интерфейс компилятора C ++ или анализатор HTML веб-браузера . Важный класс простого синтаксического анализа выполняется с использованием регулярных выражений , в которых группа регулярных выражений определяет регулярный язык, а механизм регулярных выражений автоматически генерирует синтаксический анализатор для этого языка, позволяя сопоставление с образцом и извлечение текста. В других контекстах вместо этого перед синтаксическим анализом используются регулярные выражения в качестве шага лексирования, вывод которого затем используется анализатором.

Использование парсеров зависит от ввода. В случае языков данных синтаксический анализатор часто используется как средство чтения файлов программы, например, чтение текста HTML или XML ; эти примеры являются языками разметки . В случае языков программирования синтаксический анализатор - это компонент компилятора или интерпретатора , который анализирует исходный код языка компьютерного программирования для создания некоторой формы внутреннего представления; парсер - это ключевой шаг во внешнем интерфейсе компилятора . Языки программирования, как правило, описываются в терминах детерминированной контекстно-свободной грамматики, потому что для них могут быть написаны быстрые и эффективные синтаксические анализаторы. Для компиляторов сам анализ может выполняться за один проход или за несколько проходов - см. Однопроходный компилятор и многопроходный компилятор .

Подразумеваемые недостатки однопроходного компилятора могут быть в значительной степени преодолены путем добавления исправлений , когда предусматривается перемещение кода во время прямого прохода, а исправления применяются в обратном направлении, когда текущий сегмент программы был признан завершенный. Примером, где такой механизм исправления может быть полезен, может быть прямой оператор GOTO, где цель GOTO неизвестна, пока сегмент программы не будет завершен. В этом случае применение исправления будет отложено до тех пор, пока не будет распознана цель GOTO. И наоборот, обратный GOTO не требует исправления, так как местоположение уже будет известно.

Бесконтекстные грамматики ограничены в степени, в которой они могут выразить все требования языка. Неформально причина в том, что память такого языка ограничена. Грамматика не может запомнить наличие конструкции на произвольно длинном вводе; это необходимо для языка, в котором, например, имя должно быть объявлено до того, как на него можно будет ссылаться. Однако более мощные грамматики, которые могут выразить это ограничение, не могут быть проанализированы эффективно. Таким образом, распространенной стратегией является создание упрощенного синтаксического анализатора для контекстно-свободной грамматики, который принимает надмножество желаемых языковых конструкций (то есть принимает некоторые недопустимые конструкции); позже нежелательные конструкции могут быть отфильтрованы на этапе семантического анализа (контекстного анализа).

Например, в Python следующий синтаксически допустимый код:

x = 1
print(x)

Следующий код, однако, синтаксически допустим с точки зрения контекстно-свободной грамматики, давая синтаксическое дерево с той же структурой, что и предыдущий, но синтаксически недействителен с точки зрения контекстно-зависимой грамматики , которая требует, чтобы переменные были инициализированы перед использовать:

x = 1
print(y)

Вместо анализа на этапе синтаксического анализа это обнаруживается путем проверки значений в синтаксическом дереве, следовательно, как часть семантического анализа: контекстно-зависимый синтаксис на практике часто легче анализировать как семантику.

Обзор процесса

Поток данных в типичном парсере

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

Первый этап - это генерация токена или лексический анализ , с помощью которого входной поток символов разбивается на значимые символы, определяемые грамматикой регулярных выражений . Например, программа калькулятора будет выглядеть на входе , такие как « 12 * (3 + 4)^2» и разделить его на лексемы 12, *, (, 3, +, 4, ), ^, 2, каждый из которых является значимым символом в контексте арифметического выражения. Лексер будет содержать правила , чтобы сказать ему , что символы *, +, ^, (и )отметить начало нового маркера, так бессмысленные маркеры , такие как « 12*» или « (3не будет генерироваться».

Следующим этапом является синтаксический анализ, который проверяет, что токены образуют допустимое выражение. Обычно это делается со ссылкой на контекстно-свободную грамматику, которая рекурсивно определяет компоненты, которые могут составлять выражение, и порядок, в котором они должны появляться. Однако не все правила, определяющие языки программирования, могут быть выражены только контекстно-независимыми грамматиками, например, достоверность типа и правильное объявление идентификаторов. Эти правила могут быть формально выражены с помощью грамматик атрибутов .

Заключительный этап - семантический синтаксический анализ или анализ, который определяет значение только что проверенного выражения и предпринимает соответствующие действия. В случае калькулятора или интерпретатора действие заключается в вычислении выражения или программы; компилятор, с другой стороны, генерирует какой-то код. Грамматики атрибутов также могут использоваться для определения этих действий.

Типы парсеров

Задача синтаксического анализатора, по существу , чтобы определить , когда и каким образом входные данные могут быть получены из начального символа грамматики. Это можно сделать двумя способами:

  • Нисходящий синтаксический анализ. Нисходящий синтаксический анализ можно рассматривать как попытку найти самые левые производные входного потока путем поиска деревьев синтаксического анализа с использованием нисходящего расширения заданных формальных правил грамматики . Жетоны расходуются слева направо. Включающий выбор используется для устранения двусмысленности путем расширения всех альтернативных правых частей правил грамматики. Это известно как изначальный суповой подход. Очень похоже на построение диаграмм предложений, изначальный суп разбивает составные части предложений.
  • Анализ снизу вверх - синтаксический анализатор может начать с ввода и попытаться перезаписать его на начальный символ. Интуитивно синтаксический анализатор пытается найти самые основные элементы, затем элементы, содержащие их, и так далее. Парсеры LR являются примерами восходящих парсеров. Другой термин, используемый для этого типа синтаксического анализатора, - это синтаксический анализ Shift-Reduce .

Анализаторы LL и синтаксический анализатор с рекурсивным спуском являются примерами синтаксических анализаторов сверху вниз, которые не могут поддерживать леворекурсивные производственные правила . Хотя считалось, что простые реализации нисходящего синтаксического анализа не могут приспособиться к прямой и косвенной левой рекурсии и могут потребовать экспоненциальной временной и пространственной сложности при синтаксическом анализе неоднозначных контекстно-свободных грамматик , Фрост создал более сложные алгоритмы для нисходящего синтаксического анализа. , Хафиз и Каллаган, которые приспосабливают неоднозначность и левую рекурсию за полиномиальное время и которые генерируют представления полиномиального размера потенциально экспоненциального числа деревьев синтаксического анализа. Их алгоритм может производить как самые левые, так и самые правые производные ввода с учетом заданной контекстно-свободной грамматики .

Важное различие в отношении синтаксических анализаторов заключается в том, генерирует ли синтаксический анализатор крайний левый вывод или крайний правый вывод (см. Контекстно-свободную грамматику ). Анализаторы LL будут генерировать крайнее левое происхождение, а анализаторы LR будут генерировать крайнее правое происхождение (хотя обычно в обратном порядке).

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

Алгоритмы адаптивного синтаксического анализа использовались для создания «саморасширяющихся» пользовательских интерфейсов на естественном языке .

Программное обеспечение для разработки парсеров

Некоторые из хорошо известных инструментов разработки парсеров включают следующее:

Смотреть вперед

Программа на C, которая не может быть проанализирована менее чем с 2 токенами вперед. Вверху: отрывок из грамматики C. Внизу: синтаксический анализатор переварил токены " " и собирается выбрать правило для получения Stmt . Глядя только на первый предварительный токен " ", он не может решить, какую из обеих альтернатив Stmt выбрать; последнее требует взгляда на второй токен.int v;main(){v

Lookahead устанавливает максимальное количество входящих токенов, которые анализатор может использовать, чтобы решить, какое правило он должен использовать. Предварительный просмотр особенно важен для парсеров LL , LR и LALR , где он часто явно указывается путем добавления предварительного просмотра к имени алгоритма в круглых скобках, например LALR (1).

Большинство языков программирования , которые являются основной целью синтаксических анализаторов, тщательно определены таким образом, чтобы синтаксический анализатор с ограниченным просмотром вперед, обычно один, мог анализировать их, потому что синтаксические анализаторы с ограниченным прогнозом часто более эффективны. Одно важное изменение в этой тенденции произошло в 1990 году, когда Теренс Парр создал ANTLR для своей докторской степени. thesis, генератор парсеров для эффективных парсеров LL ( k ), где k - любое фиксированное значение.

Парсеры LR обычно выполняют всего несколько действий после просмотра каждого токена. Это сдвиг (добавить этот токен в стек для последующего сокращения), уменьшить (извлечь токены из стека и сформировать синтаксическую конструкцию), конец, ошибка (не применяется известное правило) или конфликт (не знает, сдвигать или уменьшать) .

Lookahead имеет два преимущества.

  • Это помогает синтаксическому анализатору предпринять правильные действия в случае конфликтов. Например, анализ оператора if в случае предложения else.
  • Это устраняет множество повторяющихся состояний и снижает нагрузку на дополнительный стек. Непредвиденный синтаксический анализатор языка AC будет иметь около 10 000 состояний. Синтаксический анализатор просмотра вперед будет иметь около 300 состояний.

Пример: анализ выражения 1 + 2 * 3

Набор правил синтаксического анализа выражений (называемых грамматикой) выглядит следующим образом:
Правило 1: E → E + E Выражение - это сумма двух выражений.
Правило 2: E → E * E Выражение - это произведение двух выражений.
Правило 3: E → число Выражение - это простое число
Правило 4: + имеет меньший приоритет, чем *

Большинство языков программирования (за исключением некоторых, таких как APL и Smalltalk) и алгебраических формул отдают более высокий приоритет умножению, чем сложению, и в этом случае правильная интерпретация приведенного выше примера - 1 + (2 * 3) . Обратите внимание, что Правило 4 выше является семантическим правилом. Можно переписать грамматику, чтобы включить это в синтаксис. Однако не все такие правила можно перевести в синтаксис.

Простые непросматриваемые действия парсера

Первоначально ввод = [1, +, 2, *, 3]

  1. Переместите "1" в стек из ввода (в ожидании правила 3). Ввод = [+, 2, *, 3] Стек = [1]
  2. Уменьшает "1" до выражения "E" на основе правила 3. Стек = [E]
  3. Переместите "+" в стек из ввода (в ожидании правила 1). Ввод = [2, *, 3] Стек = [E, +]
  4. Переместите "2" в стек из ввода (в ожидании правила 3). Ввод = [*, 3] Стек = [E, +, 2]
  5. Уменьшите элемент стека «2» до выражения «E» на основе правила 3. Стек = [E, +, E]
  6. Уменьшите элементы стека [E, +, E] и новый ввод «E» до «E» на основе правила 1. Стек = [E]
  7. Переместите "*" в стек из ввода (в ожидании правила 2). Вход = [3] Стек = [E, *]
  8. Переместите "3" в стек из ввода (в ожидании правила 3). Ввод = [] (пусто) Стек = [E, *, 3]
  9. Сократите элемент стека «3» до выражения «E» на основе правила 3. Стек = [E, *, E]
  10. Уменьшите элементы стека [E, *, E] и новый ввод «E» до «E» на основе правила 2. Стек = [E]

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

Чтобы правильно выполнить синтаксический анализ без просмотра вперед, есть три решения:

  • Пользователь должен заключать выражения в круглые скобки. Часто это не жизнеспособное решение.
  • Синтаксическому анализатору необходимо иметь больше логики для возврата и повторной попытки всякий раз, когда правило нарушается или не завершено. Аналогичный метод используется в парсерах LL.
  • В качестве альтернативы, синтаксический анализатор или грамматика должны иметь дополнительную логику для сокращения задержки и сокращения только тогда, когда он абсолютно уверен, какое правило сокращать первым. Этот метод используется в парсерах LR. Это правильно анализирует выражение, но с большим количеством состояний и увеличенной глубиной стека.
Действия парсера Lookahead
  1. Переместите 1 в стек на входе 1 в ожидании правила 3. Снижается не сразу.
  2. Уменьшите элемент стека 1 до простого Выражения на входе + на основе правила 3. Предварительный просмотр равен +, поэтому мы находимся на пути к E +, поэтому мы можем уменьшить стек до E.
  3. Shift + в стек на входе + в ожидании правила 1.
  4. Переместите 2 в стек на входе 2 в ожидании правила 3.
  5. Уменьшите элемент стека 2 до Выражения на входе * в соответствии с правилом 3. Предварительный просмотр * ожидает только E.
  6. Теперь в стеке есть E + E, а на входе по-прежнему *. Теперь у него есть два варианта: либо сдвиг на основе правила 2, либо сокращение на основе правила 1. Так как * имеет более высокий приоритет, чем + на основании правила 4, мы переносим * в стек в ожидании правила 2.
  7. Переместите 3 в стек на входе 3 в ожидании правила 3.
  8. Уменьшите элемент стека 3 до Expression после того, как увидите конец ввода в соответствии с правилом 3.
  9. Уменьшите элементы стека с E * E до E в соответствии с правилом 2.
  10. Уменьшите элементы стека E + E до E в соответствии с правилом 1.

Сгенерированное дерево синтаксического анализа является правильным и просто более эффективным, чем парсеры без предварительного просмотра. Это стратегия, которой следуют парсеры LALR .

Смотрите также

использованная литература

21. Бесплатный анализ HTML-кодов [1]

дальнейшее чтение

внешние ссылки