Удаление действий из грамматики ANTLR меняет алгоритм синтаксического анализа - PullRequest
Новая
       61

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

1 голос
/ 09 декабря 2011

У меня есть грамматика Foo.xtext (слишком сложная, чтобы включить ее здесь).Xtext генерирует InternalFoo.g из него. После некоторой настройки он также генерирует DebugInternalFoo.g, который утверждает, что это то же самое без действий.Теперь я снимаю действия с ANTLR напрямую 

java -cp antlr-3.4.jar org.antlr.tool.Strip Internal.g > Stripped.g

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

  • InternalFoo.g - ошибка, при назначении правила принимается решение без LL (*)
  • DebugInternalFoo.g - нет проблем, хорошо разбирает
  • Stripped.g - предупреждения при назначении правила, решение может совпадать с использованием нескольких альтернатив.Он не может правильно проанализировать.

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

ОБНОВЛЕНИЕ:

Я частично нашел причину проблемы.Рассматриваемое правило было следующим: 

trickyRule:
  ({ some complex action})
  (expression '=')=>...

Удаление с помощью Antlr удалило действие, но оставило там пустую группу: 

// Stripped.g
trickyRule:
  () (expression '=')=>...

Генерация грамматики отладки удаляет оба действия,и теперь вокруг него пустая группа: 

// DebugInternalFoo.g
trickyRule:
  (expression '=')=>...

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

1 Ответ

0 голосов
/ 09 декабря 2011

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

Да, это возможно.org.antlr.tool.Strip оставляет синтаксические предикаты 1 , но удаляет проверяющие 2 - и стробированные 3 семантические предикаты (и секции member, которые могут использовать эти семантические предикаты).

Например, следующие правила будут соответствовать только A_TOKEN: 

parser_rule1
  :  (parser_rule2)=> parser_rule2
  ;

parser_rule2
  :  {input.LT(1).getType() == A_TOKEN}? .
  ;

, но если вы используете инструмент Strip, он оставляет следующее: 

parser_rule1
  :  (parser_rule2)=> parser_rule2
  ;

parser_rule2
  :  /*{input.LT(1).getType() == A_TOKEN}?*/ .
  ;

соответствие любому токену.

Другими словами, Strip может изменить поведение сгенерированного лексера или анализатора.

1 синтаксический предикат: ( ... )=> 2 проверка семантического предиката { ... }? 3 стробированный семантический предикат { ... }?=>

...