0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ But there is no left recursion there, is there? $\endgroup$ – harold May 9 at 16:23
  • $\begingroup$ @harold isn't Sequence --> Instruction Sequence | Instruction left recursion? $\endgroup$ – user105075 May 9 at 18:35
  • $\begingroup$ But Instruction cannot be empty, so there is always some terminal before the recursion into an other Sequence. $\endgroup$ – harold May 9 at 18:43
  • $\begingroup$ Left recursion is, by definition, where the recursive non-terminal appears as the leftmost symbol in a replacement. Sequence -> Instruction Sequence is right recursion. $\endgroup$ – rici May 9 at 19:28
  • $\begingroup$ 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.) $\endgroup$ – rici May 9 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.