Friday, January 7, 2011

All Black Small Gages

mini-C Parser in Python

I've been learning for some time a module to make the lexer and parser of a compiler in Python. This is a relatively easy tool to use (compared to others like antlr) and very similar in syntax to LEX and YACC. In fact, the name comes from
  Python PLY-Lex-Yacc.      There are many tutorials and examples of this module, so my intention here is not to explain how to use and little else.     install    What We   ply to install the module for Python. This can be done from the Ubuntu repositories or through the tar.gz of the project page.        $ sudo apt-get install python-ply 


lexical analyzer import
as  lex

# list of tokens
tokens = (
    
# Reserverd words
     'ELSE' ,
    
'IF'
,
    
'INT' ,      'RETURN' ,      'WHILE'
,      'VOID'
,
         # Symbols

    
'PLUS'
,      'MINUS'
,
    
'TIMES'
,
       'DIVIDE'  ,        'LESS'  ,       
'LESSEQUAL'
,      'GREATER'
,
     'GREATEREQUAL' ,
     'EQUAL' ,
     'DEQUAL' ,
     'DISTINT' ,
     'SEMICOLON' ,
     'COMMA' ,
     'LPAR' ,

'RPAREN' ,
'LBRACKET' ,
'RBRACKET' ,
'LBLOCK' ,
'RBLOCK' ,
# Others
; 'ID' ,
'NUMBER' ,
)
What's done is make an array of all tokens of the language. In this case has taken a subset of C, which we called cminus.

Now, as expected, there should be regular expressions for all these tokens. One way to do this (this is new from version 3 PLY) take all those tokens only be a sentence and do it directly in the form:
# Regular expressions rules for a simple tokens
t_PLUS = r '\\ +'

t_MINUS = r'-'
t_TIMES = r' \\ * '
t_DIVIDE = r' / '
t_EQUAL =
r '='

t_LESS = r '\u0026lt;'
t_GREATER = r '>'
t_SEMICOLON = ','


t_COMMA = r ' , '

t_LPAREN = r' \\ ('
t_RPAREN =
r '\\)'
   
t_LBRACKET = r '\\ ['
   
t_RBRACKET = r '\\]'
   
t_LBLOCK = r '{'
   
t_RBLOCK = r '}'
   
 For all other tokens, what we do is a function. Note that all the rules begin with t, this is because the module takes everything that contains that t_TOKEN creates the corresponding transition diagram. Some of them are:   
  def  
 t_ELSE  (t):   
r'else'
          
return
    t   
   def   
 
 t_IF  (t):       
r'if'
          
return
    t   
   def   
 
 t_NUMBER  (t):       
r'\d+'
    t.value =
int
(t.value)
    
   return     t       
def  
t_ID (t):      r'\w+(_\d\w)*'
    
return  t
def  
t_newline (t):      r'\n+'
    t.lexer.lineno +=
len (t.value) t_ignore = ' \t
'

def   t_comments (t):
    
r'/*(. t.lexer.lineno + = 1 def
t_error
(t): print " Lexical error: "+

str (t.value [ 0 ]) t.lexer.skip ( 1 )



Parsing Now we give an order to all these tokens that we are coming. This is achieved using a grammar. Specify PLY grammars is very similar to that used in YACC. '''not_terminal: list_of_terminals not_terminals'''
For example,
"" "program: PROGRAM ID SEMICOLON EOF block" "" PLY What does is take the first string in each production analyze and create the parser. For example, some of the production of C-minus are: ______________________________________________________ import
ply.yacc
as yacc from cminus_lexer

import token import  cminus_lexer def
  p_program
(p):     'program : declaration_list'

    pass
def   p_declaration_list_1 (p):     'declaration_list : declaration_list declaration'  

pass


def

 
p_declaration_list_2
(p):
   
'declaration_list : declaration'

   

pass



   def       p_declaration  (p):       
'''declaration : var_declaration                  
pass

def   p_var_declaration_1 (p):
    'var_declaration : type_specifier ID SEMICOLON'
    pass

def   p_var_declaration_2 (p):
    'var_declaration : type_specifier ID LBRACKET NUMBER RBRACKET SEMICOLON'
   
   pass       
   def        p_type_specifier_1  (p):       
'type_specifier : INT'    
pass

def   p_type_specifier_2 (p):    
'type_specifier : VOID'    
pass
def

  p_fun_declaration (p):     'fun_declaration : LPAR ID arRP type_specifier compount_stmt params' pass



def p_empty (p): 'empty' pass



______________________________________________________ Note that nonterminals are in lower case and the terminals are in upper case. This is by convention. In addition, tokens are created above in the lexical analyzer. In the PLY production is necessary to place a fool to do the role of epsilon . (P → epsilon ). This does nothing. This is a parser that simply checks that the syntax is correct, but if it is incorrect, we need to sing the error. We do this by producing p_error ()
. ______________________________________________________
def

p_error (p): if p is

Not  
None
:         print   "Syntax error at line "  + str
(p.lexer.lineno) +  
" Unexpected token  "  + str
(p.value)
      
 else    :            print     "Syntax error at line: " Str + 
(cminus_lexer.lexer.lineno) ______________________________________________________

Once we have all written rules, we call the parser. The first time you run, will build a py file with the parser, called
parsetab.py
and another with the lexical and syntactic information call
parser.out
. ______________________________________________________ parser = yacc.yacc ()
if
  __name__ == '__main__' :   data =   '''     
        // Comment C99 style         int gcd (int u, int v) {             if (v == 0)                 return u  
            else                 return gcd(v, v-u);         }
    '''
   parser.parse (data, tracking = True  ) ______________________________________________________  
To run the program, invoke the parser and it will take the sample code above and you will pass the parser.
cminus_parser.py $ python Syntax error at line 6
 Unexpected token else 


 complete Code 


can see the entire code in the repository: Http://bitbucket.org/jjfumero/cminus The next step is to build the AST. The strategy here is to build as it makes the parser.

References

PLY
Tutorial for a mini-lisp
    

0 comments:

Post a Comment