Re: Parsing Ambiguity

Wed, 10 Jun 2009 10:55:33 -0700

Hi Erez,

There is an ambiguity between var_list and expr_list.  So when ply has seen "a, b = c" it could reduce the last 'c' to either var_list or expr_list.  It will pick var_list because var_list appears before expr_list in the grammar.  This prevents the use of the rule "assign_list : var_list ASSIGN expr_list" in that case.

It works for "a,b=1,2" because "1" can only be an expr.

You should be able to fix this by allowing var_list to be a type of expr_list.  Perhaps something like:

expr_list: var_list
              | var_list COMMA expr2_list
              | expr2
              | expr2 COMMA expr_list

add expr2 to be any expr except NAME, and expr2_list starts with an expr2, then any expr after that:

expr: NAME
       | expr2

expr2: expr PLUS expr
         | NUMBER

expr2_list: expr2
                | expr2 COMMA expr_list   # expr_list, not expr2_list, to allow any expr after the first non-NAME

Now ply isn't forced to decide between two interpretations of what 'c' is in "a,b=c,d".  Ply doesn't have to decide until it has "c,d"; which could either be a var_list or an expr_list.  It will decide this depending on the next token.  If the token is, say, PLUS, then 'c,d' will end up an expr_list (expr_list: var_list COMMA expr2_list, where expr2_list: expr2, and expr2: expr PLUS expr).  If it's ASSIGN, it must be a var_list.

This should get you closer.

-bruce

Erez wrote: 
Hello dear plyers,
Please help me solve a little ambiguity!

I've been trying to write a parser for python for my personal
enjoyment. I'm aware that it's hard.
As you probably know, Python's assignment is rather complex. You can
use multiple assignments on one line, in two forms:
1)  a=b=c=d=4
2) a,b=3,4

I wrote a syntax for it (which I added, in minimal form, to the bottom
of this message), and it seems okay.
It can even parse statements like: "c,d=x,y=a+b"
However, it fails to parse "c,d=a,b"
My guess is that PLY thinks it's getting another variable declaration,
and cannot back down from this assumption.

I tried for several days and cannot get all forms to work.
Perhaps I'm doing something wrong (or not doing it sufficiently
right :) )
I would really appreciate pointers.


Here is the script:
#---------------------------------------
tokens = (
    'NAME','NUMBER',
    'PLUS','ASSIGN', 'COMMA', 'NL'
    )

# Tokens
t_PLUS    = r'\+'
t_COMMA  = r','
t_ASSIGN  = r'='
t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
t_NUMBER = r'\d+'


# Ignored characters
t_ignore = " \t"
#t_NL = r'\n+'

def t_NL(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")
    return t

def t_error(t):
    print "Illegal character '%s'" % t.value[0]
    t.lexer.skip(1)

# Build the lexer
import ply.lex as lex
lex.lex()

# Parsing rules

def p_statements(t):
    '''statements : statement
                  | statement statements
    '''
    t[0] = t[1:]

def p_statement(t):
    '''statement : assign_list NL
                 | NL
    '''
    t[0] = t[1:]

def p_assign_list(t):
    """assign_list : var_list ASSIGN expr_list
                   | var_list ASSIGN assign_list
    """
    t[0] = t[1:]

def p_var_list(t):
    """var_list : NAME
                | NAME COMMA var_list
    """
    t[0] = ['var_list'] + t[1:]

def p_expr_list(t):
    """expr_list : expr
                 | expr COMMA expr_list
    """
    t[0] = ['expr_list'] + t[1:]

def p_expr(t):
    """expr : NAME
            | expr PLUS expr
            | NUMBER
    """
    t[0] = t[1:]

def p_error(t):
    if t:
        print "Syntax error at '%s'" % t.value, t.lineno, t.lexpos

import ply.yacc as yacc
yacc.yacc()

print yacc.parse("""
c,d=x,y=a+b
c,d=1,2
c,d=a,b
""")
# first two work, but last throws an exception!


#--------------------------------------- END OF SCRIPT

Thanks,
  Erez


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "ply-hack" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [email protected]
For more options, visit this group at http://groups.google.com/group/ply-hack?hl=en
-~----------~----~----~----~------~----~------~--~---

Reply via email to