BNF грамматическая ассоциативность - PullRequest
Новая
       85

BNF грамматическая ассоциативность

0 голосов
/ 16 мая 2018

Я пытаюсь понять, как работают левая и правая ассоциативные грамматики, и мне нужна небольшая помощь.Поэтому я решил привести пример и попросить разъяснений.По сути, я хочу создать грамматику для двух логических операций: and + implication.Я хочу сделать так, чтобы and оставалось ассоциативным, а implication - ассоциативным справа.Это то, что я получил до сих пор.Это правильно?Я чувствую, что это может быть неоднозначным.(Я также учел, что and имеет более высокий приоритет, чем implication) 

<exp> := <and>
<and> := <impl> | <and> ^ <impl>
<impl> := <term> | <term> -> <impl>
<term> := (<exp>) | <bool>
<bool> := true | false

1 Ответ

0 голосов
/ 17 мая 2018

Из моих ограниченных знаний мне кажется, что вы перевернули прецеденты.

На уровне грамматики левый ассоциативный оператор имеет следующий формат: 

exp = exp op other | other

... и правый ассоциативный оператор будет иметь следующий формат: 

exp = other op exp | other

Как вы можете видеть, это зависит от того, как вы используете рекурсию: левая ассоциативность будет использовать левое рекурсивное правило, а правая ассоциативность будет использовать правое рекурсивное.

Как и в случае приоритета, чем позже правило находится вграмматика, тем выше ее приоритет.В приведенной ниже грамматике, где opL представляет левый ассоциативный оператор, а opR представляет правый ассоциативный оператор, exp0 имеет меньший приоритет, чем exp1, который имеет меньший приоритет, чем other: 

exp0 = exp0 opL exp1 | exp1
exp1 = other opR exp1 | other
other = ...

Например, если opL это "+", а opR это "**" и other это буква, посмотрите, как будет построено дерево разбора для нескольких выражений:

  • Ассоциативность слева: 

    a + b + c -> (a + b) + c
exp0 -+-> exp0 +-> exp0 --> exp1 --> other --> a
      |        |
      |        +-> opL --> "+"
      |        |
      |        \-> exp1 --> other --> b
      |
      +-> opL --> "+"
      |
      \-> exp1 --> c

  • Ассоциативность справа: 

      a ** b ** c -> a ** (b ** c)
  exp0 --> exp1 +-> other --> a
                |
                +-> opR --> "**"
                |
                \-> exp1 +-> other --> b
                         |
                         +-> opR --> "**"
                         |
                         \-> exp1 --> other --> c

  • Старшинство: 

    a + b ** c -> a + (b ** c)
exp0 +-> exp0 +-> exp1 --> other --> a
     |
     +-> opL --> "+"
     | 
     \-> exp1 +-> other --> b
              |
              +-> opR --> "**"
              |
              \-> exp1 --> other --> c
...