Programming language grammars

1
votes

Lets say I have the following grammar

program = mul
mul = add {"*" add}
add = NUM {"+" NUM}

and the following input

1 + 2 * 3

now normally I would assume that that input would give 7, because of BIDMAS (do the multiplication first, then the addition), but after reading up on recursive descent parsers I am confused whether this would output

A.

(1 + 2) * 3 = 9

or B.

1 + (2 * 3) = 7

I want the parser to do B because that is how maths is generally done, so is the grammar I have created correct?

2
parsinggrammarabstract-syntax-tree

2 Answers

2
votes

Well, a parser won't do anything on its own, it will just produce an abstract syntax tree (AST). I believe to fully implement the mathematics order of operations you need to expand the grammar a bit. In that short example I'd expect it (unless I misunderstand this particular syntax) for it to throw an error, as you define two binary operations and pass three numbers. 1 + 2 * 3 + 4 seems like more sensible test input, and yes, it would work completely wrong (it would tell you you have an expression that consists of multiplication of two additions): mul(add(1,2),add(3,4))

An inverted example might work:

program = add
mul = NUM {"*" NUM}
add = mul {"+" mul}

I would expect it to parse 1 * 2 + 3 * 4 into add(mul(1,2),mul(3,4)). However, as you can see, I had to change the input, as again: you are expecting very rigid thing as an input.

Try to practice with some abstract grammars - creating specific patterns of "p" and "q" (or any other characters), to get more used to quite backward way of thinking required when working with parsers/lexers.

1
votes

I have now found that no, this is not the correct grammar. The grammar should be

program = add
add = mul {"+" mul}
mul = NUM {"*" NUM}

this way it will always add together multiplications, not multiply additions.