A rigorous definition of the intuitive concept of the PEMDAS language.

Question

I apologize if this question is similar to a previous question, but I didn't get an answer and it is still bothering me. Suppose our alphabet is a countably infinite set of variables $VAR$, well-ordered by the natural numbers, along with the symbols $\{+,*,-,div,(,)\}$. $($ and $)$ are parentheses, and $+$, $*$, $-$, $div$ represent addition, multiplication, subtraction, and division, respectively. I want to know how to rigorously define the PEMDAS language, where parenthesis is done first, exponentiation is done second, multiplication and division have equal precedence and are done from left to right, and addition and subtraction have equal precedence and are done from left to right, and also where superfluous parentheses are eliminated. So, for instance, $(x_0*x_1)+x_2$ would not be allowed. Also, since this is a purely formal language, we allow terms like $x_0 div (x_0 - x_0)$. In other words, terms that denote division by zero are allowed. Is there some book where this language is explained?

Answer 1

If I understand you correctly, you want to define a language where parentheses that could be omitted without changing the abstract parse tree are not allowed.

You could do something like this:

$$\begin{align} S \to{} & E_3 \mid E_2 \mid E_1 \\ E_3 \to{} & L_3 + R_3 \mid L_3 - R_3 \\ L_3 \to{} & E_3 \mid E_2 \mid E_1 \\ R_3 \to{} & (\;E_3\;) \mid E_2 \mid E_1 \\ E_2 \to{} & L_2 * R_2 \mid L_2 \mathbin{\tt div} R_2 \\ L_2 \to{} & (\;E_3\;) \mid E_2 \mid E_1 \\ R_2 \to{} & (\;E_3\;) \mid (\;E_2\;) \mid E_1 \\ E_1 \to{} & \mathtt{x}_0 \mid \mathtt{x}_1 \mid \mathtt{x}_2 \mid \cdots \end{align} $$

Some optimizations are obviously possible here, but the principle should be clear.