How to define a function for a recursive loop command in Python by using LEX and YACC?

Question

I'm trying to define a specific grammar for commands shown down below:

• F n (go forward n units)
• R n (turn right n degrees)
• L n [ … ] (repeat commands inside parenthesis n times)
• COLOR f (f = line color and colors are: K: red, Y: green, M: blue, S: black) (defines color of the line)
• PEN n (n = line thickness) (1: thin, 2: medium, 3: thick) (defines thickness of the line)

Here is an example command:

L 36 [L 4 [F 100 R 90] R 10] 

Output:

Here is the grammar I defined:

<start> ::= <function> | <option> 
<function> ::= <forward> | <right> | <loop> | <color> | <pen>
<option> ::= <function> <start> | ε
<forward> ::= F <numbers> 
<right> ::= R <numbers>
<loop> ::= L <numbers> [ <start> ]
<color> ::= COLOR <colors>
<pen> ::= PEN <numbers>
<colors> ::= M | K | S | Y

I tried to call start non-terminal in _loop function I defined:

def p_loop(p):
    'loop : LOOP NUMBER LSQB grammar RSQB'
    
    p[0]=loop_(p[2])

def loop_(x):
    i=1
    while i<=x:
        p_grammar(p)
        i=i+1

And it did'nt work.

Then, I tried this:

def p_loop(p):
    'loop : LOOP NUMBER LSQB start RSQB '
    i=1
    while i<=p[2]:
        p[0]=p[4]

def p_start(p):
    '''start : function 
             | option'''
    p[0]=p[1]

def p_function(p):
    '''
    function : forward
             | right
             | loop
             | color
             | pen
    '''
    p[0]=p[1] 

It didn't work properly too. I cannot find another solution. So, how can I define a function for the L command?

Here are project codes if you want to check.

Answer 1

You need to distinguish between two different concepts: parsing (or compilation) and evaluation (or execution).

Parsing takes as input a textual representation of a program and produces a data object more suitable for repeated evaluation. Evaluation takes the object produced by the parser and uses it to run the program -- in this case, to draw a picture.

Except in very simple cases (such as calculators which have no loops or conditionals), these two procedures are separated, both in time and in logic. First, you use one program (or function) to parse the input and create the executable; then you set the parser aside and use a completely different program (or function) to evaluate the result.

It should be clear from thinking about how loops work. By definition, a loop is executed several times. But it is only parsed once. So how could it be executed during the parse?

One way, of course, would be to parse the body of the loop over and over again. Some scripting languages do that. But it requires a very different parsing framework, because the Ply (or yacc) framework assumes that you will just do a single pass over the input, so it doesn't keep the already parsed text anywhere. Anyway, it's really a waste of cycles to parse the same text more than once.

So the parse needs to produce a data structure which can be executed, and therefore each production's semantic value must be a data object which fits somewhere in this data structure. Thus, your first task is to design the data structure you want use. In fact, I would have recommended doing that before you wrote the parser, because it tells you what the parser's result has to be.

There are a number of possible data structures which can be used; it's possible that your assignment has a clear suggestion. Probably this was discussed in the lectures or reading material as well (and if it wasn't and you paid for the course, I'd say you have a reasonable complaint). Two common possibilities are:

• A recursive collection of objects, often referred to as an "abstract syntax tree" because it abstracts from the syntax. Calling this a "tree" is a bit misleading. Although you could implement it from a general purpose tree data object using node attributes to hold relevant information, that's usually more complicated than defining a collection of classes, each of which implements a simple interface. An evaluate method might be all that you need, although for debugging you might also want to implement a method which prints the object in some convenient format.

• A list of low-level instructions which could be evaluated by a virtual machine. Commands like LEFT and RIGHT would just be a simple instructions, which could possibly be tuples of two elements (an opcode and an integer operand). To implement loops, the virtual machine would require a stack; a simple design might be something like this:

  [0] PUSH  36     # Pushes 36 onto the stack
  [1] PUSH   4     # Body of the outer loop; pushes 4
  [2] FWD  100
  [3] RIGHT 90
  [4] LOOP   2     # '2' is the index of the loop body
  [5] FWD   10
  [6] LOOP   1
  

  The LOOP instruction decrements the integer at the stop of the stack. If it is non-zero, it continues executing with the instruction whose index is the argument; otherwise, the top element of the stack is 0 and the LOOP instruction pops that off the stack and continues with the next instruction in sequence.