Грамматика БНФ и ассоциативность операторов - PullRequest
Новая
       43

Грамматика БНФ и ассоциативность операторов

1 голос
/ 01 ноября 2010

(Прежде всего, это не HW, у меня есть все ответы)

У меня есть простая грамматика BNF 

<UNIT> ::= ( <CLAUSE> ) | a | b | c
<ITEM> ::= not <UNIT> | <UNIT>
<CLAUSE> ::= <CLAUSE> and <PHRASE> | <PHRASE>
<PHRASE> ::= <ITEM> | <ITEM> or <PHRASE>

and оператор левый ассоциативный (левый)рекурсивный) or оператор является ассоциативным справа (на этот раз он является правосторонним рекурсивным)

При заданном выражении c and b or not a and ( not b or c ), почему наиболее правильно "и" выше в дереве разбора?
Кстати, я вижу, c **and** b or not a and ( not b or c ) самое левое должно быть выше в дереве разбора.

Наш профессор дал такой ответ:

Вот дерево разбора в неряшливой записи. 

(clause (clause (clause (phrase (item (unit 'c'))))
'and'
(phrase (item (unit 'b'))
'or'
(phrase (item 'not'
(unit 'a')))))
**'and'** // is higher in parse tree
(phrase (item (unit '('
(clause (phrase (item 'not’(unit 'b'))
'or'
(phrase (item (unit 'c')))))
')' ))))

1 Ответ

1 голос
/ 02 ноября 2010

Представленная грамматика BNF, похоже, соответствует дереву разбора и согласуется с утверждением, что «и» предполагается левоассоциативным. Если вы хотите создать «a и b и c» с использованием этой грамматики, начиная с «Clause», вы начинаете так:

  1. п
  2. Пункт и Фраза

В этот момент фраза не может стать "b и c" (без скобок), потому что только предложения могут производить "и". Фраза должна перерасти в «с», а предложение во второй строке может стать «а и б». Это заставит самые правые «и» быть выше в дереве разбора.

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

...