# Creating a grammar for a a language for instructions, with repititions

I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0]

The instructions

DOWN 1 UP 10 LEFT 5 RIGHT 1


means you will move to coordinate [9,-4].

There is also the REP command which means you perform the instructions inside the REP X times.

For example

REP 2 "DOWN 1 FORWARD 10 LEFT 5 RIGHT 1"


means you will move to coordinate [18,-8].

I came up with this grammar

Instruction --> DOWN Num | UP Num | LEFT Num | Right Num | REP Num " Sequence "

Sequence --> Instruction Sequence | Instruction


Which works to some extent. However I want to be able to parse the grammar using recursive descent and if I am not not mistaken you can't do that with grammars that use left recursion.

Any ideas on how I could alter my grammar to make it suitable for recursive descent?

• But there is no left recursion there, is there? – harold May 9 at 16:23
• @harold isn't Sequence --> Instruction Sequence | Instruction left recursion? – user105075 May 9 at 18:35
• But Instruction cannot be empty, so there is always some terminal before the recursion into an other Sequence. – harold May 9 at 18:43
• Left recursion is, by definition, where the recursive non-terminal appears as the leftmost symbol in a replacement. Sequence -> Instruction Sequence is right recursion. – rici May 9 at 19:28
• A bigger problem for parsing will be the difficulty of knowing whether a " starts or ends a repetition, assuming that repetitions can be nested. (And if they can't be nested, then your grammar is incorrect.) – rici May 9 at 19:29