How to follow C++ grammar for a calculator by hand?

user_10413233 0
Viewed 752

I'm following PPP using C++ by Bjarne Stroustrup and I'm having difficulty following along with his introductory grammar for a calculator (pg 189-192) as follows:

// a simple expression grammar
Expression:
    Term
    Expression "+" Term // addition
    Expression "-" Term // subtraction

Term:
    Primary
    Term "*" Primary // multiplication
    Term "/" Primary // division
    Term "%" Primary // remainder (modulo)

Primary:
    Number
    "(" Expression ")"

Number:
    floating-point-literal

Firstly we parse 2, which is a floating-point-literal which is a Number which is a Primary which is a Term which is an Expression. Diagram

Then we go to parse 2 + 3 Diagram:

2 is a floating-point-literal which is a Number which is a Primary which is a Term which is an Expression

  • Jumps straight to Expression (this is where I start getting lost)

3 is a floating-point-literal which is a Number which is a Primary which is a Term. Why does the book stop parsing here, "3" currently fits all the criteria to be an Expression?

When I try to perform this action by hand, I can only come to a conclusion that matches the given diagram when I ignore the "+" and parse 3 to Term to match the requirement Expression "+" Term.

Furthermore, if I try and extrapolate further to parse 9 + 3 * 2, without looking ahead for a * I cannot finish working through the grammar, as 9+3 is (apparently) a valid expression which has no grammar to be multiplied...

c++
2 Answers

I guess the main issue you are having has to do with the fact that you are reading it from bottom to top. The arrows in the book are meant to denote information flow, but not parsing order.

Here is the grammar we are interested in (for reference):

Expression:
    Term
    Expression "+" Term
    Expression "-" Term

Term:
    Primary
    Term "*" Primary
    Term "/" Primary
    Term "%" Primary

Primary:
    Number
    "(" Expression ")"

Number:
    floating-point-literal

The following paragraphs try to give an overview of the parsing process in the case of this grammar, as well as in a more general setting.

Parsing expressions: a simple example

The above grammar gives the rules needed to parse an Expression. Expression is said to be an axiom of the grammar. This means that in order to parse any given expression, we have to start with the Expression rule.

Let us consider the expression 2 + 3. The parsing process goes as follows:

  1. We match 2 + 3 against the rules for Expression. It has to be either a Term, an expression of the form Expression "+" Term or an expression of the form Expression "-" Term. It turns out it is an Expression "+" Term.
  2. We match the left-hand side of 2 + 3 with Expression.
    • The only possible rule for 2 is Term.
    • We then match 2 against the rules for Term. 2 does not contain "*", nor "/", nor "%". It therefore has to be a Primary.
    • We proceed with the rules for Primary. As it does not contain any parenthesis, 2 has to be a Number.
    • Finally, we have that 2 is a floating-point-literal.
  3. We match the right-hand side of 2 + 3 with Term.
    • As for 2, 3 has to be a Primary.
    • Again, following the same path as above, 3 is deduced to be a Number and then a floating-point-literal.

Finally, 2 + 3 is an expression of the form floating-point-literal "+" floating-point-literal.

Parsing expressions: complex expressions

We now know how to parse a simple expression. But what about a more complicated one, like (2 - 1) + 9 * 3? The techniques described above also apply in this case. Here is an unrolled version of the parsing process:

  1. (2 - 1) + 9 * 3 is of the form Expression "+" Term.
  2. We match the left-hand side with the rules for Expression.
    • (2 - 1) is a Term (as it does not contain "+" nor "-").
    • Similarly, (2 - 1) is a Primary.
    • (2 - 1) is of the form "(" Expression ")". By using the exact same process as for 2 + 3, we end up with "(" floating-point-literal "-" floating-point-literal ")".
  3. We match the right-hand side with the rules for Term.
    • 9 * 3 is of the form Term "*" Primary.
    • We match 9 against the rules for Term and we go on until we get a floating-point-literal.
    • We match 3 against the rules of Primary and also get a floating-point-literal after some refinement.
    • Finally, 9 * 3 is of a Term of the form floating-point-literal "*" floating-point-literal.
  4. In the end, (2 - 1) + 9 * 3 reduces to "(" fp - fp ")" "+" fp "*" fp.
user_66741260

You are right that 3 would be an expression, but then "expression + expression" wouldn't make sense. Seeing the "+" token, we only have one option how to interpret what's on the left and on the right of it:

Expression "+" Term

So we keep promoting both 2 and 3 until the leftmost becomes an Expression and the rightmost a Term.

The diagram on the right is arguably somewhat confusing. You might be better off reading it from top to bottom, rather than the other way round. Then you could make the following sense of it:

  1. We're trying to parse an Expression, that's the starting point.
  2. We find a candidate formed as 'Expression "+" Term'.
  3. What (out of the three options) is the Expression on the left? It's a Term. What's that Term? It's a Primary. (Again, not a 'Term "*" Primary' or any of the other options.) What's that Primary? It's a Number. What Number? A floating-point-literal 2.
  4. The + symbol in the middle requires no further investigation, it fits the pattern as it is.
  5. What's the Term on the right of the 'Expression "+" Term'? Continue as in 2.
user_15379250
Related