Разбор
Синтаксический анализ , синтаксический анализ или синтаксический анализ — это процесс анализа строки символов в на естественном языке , компьютерных языках или структурах данных , соответствующий правилам формальной грамматики . Термин синтаксический анализ происходит от латинского pars ( orationis ), что означает часть (речи) . [1]
Этот термин имеет несколько разные значения в разных областях лингвистики и информатики . Традиционный анализ предложений часто выполняется как метод понимания точного значения предложения или слова, иногда с помощью таких устройств, как диаграммы предложений . Обычно подчеркивается важность таких грамматических подразделений, как подлежащее и сказуемое .
В компьютерной лингвистике этот термин используется для обозначения формального анализа с помощью компьютера предложения или другой строки слов на его составляющие, в результате чего получается дерево разбора , показывающее их синтаксическое отношение друг к другу, которое также может содержать семантическую информацию. [ нужна цитата ] Некоторые алгоритмы синтаксического анализа генерируют лес синтаксического анализа или список деревьев синтаксического анализа из строки, которая является синтаксически неоднозначной . [2]
Этот термин также используется в психолингвистике при описании понимания языка. В этом контексте синтаксический анализ означает способ, которым люди анализируют предложение или фразу (в устной речи или тексте) «с точки зрения грамматических составляющих, определения частей речи, синтаксических отношений и т. д.». [1] Этот термин особенно часто встречается при обсуждении того, какие лингвистические сигналы помогают говорящим интерпретировать предложения о садовых дорожках .
В рамках информатики этот термин используется при анализе компьютерных языков , имея в виду синтаксический анализ входного кода на его составные части с целью облегчить написание компиляторов и интерпретаторов . Этот термин также может использоваться для описания разделения или разделения.
Человеческие языки [ править ]
Традиционные методы [ править ]
Традиционное грамматическое упражнение синтаксического анализа, иногда называемое анализом предложений , включает в себя разбиение текста на составные части речи с объяснением формы, функции и синтаксических отношений каждой части. [3] Это определяется в значительной степени изучением языковых спряжений и склонений , которые могут быть довольно сложными для сильно склоняемых языков. Чтобы разобрать такую фразу, как «человек кусает собаку», необходимо отметить, что существительное «человек» в единственном числе является подлежащим в предложении, глагол «кусает» — это третье лицо единственного числа настоящего времени глагола «кусать», и существительное «собака» в единственном числе является объектом предложения. Такие методы, как диаграммы предложений, иногда используются для обозначения связи между элементами в предложении.
Раньше синтаксический анализ занимал центральное место в преподавании грамматики во всем англоязычном мире и широко считался основой использования и понимания письменной речи. Однако общее преподавание таких техник больше не актуально. [ нужна цитата ]
Вычислительные методы [ править ]
 | Это раздел нуждается в дополнительных ссылок для проверки . ( февраль 2013 г. ) |
В некоторых системах машинного перевода и обработки естественного языка письменные тексты на человеческих языках анализируются компьютерными программами. [4] Человеческие предложения нелегко анализировать с помощью программ, поскольку существует значительная двусмысленность в структуре человеческого языка, использование которого предназначено для передачи значения (или семантики ) среди потенциально неограниченного диапазона возможностей, но только некоторые из которых имеют отношение к конкретному случаю. . [5] Таким образом, высказывание «Человек кусает собаку» и «Собака кусает человека» является определенным в одной детали, но на другом языке может выглядеть как «Человек кусает собаку», если полагаться на более широкий контекст, чтобы различить эти две возможности, если бы это различие действительно было существенным. беспокойства. Трудно подготовить формальные правила для описания неформального поведения, хотя очевидно, что некоторые правила соблюдаются. [ нужна цитата ]
Чтобы проанализировать данные естественного языка, исследователи должны сначала договориться о грамматике, которая будет использоваться. На выбор синтаксиса влияют как лингвистические , так и вычислительные проблемы; например, некоторые системы синтаксического анализа используют лексическую функциональную грамматику , но в целом синтаксический анализ грамматик этого типа, как известно, является NP-полным . Грамматика структуры фраз, управляемая головой, — это еще один лингвистический формализм, который был популярен в сообществе синтаксического анализа, но другие исследовательские усилия были сосредоточены на менее сложных формализмах, таких как тот, который используется в Penn Treebank . Поверхностный синтаксический анализ направлен на обнаружение только границ основных составляющих, таких как именные фразы. Еще одна популярная стратегия, позволяющая избежать лингвистических противоречий, — это анализ грамматики зависимостей .
Большинство современных парсеров, по крайней мере частично, являются статистическими; то есть они полагаются на корпус обучающих данных, которые уже были аннотированы (проанализированы вручную). Такой подход позволяет системе собирать информацию о частоте появления различных конструкций в конкретных контекстах. (См. «Машинное обучение» .) Используемые подходы включают простые PCFG (вероятностные контекстно-свободные грамматики), [6] максимальная энтропия , [7] и нейронные сети . [8] Большинство наиболее успешных систем используют лексическую статистику (то есть они учитывают идентичность используемых слов, а также их часть речи ). Однако такие системы уязвимы к переобучению и требуют некоторого сглаживания , чтобы быть эффективными. [ нужна цитата ]
Алгоритмы синтаксического анализа естественного языка не могут полагаться на то, что грамматика имеет «хорошие» свойства, как в случае с грамматиками, созданными вручную для языков программирования. Как упоминалось ранее, некоторые грамматические формализмы очень сложно проанализировать вычислительно; в общем, даже если желаемая структура не является контекстно-свободной , для выполнения первого прохода используется некоторая контекстно-свободная аппроксимация грамматики. Алгоритмы, использующие контекстно-свободные грамматики, часто полагаются на тот или иной вариант алгоритма CYK , обычно с некоторой эвристикой , позволяющей исключить маловероятный анализ и сэкономить время. (См. анализ диаграммы .) с линейным временем Однако некоторые системы жертвуют скоростью ради точности, используя, например, версии алгоритма сдвига-сокращения . Недавней разработкой стало изменение ранжирования синтаксического анализа , при котором синтаксический анализатор предлагает большое количество анализов, а более сложная система выбирает лучший вариант. [ нужна цитата ] В для понимания естественного языка приложениях семантические анализаторы преобразуют текст в представление его значения. [9]
Психолингвистика [ править ]
В психолингвистике синтаксический анализ предполагает не просто отнесение слов к категориям (формирование онтологических представлений), но и оценку значения предложения в соответствии с правилами синтаксиса, сделанными посредством умозаключений, сделанных из каждого слова в предложении (известных как коннотация ). . Обычно это происходит во время прослушивания или чтения слов.
Нейролингвистика обычно понимает синтаксический анализ как функцию рабочей памяти, а это означает, что синтаксический анализ используется для одновременного удержания в уме нескольких частей одного предложения, которые легко доступны для анализа по мере необходимости. Поскольку рабочая память человека имеет ограничения, то же самое имеет и функция синтаксического анализа предложений. [10] Об этом свидетельствуют несколько различных типов синтаксически сложных предложений, которые потенциально создают проблемы для мысленного анализа предложений.
Первый и, пожалуй, самый известный тип предложений, который бросает вызов способности синтаксического анализа, — это предложение о садовой дорожке. Эти предложения построены таким образом, что наиболее распространенная интерпретация предложения кажется грамматически ошибочной, но при дальнейшем рассмотрении эти предложения оказываются грамматически правильными. Предложения с садовой дорожкой трудно разобрать, поскольку они содержат фразу или слово с более чем одним значением, причем часто их наиболее типичным значением является другая часть речи. [11] Например, в предложении «лошадь мчалась мимо сарая упала» первоначально интерпретируется как глагол прошедшего времени, но в этом предложении он функционирует как часть прилагательной фразы. [12] Поскольку синтаксический анализ используется для определения частей речи, эти предложения бросают вызов способности читателя анализировать.
Другой тип предложения, который трудно разобрать, — это двусмысленность вложения, которая включает в себя фразу, которая потенциально может изменить различные части предложения и, следовательно, представляет проблему в выявлении синтаксических отношений (например, «Мальчик видел женщину в телескоп», в котором двусмысленная фраза с телескопом могла изменить либо мальчика, либо женщину.) [11]
Третий тип предложений, который бросает вызов способности синтаксического анализа, - это встраивание по центру, при котором фразы помещаются в центр других фраз аналогичного строения (например, «Крыса, которую преследовал кот, которого сбил мужчина), попала в ловушку».) Предложения с 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] В случае калькулятора или интерпретатора действие заключается в вычислении выражения или программы; с другой стороны, компилятор генерирует некоторый код. Грамматики атрибутов также могут использоваться для определения этих действий.
Типы парсеров [ править ]
Задача синтаксического анализатора состоит в том, чтобы определить , можно ли и каким образом получить входные данные из начального символа грамматики. Это можно сделать по существу двумя способами:
- Синтаксический анализ сверху вниз
- Синтаксический анализ сверху вниз можно рассматривать как попытку найти крайние левые производные входного потока путем поиска деревьев синтаксического анализа с использованием нисходящего расширения заданных формальных грамматических правил. Токены расходуются слева направо. Инклюзивный выбор используется для устранения двусмысленности путем расширения всех альтернативных правых частей грамматических правил. [18] Это известно как подход «первичного супа». Очень похоже на построение диаграмм предложений, первобытный суп разбивает составные части предложений. [19]
- Анализ снизу вверх
- Анализатор может начать с входных данных и попытаться перезаписать их в начальный символ. Интуитивно анализатор пытается найти самые основные элементы, затем элементы, содержащие их, и так далее. LR-парсеры являются примерами восходящих парсеров. Другой термин, используемый для этого типа парсера, — это синтаксический анализ Shift-Reduce .
Анализаторы LL и анализатор с рекурсивным спуском являются примерами анализаторов сверху вниз, которые не могут учитывать левой рекурсии правила производства . Хотя считалось, что простые реализации нисходящего анализа не могут обеспечить прямую и косвенную левую рекурсию и могут потребовать экспоненциальной сложности времени и пространства при анализе неоднозначных контекстно-свободных грамматик , Фростом были созданы более сложные алгоритмы для нисходящего анализа. , Хафиз и Каллаган [20] [21] которые учитывают неоднозначность и левую рекурсию за полиномиальное время и генерируют представления полиномиального размера потенциально экспоненциального числа деревьев синтаксического анализа. Их алгоритм способен производить как самые левые, так и самые правые выводы входных данных относительно заданной контекстно-свободной грамматики .
Важным различием в отношении синтаксических анализаторов является то, генерирует ли синтаксический анализатор крайнее левое или крайнее правое дифференцирование (см. контекстно-свободную грамматику ). Анализаторы LL генерируют самый левый вывод , а анализаторы LR — самый правый вывод (хотя обычно в обратном порядке). [18]
Некоторый Алгоритмы графического анализа были разработаны для языков визуального программирования . [22] [23] Парсеры визуальных языков иногда основаны на грамматиках графов . [24]
Алгоритмы адаптивного анализа использовались для создания «саморасширяющихся» пользовательских интерфейсов на естественном языке . [25]
Реализация [ править ]
Простая реализация синтаксического анализатора считывает весь входной файл, выполняет промежуточные вычисления или перевод, а затем записывает весь выходной файл. в памяти такие как многопроходные компиляторы .
Альтернативные подходы к реализации парсера:
- push-парсеры вызывают зарегистрированные обработчики ( обратные вызовы ), как только парсер обнаруживает соответствующие токены во входном потоке. Push-парсер может пропускать ненужные части входных данных (пример — Expat ).
- pull-парсеры , такие как парсеры, которые обычно используются компиляторов для «вытягивания» входного текста. интерфейсами
- инкрементные анализаторы (например, инкрементальные анализаторы диаграмм ), которым, поскольку текст файла редактируется пользователем, не требуется полностью повторно анализировать весь файл.
- Активные и пассивные парсеры [26] [27]
Программное обеспечение для разработки парсеров [ править ]
 |
Некоторые из хорошо известных инструментов разработки парсеров включают следующее:
Прогноз [ править ]
|
int v;main(){"и собирается выбрать правило для получения Stmt . Смотрим только на первый токен просмотра вперед" v", он не может решить, какую из обеих альтернатив выбрать для Stmt ; последний требует просмотра второго токена. Lookahead устанавливает максимальное количество входящих токенов, которые синтаксический анализатор может использовать, чтобы решить, какое правило ему следует использовать. Упреждающий просмотр особенно актуален для анализаторов LL , LR и LALR , где он часто явно указывается путем добавления упреждающего просмотра к имени алгоритма в круглых скобках, например LALR(1).
Большинство языков программирования , основная цель анализаторов, тщательно определены таким образом, что анализатор с ограниченным просмотром (обычно один) может их анализировать, поскольку анализаторы с ограниченным просмотром часто более эффективны. Одно важное изменение [ нужна цитата ] эта тенденция возникла в 1990 году, когда Теренс Парр создал ANTLR для защиты докторской степени. диссертация — генератор синтаксических анализаторов для эффективных анализаторов LL( k ), где k — любое фиксированное значение.
Анализаторы LR обычно выполняют всего несколько действий после просмотра каждого токена. Это сдвиг (добавление этого токена в стек для последующего сокращения), сокращение (извлечение токенов из стека и формирование синтаксической конструкции), конец, ошибка (не применяется известное правило) или конфликт (неизвестно, смещать или сокращать) .
Lookahead имеет два преимущества. [ нужны разъяснения ]
- Это помогает парсеру предпринять правильные действия в случае конфликтов. Например, анализ оператора if в случае предложения else.
- Это устраняет множество повторяющихся состояний и облегчает бремя дополнительного стека. Синтаксический анализатор языка AC без прогнозирования будет иметь около 10 000 состояний. Упреждающий анализатор будет иметь около 300 состояний.
Пример: анализ выражения 1 + 2 * 3 [ сомнительно ]
| Набор правил синтаксического анализа выражений (называемых грамматикой) выглядит следующим образом: | ||
| Правило1: | Е → Е + Е | Выражение представляет собой сумму двух выражений. |
| Правило2: | Е → Е * Е | Выражение является продуктом двух выражений. |
| Правило3: | Е → номер | Выражение — это простое число |
| Правило 4: | + имеет меньший приоритет, чем * | |
Большинство языков программирования (за исключением некоторых, таких как APL и Smalltalk) и алгебраических формул отдают более высокий приоритет умножению, чем сложению, и в этом случае правильная интерпретация приведенного выше примера — 1 + (2 * 3) . Обратите внимание, что Правило 4 выше является семантическим правилом. Можно переписать грамматику, чтобы включить это в синтаксис. Однако не все такие правила можно перевести в синтаксис.
- Простые действия парсера без прогнозирования
Первоначально ввод = [1, +, 2, *, 3]
- Сдвиньте «1» в стек из ввода (в ожидании правила 3). Ввод = [+, 2, *, 3] Стек = [1]
- Сводит «1» к выражению «E» на основе правила 3. Стек = [Е]
- Сдвиг "+" в стек из ввода (в ожидании правила 1). Ввод = [2, *, 3] Стек = [E, +]
- Сдвиньте «2» в стек из ввода (в ожидании правила 3). Ввод = [*, 3] Стек = [E, +, 2]
- Уменьшите элемент стека «2» до выражения «E» на основе правила 3. Стек = [Е, +, Е]
- Уменьшите элементы стека [E, +, E] и новый ввод «E» до «E» на основе правила 1. Стек = [Е]
- Сдвиг "*" в стек из ввода (в ожидании правила 2). Ввод = [3] Стек = [E,*]
- Сдвиньте «3» в стек из ввода (в ожидании правила 3). Ввод = [] (пустой) Стек = [E, *, 3]
- Сократите элемент стека «3» до выражения «E» на основе правила 3. Стек = [Е, *, Е]
- Уменьшите элементы стека [E, *, E] и новый ввод «E» до «E» на основе правила 2. Стек = [Е]
Дерево разбора и полученный на его основе код некорректны с точки зрения семантики языка.
Чтобы правильно выполнить анализ без просмотра вперед, есть три решения:
- Пользователь должен заключать выражения в круглые скобки. Часто это не является жизнеспособным решением.
- Синтаксическому анализатору необходимо иметь больше логики для возврата и повторения всякий раз, когда правило нарушается или не завершено. Аналогичный метод используется в парсерах LL.
- В качестве альтернативы синтаксическому анализатору или грамматике необходима дополнительная логика для задержки сокращения и сокращения только тогда, когда он абсолютно уверен, какое правило следует сокращать первым. Этот метод используется в парсерах LR. Это правильно анализирует выражение, но с гораздо большим количеством состояний и увеличенной глубиной стека.
- Действия предпросмотрового анализатора [ нужны разъяснения ]
- Сдвиг 1 в стек на входе 1 в ожидании правила 3. Оно не уменьшается сразу.
- Сократите элемент стека 1 до простого выражения на входе + на основе правила 3. Упреждающий просмотр равен +, поэтому мы находимся на пути к E +, поэтому мы можем уменьшить стек до E.
- Shift + в стек при вводе + в ожидании правила 1.
- Переместить 2 в стек на входе 2 в ожидании правила 3.
- Уменьшите элемент стека 2 до Выражения на входе * на основе правила 3. Предварительный просмотр * ожидает перед собой только E.
- Теперь стек имеет E + E, а вход по-прежнему равен *. Теперь у него есть два варианта: либо сдвиг на основе правила 2, либо сокращение на основе правила 1. Поскольку * имеет более высокий приоритет, чем +, на основании правила 4, мы сдвигаем * в стек в ожидании правила 2.
- Переместите 3 в стек на входе 3 в ожидании правила 3.
- Уменьшите элемент стека 3 до Выражения после того, как увидите конец ввода на основе правила 3.
- Уменьшите элементы стека E * E до E на основе правила 2.
- Уменьшите элементы стека E + E до E на основе правила 1.
Сгенерированное дерево разбора корректно и просто более эффективно. [ объяснить ] [ нужна цитата ] чем парсеры без прогнозирования. Этой стратегии придерживаются парсеры LALR .
Список алгоритмов синтаксического анализа [ править ]
- Алгоритм CYK : O(n 3 ) алгоритм разбора контекстно-свободных грамматик в нормальной форме Хомского
- Парсер Эрли : еще один O(n 3 ) алгоритм разбора любой контекстно-свободной грамматики
- GLR-парсер : алгоритм анализа любой контекстно-свободной грамматики Масару Томита . Он настроен на детерминированные грамматики, на которых он выполняет почти линейное время и O(n 3 ) в худшем случае.
- Алгоритм внутри-вне : O(n 3 ) алгоритм переоценки вероятностей производства в вероятностных контекстно-свободных грамматиках
- LL-парсер : относительно простой алгоритм синтаксического анализа с линейным временем для ограниченного класса контекстно-свободных грамматик.
- LR-парсер : более сложный алгоритм синтаксического анализа с линейным временем для более широкого класса контекстно-свободных грамматик . Варианты:
- Парсер Packrat : алгоритм анализа с линейным временем , поддерживающий некоторые контекстно-свободные грамматики и анализ грамматик выражений.
- Анализатор рекурсивного спуска : анализатор сверху вниз, подходящий для грамматик LL( k ).
- Алгоритм сортировочной станции : преобразует математическое выражение с инфиксной записью в постфиксную.
- Парсер Пратта
- Лексический анализ
См. также [ править ]
- Возврат
- Парсер диаграмм
- Компилятор-компилятор
- Детерминированный анализ
- Проверка грамматики
- LALR-парсер
- Лексический анализ
- Парсер Пратта
- Поверхностный разбор
- Левый угловой парсер
- Разбор грамматики выражений
- Набор инструментов для реинжиниринга программного обеспечения DMS
- Трансформация программы
- Генерация исходного кода
- Обратный парсер
Ссылки [ править ]
- ^ Перейти обратно: а б «Разбор» . словарь.reference.com . Проверено 27 ноября 2010 г.
- ^ Масару Томита (6 декабря 2012 г.). Обобщенный парсинг LR . Springer Science & Business Media. ISBN 978-1-4615-4034-2 .
- ^ «Грамматика и композиция» . Архивировано из оригинала 1 декабря 2016 г. Проверено 24 ноября 2012 г.
- ^ Кристофер Д. Мэннинг; Кристофер Д. Мэннинг; Хинрих Шютце (1999). Основы статистической обработки естественного языка . МТИ Пресс. ISBN 978-0-262-13360-9 .
- ^ Юрафский, Дэниел (1996). «Вероятностная модель лексического и синтаксического доступа и устранения неоднозначности». Когнитивная наука . 20 (2): 137–194. CiteSeerX 10.1.1.150.5711 . дои : 10.1207/s15516709cog2002_1 .
- ^ Кляйн, Дэн и Кристофер Д. Мэннинг. « Точный нелексикализованный синтаксический анализ ». Материалы 41-го ежегодного собрания Ассоциации компьютерной лингвистики. Том 1. Ассоциация компьютерной лингвистики, 2003 г.
- ^ Чарняк, Евгений. « Парсер, основанный на максимальной энтропии. Архивировано 1 апреля 2019 г. на Wayback Machine ». Материалы 1-го североамериканского отделения конференции Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 2000.
- ^ Чен, Данци и Кристофер Мэннинг. « Быстрый и точный анализатор зависимостей с использованием нейронных сетей ». Материалы конференции 2014 года по эмпирическим методам обработки естественного языка (EMNLP). 2014.
- ^ Цзя, Робин; Лян, Перси (11 июня 2016 г.). «Рекомбинация данных для нейронного семантического анализа». arXiv : 1606.03622 [ cs.CL ].
- ^ Сандра Х. Вос, Томас К. Гюнтер, Герберт Шриферс и Анджела Д. Фридеричи (2001) Синтаксический анализ и рабочая память: влияние синтаксической сложности, объема чтения и одновременной нагрузки, Язык и когнитивные процессы, 16: 1, 65 -103, DOI: 10.1080/01690960042000085
- ^ Перейти обратно: а б Притчетт, Б.Л. (1988). Феномены садовых дорожек и грамматическая основа языковой обработки. Язык, 64 (3), 539–576. https://doi.org/10.2307/414532
- ^ Томас Дж. Бевер (1970). Когнитивная основа языковых структур . OCLC 43300456 .
- ^ Карлссон, Ф. (2010). Ограничения рабочей памяти при встраивании нескольких центров. Материалы ежегодного собрания Общества когнитивных наук, 32. Получено с https://escholarship.org/uc/item/4j00v1j2.
- ^ Феррейра, Ф., и Клифтон, К. (1986). Независимость синтаксической обработки. Журнал памяти и языка, 25 (3), 348–368. https://doi.org/10.1016/0749-596X(86)90006-9
- ^ Атлас, JD (1997). О модульности обработки предложений: семантическая общность и язык мысли. Язык и концептуализация, 213–214.
- ^ Лопополо, Алессандро, ван ден Бош, Антал, Петерссон, Карл-Магнус и Роэл М. Виллемс; Различение синтаксических операций в мозге: зависимость и анализ фразовой структуры. Нейробиология языка 2021; 2 (1): 152–175. дои: https://doi.org/10.1162/nol_a_00029
- ^ Берант, Джонатан и Перси Лян. « Семантический анализ через перефразирование ». Материалы 52-го ежегодного собрания Ассоциации компьютерной лингвистики (Том 1: Длинные статьи). 2014.
- ^ Перейти обратно: а б Ахо А.В., Сетхи Р. и Уллман Дж.Д. (1986) «Компиляторы: принципы, методы и инструменты». Addison-Wesley Longman Publishing Co., Inc. Бостон, Массачусетс, США.
- ^ Сиккель, Клаас, 1954- (1997). Схемы синтаксического анализа: основа для спецификации и анализа алгоритмов синтаксического анализа . Берлин: Шпрингер. ISBN 9783642605413 . OCLC 606012644 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка ) - ^ Фрост Р., Хафиз Р. и Каллаган П. (2007) « Модульный и эффективный нисходящий анализ неоднозначных леворекурсивных грамматик. Архивировано 22 августа 2018 г. в Wayback Machine ». 10-й международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE , страницы: 109–120, июнь 2007 г., Прага.
- ^ Фрост Р., Хафиз Р. и Каллаган П. (2008) « Комбинаторы парсеров для неоднозначных леворекурсивных грамматик ». 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167–181, январь 2008 г., Сан-Франциско.
- ^ Рекерс, Ян и Энди Шюрр. « Определение и анализ визуальных языков с помощью грамматик многоуровневых графов ». Журнал визуальных языков и вычислений 8.1 (1997): 27-55.
- ^ Рекерс, Ян и А. Шурр. « Грамматический подход к графическому анализу ». Визуальные языки, материалы 11-го международного симпозиума IEEE. ИИЭР, 1995.
- ^ Чжан, Да-Цянь, Кан Чжан и Цзяньнун Цао. « Контекстно-зависимый формализм графовой грамматики для спецификации визуальных языков ». Компьютерный журнал 44.3 (2001): 186–200.
- ^ Джилл Фейн Леман (6 декабря 2012 г.). Адаптивный синтаксический анализ: саморасширяющиеся интерфейсы естественного языка . Springer Science & Business Media. ISBN 978-1-4615-3622-2 .
- ^ Патрик Блэкберн и Кристина Стригниц. «Методы обработки естественного языка в Прологе» .
- ^ Сон-Чун Чжу. «Классические алгоритмы синтаксического анализа» .
- ^ взято из Брайан В. Керниган и Деннис М. Ричи (апрель 1988 г.). Язык программирования Си . Серия программного обеспечения Prentice Hall (2-е изд.). Энглвуд Клиффс / Нью-Джерси: Прентис Холл. ISBN 0131103628 . (Приложение А.13 «Грамматика», стр.193 и далее)
Дальнейшее чтение [ править ]
- Чепмен, Найджел П., Л.Р. Синтаксический анализ: теория и практика , издательство Кембриджского университета , 1987. ISBN 0-521-30413-X
- Грюн, Дик; Джейкобс, Сериэль Дж. Х., Методы синтаксического анализа — практическое руководство , Свободный университет Амстердама , Амстердам, Нидерланды. Первоначально опубликовано Эллисом Хорвудом, Чичестер, Англия, 1990 г.; ISBN 0-13-651431-6
Внешние ссылки [ править ]
- Генератор парсера Lemon LALR
- Стэнфордский парсер Стэнфордский парсер
- Парсер Туринского университета Синтаксический анализатор естественного языка итальянского языка с открытым исходным кодом, разработанный на Common Lisp Леонардо Лесмо из Туринского университета, Италия.
- Краткая история создания парсера