Re: Parsing newbie -- recursion question (probably simple)

sonicsmooth@gmail.com wrote:


# I'm having trouble getting my head wrapped around recursion. If I have
# the following rule to generate a list of nodes:
#
# nodelist := nodelist node | node


This is called left recursive, because you're recursing on the
leftmost symbol. Right recursive would be


nodelist := node | node nodelist
or
nodelist := node nodelistoption
nodelistoption := empty | nodelist


The other type of recursion is embedding, such as


embedding := something | "(" embedding ")"


Parser generators like yacc can handle left and right recursion
and embedding.


This is a recursive descent parser:


# def nodelist(tokens):
# # some logic maybe...
# # copy the tokens list in case I need to back up
# nodelist(tokens)
# # some logic for ANDing this with
# node(tokens)
# # some more logic for ORing this with
# node(tokens)
#
# I don't understand how to keep from getting caught in an infinite
# recursive loop. The only way out is to find a terminal node, but I'm


And you cannot use left recursion with recursive descent because you
do indeed get caught in an infinite loop. For recursive descent each
function has to accept at least one terminal before recursing. That
means using right recursion or embedding, and never left
recursion. You have to instead use a productions like


# nodelist := node nodelistoption


def nodelist(tokens)
if node(tokens),
# note that nodelistoption always
# returns true, so this conditional
# will always fail.
if not nodelistoption(tokens),
parse error: expected nodelistoption
return true
else
return false


# nodelistoption := empty | nodelist


def nodelistoption(tokens)
if nodelistoption(tokens),
return true
else
# empty matches nothing, so return
# true of nothing matched
return true


# another nodelist. Should I check for the terminal first? Should I


The first thing checked can be another production, but eventually you
need to accept at least one terminal before you recurse.


For example, for a simple expression:
expression := factor | factor+expression
factor := primary | primary*factor
primary := variable | (expression)
Before it recurses from primary back to expression, it will
have to accept at least one left parenthesis.


def expression
if factor,
if terminal("+"),
if not expression,
parse error
return true
else
return true
else
return false


def factor
if primary,
if terminal("*"),
if not factor,
parse error
return true
else
return true
else
return false


def primary
if variable,
return true
else if terminal("(")
if not expression,
parse error
if not terminal(")"),
parse error
return true
else
return false


--
SM Ryan http://www.rawbw.com/~wyrmwif/
Elvis was an artist. But that didn't stop him from joining the service
in time of war. That's why he is the king, and you're a shmuck.

Return to the comp.compilers page.
Search the comp.compilers archives again.