Какие две основные стратегии синтаксического разбора вы знаете? в чем состоит основная проблема разбора?
Типы алгоритмов
Нисходящий парсер (англ. top-down parser) - такой парсер, в котором продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности лексем.
Восходящий парсер (англ. bottom-up parser) - такой парсер, в котором продукции восстанавливаются из правых частей, начиная с токенов-лексем и кончая стартовым символом.
Структурный нисходящий анализ - самый точный. Восходящий анализ работает очень быстро и способен разобрать даже очень длинные предложения, игнорируя непонятные фрагменты. Достоинства и недостатки каждого вида анализа мы рассмотрим ниже.
Восходящий и нисходящий вероятностный парсинг предложения
В парсере реализованы два алгоритма недетерминированного синтаксического разбора предложения - нисходящий (top-down) и восходящий (bottom-up).
Как следует из названий, они по-разному организуют процесс распознавания синтаксических конструкций.
Нисходящий синтаксический анализ, или анализ через синтез, начинает с выдвижения предположений о крупномасштабной структуре предложения, а затем уточняет и детализирует это предположение, рекурсивно опускаясь на уровень конкретных слов. Другими словами, этот алгоритм инициирует разбор с начального нетерминала S.
Восходящий синтаксический анализ начинает разбор с конкретных слов, связывая сначала пары слов, затем подсоединяет к этим парам новые слова или другие связанные пары. Постепенно процесс связывания доходит до начального нетерминала S - то есть все слова в предложения оказываются связаны в единую структуру.
Обоим алгоритмам присущи важные общие черты. Они недетерминированы, то есть могут выдавать множество альтернативных вариантов синтаксического разбора, хотя оба стремятся отсечь недостоверные варианты с помощью общей модели языка (см. далее). Они управляются правилами, которые задаются вручную. Они позволяют задавать типы связей в создаваемом синтаксическом дереве. Наконец, оба алгоритма реализуют идею динамического программирования для эффективного снижения времени разбора.
Выбор между восходящим и нисходящим алгоритмом обычно происходит автоматически. Встроенный в грамматический движок планировщик анализа сначала пытается распарсить предложение самым точным нисходящим алгоритмом, а в случае неудачи переключается на более устойчивый к ошибкам восходящий анализ. При необходимости, прикладной код может управлять выбором с помощью специальных флагов в функции API sol_SyntaxAnalysis.
Правила, управляющие синтаксическим разбором
Восходящий и нисходящий алгоритмы воплощают "классический" подход к созданию грамматики естественного яхыка. Этот подход заключается в создании набора правил, которые работают со словами и грамматическими категориями слов. Правила обычно пишутся на специальном предметно-ориентированном языке (DSL), чтобы упростить изменение грамматики без перекомпиляции кода парсера и дать в руки разработчику грамматики эффективный набор средств, обычно имеющих мало общего с обычными императивными языками перограммирования. Выразительные средства этого языка будут описаны далее с необходимой детальностью. Вместе с исходными текстами учебного парсера русских предложений, данное описание позволит Вам создавать собственные анализаторы.
Правила описывают порядок распознавания различных синтаксических конструкций естественного языка. Исходный текст правил читается компилятором словаря и преобразуется в сильно оптимизированное внутреннее представление, фактически в набор команд для виртуальной машины.
Вообще говоря, грамматический движок предоставляет два алгоритмически различных подхода к построению анализатора: итерационный алгоритм на основе правил переписывания и очень мощный структурный нисходящий парсер. Правила переписывания детально описываются в отдельном параграфе далее. Несмотря на некоторое различие в математической основе, существует способ применять в обоих типах анализа общий набор правил, таким образом реализуя сложный процесс синтаксического анализа с динамическим переключением направления.
В терминах теории автоматов, набор правил реализует распознающую грамматику для предложений на естественном языке. Результатом работы анализатора является не только подтверждение того, что входное предложение с определенной достоверностью принадлежит к распознаваемому набору синтаксических конструкций и идеоматических оборотов, но и набор альтернативных синтаксических деревьев с весами в случае неоднозначности анализа.
Достоинства и недостатки структурного нисходящего парсера
Далее приводятся характерные особенности структурного нисходящего парсера (далее СНП), работающего в режиме “анализ через синтез”.
(+) СНП даст 100% верный разбор предложения на составляющие, если используемая грамматика адекватно описывает такие предложения. Процесс разбора структурным парсером очень похож на математически строгое доказательство.
(+) СНП найдет все возможные варианты разбора предложения, если грамматика содержит неоднозначности.
(+) СНП способен делать ослабляющие допущения и оценивать выполненный анализ с учетом таких допущений.
(+) СНП может учитывать контекст любой ширины, вплоть до всего предложения. Другими словами, учитываются не только непосредственные соседи, но также связанные синтаксически части предложения, находящиеся на любом удалении от слова.
(+/-) СНП не имеет внутреннего состояния и выполняет разбор за 1 заход. Нет естественного способа остановить выполнения разбора в промежуточной стадии и получить частичные результаты. Эта особенность имеет также важное положительное следствие. Отсутствие состояния позволяет распараллеливать выполнение анализа.
(-) СНП естественным образом реализует поиск в глубину. Это может приводить к тому, что из-за отсутствия хороших эвристик очень много времени будет уделено проверке заведомо проигрышным вариантам анализа, а выигрышный путь в пространстве состояний так и не будет найден до исчерпания лимита времени.
(-) Следствием отсутствия состояния является трудность отладки. Отладчик парсера предоставляет некоторые ограниченные возможности, включая задание точек останова в некоторых местах правил и просмотр локального состояния вывода. Однако наличие множества параллельных процессов вывода делает интерактивную отладку крайне трудной в реализации и использовании. В реальности самым удобным способом отладки является просмотр пошаговой трассировки для полученных результатов.
(-) Если структура предложения не выводится правилами грамматики в точном виде, то СНП вообще ничего не выведет, если не принимать специальные меры. Под такими специальными мерами подразумевается неполный анализ.
(-) СНП реализует в большей степени математическую концепцию, чем языковую. В сочетании с декларативным и функциональным стилем задания правил вывода это может поднять порог вхождения для незнакомого с математической лингвистикой разработчика, привыкшего к императивному стилу программирования.
(+) СНП работает с предложением в ленивом стиле. Начав с левой границы, он постепенно выводит синтаксическую структуру, запрашивая у лексера новые и новые слова. Более того, СНП очень хорошо элегантно работают с графом токенизации, который получается в ходе лексического анализа.
Достоинства и недостатки итерационного анализа
Так как данный алгоритм анализа в целом основан на использовании таких же правил, как рассмотренный ранее нисходящий анализ через синтез, то он в определенной степени наследует некоторые его особенности. В частности, можно упомянуть необходимость ручного описания грамматики с большим количеством абстрактных категорий и некоторая сложность с пониманием процесса сопоставления правил.
Далее перечисляются только собственные особенности данного алгоритма.
1. Недетерминированность процесса. Входная цепочка токенов может породить несколько альтернативных новых цепочек после применения правила переписывания. Выбор оптимального результата выполняется с помощью механизма задания баллов для правил переписывания, либо с использованием общих с алгоритмов анализ-через-синтез приемов - ассоциации слов, tree scorer.
2. Итерации, состояние. Автомат имеет явное состояние. Процесс применения правил переписывания имеет заранее известные точки, в которых его можно прервать и получить текущие результаты связывания. Благодаря этому можно реализовать управление анализом по таймауту - привязывания деталей будет продолжаться до тех пор, пока автомат не перейдет в конечное состояние (успех - построен синтаксический граф с одним корнем) либо пока не будет исчерпан заданный лимит времени. Более того, механизм оценки достоверности переписывания позволяет создавать планировщик итераций, который меняет приоритет того или иного варианта анализа динамически.
3. Простота отладки. Процесс переписывания можно прервать в момент применения очередного правила и увидеть весь текущий набор результатов.
4. Порядок задания правил имеет значение.
5. Работа с длинными предложениями. Можно задать такие правила, что автомат будет работать в минимальным контекстом - например, ограничить его правилами для пар слов. К примеру, связывать частицу НЕ с наречиями, прилагательными, деепричастиями и глаголами и т.д. Поэтому автомат может выполнять постепенное построение синтаксического дерева для очень длинных предложений, не пытаясь сразу охватить слишком большие фрагменты текста.
6. Правила переписывания используют весь набор возможностей для задания опорных точек контекста. Это позволяет задавать правила, которые сопоставляются с контекстом заранее неизвестной длины. Кроме того, доступны такие средства, как 1) теоретико-множественные операторы для проверки вхождения токена в именованное множество, 2) проверка с помощью регулярных выражений, 3) использование пользовательских функций, написанных на встроенном языке, 4) проверка согласования фрагментов сопоставляемого контекста.
7. Основной недостаток итерационного анализа - меньшая эффективность в равных условиях с анализом-через-синтез. В силу некоторых алгоритмических особенностей второго варианта компилятор словаря может выполнить весьма агрессивную оптимизацию, которая ускоряет процесс синтеза с проверкой. Более того, анализ-через-синтез реализует очень эффективную оптимизацию процесса во время работы. Со своей стороны, итерационный анализ очень ограничен в возможных оптимизациях. Эффективность анализа в нем приносится в жертву итеративности и возможности постепенно улучшать результат, динамически отслеживая прогресс.
8. Итерационный анализ можно начинать не просто с исходной цепочки токенов, а попытаться "прикинуть" общую структуру предложения с помощью набора специальных правил. Например, можно найти в предложении местоимение я и согласующийся с ним глагол, предположить из связь как подлежащего и сказуемого и далее уже запускать итерации, опираясь на эти ключевые токены
Кс-Контекстно-свободная грамматика
ООП – объектно ориентированное программирование.
1/ Определите состав программного обеспечения САПР. (или “Разработка САПР”)
Совокупность однотипных компонентов образует средство обеспечения САПР. Выделяют следующие виды обеспечения САПР:
Техническое обеспечение (ТО) — совокупность связанных и взаимодействующих технических средств (ЭВМ, периферийные устройства, сетевое оборудование, линии связи, измерительные средства).
Математическое обеспечение (МО), объединяющее математические методы, модели и алгоритмы, используемые для решения задач автоматизированного проектирования. По назначению и способам реализации делят на две части:
математические методы и построенные на них математические модели;
формализованное описание технологии автоматизированного проектирования.
Программное обеспечение (ПО). Подразделяется на общесистемное и прикладное:
прикладное ПО реализует математическое обеспечение для непосредственного выполнения проектных процедур. Включает пакеты прикладных программ, предназначенные для обслуживания определенных этапов проектирования или решения групп однотипных задач внутри различных этапов (модуль проектирования трубопроводов, пакет схемотехнического моделирования, геометрический решатель САПР).
общесистемное ПО предназначено для управления компонентами технического обеспечения и обеспечения функционирования прикладных программ. Примером компонента общесистемного ПО является операционная система.
Информационное обеспечение (ИО) — совокупность сведений, необходимых для выполнения проектирования. Состоит из описания стандартных проектных процедур, типовых проектных решений, комплектующих изделий и их моделей, правил и норм проектирования. Основная часть ИО САПР — базы данных.
Лингвистическое обеспечение (ЛО) — совокупность языков, используемых в САПР для представления информации о проектируемых объектах, процессе и средствах проектирования, а также для осуществления диалога проектировщик-ЭВМ и обмена данными между техническими средствами САПР. Включает термины, определения, правила формализации естественного языка, методы сжатия и развертывания.
В лингвистическом обеспечении выделяют класс различного типа языков проектирования и моделирования (VHDL, VERILOG, UML, GPSS).
Методическое обеспечение (МетО) — описание технологии функционирования САПР, методов выбора и применения пользователями технологических приемов для получения конкретных результатов. Включает в себя теорию процессов, происходящих в проектируемых объектах, методы анализа, синтеза систем и их составных частей, различные методики проектирования. Иногда к МетО относят также МО и ЛО.
Организационное обеспечение (ОО) — совокупность документов, определяющих состав проектной организации, связь между подразделениями, организационную структуру объекта и системы автоматизации, деятельность в условиях функционирования системы, форму представления результатов проектирования… В ОО входят штатные расписания, должностные инструкции, правила эксплуатации, приказы, положения и т. п.
В САПР как проектируемой системе выделяют также эргономическое и правовое обеспечения.[1][3]
Эргономическое обеспечение объединяет взаимосвязанные требования, направленные на согласование психологических, психофизиологических, антропометрических характеристик и возможностей человека с техническими характеристиками средств автоматизации и параметрами рабочей среды на рабочем месте.
Правовое обеспечение состоит из правовых норм, регламентирующих правоотношения при функционировании САПР, и юридический статус результатов её функционирования.
Программное обеспечение САПР:
- системное
- прикладное
- Системы 3D моделирования
- Системы инженерного анализа
- Системы 2D
- Системы эргономического анализа
- Простые приложения
Программное обеспечение САПР объединяет собственно программы для систем обработки данных на машинных носителях и программную документацию, необходимую для эксплуатации программы. Программное обеспечение (ПО) делится на общесистемное, базовое и прикладное (специальное). Общесистемное ПО предназначено для организации функционирования технических средств, т.е. для планирования и управления вычислительным про цессом, распределения имеющихся ресурсов, и представлено операционными системами ЭВМ и ВС. Общесистемное ПО обычно создается для многих приложений и специфики САПР не отражает. Базовое и прикладное ПО создаются для нужд САПР. В базовое ПО входят программы, обеспечивающие правильное функционирование прикладных программ.
В прикладном ПО реализуется математическое обеспечение для непосредственного выполнения проектных процедур. Прикладное ПО обычно имеет форму пакетов прикладных программ (ППП), каждый из которых обслуживает определенный этап процесса проектирования или группу однотипных задач внутри различных этапов.