For the following grammar, how can I include both precedence and associativity of operators:

S -> S|S

S -> S.S

S -> S*

S -> (S)

S -> a|b

Note: In the first rule S -> S|S, the symbol | is the OR symbol and not two rules.

Here, operators are |, ., * and ().

PS: Suppose the precedence order is : () > * > . > |. And all are left associative.

  • 1
    $\begingroup$ But you did not tell us what precendence and associativity you want. $\endgroup$ – Andrej Bauer Feb 15 '20 at 18:56
  • $\begingroup$ Suppose the precedence order is : () > * > . > |. And all are left associative. $\endgroup$ – Ravi Kumar Feb 15 '20 at 20:03
  • 1
    $\begingroup$ Why don't you give it a try? Consult any algebraic grammar for reference. See, for example, users.monash.edu/~lloyd/tildeProgLang/Grammar/Arith-Exp or pages.cs.wisc.edu/~fischer/cs536.s08/course.hold/html/NOTES/… (Google search found me at least dozens of study guides; I chose those two because they were on the first page of results and not PDFs). $\endgroup$ – rici Feb 15 '20 at 20:37
  • $\begingroup$ You mention "compilers", there the task of managing precedence/associativity is normally handled by the parser generator (bison, ply come with detailed examples, there are many others), or if the parser is hand-written, a technique like Hanson's "Compact recursive-descent parsing of expressions" is used instead. $\endgroup$ – vonbrand Feb 29 '20 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.