Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Parser )
Перейти к навигации Перейти к поиску
"Parse" перенаправляется сюда. Для использования в других целях, см. Разбор (значения) .

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

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

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

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

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

Человеческие языки [ править ]

Основная категория: парсинг естественного языка

Традиционные методы [ править ]

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

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

Вычислительные методы [ править ]

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

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

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

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

Психолингвистика [ править ]

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

Анализ дискурса [ править ]

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

Компьютерные языки [ править ]

Парсер [ править ]

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

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

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

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

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

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

x  =  1 печать ( x )

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

x  =  1 печать ( y )

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

Обзор процесса [ править ]

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

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

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

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

Типы парсеров [ править ]

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

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

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

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

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

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

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

См. Также: сравнение генераторов парсеров

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

  • ANTLR
  • Бизон
  • Коко / Р
  • Грамматика с определенным предложением
  • ЗОЛОТО
  • JavaCC
  • Лимон
  • Лекс
  • LuZc
  • Пропаренный
  • Парсек
  • Рагель
  • Фреймворк Spirit Parser
  • Формализм определения синтаксиса
  • СИНТАКСИС
  • XPL
  • Yacc
  • PackCC

Lookahead [ править ]

Программа на C, которая не может быть проанализирована с опережением менее чем на 2 токена. Вверху: отрывок из грамматики C. [19] Внизу: синтаксический анализатор переварил токены " " и собирается выбрать правило для получения 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. Это правильно анализирует выражение, но с большим количеством состояний и увеличенной глубиной стека.
Действия синтаксического анализатора упреждающего просмотра [ требуется пояснение ]
  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 .

См. Также [ править ]

  • Возврат
  • Парсер диаграмм
  • Компилятор-компилятор
  • Детерминированный анализ
  • Генерация строк
  • Проверка грамматики
  • Парсер LALR
  • Лексический анализ
  • Парсер Пратта
  • Мелкий разбор
  • Анализатор левого угла
  • Анализ грамматики выражений
  • Мета-среда ASF + SDF
  • Набор инструментов для реинжиниринга программного обеспечения DMS
  • Трансформация программы
  • Генерация исходного кода

Ссылки [ править ]

  1. ^ a b "Разбор" . Dictionary.reference.com . Проверено 27 ноября 2010 года .
  2. ↑ Масару Томита (6 декабря 2012 г.). Обобщенный парсинг LR . Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  3. ^ «Грамматика и композиция» .
  4. ^ Кристофер Д. Мэннинг; Кристофер Д. Мэннинг; Хинрих Шютце (1999). Основы статистической обработки естественного языка . MIT Press. ISBN 978-0-262-13360-9.
  5. ^ Jurafsky, Daniel (1996). «Вероятностная модель лексического и синтаксического доступа и устранения неоднозначности». Когнитивная наука . 20 (2): 137–194. CiteSeerX 10.1.1.150.5711 . DOI : 10,1207 / s15516709cog2002_1 . 
  6. ^ Кляйн, Дэн, и Кристофер Д. Мэннинг. « Точный нелексикальный разбор ». Труды 41-го ежегодного собрания Ассоциации компьютерной лингвистики - Том 1. Ассоциация компьютерной лингвистики, 2003.
  7. ^ Чарняк, Евгений. « Синтаксический анализатор с максимальной энтропией ». Труды 1-го североамериканского отделения конференции Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 2000.
  8. ^ Chen, Danqi, и Кристофер Маннинг. « Быстрый и точный парсер зависимостей с использованием нейронных сетей ». Материалы конференции 2014 г. по эмпирическим методам обработки естественного языка (EMNLP). 2014 г.
  9. ^ Цзя, Робин; Лян, Перси (2016-06-11). «Рекомбинация данных для нейросемантического анализа». arXiv : 1606.03622 [ cs.CL ].
  10. ^ Berant, Джонатан, и Перси Лян. « Семантический разбор через перефразирование ». Материалы 52-го ежегодного собрания Ассоциации компьютерной лингвистики (Том 1: Длинные статьи). 2014 г.
  11. ^ a b Ахо, А. В., Сетхи, Р. и Ульман, Дж. Д. (1986) «Компиляторы: принципы, методы и инструменты». Эддисон-Уэсли Лонгман Паблишинг Ко., Инк. Бостон, Массачусетс, США.
  12. ^ Sikkel, Клаас, 1954- (1997). Схемы синтаксического анализа: структура для спецификации и анализа алгоритмов синтаксического анализа . Берлин: Springer. ISBN 9783642605413. OCLC  606012644 .CS1 maint: несколько имен: список авторов ( ссылка )
  13. ↑ Frost, R., Hafiz, R. и Callaghan, P. (2007) « Модульный и эффективный анализ сверху вниз для неоднозначных леворекурсивных грамматик ». 10-й Международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE , страницы: 109–120 , июнь 2007 г., Прага.
  14. ^ Frost, R., Hafiz, R. и Callaghan, P. (2008) " Комбинаторы синтаксического анализатора для неоднозначных леворекурсивных грамматик ". 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167–181, январь 2008 г., Сан-Франциско.
  15. ^ Rekers, Ян, и Энди Шерр. « Определение и анализ визуальных языков с помощью грамматик многоуровневых графов ». Журнал визуальных языков и вычислений 8.1 (1997): 27-55.
  16. ^ Rekers, Ян, и А. Шерр. « Грамматический подход к графическому синтаксическому анализу ». Визуальные языки, Труды., 11-й международный симпозиум IEEE по. IEEE, 1995.
  17. ^ Zhang, Da-Цянь, Кан Чжан и Jiannong Цао. « Контекстно-зависимый формализм грамматики графов для спецификации визуальных языков ». Компьютерный журнал 44.3 (2001): 186-200.
  18. ^ Джил Файн Леман (6 декабря 2012). Адаптивный синтаксический анализ: самораспространяющиеся интерфейсы естественного языка . Springer Science & Business Media. ISBN 978-1-4615-3622-2.
  19. ^ взято из Брайана В. Кернигана и Денниса М. Ричи (апрель 1988 г.). Язык программирования C . Серия программного обеспечения Prentice Hall (2-е изд.). Englewood Cliffs / NJ: Prentice Hall. ISBN 0131103628. (Приложение A.13 «Грамматика», стр.193 и далее)

Дальнейшее чтение [ править ]

  • Чапмен, Найджел П., Анализ LR: теория и практика , Cambridge University Press , 1987. ISBN 0-521-30413-X 
  • Грун, Дик; Джейкобс, Сериэль Дж. Х., Методы синтаксического анализа - Практическое руководство , Университет Амстердама , Амстердам, Нидерланды. Первоначально опубликовано Эллисом Хорвудом, Чичестер, Англия, 1990; ISBN 0-13-651431-6 

Внешние ссылки [ править ]

  • Генератор синтаксического анализатора Lemon LALR
  • Стэнфордский парсер Стэнфордский парсер
  • Parser Туринского университета Синтаксический анализатор естественного языка для итальянского языка с открытым исходным кодом, разработанный на Common Lisp Леонардо Лесмо, Университет Турина, Италия.
  • Краткая история создания парсера