0

This is an arithmetic expression for my language: ADD 100 MUL 5 DIV 10 SUB 7 MOD 10 4

Where ADD = addition, SUB = subtraction, MUL = multiplication, DIV = division, MOD = modulo.

The expression above can also be rewitten into the standard 100 + (5 * (10 / (7 - (10 % 4)))), parenthesis included to mark the order of operations.

This is quite different than the standard because evaluation starts with the right most operation, that is MOD 10 4, then the result of that is then used to evaluate the next operation, that is SUB 7 2, where 2 is the result of the modulo operation. Parenthesis is not required for this grammar.

I have gotten hold the grammar for the standard notation from https://ruslanspivak.com/lsbasi-part6/, here it is:

 <expr> := <term> ((ADD|SUB) <term>)*
 <term> := <factor> ((MUL|DIV|MOD) <factor>)*
 <factor> := integer

In my language, I am clueless in writing the grammar for arithmetic operations. Are modifications needed for the grammar above? Or do I need to write a completely new grammar?

Jeano Ermitaño
  • 169
  • 3
  • 17
  • Writing a grammar is just like writing a program. You propose some code/grammar fragment, you decide if it does what you expect, and if not, change it until it does. If you understand grammars, this shouldn't be hard. If you don't, the experience will help you understand them. What have you tried to do to write your own grammar or test that this one is OK? – Ira Baxter Oct 30 '16 at 10:59
  • I have successfully written the methods and code to parse a standard arithmetic expression (+, -, *, /, %) like what the guide did, I just converted the Python code to C#. I have also successfully parsed a single operation using my language by modifying the grammar in the guide to ` := (ADD|SUB) `, but I'm stuck at solving how to parse an expression with multiple operations. – Jeano Ermitaño Oct 30 '16 at 12:14

1 Answers1

-1

I managed to solve this by analyzing the execution of each production in my code. To my surprise, I forgot to include an <expr> production in <factor>. Changing my code a bit my moving certain conditions and I was able to parse the sample expression above. This is the grammar for the arithmetic expression in my language:

<expr> := ((ADD|SUB) <term> <term>)* | <term>
<term> := ((MUL|DIV|MOD) <factor> <factor>)* | <factor>
<factor> := INTEGER | <expr>

The <expr> production in <factor> makes it possible to have multiple operations because it goes back to the start to parse the next operation.

Jeano Ermitaño
  • 169
  • 3
  • 17
  • 1
    This actually works? It looks to me like it can infinitely expand expr to term to factor to expr ... I think you have some more work to do. – Ira Baxter Oct 30 '16 at 15:47
  • I generated a parse tree using [ironcreek.net](http://ironcreek.net/phpsyntaxtree/) with the phrase in bracket notation: `[ [ADD][ [ 100]][ [MUL][ 5][ [ [ [DIV][ 10][ [ [SUB][ [ 7]][ [MOD][ 10][ 4]]]]]]]]]` as far as I know, grammar is correct. What makes you think otherwise? – Jeano Ermitaño Oct 31 '16 at 08:31
  • You didn't "generate" a parse tree; it appears you invented one out your imagination and simply wrote it down. Inventing an answer isn't a way to test a parser. Build a real parser with your grammar and use that to build a parse tree. You'll find your grammar has errors. (See that "1" on my comment? That means somebody else agrees with me). Either use a real parser generator (ANTLR will do) or hand write a recursive descent parser (see http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769). – Ira Baxter Oct 31 '16 at 10:35
  • I am indeed writing an RDP in C# for this and the grammar checks out. It parsed the expression correctly and returned the result. Please point out the errors in my grammar. – Jeano Ermitaño Oct 31 '16 at 10:52
  • I did. Read my comment carefully. – Ira Baxter Oct 31 '16 at 13:27