Статьи

ANTLR — семантические предикаты

Январь 2, 2019

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

Семантические предикаты — это условия java (или C ++, или JavaScript, или …), написанные внутри грамматики. Antlr использует их либо для выбора между несколькими альтернативами, либо в качестве дополнительных проверяемых утверждений. Они могут быть размещены как в лексере, так и в парсере, но этот пост посвящен только их использованию в парсере. Они добавляют много силы в antlr.

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

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

Все примеры и грамматики, использованные в этом посте, доступны на Github .

Содержание

Случаи применения

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

Если вы никогда не работали с css или не заинтересованы в вариантах использования, пропустите эту главу.

Ключевые слова — nth

Для некоторых псевдоклассов CSS требуется параметр, который может быть числом, идентификатором, селектором или чем-то, что называется n-м выражением. N-е выражения допускаются только внутри некоторых псевдоклассов, и имена этих псевдоклассов не являются зарезервированными ключевыми словами в css.

N-е выражение — это выражение вида an+b где a и b — необязательные целые числа. Примеры правильных n-х выражений: 5n+2 , -5n-2 , -5n , -2 , -n , n .

Мы хотели, чтобы наша грамматика принимала n-е выражения, но только в качестве параметров псевдоклассов, где это фактически разрешено. Мы хотели, чтобы он отклонял n-е выражения в качестве параметров всех оставшихся псевдоклассов.

Все имена обычно соответствуют токенам IDENT . Создание специального токена, соответствующего n-му псевдоклассу, нецелесообразно, поскольку они не являются зарезервированными ключевыми словами. Например, они также являются совершенно допустимыми именами классов или имен элементов. Наличие специального токена заставит нас заменить почти все вхождения IDENT | NTH на IDENT | NTH IDENT | NTH .

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

Ссылка на решение.

Значительные пробелы

У Css есть полу важные пробелы. Полу-важный означает, что большинство из них представляют только концы токенов, и на этом заканчивается их полезность. Например, пробелы в объявлении не имеют значения. Следующие объявления равны:

1
2
padding  :  2;
padding:2;

Большинство CSS-грамматик ведут себя так, как описано выше, поэтому существует сильное искушение отбросить все пробелы. Однако, если мы это сделаем, то следующие два селектора в итоге IDENT COLON IDENT LPAREN COLON IDENT RPAREN COLON IDENT LPAREN COLON IDENT RPAREN LBRACE один и тот же IDENT COLON IDENT LPAREN COLON IDENT RPAREN COLON IDENT LPAREN COLON IDENT RPAREN LBRACE поток токенов:

1
2
div :not(:enabled) :not(:disabled) {}
div:not(:enabled):not(:disabled) {}

Пробелы в селекторах значительны. Первый селектор эквивалентен div *:not(:enabled) *:not(:disabled) а второй нет.

Замечания:

Грамматика CSS 2.1, доступная на сайте antlr, игнорирует эту проблему. Если вы хотите использовать его, вы должны сначала исправить это.

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

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

Ссылка на решение.

основы

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

Синтаксис

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

  • { condition }?
  • { condition }?=>

Первый пример использует простой
1+2==3 и 2+3==5 условий. Грамматика хранится в файле Basics.g:

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
word: LETTER {1+2==3}? LETTER;
 
NUMERAL: '0'..'9';
number: {2+3==5}?=> NUMERAL NUMERAL;

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

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

  • однозначный семантический предикат,
  • проверка семантического предиката,
  • стробированный семантический предикат.

Однозначный семантический предикат

Однозначные предикаты используют более короткий {...}? синтаксис. Однако предикат называется устранением неоднозначности только в том случае, если он помещен в начало правила или в начало альтернативы.

Однозначный семантический предикат:

1
2
3
4
5
6
7
8
9
LETTER : 'a'..'z' | 'A'..'Z';
// beginning of a rule
rule: {1+2==3}? LETTER LETTER;
 
// beginning of an alternative
alternatives: LETTER (
  {2+3==5}? LETTER*
  | {2+3==5}? LETTER+
);

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

При проверке предикатов также используется более короткий {...}? синтаксис. Разница против однозначных предикатов только в размещении. Проверяющие предикаты помещаются в середине правила или в середине альтернативы:

1
2
LETTER : 'a'..'z' | 'A'..'Z';
word: LETTER {1+2==3}? LETTER;

Закрытый семантический предикат

Строковые семантические предикаты используют более длинный синтаксис {...}?=> . Условие может быть размещено где угодно.

Закрытый семантический предикат:

1
2
NUMERAL: '0'..'9';
number: {2+3==5}?=> NUMERAL NUMERAL;

Неудачные предикаты

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

Если при сопоставлении встречается семантический предикат, то он проверяет, выполняется ли условие. Если оно не выполнено, FailedPredicateException исключение FailedPredicateException .

Рассмотрим грамматику Basics.g, показанную в начале этой главы:

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
word: LETTER {1+2==3}? LETTER;
 
NUMERAL: '0'..'9';
number: {2+3==5}?=> NUMERAL NUMERAL;

Если вы откроете сгенерированный класс BasicsParser , вы обнаружите, что каждому правилу соответствует соответствующий метод с тем же именем. Оба они содержат копию предиката, и оба они выдают исключение, если условие не выполняется:

1
2
3
4
5
6
7
8
// inside the generated word() method
if ( !((1+2==3)) ) {
  throw new FailedPredicateException(input, 'word', '1+2==3');
}
// inside the generated number() method
if ( !((2+3==5)) ) {
  throw new FailedPredicateException(input, 'number', '2+3==5');
}

Предсказание, например, что произойдет, если синтаксический анализатор встретит правило с несколькими альтернативами и предикатами, например
start: word | number Правило start: word | number описано в следующей главе.

Подъем и прогнозирование

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

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

Что это

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

Рассмотрим грамматику, хранящуюся в файле DisambiguatingHoistingNeeded.g:

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
word: {1+2==3}? LETTER LETTER;
sameWord: {1+2!=3}? LETTER LETTER;
 
start: word | sameWord;

Оба sameWord() word() и sameWord() сгенерированного синтаксического анализатора содержат обычную неудачную проверку предикатов.
Извлечение класса DisambiguatingHoistingNeededParser :

1
2
3
4
5
6
7
8
//inside the word() method
if ( !((1+2==3)) ) {
  throw new FailedPredicateException(input, 'word', '1+2==3');
}
//inside the sameWord() method
if ( !((1+2!=3)) ) {
  throw new FailedPredicateException(input, 'sameWord', '1+2!=3');
}

Кроме того, код, соответствующий правилу start содержит копии семантических предикатов word и sameWord . Часть, которая выбирает, какое правило использовать дальше, содержит следующий код (мои комментарии):

01
02
03
04
05
06
07
08
09
10
11
12
int LA1_2 = input.LA(3);
//predicate copied from the word rule
if ( ((1+2==3)) ) {
  alt1=1;
} //predicate copied from the sameWord rule
else if ( ((1+2!=3)) ) {
  alt1=2;
}
else {
  NoViableAltException nvae = new NoViableAltException('', 1, 2, input);
  throw nvae;
}

Копирование предиката в часть прогнозирования сгенерированного синтаксического анализатора называется подъемом.

последствия

Если бы не было подъема, предикаты действовали бы только как утверждения. Мы могли бы использовать их для проверки некоторых условий, и это было бы так. Приведенная выше грамматика была бы недопустимой — она ​​имеет две синтаксически эквивалентные альтернативы, если вы игнорируете предикаты.

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

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

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

Только предикаты, помещенные в начало правила, включаются в другие правила. Подъем в случае альтернативы только в рамках правила. Следовательно, вы можете нарушить третье правило, если предикат не помещен в начало правила.

Когда это используется

Подъем используется только тогда, когда парсер должен выбирать между несколькими правилами или альтернативами, и некоторые из них начинаются с предиката. Если это предикат gated, например, условие внутри синтаксиса {...}?=> , То предикат поднимается несмотря ни на что.

Если это однозначный предикат, например, условие внутри {...}? синтаксис, то предикат поднимается, только если он действительно нужен. Термин «фактически необходимый» означает, что несколько альтернатив могут соответствовать одному входу. Иначе говоря, он используется только в том случае, если несколько альтернатив неоднозначны для некоторого ввода.

Предикаты, помещенные в середине правил или в середине альтернатив, никогда не поднимаются.

При необходимости подъем — устранение неоднозначности предиката

Рассмотрим правило
start в грамматике DisambiguatingHoistingNotNeeded.g:

1
2
3
4
5
6
LETTER : 'a'..'z' | 'A'..'Z';
NUMBER : '0'..'9';
word: {1+2==3}? LETTER LETTER;
differentWord: {1+2!=3}? LETTER NUMBER;
 
start: word | differentWord;

Правило
start должно выбирать между word и differentWord правилами слова. Оба они начинаются с предиката, но предикат не нужен для того, чтобы различать их. Второй токен word — LETTER а второй токен differentWord — NUMBER .

Подъем не будет использоваться. Вместо этого грамматика рассмотрит предстоящие 2 токена, чтобы различать эти правила. Чтобы проверить это, откройте метод start() сгенерированного класса DisambiguatingHoistingNotNeededParser в нашем примере проекта: в него не было скопировано ни условие 1+2==3 ни 1+2!=3 .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
int alt1=2;
switch ( input.LA(1) ) {
case LETTER: {
  switch ( input.LA(2) ) {
  case LETTER: {
    alt1=1;
  }
  break;
  case NUMBER: {
    alt1=2;
  }
  break;
  default:
    NoViableAltException nvae =
      new NoViableAltException('', 1, 1, input);
 
  throw nvae;
}

С другой стороны, рассмотрим начало правила в грамматике DisambiguatingHoistingNeeded.g:

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
word: {1+2==3}? LETTER LETTER;
sameWord: {1+2!=3}? LETTER LETTER;
 
start: word | sameWord;

Начало правила должно выбирать между word и правилами sameWord . Эти два правила соответствуют абсолютно одинаковой последовательности токенов и отличаются только предикатом.

Подъем будет использоваться. Для проверки откройте метод start() сгенерированного класса DisambiguatingHoistingNeededParser в нашем примере проекта. Он содержит копии условий 1+2==3 и 1+2!=3 .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
int alt1=2;
switch ( input.LA(1) ) {
case LETTER: {
  switch ( input.LA(2) ) {
  case LETTER: {
    int LA1_2 = input.LA(3);
 
    if ( ((1+2==3)) ) {
      alt1=1;
    } else if ( ((1+2!=3)) ) {
      alt1=2;
    } else { /* ... */ }
  }
  break;
  default: // ...
  }
}
break;
default: // ...
}

Точно то же самое происходит с неоднозначностью предикатов в альтернативах.

Это не будет поднят (грамматика DisambiguatingHoistingNotNeeded.g):

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
alternatives: LETTER (
  {2+3==5}? LETTER
  | {2+3==5}? NUMBER
);

Это будет поднят (грамматика DisambiguatingHoistingNeeded.g):

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
alternatives: LETTER (
  {2+3==5}? LETTER
  | {2+3==5}? LETTER
);

Всегда Подъем — Закрытые Правила

Посмотрите на правило start в грамматике GatedHoisting.g:

1
2
3
4
5
6
7
LETTER : 'a'..'z' | 'A'..'Z';
NUMBER: '0'..'9';
 
word: {1+2==3}?=> LETTER LETTER;
differentWord: {1+2!=3}?=> LETTER NUMBER;
 
start: word | differentWord;

Правило start должно выбирать между word и differentWord словами. Оба они начинаются с предиката, и этот предикат не нужен для того, чтобы различать их.

Однако подъем будет использоваться, потому что мы использовали стробированный семантический предикат. Для проверки откройте метод start() сгенерированного класса GatedHoisting в нашем примере проекта. Он содержит копии условий 1+2==3 и 1+2!=3 .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int LA1_0 = input.LA(1);
 
if ( (LA1_0==LETTER) && (((1+2==3)||(1+2!=3)))) {
  int LA1_1 = input.LA(2);
 
  if ( (LA1_1==LETTER) && ((1+2==3))) {
    alt1=1;
  }
  else if ( (LA1_1==NUMBER) && ((1+2!=3))) {
    alt1=2;
  }
  else {
    NoViableAltException nvae =
      new NoViableAltException('', 1, 1, input);
 
    throw nvae;
  }
}
else {
  NoViableAltException nvae =
      new NoViableAltException('', 1, 0, input);
 
  throw nvae;
}

Точно то же самое происходит с закрытыми предикатами в альтернативах. Это будет поднято (грамматика GatedHoisting.g):

1
2
3
4
5
6
7
LETTER : 'a'..'z' | 'A'..'Z';
NUMBER: '0'..'9';
 
alternatives: LETTER (
  {2+3==5}?=> LETTER
  | {2+3==5}?=>NUMBER
);

Никогда не поднимать — середина правила

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

Неподтвержденный предикат gated (GatedNoHoisting.g):

1
2
3
4
5
6
7
8
LETTER: 'a'..'z' | 'A'..'Z';
NUMBER: '0'..'9';
 
//gated predicate in the middle of a rule
word: LETTER {1+2==3}?=> LETTER;
differentWord: LETTER {1+2!=3}?=> NUMBER;
 
start: word | differentWord;

Еще один невнятный предикат gated (GatedNoHoisting.g):

1
2
3
4
5
6
7
8
LETTER: 'a'..'z' | 'A'..'Z';
NUMBER: '0'..'9';
 
//gated predicate in the middle of an alternative
alternatives: LETTER (
  LETTER {2+3==5}?=> LETTER
  | LETTER {2+3==5}?=> NUMBER
);

Сгенерированный парсер находится в классе GatedNoHoistingParser .

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

Неверная грамматика (SyntacticallyIncorrect.g):

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
word: LETTER {1+2==3}? LETTER;
sameWord: LETTER {1+2!=3}? LETTER;
 
start: word | sameWord;

Ошибка в консоли:

1
2
3
warning(200): org\meri\antlr\predicates\SyntacticallyIncorrect.g:28:6: Decision can match input such as 'LETTER LETTER' using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): org\meri\antlr\predicates\SyntacticallyIncorrect.g:28:6: The following alternatives can never be matched: 2

Еще одна неправильная грамматика (SyntacticallyIncorrect.g):

1
2
3
4
alternativesStart: LETTER (
  LETTER {1+2==3}?
  | LETTER {1+2!=3}?
);

Ошибка в консоли:

1
2
3
warning(200): org\meri\antlr\predicates\SyntacticallyIncorrect.g:31:27: Decision can match input such as 'LETTER' using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): org\meri\antlr\predicates\SyntacticallyIncorrect.g:31:27: The following alternatives can never be matched: 2

Еще одна неправильная грамматика (SyntacticallyIncorrect.g):

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
gatedWord: LETTER {1+2==3}?=> LETTER;
gatedSameWord: LETTER {1+2!=3}?=> LETTER;
 
gatedStart: gatedWord | gatedSameWord;

Ошибка в консоли:

1
2
3
warning(200): org\meri\antlr\predicates\SyntacticallyIncorrect.g:40:11: Decision can match input such as 'LETTER LETTER' using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): org\meri\antlr\predicates\SyntacticallyIncorrect.g:40:11: The following alternatives can never be matched: 2

Последняя неправильная грамматика (SyntacticallyIncorrect.g):

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
gatedAlternativesStart: LETTER (
  LETTER {1+2==3}?=> LETTER
  | LETTER {1+2!=3}?=> LETTER
);

Ошибка в консоли:

1
2
3
warning(200): org\meri\antlr\predicates\SyntacticallyIncorrect.g:43:32: Decision can match input such as 'LETTER LETTER' using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): org\meri\antlr\predicates\SyntacticallyIncorrect.g:43:32: The following alternatives can never be matched: 2

Нюансы

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

Этот подраздел содержит другой набор примеров. Мы выбрали наиболее потенциально запутанные из известных нам. Все используемые примеры находятся в файле Nuances.g.

Предсказания двусмысленности — Продвинутый

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

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

1
2
3
4
advancedDisambiguating: LETTER (
  {1+2==3}? LETTER LETTER
  | {1+2!=3}? LETTER*
);

Если ввод начинается ровно с одной LETTER , то он не может быть проанализирован по первой альтернативе. Поскольку только вторая альтернатива соответствует ему, предикат не будет использоваться. Парсер будет использовать вторую альтернативу, и если условие 1+2!=3 окажется false , парсер сгенерирует исключение с ошибкой предиката.

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int alt4=2;
switch ( input.LA(1) ) {
case LETTER: {
    switch ( input.LA(2) ) {
    case LETTER: {
      int LA4_3 = input.LA(3);
      //predicate is used only if first two tokens are LETTER
      if ( ((1+2==3)) ) {
        alt4=1;
      }
      else if ( ((1+2!=3)) ) {
        alt4=2;
      }
      else {
        // ... irrelevant code ...
      }
    }
    break;
    //if the second token is not LETTER, predicate is not used
    case EOF: { alt4=2; } break;
    default: // ...
    }
  }
  break;
//if the first token is not LETTER, predicate is not used
case EOF: // ...
default: // ...
}

Сравните это с очень похожим стробированным правилом:

1
2
3
4
compareGated: LETTER (
  {1+2==3}?=> LETTER LETTER
  | {1+2!=3}?=> LETTER*
);

Парсер будет использовать предикат независимо от того, что. Второй вариант никогда не будет введен, потому что предикат 1+2!=3 никогда не выполняется:

1
2
3
4
5
6
7
8
int alt6=2;
int LA6_0 = input.LA(1);
 
if ( (LA6_0==LETTER) && (((1+2==3)||(1+2!=3)))) {
  int LA6_1 = input.LA(2);
 
  if ( (LA6_1==LETTER) && (((1+2==3)||(1+2!=3)))) {
    int LA6_3 = input.LA(3);

Предикат Gated заставляет antlr генерировать исключения другого рода в этом случае. Как мы покажем позже в этом посте , различное поднятие закрытых и однозначных предикатов может иметь гораздо большее значение для более сложных предикатов. А именно, это может иметь значение между принятием и отклонением ввода.


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

Используйте предикат, чтобы оставаться в цикле только пока он возвращает true:

1
2
LETTER : 'a'..'z' | 'A'..'Z';
loop: ( {somePredicate()}?=> LETTER )*;

Правило loop будет сопоставлять буквы до тех пор, пока функция somePredicate() вернет false или пока в правиле не закончатся токены LETTER .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
loop1:
do {
  int alt1=2;
  int LA1_0 = input.LA(1);
  // predicate is used during the prediction
  if ( (LA1_0==LETTER) && ((somePredicate()))) {
    alt1=1;
  }
  //matching: either jump out or match another LETTER
  switch (alt1) {
    case 1: {
      if ( !((somePredicate())) ) {
        throw new FailedPredicateException(...);
      }
      // ... match LETTER ...
      }
      break;
 
    default:
      break loop1;
  }
} while (true);

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

1
2
LETTER : 'a'..'z' | 'A'..'Z';
loopDisambiguating: ( {somePredicate()}? LETTER )*;

Технически, цикл LETTER альтернативу LETTER и <nothing> . Они синтаксически различны, и предсказание использует однозначные предикаты, только если оно должно выбирать между синтаксически неоднозначными альтернативами.

Правило loopDisambiguating будет сопоставлять буквы до тех пор, пока не закончатся токены LETTER . Если функция somePredicate() возвращает false течение этого времени, правило FailedPredicateException исключение FailedPredicateException .

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
loop2:
do {
  int alt2=2;
  //prediction ignores the predicate
  switch ( input.LA(1) ) {
    case LETTER: {
      alt2=1;
    }
    break;
  }
  //matching: either jump out or match another LETTER
  switch (alt2) {
    case 1: {
      if ( !((somePredicate())) ) {
        throw new FailedPredicateException(...);
      }
      // ... match LETTER ...
      }
      break;
 
    default:
      break loop2;
  }
} while (true);

Открытые альтернативы

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

Закрытый предикат всегда поднимается:

1
2
3
4
uncoveredGated: LETTER (
  {3+4==7}?=> LETTER
  | NUMBER
);

Поднял однозначный предикат:

1
2
3
4
uncoveredDisambiguatingHoisted: LETTER (
  {2+5==7}? LETTER*
  | LETTER+
);

Не поднятый однозначный предикат:

1
2
3
4
uncoveredDisambiguatingNotHoisted: LETTER (
  {2+4==6}? LETTER
  | NUMBER
);


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

Предикат закрытого типа поднимается, в то время как однозначный предикат не поднимается:

1
2
3
4
combinationDisambiguatingNotHoisted: LETTER (
  {1+4==5}?=> LETTER
  | {1+4!=5}? NUMBER
);

Оба предиката подняты:

1
2
3
4
combinationDisambiguatingHoisted: LETTER (
  {1+5==6}?=> LETTER*
  | {1+5!=6}? LETTER+
);

Дополнительная скобка

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

Еще один способ написать однозначный предикат:

1
2
stillDisambiguating: ({2+2==4}?) LETTER;
testStillDisambiguating: stillDisambiguating | LETTER;

Если вы поставите дополнительные скобки вокруг gated-предиката, предикат будет проигнорирован:

1
ignored: ({3+3==6}?)=>LETTER;

Откат

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

Правило backtrack инициирует возврат (Backtracking.g):

1
2
3
4
5
LETTER : 'a'..'z' | 'A'..'Z';
word: LETTER {1+2==3}? LETTER;
number:  LETTER {2+3!=5}? LETTER;
 
backtrack: (number)=> number | word;

Поскольку возврат возможен, сгенерированная проверка предикатов отличается:

1
2
3
4
if ( !((2+3!=5)) ) {
  if (state.backtracking>0) {state.failed=true; return retval;}
  throw new FailedPredicateException(input, 'number', '2+3!=5');
}

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

Условия написания

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

Если не указано иное, все используемые примеры находятся в файле Environnement.g.

Входной токен

Каждый сгенерированный парсер имеет открытое TokenStream input . Это поле обеспечивает доступ ко всему потоку входного токена, а также к текущей позиции в этом потоке токенов. Его наиболее важным методом является метод Token LT(int k) . Параметр k содержит относительную позицию интересующего вас токена.

Число 1 означает «смотреть вперед на один токен», 2 означает «второй токен вперед» и так далее. Отрицательные числа ссылаются на переданные токены: -1 возвращает предыдущий токен, -2 возвращает предыдущий токен и так далее. Не используйте 0. Его значение не определено, и анализатор по умолчанию возвращает null .

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

Примеры

Устранение неоднозначности: если
word начинается с буквы
a , тогда оно должно содержать как минимум две буквы:

1
2
3
4
word: LETTER (
    { input.LT(-1).getText().equals('a')}? LETTER+
  | { !input.LT(-1).getText().equals('a')}? LETTER*
  );

Gated: если вторая цифра number 9 , то она должна иметь ровно 3 цифры:

1
2
3
4
number: NUMERAL (
  {input.LT(1).getText().equals('9')}?=> NUMERAL NUMERAL
  | {!input.LT(1).getText().equals('9')}?=> NUMERAL*
);

Примечание: выбор предиката незначительно имеет значение в этом случае. Это влияет на то, какая ошибка будет выброшена, если ввод не соответствует правилу.

Ярлыки и Списки

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

Пример метки

Если первая буква слова — a , то слово должно содержать как минимум две буквы:

1
2
3
4
labeledWord: a=LETTER (
    { $a.getText().equals('a')}? LETTER+
  | { !$a.getText().equals('a')}? LETTER*
  );


Пример списка меток Если слово начинается не более чем с трех букв, оно должно заканчиваться цифрой:

1
2
3
4
labeledListWord: a+=LETTER+ (
    { $a.size() < 3 }?=> NUMERAL
  | { $a.size() >= 3}?=>
  );

Примечание: выбор предиката имеет значение в этом случае. Приведенный выше пример работает правильно, только если он использует предикат gated {...}?=> Вместо устранения неоднозначности {...}? один. NUMERAL и <nothing> синтаксически разные. Предикат неоднозначности не будет использоваться для прогнозирования, например, он не будет поднят. Парсер будет основывать свое решение исключительно на следующем токене (это NUMERAL ?).

Условие будет использоваться в качестве последующего утверждения для проверки правильности количества букв. Такая грамматика создаст исключение на входе abcd9 , в то время как наша примет это.

Неопределенные ярлыки

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

1
2
//this would cause null pointer exception
nullPointerAtPredicate: LETTER { $a.getText().equals('a') }? a=LETTER;

Ярлыки и переход в другие правила

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

Доступ к локальным переменным

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

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

1
2
3
4
5
6
7
localVariables
@init {int num=0;} //define local variable num
  : (LETTER { num++; })* //raise the num variable by 1 for each letter 
  ( // what should follow depends on the variable value
    { num < 10 }?=> NUMERAL
    | { num >= 10}?=>
  );

Примечание: применяется то же предупреждение, что и раньше. Мы должны использовать закрытые предикаты.

Вы должны быть особенно осторожны, чтобы не использовать локальные переменные в потенциальных предикатах. Например, Справочник Antlr рекомендует следующее правило, чтобы соответствовать только числам, состоящим из менее чем четырех чисел (ANTLRReference3Error.g):

1
2
3
4
localVariablesWarning
@init {int n=1;} // n becomes a local variable
  : ( {n<=4}?=> NUMERAL {n++;} )+ // enter loop only if n<=4
  ;

Вышеупомянутое правило хорошо работает в изоляции, то есть когда оно не используется в других правилах. К сожалению, если вы включите его в другие правила, предикат может быть включен в это другое правило (ANTLRReference3Error.g):

1
2
// syntax error in generated parser
syntaxError: localVariablesWarning | LETTER;

Предикат n<=4 будет скопирован в правило syntaxError . Переменная n недоступна внутри этого правила, и сгенерированный синтаксический анализатор будет синтаксически некорректным.

Решение начальных вариантов использования

Наконец, мы собираемся решить оба варианта использования, описанные в мотивационной главе.


Ключевые слова — nth
Ссылка на оригинальный вариант использования.

Мы создали функцию isInsideNth которая возвращает true только в том случае, если предыдущий токен совпал с именем некоторого n-го псевдокласса. Функция используется как условие внутри стробированного предиката. Сгенерированный парсер будет предполагать, что входные данные содержат n-е выражение тогда и только тогда, когда они находятся внутри n-го псевдокласса.

Файл UseCasesNth.g:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
@parser::members {
  private static Set<String> NTH_PSEUDOCLASSES = new HashSet<String>();
  static {
    NTH_PSEUDOCLASSES.add('nth-child');
    NTH_PSEUDOCLASSES.add('nth-last-child');
    NTH_PSEUDOCLASSES.add('nth-of-type');
    NTH_PSEUDOCLASSES.add('nth-last-of-type');
  }
 
  public boolean isInsideNth() {
    return isNthPseudoClass(input.LT(-1));
  }
 
  private boolean isNthPseudoClass(Token a) {
    if (a == null)
      return false;
    String text = a.getText();
    if (text == null)
      return false;
    return NTH_PSEUDOCLASSES.contains(text.toLowerCase());
  }
 
}
 
LPAREN: '(';
RPAREN: ')';
COLON: ':';
COMMA: ',';
IDENT : ('a'..'z' | 'A'..'Z')+;
 
//pseudoparameters and nth with dummy syntax
pseudoparameters: IDENT (COMMA IDENT)*;
nth: IDENT; //real nth syntax ommited for simplicity sake
 
// pseudoclass
pseudo
    : COLON COLON? IDENT ((
        { isInsideNth()}?=> LPAREN nth RPAREN
        | LPAREN pseudoparameters RPAREN
        )?)
    ;

Альтернативное решение с метками и правилом перезаписи:

1
2
3
4
5
6
7
8
//different solution - note that we need to use rewrite rules in this case
pseudoDifferentSolution
    : COLON COLON? name=IDENT ((
        { isNthPseudoClass($name)}?=> LPAREN nthParameters=nth RPAREN
        | LPAREN parameters=pseudoparameters RPAREN
        )?)
    -> $name $nthParameters? $parameters? 
    ;


Значительные пробелы
Ссылка на оригинальный вариант использования.

Селекторы Css могут состоять из нескольких частей, разделенных комбинаторами > , + , ~ и <space> . Каждая часть, называемая простым селектором, начинается с необязательного имени элемента и может сопровождаться несколькими псевдоклассами, атрибутами и аналогичными структурами.

Игнорирование пространства как проблемы комбинатора упрощенная грамматика простого селектора может выглядеть так:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
COLON: ':';
STAR: '*';
NUMBER: ('0'..'9')+;
IDENT : ('a'..'z' | 'A'..'Z')+;
 
//some options have been removed from following rules for simplicity sake
elementName: IDENT | STAR | NUMBER;
pseudoClass: COLON COLON? IDENT;
elementSubsequent: pseudoClass;
 
simpleSelectorWrong:
  (elementName elementSubsequent*)
  | elementSubsequent+
;

Приведенное выше правило simpleSelectorWrong соответствует допустимым простым селекторам: h1 , h1:first-child:hover simpleSelectorWrong :first-child:hover и :hover .

К сожалению, поскольку пробелы выбрасываются, вышеприведенное правило больше соответствует этому. Например, он будет также соответствовать h1:first-child :hover который должен интерпретироваться точно так же, как h1:first-child *:hover selector, например, как два простых селектора, соединенных <space> .

Мы создали метод, который возвращает true, только если между предыдущим и следующим токенами нет скрытого токена. Если не указано иное, все токены являются экземпляром класса CommonToken . Так как обычный токен знает свой индекс начала и окончания, мы можем привести их и сравнить, чтобы увидеть, было ли что-то между ними.

Новые методы парсера (UseCasesSelectors.g):

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
@parser::members {
  public boolean onEmptyCombinator(TokenStream input) {
    return !directlyFollows(input.LT(-1), input.LT(1));
  }
 
  private boolean directlyFollows(Token first, Token second) {
    CommonToken firstT = (CommonToken) first;
    CommonToken secondT = (CommonToken) second;
 
    if (firstT.getStopIndex() + 1 != secondT.getStartIndex())
      return false;
 
    return true;
  }
}

Фиксированный простой селектор использует gated-предикат, чтобы проверить, следует ли продолжать добавлять последующие элементы (UseCasesSelectors.g):

1
2
3
4
5
simpleSelector: (
    elementName ({!onEmptyCombinator(input)}?=>elementSubsequent)*
  ) | (
    elementSubsequent ({!onEmptyCombinator(input)}?=>elementSubsequent)*
  );

В этом случае мы должны использовать закрытые предикаты. Если бы мы использовали однозначный предикат, сгенерированный парсер не использовал бы наш предикат, чтобы решить, оставаться ли внутри цикла или нет. Это связано с тем, что цикл технически определяет elementSubsequent и <nothing> и они синтаксически различны. {...}? Предикат не будет использоваться во время прогнозирования, он просто будет выдавать исключения.

Завершение

Семантические предикаты — это условия Java, написанные внутри грамматики. Они копируются в сгенерированный парсер без изменений. Если алгоритм сопоставления токенов достигает семантического предиката и этот предикат завершается ошибкой, FailedPredicateException исключение FailedPredicateException .

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

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

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

Проверка семантических предикатов

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

Условие закрыто внутри фигурных скобок с последующим знаком вопроса { condition }? , Он должен быть помещен либо в середине правила, либо в середине альтернативы:

1
2
LETTER : 'a'..'z' | 'A'..'Z';
word: LETTER {1+2==3}? LETTER;

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

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

Для устранения неоднозначности семантических предикатов используется тот же синтаксис, что и для проверки предикатов. Условие закрыто внутри фигурных скобок с последующим знаком вопроса{ condition }? , Тем не менее, они должны быть размещены либо в начале правила, либо в начале альтернативы:

1
2
3
4
5
6
LETTER : 'a'..'z' | 'A'..'Z';
// beginning of an alternative
alternatives: LETTER (
  {2+3==5}? LETTER*
  | {2+3==5}? LETTER+
);

Закрытые семантические предикаты

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

Условие закрывается внутри фигурных скобок с последующим знаком вопроса и двойной стрелкой { condition }?=>:

1
2
NUMERAL: '0'..'9';
number: {2+3==5}?=> NUMERAL NUMERAL;


Ресурсы

Ссылка: ANTLR — Семантические предикаты от нашего партнера по JCG Марии Юрковичовой вблоге This Is Stuff .

51
Share: