Пешт не разбирает рекурсивную грамматику, как я ожидал - PullRequest
Новая
       58

Пешт не разбирает рекурсивную грамматику, как я ожидал

0 голосов
/ 25 июня 2019

Я использую ящик pest для реализации рекурсивной грамматики в Rust: 

id = _{ ASCII_ALPHA_LOWER ~ (ASCII_ALPHANUMERIC|"_")* }
integer = _{ (ASCII_NONZERO_DIGIT ~ ASCII_DIGIT*)|"0" }
real = _{ ((integer ~ "." ~ ASCII_DIGIT*) | (integer? ~ "." ~ ASCII_DIGIT+)) ~ (("e"|"E") ~ ("-"|"+")? ~ ASCII_DIGIT+)? }

unaryop = _{ "sin"|"cos"|"tan"|"exp"|"ln"|"sqrt" }

inner_exp = _{ real|integer|"pi"|id }

exp = { SOI ~ ( inner_exp | (exp ~ ( "+"|"-"|"*"|"/"|"^" ) ~ inner_exp) | ("-" ~ exp) | ("(" ~ exp ~ ")") | (unaryop ~ "(" ~ exp ~ ")") ) ~ EOI }

Однако я обнаружил, что вредитель не разбирает грамматику, как я ожидал. Например, 2+3 дает мне ошибку: 

 --> 1:2
  |
1 | 2+3
  |  ^---
  |
  = expected EOI

Похоже, что выбор inner_exp анализируется, а затем, когда встречается символ +, анализатор не знает, что делать. Я почти уверен, что есть проблема с тем, как я написал выбор exp ~ ( "+"|"-"|"*"|"/"|"^" ) ~ inner_exp, но я не уверен, что именно является причиной проблемы. Если я заменю этот выбор на exp ~ ( "+"|"-"|"*"|"/"|"^" ) ~ exp, я получу ошибку, утверждающую, что выражение является леворекурсивным. Как мне исправить эту грамматику?

1 Ответ

1 голос
/ 25 июня 2019

Оператор выбора в PEG упорядочен и работает следующим образом: Дано e = {alt1 | alt2}:

  • Если alt1 может быть успешно сопоставлено, применяется alt1 и alt2 никогда не пробуется.
  • В противном случае alt2 соответствует
  • Если alt2 не может совпадать, e не может совпадать

Теперь e = {e1 ~ e2} работает следующим образом:

  • Если e1 можно сопоставить и e2 можно сопоставить после него, то оба сопоставляются последовательно.
  • В противном случае e не соответствует.

Так что если у вас что-то вроде e = {(e1 | e2) ~ e3}, произойдет следующее:

  • Если e1 может быть сопоставлено:
    • Если e3 можно сопоставить после e1, то оба сопоставляются последовательно
    • В противном случае e не соответствует
  • Если e1 не соответствует, но e2 может быть найдено:
    • Если e3 можно сопоставить после e2, то оба сопоставляются последовательно
    • В противном случае e не соответствует

Примечательно, что если e1 завершается успешно, а e3 завершается неудачей, он не возвращается и пытается вместо этого сопоставить e2. Таким образом, если и e1, и e2 могут дать совпадение, но только e2 позволяет сопоставить e3 впоследствии, (e1 | e2) ~ e3 завершится неудачей, тогда как (e1 ~ e3) | (e2 ~ e3) будет успешным.

Итак, в вашей грамматике у вас есть (inner_exp | ...) ~ EOI. Теперь для вашего ввода inner_exp выдает совпадение, поэтому в соответствии с приведенными выше правилами другие альтернативы никогда не пробуются, и он пытается сопоставить EOI дальше. EOI не совпадает, поэтому все правило не выполняется, и вы получаете синтаксическую ошибку, которую получаете.

Это объясняет синтаксическую ошибку, но это не единственная проблема вашей грамматики:

Ваше правило exp является рекурсивным, но оно привязывается с помощью SOI и EOI, поэтому оно никогда не может совпадать ни с чем, кроме всего ввода. Это означает, что рекурсивные вызовы обязательно всегда будут неудачными. Чтобы это исправить, вы должны удалить SOI и EOI из определения exp и вместо этого иметь почтовое правило вроде start = {SOI ~ exp ~ EOI}.

Как только вы это сделаете, вы получите сообщение об ошибке, что ваше правило exp теперь является леворекурсивным, что вредный организм не поддерживает. Чтобы исправить это, вы можете заменить левую рекурсию повторением, как показано здесь (заменив альтернативы inner_exp и exp ~ (...) ~ inner_exp), где operand - это правило, которое соответствует конструкциям, отличным от операций инфикса: 

operand ~ (( "+"|"-"|"*"|"/"|"^") ~ operand)*

Между прочим, это также исправит вашу текущую проблему, потому что у вас больше нет альтернативы inner_exp, которая была опробована до альтернативы для выражений инфикса.

Ваша последняя проблема заключается в том, что вы вообще не учитываете приоритет оператора. Это можно исправить, введя дополнительные «уровни» выражений в дополнение к inner_exp и exp, чтобы в одном правиле определялись только операторы с одинаковым приоритетом, а затем каждое правило вызывает правило, содержащее следующий более высокий приоритет. разобрать операнды. Это будет выглядеть так: 

exp = { summand ~ (("+" | "-") ~ summand)* }
summand = { factor ~ (("*" | "/" | "%") ~ factor)* }
factor = { unary ~ ("^" ~ unary)* }
unary = { "-" ~ unary | unaryop ~ "(" ~ exp ~ ")" | primary }
primary = { "(" ~ exp ~ ")" | real | integer | "pi" | id }
...