Оператор Ассоциативность

Question

У меня есть следующее выражение EBNF грамматику:

<expr> -> <term> { (+|-) <term> } 
<term> -> <factor> { (*|/|%) <factor> } 
<factor> -> <pow> { ** <pow> } 
<pow>  -> (<expr>) | <id> 
<id>  -> A | B | C 

мне нужно, чтобы определить, если грамматика навязывает какую-либо конкретную ассоциативность для своих операторов, или если бы реализовать в коде парсера. Из того, что я прочитал до сих пор, похоже, что это не так, но мне трудно понять, что вызывает ассоциативность. Любая помощь была бы очень восприимчивой!

Answer 1

Стандартного преобразование, которое уродует преобразует грамматику выражения в форму, которая может быть разобранной с сверху вниз (LL) грамматикой уже удалена информацией ассоциативности, потому что грамматика LL не может справиться с левым ассоциативным operatord. По сути, дерево разбора индуцируется грамматикой LL, что делает все биари-операторы право-ассоциативными. Однако вы можете вообще связать операторов без особых проблем в семантическом действии.

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

В грамматике LR, это было бы очевидно:

<expr> -> <term> | <expr> + <term> | <expr> - <term> 
<term> -> <factor> | <term> * <factor> | <term>/<factor> | <term> % <factor> 
<factor> -> <pow> | <pow> ** <factor> 
<pow> -> (<expr>) | <id> 
<id>  -> A | B | C 

В приведенном выше грамматике, оператор лево-ассоциативным, если производство лево-рекурсивным (так как оператор может происходить только как часть без терминала слева от оператора). Аналогичным образом, по той же причине правый ассоциативный оператор имеет право-рекурсивное правило.