Грамматика для языка выражения - PullRequest
Новая
       14

Грамматика для языка выражения

0 голосов
/ 26 марта 2020

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

  • A = 3
  • A <5 OR B> C
  • A = null ИЛИ (B = 3 И C = false)

И затем создать Mon go выражение запроса. Если бы была такая библиотека, она бы мне очень помогла. Тем временем я начал с написания своего собственного парсера. Я нашел Ома. js, который выглядит легко, и у него есть онлайн-редактор. Мне удалось туда попасть: 

Query {
  exp = simpleExp | andExp | orExp
  simpleExp = identifierName operator literal
  andExp = simpleExp "AND" simpleExp
  orExp = simpleExp " OR " simpleExp
  identifierName = identifierStart identifierPart*
  identifierStart = letter
  identifierPart =  letter | digit
  nullLiteral = "null"
  booleanLiteral = ("true" | "false")
  decimalLiteral = digit*
  stringLiteral = "\"" digit* "\""
  literal = stringLiteral | decimalLiteral | booleanLiteral | nullLiteral
  operator = "=" | "<" | ">" | ">=" | "<="  
}

Онлайн-редактор принимает тривиальные выражения (A = 3), но не соответствует объединенным выражениям AND / OR. Где моя ошибка? Кстати, я не настаиваю на этой библиотеке, я могу принять и другие парсеры .

1 Ответ

1 голос
/ 26 марта 2020

Две вещи не позволяют вашему правилу exp соответствовать входным данным A=2 AND B=3.

Чтобы лучше понять их, было бы неплохо прочитать документацию Ома, такую ​​как она есть; в частности, синтаксическая ссылка .

Во-первых, правило exp является "лексическим правилом", в терминах Ома, потому что его имя начинается со строчной буквы. Существует только небольшая разница между syntacti c и лексическими правилами , но здесь все имеет значение:

Разница между лексическими и синтаксическими c правилами заключается в том, что syntacti c правила неявно пропускают пробельные символы.

Поскольку ни одно из ваших правил не является синтаксическим c, пробел не игнорируется. Но это также не распознается, за исключением некоторого странного " OR " токена. В частности, пробел до AND не может быть распознан грамматикой, поэтому синтаксический анализ в этой точке не выполняется.

Поэтому первым шагом является изменение simpleExp, andExp и orExp на syntacti c правил, переименовывая их SimpleExp, AndExp и OrExp, соответственно. Затем вы можете изменить " OR " на "OR", если хотите.

Вторая проблема не так проста. Чтобы решить эту проблему, было бы полезно взглянуть на модель, использованную в примере Ohm c грамматика . (Помните, что грамматика просто связана с организацией символов; значение символа рассматривается в другом месте. Поэтому грамматика для логических выражений с использованием операторов AND и OR отличается от грамматики арифметических c с использованием операторов * и + только в том, как пишутся операторы. Способ, которым синтаксис языка арифметики c определяет, что * имеет приоритет над +, точно такой же, как способ, которым булева грамматика определила бы, что AND имеет приоритет над OR. Но это не так, как организована ваша грамматика.

В частности, вы недовольны ключевым аспектом синтаксических анализаторов PEG (например, Ома), который также упоминается в Документация Ом . Чередование (оператор |) в формализме PEG упорядочено : ( выделение добавлено ) 

expr1 | expr2

Соответствует выражению expr1 и , если это не удается , соответствует выражению expr2.

Другими словами, если expr1 соответствует, expr2 никогда не предпринимается.

Имея это в виду, рассмотрите правило:

exp = simpleExp | andExp | orExp

Поскольку оба andExp и orExp начинаются с simpleExp, ни один из них не может быть сопоставлен. Для того, чтобы они соответствовали, simpleExp должен был бы соответствовать, и если simpleExp соответствует, чередование завершается немедленно, не пытаясь найти другие альтернативы. (Многие системы синтаксического анализа PEG используют / в качестве имени оператора чередования, а не |, используемого в контекстно-свободных грамматиках, чтобы избежать путаницы в семантике двух операторов. Но Ом решил этого не делать.)

На самом деле пример грамматики Ома не совсем идеален; он страдает от обычной проблемы с синтаксическим анализом «сверху вниз» (совместно с анализом PEG), который не может обрабатывать леворекурсивные грамматики. В результате язык, описанный в примере грамматики, делает умножение и сложение правоассоциативным. Для умножения и сложения это не проблема; (a*b)*c математически совпадает с a*(b*c). Но это будет иметь большое значение для деления и вычитания, поскольку (a-b)-c равно , а не то же самое, что a-(b-c) (если c не равно 0).

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

Exp = AndExp ("OR" AndExp)*
AndExp = SimpleExp ("AND" SimpleExp)*
SimpleExp = identifierName operator literal | "(" Exp ")"
...