Альтернативы Stateful Parsing

Question

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

Позвольте мне проиллюстрировать это на примере.Допустим, я анализирую текстовый файл (в данном случае YAML, но это может быть обычный текст или XML. Я делаю простую игру викторины; моя игра будет содержать set s question s, каждый сдва или более answer с. В YAML я мог бы структурировать свой файл следующим образом:

set:
  name: math questions
  question:
    text: 1 + 1 = ?
      answer: 3
      answer: 4
      best-answer: 2
  question:
    text: 2 * 3 = ?
      answer: 5
      best-answer: 6
set:
  name: chemistry questions
  question:
    text: the valence of a Chlorine free radical is?
      answer: 1
      answer: 0
      best-answer: -1
  question:
    text: Xeon is a noble gas
      best-answer: true
      answer: false

(Я некоторое время не использовал YAML, извиняюсь, если это псевдо-YAML.) Когда япарсинг, если я читаю текущую строку и вижу «ответ: ...», я должен знать, что я отвечаю на вопрос о множестве.

Это, как правило, очень сложный код,например:

if (currentLine starts with "answer")
  currentQuestion.addAnswer(...)
else if (currentLine starts with "question")
  currentQuestion = new question
...

В любой точке синтаксического анализа нам нужна ссылка на текущий объект, который может быть вложен в несколько других объектов.

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

Итак, еще раз, мой вопрос: существует ли способ анализа данных без сохранения состояния? У меня такое ощущение, что подходВозможно, существуют более понятные и легкие для чтения / понимания / кодирования, чем мои обычные циклы for для всех строк текста.

Answer 1

Вы, очевидно, ищете не «синтаксический анализ», а необязательный, чисто функциональный анализ.Конечно, всегда есть своего рода состояние, но при функциональном подходе ваше состояние полностью неявно.

Взгляните на «Функциональные жемчужины: монадический анализ в Haskell» article,Изучите различные Parsec-подобные библиотеки комбинаторов синтаксического анализа, которые существуют даже для таких крайне необходимых языков, как Java и C ++.

Answer 2

То, что вы описываете, является более или менее подходом, основанным на использовании конечного автомата: вы перебираете строки файла, а переменная состояния отслеживает, где вы находитесь в дереве разбора.Возможно, вам будет проще и проще использовать рекурсивный анализ спуска , в котором большая часть состояния неявна, в форме стека программы.Как отмечают другие, синтаксический анализ по своей сути является состоянием, но рекурсивный спуск позволяет явно сохранять меньше состояний.

Answer 3

Сама концепция синтаксического анализа подразумевает, что некоторые фигуры являются одним типом токена, другие - другим, а другие вообще недействительны.Как вы узнаете, что, не поддерживая какое-то состояние, которое говорит: «Хорошо, я сейчас анализирую foo ... это то, что я должен был иметь здесь»?

Answer 4

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

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

Существует причина, по которой вводный курс по компиляторам начинается с конечных автоматов.