Хорошая грамматика для типа данных даты для анализатора рекурсивного спуска LL (1) - PullRequest
Новая
       49

Хорошая грамматика для типа данных даты для анализатора рекурсивного спуска LL (1)

1 голос
/ 17 марта 2010

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

Мое текущее решение - использовать метод рекурсивного спуска с грамматикой LL (1), чтобы даже программисты, не имеющие предыдущего опыта в оценке выражения, могли быстро узнать, как работает код.

Он должен обрабатывать смешанные выражения, состоящие из нескольких типов данных: десятичные числа, проценты, строки и даты. И даты в формате дд / мм / гггг легко спутать со строкой деления операций.

Где хорошее решение этой проблемы?

Мое собственное решение, которое нацелено на простоту синтаксического анализатора и включает в себя префикс даты с помощью специального символа, скажем, апостроф: 

<date>   ::= <apostr><digit><digit>/<digit><digit>/<digit><digit><digit><digit>

<apostr> ::= '

<digit>  ::= '0'..'9'

Ответы [ 3 ]

2 голосов
/ 17 марта 2010

LL-подобный синтаксический анализатор без лексеров с бесконечной перспективой - это то, что вам нужно. А именно, это ПЭГ.

http://en.wikipedia.org/wiki/Parsing_expression_grammar

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

2 голосов
/ 17 марта 2010

Во-первых, я фанат LL-парсеров, поэтому я от всей души одобряю ваш подход. Обратите внимание, что одним из новых популярных генераторов синтаксического анализатора ( ANTLR ) является LL. Если вы позволите себе больше смотреть вперед, вместо того, чтобы ограничивать себя LL (1), вы можете делать практически все, что вы когда-либо захотите сделать с парсером LR (1), но код будет намного более понятным, более надежным и легче отлаживать.

Я не знаю достаточно о вашей общей грамматике, чтобы сказать. Возможно, вам удастся спроектировать вещи так, чтобы анализатор LL всегда мог определить из контекста, является ли это целочисленным выражением или константой даты. Однако, если вы не можете, да, вам нужен какой-то способ, чтобы отличить. Единственное, о чем я могу думать, это использовать обратную косую черту в качестве разделителя вместо косой черты, но это довольно уродливо.

0 голосов
/ 17 марта 2010

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

  • добавление синтаксических ограничений для обеспечения однозначного и простого анализа
  • удаление / изменение синтаксиса, чтобы язык казался интуитивно понятным, «естественным» для целевой аудитории.

Удовлетворение второго требования намного сложнее, чем первое, и требует понимания

  • предполагаемые варианты использования языка
    Какой тип клавиатуры / устройства ввода доступен? Есть ли среди разрешенных символов какие-либо символы, которые трудно воспроизвести или увидеть на дисплее?
    Какие токены / выражения будут использоваться часто, что потребуется только изредка? Часто ли пользователи вводят короткие фрагменты специального кода или программы предназначены для повторного использования и изменения в течение длительных периодов времени
    ... и т. д.
  • фон / культура предполагаемой аудитории
    Какие общие практики / идиомы из других регулярных (и просто естественных) языков можно или нужно использовать повторно, если это возможно?
    Стоит ли отдавать предпочтение лаконичному, но загадочному стилю или более явному, но более многословному стилю?
    ... и т. д.

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

Использовать альтернативный формат для значений даты в целом ; такой, который был бы «естественным» для пользователей, но достаточно отличительным, чтобы его могла описать обычная грамматика.
Например, тот, который использует трехбуквенную аббревиатуру для месяца (нижняя сторона DSL становится привязанной к английскому или другому языку, но также имеет преимущество, двусмысленность для людей, которой является день, а который месяц, удаляется) Ориентировочно: 

  dd-mmm-yyyy    (may seem unnatural in cultures where the prevailing date order 
                  starts with the month maybe yyyy-mmm-dd then ?)
  mmm-dd-yyyy    (better for the above mentioned cultures)
  ddmmmyyyy      (avoid the dashes, but impose leading zeros)

  MnnDnnYyyyy    (using "M", "D" and "Y" (or others) as explicit prefixes; now, 
                  this is completely culture neutral, but maybe a bit awkward...)

В любом случае, просто идеи ... Применимость будет зависеть от упомянутых человеческих / культурных факторов, и с остальной частью синтаксиса. Например, приведенное выше может означать, что переменные должны быть явно помечены (это одна из причин, по которой многие языки используют префикс $, например), чтобы избежать возможного конфликта с [нечетными, но возможными] идентификаторами переменных.

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

...