Синтаксический предикат

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

Более формально, синтаксический предикат — это форма производственного пересечения , используемая в спецификациях синтаксического анализатора или в формальных грамматиках . В этом смысле термин предикат имеет значение математической индикаторной функции . Если p ₁ и p ₂ являются продукционными правилами, то язык , порожденный обоими p ₁ и p _2, является пересечением их множеств.

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

Грамматики синтаксического анализа выражений (PEG), изобретенные Брайаном Фордом, расширяют эти простые предикаты, позволяя использовать «не предикаты» и позволяя предикату появляться в любом месте внутри продукта. Более того, Форд изобрел синтаксический анализ Packrat для обработки этих грамматик в линейном времени, используя мемоизацию за счет пространства в куче.

Можно поддерживать синтаксический анализ предикатов в линейном времени, такой же общий, как и те, которые разрешены PEG, но уменьшить затраты памяти, связанные с мемоизацией, избегая обратного отслеживания, где достаточно более эффективной реализации просмотра вперед. Этот подход реализован в ANTLR версии 3, которая использует детерминированные конечные автоматы для просмотра вперед; для этого может потребоваться проверка предиката для выбора между переходами DFA (так называемый синтаксический анализ «pred-LL(*)»).

Обзор

Терминология

Термин синтаксический предикат был придуман Парром и Куонгом и отличает эту форму предиката от семантических предикатов (также обсуждаемых).

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

Свойства формального замыкания

Бар-Хилель и др. покажите, что пересечение двух регулярных языков также является регулярным языком, то есть регулярные языки замкнуты относительно пересечения .

Пересечение регулярного языка и контекстно-свободного языка также закрыто и известно как минимум со времен Хартманиса. что пересечение двух контекстно-свободных языков не обязательно является контекстно-свободным языком (и, следовательно, не является замкнутым). Это можно легко продемонстрировать, используя канонический типа 1 : язык $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$:

Позволять $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$(Тип 2)
 Позволять $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$(Тип 2)
 Позволять $L_{3}=L_{1}\cap L_{2}$

Учитывая строки abcc , aabbc и aaabbbccc , ясно, что единственная строка, которая принадлежит как L ₁ , так и L ₂ (то есть единственная строка, которая создает непустое пересечение), — это aaabbbccc .

Другие соображения

В большинстве формализмов, использующих синтаксические предикаты, синтаксис предикатов некоммутативен , то есть операция предикации упорядочена. Например, используя приведенный выше пример, рассмотрим следующую псевдограмматику, где X ::= Y PRED Z означает: « Y производит X тогда и только тогда, когда Y также удовлетворяет предикату Z »:

S ::= а X
 X ::= Y ПРЕД Z
 Y ::= a+ BNCN
 Z ::= АНБН c+
 BNCN ::= b [BNCN] c
 АНБН ::= а [АНБН] б
 

Учитывая строку aaaabbbccc , в случае, когда Y должно быть удовлетворено первым (и при условии жадной реализации), S сгенерирует aX , а X, в свою очередь, сгенерирует aaabbbccc , тем самым сгенерировав aaaabbbccc . В случае, когда сначала должно быть удовлетворено Z , ANBN не сможет сгенерировать aaaabbb , и, следовательно, aaaabbbccc не генерируется грамматикой. Более того, если Y или Z (или оба) определяют какое-либо действие, которое необходимо предпринять при сокращении (как это имеет место во многих синтаксических анализаторах), порядок, в котором совпадают эти произведения, определяет порядок, в котором возникают эти побочные эффекты. Формализмы, которые изменяются со временем (например, адаптивные грамматики ), могут полагаться на эти побочные эффекты .

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

АНТЛР

Парр и Куонг приведите такой пример синтаксического предиката:

 стат  :   (  объявление  )  ?    декларация 
      |    выражение 
      ; 

который предназначен для удовлетворения следующих неофициально заявленных ограничения C++ :

1. Если это похоже на декларацию, то так оно и есть; в противном случае
2. если это похоже на выражение, то так оно и есть; в противном случае
3. это синтаксическая ошибка.

При первом создании правила stat синтаксический предикат (объявление)? указывает это объявление является синтаксическим контекстом, который должен присутствовать для успеха остальной части этого продукта. Мы можем интерпретировать использование (объявления)? как «Я не уверен, что декларация будет соответствовать; позвольте мне попробовать это, и, если оно не совпадет, я попробую следующее альтернатива.» Таким образом, при обнаружении действительного объявления объявление правила будет распознается дважды — один раз как синтаксический предикат и один раз во время фактического анализа для выполнения семантических действий.

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

Канонические примеры

Язык $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ можно представить в различных грамматиках и формализмах следующим образом:

Анализ грамматик выражений

 S   ←   &  (  А   !  б  )   а  +   Б   !   с 
  А   ←   а   А  ?    б 
  Б   ←   б   Б  ?    с 

§-исчисление

Использование связанного предиката:

С → {А} Б 

А → Х 'с+'
 X → 'а' [X] 'б'
 Б → 'а+' Y
 Y → 'b' [Y] 'c'
 

Использование двух свободных предикатов:

A → <'a+'>  a  <'b+'>  b  Ψ(  a   b  ) Икс  <'c+'>  c  Ψ(  b   c  ) И 

X → 'а' [X] 'б'
 Y → 'b' [Y] 'c'
 

Конъюнктивная грамматика

(Примечание: следующий пример фактически генерирует $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$, но включен сюда, потому что это пример, приведенный изобретателем соединительных грамматик. ):

S → AB&DC
 А → аА |  ε
 Б → BC |  ε
 С → СС |  ε
 Д → аДб |  ε
 

Правила Perl 6

 правило  S  {  <before <A> <!before b>> a+ <B> <!before c>  } 
   правило  A  {  a <A>?   б  } 
   правило  B  {  b <B>?   с  } 
 

Парсеры/формализмы, использующие ту или иную форму синтаксического предиката

Хотя это ни в коем случае не исчерпывающий список, следующие синтаксические анализаторы и грамматические формализмы используют синтаксические предикаты:

ANTLR (Парр и Куонг)

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

Расширенное сопоставление шаблонов (Balmas)

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

Анализ грамматик выражений (Форд)

PEG Форда имеют синтаксические предикаты, выраженные как предикат «и» и «предикат не» .

§-Исчисление (Джексон)

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

Раку рулит

Raku представляет обобщенный инструмент для описания грамматики, называемый правилами , который является расширением синтаксиса регулярных выражений Perl 5. Предикаты вводятся посредством механизма просмотра вперед, вызываемого ранее , либо с помощью " <before ...>" или " <!before ...>" (то есть: " не раньше"). Perl 5 также имеет такой просмотр вперед, но он может инкапсулировать только более ограниченные возможности регулярных выражений Perl 5.

Программатика (NorKen Technologies)

GDL (язык определения грамматики) ProGrammar использует синтаксические предикаты в форме, называемой ограничениями синтаксического анализа . ВНИМАНИЕ: эта ссылка больше не действительна!

Конъюнктивная и булева грамматики (Охотин)

Конъюнктивная грамматика, впервые введенная Охотиным, ввести явное понятие союза -как-предикации. Дальнейшее лечение конъюнктивных и логических грамматик. является наиболее тщательной трактовкой этого формализма на сегодняшний день.

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

• сайт ANTLR
• Alexander Okhotin's Conjunctive Grammars Page
• Alexander Okhotin's Boolean Grammars Page
• Страница грамматики синтаксического анализа и синтаксического анализа выражений Packrat