Когда использовать синтаксический анализатор, достаточно ли регулярного выражения?

Question

Я еще не попал в область официальных языков в области компьютерных наук, поэтому, возможно, мой вопрос глупо. Я пишу простой синтаксический анализатор NMEA на C++, и мне нужно выбрать:

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

Тогда я подумал об использовании генератора синтаксического анализатора. Я думаю, что все используют один и тот же метод: они генерируют FSA. Но я не знаю, что более эффективно. Когда вы обычно используете генераторы парсеров вместо регулярных выражений (я думаю, вы могли бы писать регулярное выражение в генераторе синтаксического анализатора)?

Пожалуйста, объясните различия, меня интересуют как теория, так и опыт.

Answer 1

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

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

Answer 2

Regex является синтаксический анализатор.

Из википедии:

Регулярные выражения (сокращенно регулярное выражение или регулярное выражение, с множественного числа регулярных выражений, регулярных выражений, или regexen) написаны на формальном языке, который может быть интерпретирован регулярным процессором экспрессии, одной из программ который либо служит генератором парсера, либо анализирует текст и идентифицирует части, которые соответствуют предоставленной спецификации.

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

Это намного быстрее, чем вы предполагали. Я видел выражения больше, чем этот пост.

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

Answer 3

Как указывает Sneakyness, у вас может быть большое и сложное регулярное выражение, которое удивительно мощно. Я видел некоторые примеры этого, но ни один из них не мог быть поддержан простым смертным. Даже использование Expresso помогло так много; все еще было трудно понять и рискованно изменить. Поэтому, если вы не ученый с фиксацией на Grep, я бы не рекомендовал это направление.

Вместо этого сосредоточьтесь на грамматике и дайте compiler compiler сделать тяжелый подъем для вас.