Можно ли преобразовать грамматику ANTLR3 в регулярное выражение?

У меня есть простой анализатор грамматики ANTLR3, который берет короткие строки текста и преобразует их в объекты Java. Далее у меня есть большой список текстовых строк. Некоторые из них (менее 1%) могут быть преобразованы, потому что они соответствуют грамматике.

Мне нужно пропустить их все через синтаксический анализатор, чтобы понять, какие из них являются конвертируемыми, и создать коллекцию объектов Java. Очень трудоемкая операция. Гораздо эффективнее было бы передать их через регулярное выражение перед отправкой в ​​ANTLR3.

Я могу создать такое регулярное выражение самостоятельно, но было бы гораздо лучше получить его динамически из парсера ANTLR3. Возможно ли это сделать?


java antlr antlr3
person yegor256    schedule 15.03.2011    source источник
comment
Несколько несвязанный, но если существует строгое отношение одна строка к одному объекту, вы можете легко распараллелить обработку.   -  person biziclop    schedule 16.03.2011

Ответы (2)


arrow_upward
4
arrow_downward

В общем, только обычные языки могут иметь описывающие их регулярные выражения. (Большинство RE-движков поддерживают функции, которые также соответствуют некоторым нерегулярным языкам (например, по обратным ссылкам), но все же не все контекстно-свободные или даже общие формальные языки.)

Я на самом деле не эксперт по antlr, но я полагаю, что его грамматика может соответствовать языкам, которые не совместимы с RE.

Так что даже теоретическая разрешимость вашей задачи на самом деле не дается, она зависит от грамматики.

Может быть, что

  • ваша грамматика на самом деле является обычной грамматикой, или
  • что существует обычный язык, который является небольшим надмножеством вашего языка грамматики - таким образом, RE может отфильтровать большинство несовпадающих строк, в то время как некоторые будут отфильтрованы только грамматикой/парсером.

Скорее всего, нет определенного способа убедиться, не видя вашей грамматики.

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

person Paŭlo Ebermann    schedule 15.03.2011
comment
+1 за теорию языка и за наблюдение, что может существовать регулярный язык, который является небольшим надмножеством данного нерегулярного языка - я не думал об этом раньше. - person Aasmund Eldhuset; 16.03.2011

arrow_upward
1
arrow_downward

Чтобы быть конкретным, ANTLR может анализировать подкласс LL(*) контекстно-свободные грамматики.

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

person Matthew Sowders    schedule 15.03.2011