Как определить, нужны ли скобки или нет? - PullRequest
Новая
       14

Как определить, нужны ли скобки или нет?

0 голосов
/ 03 декабря 2018

Я написал синтаксический анализатор в Haskell, который анализирует формулы в виде строковых входных данных и создает тип Haskell data, определенный в BNF ниже. 

formula ::=  true  
         |  false  
         |  var  
         |  formula & formula  
         |  ∀ var . formula
         |  (formula)

    var ::=  letter { letter | digit }*

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

Например, учитывая формулу ∀ X . (X & Y) & (∀ Y . Y) & false, которая при разборе создает структуру данных 

And (And (Forall "X" (And (Var "X") (Var "Y"))) (Forall "Y" (Var "Y"))) False

, у нас есть 

   Too little parentheses:    ∀ X . X & Y & ∀ Y . Y & false
   Too much parentheses:      (∀ X . (((X) & (Y)))) & (∀ Y . (Y)) & (false)
   Just right:                ∀ X . (X & Y) & (∀ Y . Y) & false

Есть ли способ определить, сколько скобок необходимо, чтобы семантика никогда не была неоднозначной?Я ценю любые отзывы.

1 Ответ

0 голосов
/ 03 декабря 2018

Неопробованный псевдокод: 

instance Show Formula where
   showsPrec _p True  = "True"
   showsPrec _p False = "False"
   showsPrec p (And f1 f2) = showParen (p > 5) $
      showsPrec 5 f1 . (" & " ++) . showsPrec 5 f2
   showsPrec p (Forall x f) = showParen (p > 8) $
      ("forall " ++ x ++) . showsPrec 8 f
   ...

(я, вероятно, должен использовать showString вместо тех, что ++ выше. Я думаю, это должно работать в любом случае.)

Выше целое числоp представляет приоритет контекста, в котором мы показываем текущую формулу.Например, если мы показываем f внутри f & ..., тогда p будет иметь уровень приоритета &.

Если нам нужно напечатать символ в контексте, который имеет более высокий приоритет, мынужно добавить скобки.Например, если f равно a | b, мы не можем написать a | b & ..., в противном случае оно интерпретируется как a | (b & ...).Нам нужно поставить круглые скобки вокруг a | b.Это делается с помощью showParen (p > ...).

Когда мы выполняем рекурсию, мы передаем уровень приоритета имеющегося символа в подтермы.

Выше я выбирал уровни приоритета случайным образом.Вы должны настроить их по своему вкусу.Вам также следует убедиться, что выбранные вами уровни соответствуют стандартным библиотекам.Например, печать Just someFormula не должна генерировать такие вещи, как Just a & b, а добавлять скобки.

...