Search code examples
parsingdata-structurescompiler-constructionpostfix-notationinfix-notation

Why does a compiler have trouble parsing infix expressions compared to postfix expressions?


I was reading compiler design book and it said "compilers have problem solving infix expression because it has trouble with determining the priority of operands and you should always convert it to postfix then parse the expression" .

Why does a compiler have trouble parsing infix expressions compared to postfix expressions?


Solution

  • Consider a + b * c / d e. According to conventional precedence rules, this should be parsed as a + ((b * c) / d). Simply reading from right to left would yield ((a + b) * c)/d, which is not what you want. The compiler needs to know the precendence (and associativity) of every operator and take them into account.

    On the other hand, postfix expressions have explicit precedence. For example, the first expression above is equivalent to b c * d / a +.

    Not sure if I know what the author is getting at with "should always convert it to postfix then parse the expression", but that is the gist. (seems to me that converting to postfix requires parsing already).