0
$\begingroup$

Request to vet the evaluation for given two grammars, handling arithmetic expressions, having two precedence classes of operators:

addop= {+,-}, mulop = {*,/},

such that:

precedence(mulop) > precedence (addop)

My intent to introduce this example was to show how the C compiler, uses the left-to-right associativity to process a smallish arithmetic expression, as shown below:

200+300+400-50*10/5*2

Also, wanted to show the same expression processed under right-to-left associativity. This was to give a suitable small (though irrelevant example, as the C compiler follows only left-to-right associativity for these four operators) example, as the C compiler also has many operators where right-to-left associativity is followed.

But, still have to search for good examples for those operators, as well as to search for different examples, for more levels of precedence , than just two; as the C-compiler has 15 levels of precedence. Hence, request for sources for the same too.

For the case of left-to-right associativity, have a small parsing grammar:

expr -> expr + term | exp - term | term
term -> term * factor | term / factor | factor
factor -> factor digit | digit
digit -> 0|1|2|...|9

This grammar is also fit for BUP (bottom-up parsing), as left recursion is not a problem for BUP.

Though not needed, but it gels in the class to state that, the C-compiler is based on BUP.

In the absence of latex skills, to draw binary trees; have shown the similar effect, by the order imposed by the enclosing parenthesis:

((200+300)+400)-(((50*10)/5)*2))
=> 900 - ((100)*2)
=> 700

Right-to-left associativity The corresponding grammar is:

expr -> term + expr | term - expr | term
term -> factor * term | factor / term | factor
factor -> digit factor | digit
digit -> 0|1|2|...|9

((200+(300+(400-((50*(10/(5*2)))))
=> ((200+(300+(400-((50)))
=> 850
Improve this question
$\endgroup$
9
  • $\begingroup$ Are we to read all this as coming from a CS student or teacher? $\endgroup$
    – Rushi
    Commented Aug 1, 2023 at 7:24
  • 1
    $\begingroup$ @Rusi I am a faculty, and done masters in CSE, from a prestigious govt. institute in India. $\endgroup$
    – jiten
    Commented Aug 1, 2023 at 7:43
  • $\begingroup$ Well that makes the question (more) on topic. But it's very confused — What u want to ask. Bottom up and top down parsing can both handle both precedence. Though with different convenience $\endgroup$
    – Rushi
    Commented Aug 1, 2023 at 7:45
  • 2
    $\begingroup$ I really can't make our what you're asking. There seems to be basic confusion between (1) (C) language, (2) specific compiler technology (eg yacc) and (3) general compiler knowhow ( eg the 'dragon book' of Aho Sethi Ullman) $\endgroup$
    – Rushi
    Commented Aug 3, 2023 at 7:19
  • 2
    $\begingroup$ And I suspect that if you clean up the question it will hardly be a CSE question but will fit better in CS or stackoverflow itself $\endgroup$
    – Rushi
    Commented Aug 3, 2023 at 7:20

1 Answer 1

Reset to default
1
$\begingroup$

the examples you gave are correctly parenthesized w.r.t. the associativity of the two grammars and the evaluation order is correct. Consequently, results are correct as well.

You can try this yourself employing GOLD Parser Builder (it is available for free), it is a simple but intuitive BUP compiler-compiler that let's you specify a grammar, parse some input string and see:

  1. the reduction order,
  2. the corresponding derivation tree.

Inspecting it, you will reach the same conclusion.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.