Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ply Lex parsing problem

Tags:

parsing

lex

ply

I'm using ply as my lex parser. My specifications are the following :

t_WHILE = r'while'  
t_THEN = r'then'  
t_ID = r'[a-zA-Z_][a-zA-Z0-9_]*'  
t_NUMBER = r'\d+'  
t_LESSEQUAL = r'<='  
t_ASSIGN = r'='  
t_ignore  = r' \t'  

When i try to parse the following string :

"while n <= 0 then h = 1"

It gives following output :

LexToken(ID,'while',1,0)  
LexToken(ID,'n',1,6)  
LexToken(LESSEQUAL,'<=',1,8)  
LexToken(NUMBER,'0',1,11)  
LexToken(ID,'hen',1,14)      ------> PROBLEM!  
LexToken(ID,'h',1,18)  
LexToken(ASSIGN,'=',1,20)  
LexToken(NUMBER,'1',1,22)  

It doesn't recognize the token THEN, instead it takes "hen" as an identifier.

Any ideas?

like image 403
Karan Avatar asked Feb 16 '11 21:02

Karan


2 Answers

The reason that this didn't work is related to the way ply prioritises matches of tokens, the longest token regex is tested first.

The easiest way to prevent this problem is to match identifiers and reserved words at the same type, and select an appropriate token type based on the match. The following code is similar to an example in the ply documentation

import ply.lex

tokens = [ 'ID', 'NUMBER', 'LESSEQUAL', 'ASSIGN' ]
reserved = {
    'while' : 'WHILE',
    'then' : 'THEN'
}
tokens += reserved.values()

t_ignore    = ' \t'
t_NUMBER    = '\d+'
t_LESSEQUAL = '\<\='
t_ASSIGN    = '\='

def t_ID(t):
    r'[a-zA-Z_][a-zA-Z0-9_]*'
    if t.value in reserved:
        t.type = reserved[ t.value ]
    return t

def t_error(t):
    print 'Illegal character'
    t.lexer.skip(1)

lexer = ply.lex.lex()
lexer.input("while n <= 0 then h = 1")
while True:
    tok = lexer.token()
    if not tok:
        break
    print tok
like image 155
Andrew Walker Avatar answered Sep 20 '22 07:09

Andrew Walker


PLY prioritizes the tokens declared as simple strings according the longest regular expression, but the tokens declared as functions have their order prioritized.

From the docs:

When building the master regular expression, rules are added in the following order:

  1. All tokens defined by functions are added in the same order as they appear in the lexer file.
  2. Tokens defined by strings are added next by sorting them in order of decreasing regular expression length (longer expressions are added first).

So, an alternative solution would be simply to specify the tokens you want prioritized as functions, instead of strings, like so:

def t_WHILE(t): r'while'; return t
def t_THEN(t): r'then'; return t
t_ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
t_NUMBER = r'\d+'
t_LESSEQUAL = r'<='
t_ASSIGN = r'='
t_ignore = ' \t'

This way WHILE and THEN will be the first rules to be added, and you get the behaviour you expected.

As a side note, you were using r' \t' (raw string) for t_ignore, so Python was treating the \ as a backslash. It should be a simple string instead, as in the example above.

like image 43
Elias Dorneles Avatar answered Sep 20 '22 07:09

Elias Dorneles