Блог

Главная - Вопросы по программированию - ANTLR: как присвоить приоритет альтернативному правилу синтаксического анализа

ANTLR: как присвоить приоритет альтернативному правилу синтаксического анализа

#parsing #nlp #compiler-construction #antlr #grammar

#синтаксический анализ #nlp #компилятор-конструкция #antlr #грамматика

Вопрос:

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

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

  1. What was the temperature in August 2019? — Просто. Единая единица измерения даты (август 2019 года).
  2. Which was hotter between June 3rd 2019 and yesterday? — Все еще просто. Две единицы измерения даты (3 июня 2019 года и вчера).
  3. Between August 2018 and 2019, which was hotter? — Сложно. Естественным ожиданием пользователя в этом случае было бы сравнить август 2018 и август 2019 (неявно). Для обработки таких случаев я хочу 2018 and 2019 , чтобы меня анализировали как единое year_pair правило и August анализировали как month .

В настоящее время я обрабатываю только случаи 1 и 2. Случай 1 обрабатывается простым способом. Случай 2 обрабатывается с помощью date_unit AND date_unit правила. Но чтобы обработать случай 3 сейчас, я также попытался добавить year AND year правило, так что 2018 and 2019 оно воспринимается как year_pair намного раньше, но из-за нисходящей природы ANTLR оно по-прежнему анализирует их в August 2018 и 2019 .

Как я могу изменить это так, чтобы оно анализировалось August 2018 and 2019 в August и 2018 and 2019 вместо (сохраняя при этом общее date_unit AND date_unit правило?

Комментарии:

1. Не могли бы вы отредактировать свой вопрос и добавить свою грамматику?

2. Этот заголовок вопроса довольно вводит в заблуждение. Вам следует подумать о замене его чем-то, что соответствует вашему фактическому вопросу.

3. Да, учитывая название, я ожидал чего-то другого. Хотя я понимаю формулировку…

4. @MikeLischke Почему вы думаете, что это вводит в заблуждение? Я действительно хочу присвоить одному правилу приоритет над другим.

5. «синтаксический анализ в стиле снизу вверх» подразумевает синтаксический анализатор LR, который ANTLR не генерирует: он генерирует синтаксические анализаторы LL (см. geeksforgeeks.org/difference-between-ll-and-lr-parser ). По крайней мере, я думаю, что это то, что имел в виду Майк 🙂

Ответ №1:

Вы пытаетесь добавить семантику к синтаксису. С точки зрения языка неявное ожидание пользователя вообще не имеет значения. Анализатор (как инструмент синтаксиса) может только определить, соответствует ли ввод языку, а не соответствует ли ввод семантическим правилам).

Вместо этого вы должны использовать ANTLR4 для количественной оценки ваших входных данных и создания дерева синтаксического анализа. Затем на втором шаге выполните семантический анализ, где вы можете применить свои специальные правила даты (например, автоматическое заполнение неявных частей даты).

Комментарии:

1. Да нет, на самом деле я пытаюсь повлиять только на синтаксис. Это влияние, мотивированное семантической заботой, не делает его автоматически семантической проблемой, нет?

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

Ответ №2:

«Восходящий» — это термин, который десятилетиями является синонимом синтаксического анализа LR и не имеет ничего общего ни с ANTLR, ни с проблемой. Это неправильный термин.

Решение Майка выше — это то, что сделало бы большинство людей, потому что a date_range соответствует только a Tuple<date_unit, date_unit> , и можно было бы просто создать этот тип в семантическом анализаторе. Вы хотите синтаксически описать другой диапазон, что-то вроде Tuple<month, Tuple<year, year>> и другие варианты. Вот грамматика, которая это делает. Он создает деревья, которые вы ищете, для всех трех ваших примеров.

 grammar Dates;

MONTH : 'January' | 'February' | 'March' | 'April' | 'May' | 'June' | 'July' | 'August' | 'September' | 'October' | 'November' | 'December' ;
YESTERDAY : 'yesterday' ;
FIRST : 'First';
SECOND : 'Second';
THIRD : 'Third';
AND : 'and' ;
BETWEEN : 'between';
ORDINAL: [1-9][0-9]* ('rd' | 'th');
CARDINAL : [0-9]  ;
WS: [ trn]  -> skip;

// NB: Note order here.
range
    : BETWEEN month year_group
    | BETWEEN date_unit AND date_unit
    ;

input: ( date_unit | range ) EOF ;
year_group : year AND year ;
date_unit : month day year | month year | year | yesterday ;
day : ordinal | CARDINAL ;
ordinal : ORDINAL | FIRST | SECOND | THIRD ;
month : MONTH ;
year : CARDINAL ;
yesterday : YESTERDAY ;