Что такое «семантический предикат» в ANTLR?

102

Что такое семантический предикат в ANTLR?

Барт Кирс
источник
3
Обратите внимание, что, поскольку я не смог найти достойный онлайн-ресурс для публикации для кого-то, кто хотел бы знать, что такое семантический предикат , я решил сам опубликовать здесь вопрос (на который я тоже вскоре отвечу).
Барт Кирс
1
Спасибо за это; Мне всегда нравится, когда люди отвечают на свои вопросы, особенно если они задают вопрос специально, чтобы ответить на него таким образом.
Daniel H
1
Читать книгу. В главе 11 The Definitive ANTLR 4 Reference рассматриваются семантические предикаты. Нет книги? Возьми! Стоит каждого доллара.
james.garriss

Ответы:

169

ANTLR 4

Для предикатов в ANTLR 4 ознакомьтесь с этими вопросами и ответами по переполнению стека :


ANTLR 3

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

Есть 3 типа семантических предикатов:

  • проверка семантических предикатов;
  • стробированные семантические предикаты;
  • устранение неоднозначности семантических предикатов.

Пример грамматики

Допустим, у вас есть блок текста, состоящий только из чисел, разделенных запятыми, без учета пробелов. Вы хотели бы проанализировать этот ввод, убедившись, что числа не более 3 цифр "длинные" (не более 999). Следующая грамматика ( Numbers.g) сделает такую ​​вещь:

grammar Numbers;

// entry point of this parser: it parses an input string consisting of at least 
// one number, optionally followed by zero or more comma's and numbers
parse
  :  number (',' number)* EOF
  ;

// matches a number that is between 1 and 3 digits long
number
  :  Digit Digit Digit
  |  Digit Digit
  |  Digit
  ;

// matches a single digit
Digit
  :  '0'..'9'
  ;

// ignore spaces
WhiteSpace
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

Тестирование

Грамматику можно проверить с помощью следующего класса:

import org.antlr.runtime.*;

public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("123, 456, 7   , 89");
        NumbersLexer lexer = new NumbersLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        NumbersParser parser = new NumbersParser(tokens);
        parser.parse();
    }
}

Проверьте это, сгенерировав лексер и парсер, скомпилировав все .javaфайлы и запустив Mainкласс:

java -cp antlr-3.2.jar org.antlr.Tool Numbers.g
javac -cp antlr-3.2.jar * .java
java -cp.: antlr-3.2.jar Главный

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

ANTLRStringStream in = new ANTLRStringStream("123, 456, 7   , 89");

в:

ANTLRStringStream in = new ANTLRStringStream("123, 456, 7777   , 89");

и повторите тест: вы увидите сообщение об ошибке в консоли сразу после строки 777.


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

Это подводит нас к семантическим предикатам. Допустим, вы хотите проанализировать числа длиной от 1 до 10 цифр. Правило вроде:

number
  :  Digit Digit Digit Digit Digit Digit Digit Digit Digit Digit
  |  Digit Digit Digit Digit Digit Digit Digit Digit Digit
     /* ... */
  |  Digit Digit Digit
  |  Digit Digit
  |  Digit
  ;

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


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

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

RULE { /* a boolean expression in here */ }?

Чтобы решить указанную выше проблему с помощью проверяющего семантического предиката, измените numberправило грамматики на:

number
@init { int N = 0; }
  :  (Digit { N++; } )+ { N <= 10 }?
  ;

Части { int N = 0; }и { N++; }представляют собой простые операторы Java, первая из которых инициализируется, когда синтаксический анализатор «входит» в numberправило. Фактический предикат:, { N <= 10 }?который заставляет синтаксический анализатор выдавать FailedPredicateException каждый раз, когда число превышает 10 цифр.

Проверьте это, используя следующее ANTLRStringStream:

// all equal or less than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,1234567890"); 

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

// '12345678901' is more than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,12345678901");

2. Стробированные семантические предикаты

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

Синтаксис стробированного семантического предиката :

{ /* a boolean expression in here */ }?=> RULE

Чтобы вместо этого решить указанную выше проблему, используя стробированные предикаты для сопоставления чисел длиной до 10 цифр, вы должны написать:

number
@init { int N = 1; }
  :  ( { N <= 10 }?=> Digit { N++; } )+
  ;

Проверьте это снова с обоими:

// all equal or less than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,1234567890"); 

и:

// '12345678901' is more than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,12345678901");

и вы увидите, что последний вызовет ошибку.


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

Последний тип предиката - это семантический предикат , устраняющий неоднозначность , который немного похож на проверяющий предикат ( {boolean-expression}?), но действует больше как стробируемый семантический предикат (при вычислении логического выражения исключение не генерируется false). Вы можете использовать его в начале правила, чтобы проверить какое-либо свойство правила и позволить синтаксическому анализатору соответствовать указанному правилу или нет.

Предположим, что в примере грамматики создаются Numberтокены (правило лексера вместо правила синтаксического анализатора), которые будут соответствовать числам в диапазоне 0..999. Теперь в синтаксическом анализаторе вы хотите различать низкие и высокие числа (low: 0..500, high: 501..999). Это можно сделать с помощью семантического предиката, устраняющего неоднозначность, когда вы проверяете токен, следующий в stream ( input.LT(1)), чтобы проверить, низкий он или высокий.

Демо:

grammar Numbers;

parse
  :  atom (',' atom)* EOF
  ;

atom
  :  low  {System.out.println("low  = " + $low.text);}
  |  high {System.out.println("high = " + $high.text);}
  ;

low
  :  {Integer.valueOf(input.LT(1).getText()) <= 500}? Number
  ;

high
  :  Number
  ;

Number
  :  Digit Digit Digit
  |  Digit Digit
  |  Digit
  ;

fragment Digit
  :  '0'..'9'
  ;

WhiteSpace
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

Если вы сейчас проанализируете строку "123, 999, 456, 700, 89, 0", вы увидите следующий результат:

low  = 123
high = 999
low  = 456
high = 700
low  = 89
low  = 0
Барт Кирс
источник
12
Чувак, тебе действительно стоит подумать о написании руководства по ANTLR для начинающих: P
Юрий Генсев
5
@Bart Kiers: Пожалуйста, напишите книгу об ANTLR
Сантош Сингх
2
Для ANTLR v4, input.LT(1)является в getCurrentToken()настоящее время :-)
Сяо Цзя
Фантастически ... Это исчерпывающее объяснение и примеры, которые должны быть в документации!
Иезекииль Виктор
+1. Этот ответ намного лучше, чем The Definitive ANTLR 4 Reference book. Этот ответ вписывается в концепцию с хорошими примерами.
asyncwait
11

Я всегда использовал краткую ссылку на предикаты ANTLR на wincent.com в качестве руководства.

Калеб Педерсон
источник
6
Да отличная ссылка! Но, как вы упомянули, это может быть немного сложно для кого-то (относительно) нового в ANTLR. Я просто надеюсь, что мой ответ будет (немного) более дружелюбным для ANTLR-травосборника. :)
Барт Кирс