Стандартный синтаксический анализатор запросов | Справочное руководство Apache Solr 6.6

Парсер запросов Solr по умолчанию также известен как парсер « lucene ».

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

Стандартные параметры синтаксического анализатора запросов

В дополнение к общим параметрам запроса, параметрам фасетирования, параметрам выделения и параметрам MoreLikeThis стандартный синтаксический анализатор запросов поддерживает параметры, описанные в таблице ниже.

Параметр	Описание
q	Определяет запрос, используя стандартный синтаксис запроса. Этот параметр является обязательным.
ежеквартально	Указывает оператор по умолчанию для выражений запроса, переопределяя оператор по умолчанию, указанный в схеме. Возможные значения: «И» или «ИЛИ».
дф	Указывает поле по умолчанию, переопределяя определение поля по умолчанию в схеме.
свиноматка	Разделить по пробелам: если установлено значение false , последовательности терминов, разделенные пробелами, будут предоставлены для анализа текста за один раз, что позволит правильно использовать фильтры анализа, которые работают с последовательностями терминов, например. многословные синонимы и опоясывающий лишай. По умолчанию true : анализ текста вызывается отдельно для каждого отдельного термина, разделенного пробелами.

Значения параметров по умолчанию указаны в solrconfig. xml или переопределены значениями времени запроса в запросе.

Ответ стандартного анализатора запросов

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

Примеры ответов

В этом разделе представлены примеры ответов стандартного анализатора запросов.

Приведенный ниже URL-адрес отправляет простой запрос и запрашивает модуль записи ответов XML для использования отступов, чтобы сделать ответ XML более удобочитаемым.

http://localhost:8983/solr/techproducts/select?q=id:SP2514N

Результаты:

 <ответ>
01
<результат numFound="1" start="0">
 <док>
  электроникажесткий диск
  7200 об/мин, 8 МБ кэш-памяти, IDE Ultra ATA-133
    NoiseGuard, технология SilentSeek, двигатель с гидродинамическим подшипником (FDB)
  SP2514N
  true
  Samsung Electronics Co. Ltd.
  Samsung SpinPoint P120 SP2514N — жесткий диск — 250 ГБ — ATA-133
  6
  <плавающее имя="цена">92.0
  SP2514N
 

 

Вот пример запроса с ограниченным списком полей.

http://localhost:8983/solr/techproducts/select?q=id:SP2514N&fl=id+name

Результаты:

 <ответ>
02
<результат numFound="1" start="0">
 <док>
  SP2514N
  Samsung SpinPoint P120 SP2514N — жесткий диск — 250 ГБ — ATA-133
 

 

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

Запрос к стандартному анализатору запросов разбит на термины и операторы. Есть два типа терминов: отдельные термины и словосочетания.

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

Важно, чтобы анализатор, используемый для запросов, разбирал термины и фразы таким же образом, как и анализатор, используемый для индексации, разбирает термины и фразы; в противном случае поиск может дать неожиданные результаты.

Модификаторы терминов

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

Поиск с подстановочными знаками

Стандартный синтаксический анализатор запросов Solr поддерживает односимвольный и многосимвольный поиск с подстановочными знаками в пределах одного термина. Подстановочные знаки можно применять к отдельным терминам, но не к поисковым фразам.

Тип поиска с подстановочными знаками	Специальный символ	Пример
Один символ (соответствует одному символу)	?	Строка поиска te?t будет соответствовать как тесту, так и тексту.
Несколько символов (соответствует нулю или более последовательным символам)	*	Поиск с подстановочными знаками: tes* будет соответствовать test, testing и tester. Вы также можете использовать подстановочные знаки в середине термина. Например: te*t будет соответствовать тесту и тексту. *est соответствует вредителю и тесту.

Нечеткий поиск

Стандартный анализатор запросов Solr поддерживает нечеткий поиск на основе алгоритма расстояния Дамерау-Левенштейна или алгоритма редактирования расстояния. Нечеткий поиск обнаруживает термины, похожие на указанный термин, но не обязательно являющиеся точным совпадением. Чтобы выполнить нечеткий поиск, используйте символ тильды ~ в конце термина, состоящего из одного слова. Например, чтобы найти термин, похожий по написанию на «бродить», используйте нечеткий поиск:

бродить~

Этот поиск будет соответствовать таким словам, как бродить, пена и пена. Оно также будет соответствовать самому слову «бродить».

Необязательный параметр расстояния определяет максимально допустимое количество правок от 0 до 2, по умолчанию 2. Например:

бродить~1

расстояние редактирования «2».

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

Поиск по близости

Поиск по близости ищет термины, находящиеся на определенном расстоянии друг от друга.

Чтобы выполнить поиск по близости, добавьте символ тильды ~ и числовое значение в конце поисковой фразы. Например, для поиска слов «апач» и «джакарта» в пределах 10 слов друг от друга в документе используйте поиск:

«апач джакарта»~10

Расстояние, которое здесь указано, — это номер термина. движения, необходимые для соответствия заданной фразе. В приведенном выше примере, если «apache» и «jakarta» находятся на расстоянии 10 пробелов друг от друга в поле, но «apache» стоит перед «jakarta», потребуется более 10 перемещений терминов, чтобы переместить термины вместе и расположить «apache» на справа от «джакарты» с пробелом между ними.

Поиск в диапазоне

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

Например, приведенный ниже запрос диапазона соответствует всем документам, в которых поле популярности имеет значение от 52 до 10 000 включительно.

популярность:[52 TO 10000]

Запросы диапазона не ограничиваются полями даты или даже числовыми полями. Вы также можете использовать диапазонные запросы с полями без даты:

title:{Aida TO Carmen}

Это найдет все документы, заголовки которых находятся между Aida и Carmen, но не включая Aida и Carmen.

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

• Квадратные скобки [ и ] обозначают включающий запрос диапазона, который соответствует значениям, включая верхнюю и нижнюю границу.

• Фигурные скобки { и } обозначают запрос исключительного диапазона, который сопоставляет значения между верхней и нижней границами, но исключает сами верхнюю и нижнюю границы.

• Вы можете смешивать эти типы, чтобы один конец диапазона был включающим, а другой — исключающим. Вот пример: count:{1 TO 10]

9=1.0 text:shoes

Указание полей в запросе к стандартному синтаксическому анализатору запросов

Данные, проиндексированные в Solr, организованы в поля, которые определены в схеме Solr. Поиск может использовать преимущества полей для повышения точности запросов. Например, вы можете искать термин только в определенном поле, например в поле заголовка.

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

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

Например, предположим, что индекс содержит два поля, заголовок и текст, и этот текст является полем по умолчанию. Если вы хотите найти документ под названием «Правильный путь», который содержит текст «не идите этим путем», вы можете включить в поисковый запрос любой из следующих терминов:

заголовок: «Правильный путь» И text:go

title:"Делай правильно" AND go

Поскольку текстовое поле является полем по умолчанию, индикатор поля не требуется; следовательно, второй запрос выше пропускает его.

Поле допустимо только для термина, которому оно непосредственно предшествует, поэтому запрос title:Do it right найдет только «Do» в поле заголовка. Он найдет «это» и «правильно» в поле по умолчанию (в данном случае в текстовом поле).

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

Логический оператор	Альтернативный символ	Описание
И	&&	Для совпадения требуется присутствие обоих терминов по обе стороны от логического оператора.
НЕ	!	Требует отсутствия следующего термина.
ИЛИ	||	Требуется, чтобы для совпадения присутствовал один термин (или оба термина).
	+	Требуется наличие следующего термина.
	-	Запрещает следующий термин (то есть совпадения в полях или документах, не содержащих этот термин). 9Оператор 0003 — функционально аналогичен логическому оператору ! . Поскольку он используется популярными поисковыми системами, такими как Google, он может быть более знаком некоторым сообществам пользователей.

Логические операторы позволяют комбинировать термины с помощью логических операторов. Lucene поддерживает И, «+», ИЛИ, НЕ и «-» в качестве логических операторов.

При указании логических операторов с такими ключевыми словами, как И или НЕ, ключевые слова должны быть указаны в верхнем регистре.

Стандартный анализатор запросов поддерживает все логические операторы, перечисленные в таблице выше. Анализатор запросов DisMax поддерживает только + и -.

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

Для поиска документов, содержащих «jakarta apache» или просто «jakarta», используйте запрос:

«jakarta apache» jakarta

или

«jakarta apache» OR jakarta 54 504 +

Символ + (также известный как «обязательный» оператор) требует, чтобы термин после символа + существовал где-то в поле хотя бы в одном документе, чтобы запрос вернул совпадение.

Например, для поиска документов, которые должны содержать слово «jakarta» и могут содержать или не содержать слово «lucene», используйте следующий запрос:

+jakarta lucene

Этот оператор поддерживается как стандартным парсером запросов, так и парсером запросов DisMax.

Логический оператор И (

&& )

Оператор И сопоставляет документы, в которых оба термина присутствуют в любом месте в тексте одного документа. Это эквивалентно пересечению с использованием множеств. Символ 9Вместо слова AND можно использовать 0003 && .

Для поиска документов, содержащих «jakarta apache» и «Apache Lucene», используйте любой из следующих запросов:

«jakarta apache» И «Apache Lucene»

«jakarta apache» && «Apache Lucene»

Булев оператор НЕ (

! )

Оператор НЕ исключает документы, содержащие термин после НЕ. Это эквивалентно различию с использованием наборов. Символ ! Вместо слова NOT можно использовать .

Следующие запросы выполняют поиск документов, содержащих фразу «jakarta apache», но не содержащих фразу «Apache Lucene»:

"jakarta apache" НЕ "Apache Lucene"

"jakarta apache" ! "Apache Lucene"

Логический оператор

-

Символ - или оператор «запретить» исключает документы, содержащие термин после символа - .

Например, для поиска документов, содержащих «jakarta apache», но не «Apache Lucene», используйте следующий запрос:

«jakarta apache» - «Apache Lucene»

Экранирование специальных символов

Solr дает особое значение следующих символов при их появлении в запросе:

+ - && || ! ( ) { } [ 9 " ~ * ? : /

Чтобы Solr интерпретировал любой из этих символов буквально, а не как специальный символ, поставьте перед ним обратную косую черту 0. Например, 90 \0003 символ обратной косой черты 90. , чтобы найти (1+1):2, не заставляя Solr интерпретировать знак плюс и круглые скобки как специальные символы для формулировки подзапроса с двумя терминами, экранируйте символы, ставя перед каждым из них обратную косую черту:

 \(1\+1\)\:2 

Группировка условий для формирования подзапросов

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

Приведенный ниже запрос ищет либо «jakarta», либо «apache» и «веб-сайт»:

(jakarta ИЛИ apache) И веб-сайт

Это повышает точность запроса, требуя, чтобы термин «веб-сайт» существовал, наряду с любым термином «джакарта» и «апач».

Группировка предложений внутри поля

Чтобы применить два или более логических оператора к одному полю при поиске, сгруппируйте логические предложения в круглых скобках. Например, приведенный ниже запрос ищет поле заголовка, содержащее слово «возврат» и фразу «розовая пантера»:

title:(+return +»pink panther»)

Поддерживаются комментарии C-Style. в строках запроса.

Пример:

"jakarta apache" /* это комментарий в середине обычной строки запроса */ ИЛИ jakarta

Комментарии могут быть вложенными.

Различия между синтаксическим анализатором запросов Lucene и стандартным синтаксическим анализатором запросов Solr

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

• A * может использоваться для одной или обеих конечных точек, чтобы указать открытый запрос диапазона

  • field:[* TO 100] находит все значения поля меньше или равные 100

  • поле: [100 ДО *] находит все значения поля больше или равные 100

  • field:[* TO *] соответствует всем документам с полем

• Чисто отрицательные запросы (все предложения запрещены) разрешены (только как предложение верхнего уровня)

• Перехват синтаксиса FunctionQuery. Вам нужно будет использовать кавычки для инкапсуляции функции, если она включает круглые скобки, как показано во втором примере ниже:

• Поддержка использования анализатора запросов любого типа в качестве вложенного предложения.

• Поддержка специального синтаксиса filter(…​) для указания того, что некоторые предложения запроса должны кэшироваться в кэше фильтра (как логический запрос с постоянной оценкой). Это позволяет кэшировать подзапросы и повторно использовать их в других запросах. Например, inStock:true будет кэшировано и повторно использовано во всех трех следующих запросах:

  • q=функции:песни ИЛИ фильтр(на складе:true)

  • q=+manu:Apple +фильтр(на складе:true)

  • q=+manu:Apple & fq=inStock:true

    Это можно использовать даже для кэширования отдельных предложений сложных запросов с фильтрацией. В приведенном ниже первом запросе в кеш фильтра будут добавлены 3 элемента (верхний уровень fq и оба предложения filter(…​) ), а во втором запросе будет 2 попадания в кеш и один новый кеш. вставка (для нового верхнего уровня fq ):

  • q=features:songs & fq=+filter(inStock:true) +filter(price:[* TO 100])

  • q=manu:Apple & fq=-filter(inStock:true) -filter(price:[* TO 100])

• Запросы диапазона («[a TO z]»), префиксные запросы («a*») и запросы с подстановочными знаками («a*b») имеют постоянную оценку (все соответствующие документы получают одинаковую оценку). Факторы оценки TF, IDF, повышение индекса и «координация» не используются. Количество совпадающих терминов не ограничено (как это было в прошлых версиях Lucene).

• 9= , который устанавливает для всего предложения указанную оценку для любых документов, соответствующих этому предложению:

Указание даты и времени

Запросы к полям с использованием типа TrieDateField (обычно запросы диапазона) должны использовать соответствующий синтаксис даты:

• метка времени: [* ДО СЕЙЧАС]

• createdate:[1976-03-06T23:59:59. 999Z TO *]

• создано:[1995-12-31T23:59:59.999Z К 2007-03-06T00:00:00Z]

• публикация: [СЕЙЧАС-1ГОД/ДЕНЬ ДО СЕЙЧАС/ДЕНЬ+1ДЕНЬ]

• createdate:[1976-03-06T23:59:59.999Z TO 1976-03-06T23:59:59.999Z+1YEAR]

• createdate:[1976-03-06T23:59:59.999Z/ГОД ДО 1976-03-06T23:59:59.999Z]

• Локальные параметры в запросах

• Другие парсеры

Общие параметры запроса Парсер запросов DisMax

Парсер BNF в Forth

(Эта статья впервые появилась в ACM SigFORTH Информационный бюллетень об. 2 нет. 2)

Брэдфорд Дж. Родригес
Т-рекурсивная технология
115 Первая улица #105
Коллингвуд, Онтарио L9Y 4W3 Канада
[email protected]

1. Введение

Форма Бэкуса-Наура (БНФ) — это нотация для формального описания языки программирования. Хотя чаще всего используется для указания синтаксиса «обычные» языки программирования, такие как Pascal и C, BNF также имеет значение в интерпретаторах командного языка и других языковых обработках.

В этой статье описывается одноэкранное расширение Forth, которое преобразует BNF выражения в исполняемые слова Forth. Это дает Форту возможности, эквивалентные на YACC или TMG, чтобы создать работающий парсер из описания языка BNF.

2. Выражения БНФ

Выражения или продукции BNF записываются следующим образом:

 производство ::= срок ... срок (вариант № 1)
                          | срок ... срок (вариант № 2)
                          | срок ... срок (вариант № 3) 

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

Продукция может рекурсивно использовать себя в своем определении. Например, целое число без знака может быть определено с помощью продукции

<цифра> ::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<число> ::=<цифра> | <цифра> <число>

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

Мы будем использовать условные обозначения вертикальной черты | разделить альтернативы, и угловые скобки для обозначения названия производства. ASCII без украшений символы являются терминалами (фундаментальные токены).

3. Простое решение с помощью условного выполнения

Логика последовательности и чередования может быть реализована в двух операторы «условного выполнения», && и ||. Эти точно соответствуют «логическим связкам» тех же имен в язык C (хотя их использование здесь на самом деле было вдохновлено Unix команду «найти»). Они определены:

: || IF R> DROP 1 THEN ; (выход на true)
: && 0=IF R> DROP 0 THEN ; (выход на ложь)

|| получив истинное значение в стеке, немедленно выходит из определения двоеточия с true в стеке. Это можно использовать для объединения альтернатив: первая удовлетворенная альтернатива (возвращает истину) остановит оценку дальнейшие альтернативы.

&& при ложном значении в стеке выходит из определения двоеточия сразу с false в стеке. Это «конкатенация» оператор: первый термин, который терпит неудачу (возвращает false), останавливает оценку и приводит к сбою всей последовательности.

Мы предполагаем, что каждый «токен» (терминал) представлен Форт слово, которое сканирует входной поток и возвращает флаг успеха. Производство (нетерминалы), построенные с использованием таких токенов, || и &&, являются гарантированно возвращает флаг успеха.

Итак, предполагая, что слова-маркеры от ‘0’ до ‘9’ определены, предыдущий пример становится:

 : <ЦИФРА> '0' || '1' || '2' || '3' || «4»
                      || '5' || '6' || '7' || '8' || '9';
            : <ЧИСЛО1> <ЦИФРА> && <ЧИСЛО> ;
            : <ЧИСЛО> <ЦИФРА> || <НОМЕР1> ;
 

На данный момент пренебрегая проблемой прямой ссылки, этот пример иллюстрирует три ограничения:

а) нам нужен явный оператор конкатенации, в отличие от БНФ.

б) && и || имеют равный приоритет, что означает, что мы не можем смешивать && и || в том же слове Forth и получить эквивалентное выражение BNF. Нам нужно было разделить продукцию на два слова.

c) мы не предусмотрели восстановление указателя сканирования, если BNF производство терпит неудачу.

Далее мы рассмотрим их.

4. Лучшее решение

В этот «грубый» анализатор BNF можно внести несколько улучшений, чтобы снять его ограничения и улучшить его «косметику».

а) Конкатенация путем сопоставления. Мы можем заставить действие && выполняться «невидимо», применяя это правило для всех терминов (терминалы и нетерминалы): каждый термин проверяет стек при входе. если ложно, слово немедленно выходит с ложью в стеке. В противном случае он анализирует и возвращает значение успеха.

Чтобы проиллюстрировать это: рассмотрим ряд терминов

<ОДИН> <ДВА> <ТРИ> <ЧЕТЫРЕ>

Разрешить нормальному выполнению и возврату «false». вводится и немедленно выходит, ничего не делая. Точно так же и ничего не делают. Таким образом оставшаяся часть выражения пропускается без необходимости стека возврата выход.

Реализация этого будет описана в ближайшее время.

б) Приоритет. Исключая оператор && таким образом, мы позволяют смешивать конкатенацию и чередование в одном выражении. А неудачная конкатенация будет «пропускать» только до следующего оператора. Итак, наш предыдущий пример становится:

: <ЧИСЛО> <ЦИФРА> || <ЦИФРА> <ЧИСЛО> ;

в) Возврат. Если токен не соответствует входному потоку, он не переместите указатель сканирования. Точно так же, если производство BNF выходит из строя, оно должно восстановить указатель сканирования на «начальную точку», где производство было попытка, так как это точка, в которой альтернативы должны быть опробованы. Мы поэтому применяйте это правило для всех терминалов и нетерминалов: каждый термин сохраняет указатель сканирования при входе. Если терм терпит неудачу, указатель сканирования восстанавливается; в противном случае сохраненное значение отбрасывается.

Позже мы обнаружим, что полезно «возвратить» указатель вывода, т.к. хорошо.

г) Успех как переменная. Проверка содержимого стека во время синтаксический анализ обнаруживает удивительный факт, что в любой момент времени существует только один флаг успеха в стеке! (Это связано с тем, что флаги, помещенные в стек, немедленно «потребляется».) Мы можем использовать переменную SUCCESS для флаги успеха синтаксического анализатора и тем самым упростить манипуляции, необходимые для используйте стек для других данных. Все постановки BNF принимают и возвращают правду ценность в УСПЕХЕ.

5. Реализация

Окончательный набор слов синтаксического анализатора BNF отображается на экране 3. Реализация трех слов основная логика:

В противном случае он сохраняет указатель сканирования в стеке возврата.

| разделяет альтернативы. Если УСПЕХ истинно, это вызывает немедленный выход и отбрасывает сохраненный указатель сканирования. В противном случае он восстанавливает положение сканирования от сохраненного указателя.

BNF> используется в конце производства. Если УСПЕХ false, восстанавливает позицию сканирования из сохраненного указателя. В любом случае, это удаляет сохраненный указатель из стека возврата.

являются логикой «во время выполнения», составлено словами BNF: и ;BNF соответственно.

BNF: имя начинает определение имени продукции BNF.

;BNF завершает определение BNF.

Наконец, есть четыре слова, которые упрощают определение слов-токенов. и другие терминалы:

@TOKEN получить текущий токен из ввода.

+TOKEN переместить указатель сканирования ввода.

=TOKEN сравнить значение на вершине стека с текущим токеном, следуя правилам разбора слов BNF.

nn Имя TOKEN создает имя «терминала» с кодом ASCII. значение пп.

Синтаксический анализатор использует fig-Forth IN в качестве указателя ввода, а словарь указатель DP в качестве выходного указателя. Этот выбор был сделан строго для удобство; нет никакой подразумеваемой связи с компилятором Forth.

6. Примеры и использование

Синтаксис определения BNF в Forth напоминает «традиционный» синтаксис BNF:

Традиционный: prod ::=term term | срок срок
В-четвертых: БНФ: прод термин термин | срок срок ;BNF

Экран 6 представляет собой простую задачу распознавания образов, чтобы идентифицировать текст, имеющий сбалансированные левые и правые скобки. Несколько аспектов парсера проиллюстрировано этим примером:

а) В строке 4 определены три токена. Во избежание конфликтов имен они имя с заключенными в кавычки. соответствует концу строки символ в буфере ввода терминала fig-Forth.

b) Строка 9 показывает рекурсивное производство, . Вовремя определение произведения, его имя автоматически очищается.

c) Строка 9 также показывает нулевую альтернативу. Это часто встречается в BNF. Нулевая альтернатива не анализирует токены и всегда удовлетворяется.

d) Не все слова синтаксического анализа нужно записывать как продукцию BNF. Строка 6 — Форт код для анализа любого символа ASCII, за исключением круглых скобок и нулей. Обратите внимание, что BNF: и ;BNF используются не для создания производства, а как простой способ создать условно исполняемое (для УСПЕХА) Форт-слово.

e) В строке 11 показано, как вызвать синтаксический анализатор: SUCCESS инициализируется в «истина», и выполняется «самое верхнее» производство БНФ. на его возвращение, УСПЕХ проверяется, чтобы определить окончательный результат.

f) В строке 11 также показано, как конец ввода указывается парсеру BNF: последовательность определяется как желаемое производство BNF, за которым следует конец линии.

Экраны 7 и 8 анализируют алгебраические выражения с приоритетом. Эта грамматика непосредственно из [AH077], с. 138. Использование постановок <Т'> и , чтобы избежать проблемы левой рекурсии, описано на п. 178 этой книги. Примечание также:

а) <ЦИФРА> определена «сложным способом». Это было бы лучше сделать это с помощью Форт-слова.

b) <ЭЛЕМЕНТ> требует прямой ссылки на <ВЫРАЖЕНИЕ>. Мы должны исправить эту ссылку вручную.

На экранах с 9 по 11 показано, как можно изменить этот алгебраический синтаксический анализатор для выполнить генерацию кода, совпадающую с процессом синтаксического анализа. Кратко: каждый Альтернатива продукции BNF включает код Forth для компиляции вывода, который будет результатом этой альтернативы. Если альтернатива успешна, этот вывод осталось в словаре. Если это не удается, указатель словаря «обратно», чтобы удалить этот вывод. Таким образом, по мере работы парсера образом, сверху вниз, через дерево синтаксического анализа, он постоянно производит и отбрасывание пробного вывода.

В этом примере создается исходный код Forth для алгебраического выражения.

а) Слово ,» добавляет текстовую строку к выходным данным.

б) Мы решили выводить каждую цифру числа по мере его разбора. (ЦИФРА) — вспомогательное слово для разбора действительной цифры. берет символ из входного потока перед ним. анализируется, а затем добавляется к выходным данным. Если бы это была не цифра, SUCCESS будет ложным, и ;BNF отбросит добавленный символ.

Если бы нам нужно было скомпилировать числа в двоичном виде, <ЧИСЛО> было бы надо сделать вывод. <ЧИСЛО> может начинаться с добавления нуля стек как аккумулятор. может увеличить это значение для каждой цифры. Затем, в конце , двоичное значение в стек можно было вывести.

в) После каждого полного числа нужен пробел. Мы могли бы фактор <ЧИСЛО> на два слова, например <ЦИФРА>. Но с тех пор <ЧИСЛО> появляется только один раз, в <ЭЛЕМЕНТ>, мы добавьте туда пробел.

d) В МИНУС добавляется после аргумент анализируется. В добавляется POWER после анализа двух его аргументов. добавляет * или / после два аргумента, а также добавляет + или -.

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

e) PARSE был изменен для TYPE вывода из синтаксический анализатор, а затем восстановить указатель словаря.

7. Предостережения

Этот синтаксический анализатор подвержен двум классическим ошибкам выражений BNF. Оба этих предостережения можно проиллюстрировать на примере производства <НОМЕР>:

BNF: <НОМЕР> <ЦИФРА> <НОМЕР> | <ЦИФРА> ;БНФ

а) Тщательно заказывайте альтернативы. Если бы <ЧИСЛО> было написано

BNF: <ЧИСЛО> <ЦИФРА> | <ЦИФРА> <НОМЕР> ;БНФ

, тогда все числа будут проанализированы как одна и только одна цифра! Это потому что альтернатива № 1, которая является подмножеством альтернативы № 2, всегда проверяется первый. В общем, альтернатива, которая является подмножеством или «более простым to-satisfy» следует проверять в последнюю очередь.

б) Избегайте «левой рекурсии». Если бы было написано <ЧИСЛО>

BNF: <ЧИСЛО> <ЧИСЛО> <ЦИФРА> | <ЦИФРА> ;БНФ

, то у вас будет бесконечный рекурсивный цикл звоню <НОМЕР>! Чтобы избежать этой проблемы, не делайте первый термин в любой альтернативе является рекурсивной ссылкой на определяемую продукцию. (Это правило несколько упрощено, для более подробного обсуждения этого проблему, см. [AH077], стр. 177–179.)

8. Сравнение с «традиционной» работой

На жаргоне составителей компиляторов этот синтаксический анализатор называется «сверху вниз синтаксический анализатор». с откатом.» Еще один такой синтаксический анализатор, из старых дней Unix, был ТМГ. Парсеры «сверху вниз» — одни из самых гибких парсеров; Это особенно в этой реализации, которая позволяет смешивать код Forth с выражениями БНФ.

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

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

9. Приложения и варианты

Компиляторы. Очевидное применение синтаксического анализатора BNF — письменное переводчики на другие языки. (Это, безусловно, должно усилить позиции Форта. претендовать на то, чтобы писать на других языках.)

Интерпретаторы команд. Сложные приложения могут иметь оператор интерфейс достаточно сложен, чтобы заслужить описание BNF. Например, это парсер использовался в экспериментальной системе управления освещением; команда язык занимал 30 экранов BNF.

Распознавание образов. Aho & Ullman [AH077] отмечают, что любая конструкция который может быть описан регулярным выражением, также может быть описан контекстно-свободная грамматика и, следовательно, в BNF. [AH077] определяет некоторые варианты использования обычных выражения для задач распознавания образов; такие проблемы тоже могут быть адресуется этим парсером.

Расширение этих методов синтаксического анализа было использовано для Сопоставитель шаблонов в стиле Snobol4 [ROD89а].

Целенаправленная оценка. Процесс поиска дерева синтаксического анализа для успешный результат, по сути, является результатом «целенаправленной оценки». Многие проблемы могут быть решены с помощью целенаправленных методов.

Например, вариант этого синтаксического анализатора был использован для создания эксперта система [ROD89b].

10. Ссылки

[AH077] Альфред Ахо и Джеффри Ульман, Принципы разработки компилятора, Эддисон-Уэсли, Рединг, Массачусетс (1977), 604 стр.

[ROD89a] Б. Родригес, «Сопоставление шаблонов в Forth», представлено на Конференция FORML 1989 г., 14 стр.

Листинг программы

 Скр # 3
 0 \ BNF Parser (c) 1988 Б. Дж. Родригес
 1 0 ПЕРЕМЕННЫЙ УСПЕХ
 2 :  IN @ >R DP @ >R >R
 3 ELSE R> ОТМЕНИТЬ ТОГДА ;
 4 : BNF> УСПЕХ @ ЕСЛИ R> R> R> 2DROP> R
 5 ИНАЧЕ R> R> DP ! Р>В ! >ТОГДА ;
 6 : | УСПЕХ @ ЕСЛИ R> R> R> 2DROP DROP
 7 ИНАЧЕ R> R> R> 2DUP >R >R IN ! ДП! 1 УСПЕХ! >ТОГДА ;
 8 : BNF: [КОМПИЛИРОВАНИЕ] : SMUDGE COMPILE  SMUDGE [COMPILE] ; ; НЕМЕДЛЕННЫЙ
10
11 : @TOKEN (-n) IN @TIB @ + C@ ;
12 : + ЖЕТОН ( f) ЕСЛИ 1 В +! ТОГДА ;
13 : =TOKEN ( n) УСПЕХ @ IF @TOKEN = DUP УСПЕХ ! + ЖЕТОН
14 ИНАЧЕ БРОСИТЬ ;
15 : ЖЕЛЕЗ (n) <СТРОИТ C, ДЕЛАЕТ> (a) C@ = ЖЕЛЕЗ;  Скр# 4
 0 \ BNF Parser - версия на ассемблере 8086 (c) 1988 г. Б. Дж. Родригес
 1 0 ПЕРЕМЕННЫЙ УСПЕХ
 2 КОД  -1 # УСПЕХ #) ТЕСТ, EQ IF, \ при неудаче,
10 0FDFE # W MOV, ( Up ptr) \ вернуться к
11 0 [RP]AX MOV,AX' DP@[W]MOV,\контрольная точка
12 2 [RP]AX MOV,AX' IN@[W]MOV,
13 ЗАТО, 4#РП ДОБАВИТЬ, ДАЛЕЕ\сбросить чекпойнт
14 \ и далее
15  Скр# 5
 0 \ BNF Parser - версия ассемблера 8086 (c) 1988 Б. Дж. Родригес
 1 КОД | -1 # УСПЕХ #) ТЕСТ, NE ЕСЛИ, \ если пройден,
 2 4 # RP ADD,\скинуть чекпойнт
 3 0 [RP] IP MOV, RP INC, RP INC, \ и выйти сейчас
 4 ELSE, 0FDFE # W MOV, \else, возврат,
 5 0 [RP] AX MOV, AX ' DP @ [W] MOV, \ выход из КПП
 6 2 [RP] AX MOV, AX ' IN @ [W] MOV, \ в стопке и
 7 УСПЕХ #) INC, \ установить true для следующего
 8 ЗАТЕМ, СЛЕДУЮЩИЙ \ чередовать
 910
11
12
13
14
15  Скр # 6
 0 \ Пример синтаксического анализатора BNF № 1 — распознавание шаблона. 18 9 88 мкр 19:41
 1 \ из Aho & Ullman, Principles of Compiler Design, p.137
 2 \ эта грамматика распознает строки со сбалансированными круглыми скобками
 3
 4 HEX 28 TOKEN '(' 29 TOKEN ')' 0 TOKEN  5
 6 BNF:  @TOKEN DUP 2A 7F WITHIN SWAP 1 27 WITHIN OR
 7 ДУП УСПЕХА! +ТОКЕН ;BNF
 8
 9БНФ:  '('  ')'  | <СИМВОЛ>  | ;БНФ
10
11: РАЗБОР 1 УСПЕХ!   12 CR УСПЕХ @ ЕСЛИ." Успешно " ИНАЧЕ " Не удалось " ТОГДА ;
13
14
15  Скр# 7
 0 \ Пример синтаксического анализатора BNF № 2 — инфиксная нотация 18 9 88 bjr 14:54
 1 HEX 2B TOKEN '+' 2D TOKEN '-' 2A TOKEN '*' 2F TOKEN '/'
 2 28 ЖЕТОН '(' 29'
 3 30 ЖЕТОН "0" 31 ЖЕЛЕЗ "1" 32 ЖЕЛЕЗ "2" 33 ЖЕЛЕЗ "3"
 4 34 ЖЕТОН "4" 35 ЖЕЛЕЗ "5" 36 ЖЕЛЕЗ "6" 37 ЖЕЛЕЗ "7"
 5 38 ЖЕЛЕЗНЫЙ '8' 39 ЖЕЛЕЗНЫЙ '9' 0 ЖЕЛЕЗНЫЙ  6
 7 BNF: <ЦИФРА> '0' | '1' | '2' | '3' | '4' | '5' | '6' | «7»
 8 | '8' | '9' ;БНФ
 9 BNF: <НОМЕР> <ЦИФРА> <НОМЕР> | <ЦИФРА> ;БНФ
10
11
12
13
14
15  Скр# 8
 0 \ Пример синтаксического анализатора BNF #2 - инфиксная нотация 18 9' <ФАКТОР> | <ПЕРВИЧНЫЙ> ;БНФ
 7 БНФ: '*'  | '/' <ФАКТОР> ;БНФ
 8 БНФ: <ТЕРМИН> <ФАКТОР> <Т'> ;БНФ
 9 BNF:  '+'   | '-'   ;BNF
10 BNF:    ;BNF
11 '  CFA SWAP ! \ исправить рекурсию в  12
13: РАЗБОР 1 УСПЕХ! <ВЫРАЖЕНИЕ> <КОНЕЦ> 14 CR УСПЕХ @ ЕСЛИ.