# Python Lex-Yacc

PLY, Python Lex-Yacc, is a pure-Python implementation of the popular compiler construction tools lex and yacc. Learn more about it here.

## Python Lex-Yacc: Getting Started with PLY

To install PLY on your machine for python2/3, follow the steps outlined below:

``````Download the source code from here.

Navigate into the unzipped ply-3.10 folder

Run the following command in your terminal: python setup.py install``````

If you completed all the above, you should now be able to use the PLY module. You can test it out by opening a python interpreter and typing import ply.lex.

Note: Do not use pip to install PLY, it will install a broken distribution on your machine.

## Python Lex-Yacc The “Hello, World!” of PLY – A Simple Calculator

Let’s demonstrate the power of PLY with a simple example: this program will take an arithmetic expression as a string input, and attempt to solve it.

Open up your favourite editor and copy the following code:

```from ply import lex
import ply.yacc as yacc
tokens = (
'PLUS',
'MINUS',
'TIMES',
'DIV',
'LPAREN',
'RPAREN',
'NUMBER',
)
t_ignore = ' \t'
t_PLUS = r'+'
t_MINUS = r'-'
t_TIMES = r'*'
t_DIV = r'/'
t_LPAREN = r'('
t_RPAREN = r')'
def t_NUMBER( t ) :
r'[0-9]+'
t.value = int( t.value )
return t
def t_newline( t ):
r'\n+'
t.lexer.lineno += len( t.value )
def t_error( t )```
`print("Invalid Token:",t.value)t.lexer.skip( 1 )lexer = lex.lex()precedence = ('left', 'PLUS', 'MINUS' ),'left', 'TIMES', 'DIV' ),'nonassoc', 'UMINUS' ))def p_add( p ) :'expr : expr PLUS expr'p = p + pdef p_sub( p ) :'expr : expr MINUS expr'p = p - pdef p_expr2uminus( p ) :'expr : MINUS expr %prec UMINUS'p = - pdef p_mult_div( p ) :'''expr : expr TIMES expr| expr DIV expr'''if p == '*' :p = p * pelse :if p == 0 :print("Can't divide by 0")raise ZeroDivisionError('integer division by 0')p = p / pdef p_expr2NUM( p ) :'expr : NUMBER'p = pdef p_parens( p ) :'expr : LPAREN expr RPAREN'p = pdef p_error( p ):print("Syntax error in input!")parser = yacc.yacc()res = parser.parse("-4*-(3-5)") # the inputprint(res)Save this file as calc.py and run it.`

Output:

-8

Which is the right answer for -4 * – (3 – 5).

## Part 1: Tokenizing Input with Lex

There are two steps that the code from example 1 carried out: one was tokenizing the input, which means it looked for symbols that constitute the arithmetic expression, and the second step was parsing, which involves analysing the extracted tokens and evaluating the result.

This section provides a simple example of how to tokenize user input, and then breaks it down line by line.

```import ply.lex as lex
List of token names. This is always required tokens = [
'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN',
]
Regular expression rules for simple tokens
t_PLUS = r'+'
t_MINUS = r'-'
t_TIMES = r'*'
t_DIVIDE = r'/'
t_LPAREN = r'('
t_RPAREN = r')'
A regular expression rule with some action code def t_NUMBER(t):
r'\d+'
t.value = int(t.value) return t
Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
A string containing ignored characters (spaces and tabs) t_ignore = ' \t'
Error handling rule
def t_error(t):
print("Illegal character '%s'" % t.value)
t.lexer.skip(1)
Build the lexer lexer = lex.lex()
Give the lexer some input lexer.input(data)
Tokenize
while True:
tok = lexer.token()
if not tok:
break # No more input
print(tok)```

Save this file as calclex.py. We’ll be using this when building our Yacc parser.

Breakdown

``````Import the module using import ply.lex

All lexers must provide a list called tokens that defines all of the possible token names that can be produced by the lexer. This list is always required.``````
`tokens = ['NUMBER','PLUS','MINUS','TIMES','DIVIDE','LPAREN','RPAREN',]`

tokens could also be a tuple of strings (rather than a string), where each string denotes a token as before.

``The regex rule for each string may be defined either as a string or as a function. In either case, the variable name should be prefixed by t_ to denote it is a rule for matching tokens.``

For simple tokens, the regular expression can be specified as strings: t_PLUS = r’+’

If some kind of action needs to be performed, a token rule can be specified as a function.

`def t_NUMBER(t):r'\d+'t.value = int(t.value)return t`

Note, the rule is specified as a doc string within the function. The function accepts one argument which is an instance of LexToken, performs some action and then returns back the argument.

If you want to use an external string as the regex rule for the function instead of specifying a doc string, consider the following example:

@TOKEN(identifier) # identifier is a string holding the regex def t_ID(t):
… # actions

An instance of LexToken object (let’s call this object t) has the following attributes:

``````t.type which is the token type (as a string) (eg: 'NUMBER', 'PLUS', etc). By default, t.type is set to the name following the t_ prefix.

t.value which is the lexeme (the actual text matched)

t.lineno which is the current line number (this is not automatically updated, as the lexer knows nothing of line numbers). Update lineno using a function called t_newline.``````
`def t_newline(t):r'\n+'t.lexer.lineno += len(t.value)`

GoalKicker.com – Python® Notes for Professionals 728

1. t.lexpos which is the position of the token relative to the beginning of the input text. If nothing is returned from a regex rule function, the token is discarded. If you want to discard a token, you can alternatively add t_ignore_ prefix to a regex rule variable instead of defining a function for the same rule.
`def t_COMMENT(t):r'#.*'pass`

### No return value. Token discarded

…Is the same as:

`t_ignore_COMMENT = r'#.*'`

This is of course invalid if you’re carrying out some action when you see a comment. In which case, use a function to define the regex rule.

If you haven’t defined a token for some characters but still want to ignore it, use t_ignore = “” (these prefixes are necessary):

`t_ignore_COMMENT = r'#.*'t_ignore = ' \t' # ignores spaces and tabs`

When building the master regex, lex will add the regexes specified in the file as follows:

``````Tokens defined by functions are added in the same order as they appear in the file.

Tokens defined by strings are added in decreasing order of the string length of the string defining the regex for that token.``````

If you are matching == and = in the same file, take advantage of these rules.

Literals are tokens that are returned as they are. Both t.type and t.value will be set to the character itself. Define a list of literals as such:

`literals = [ '+', '-', '*', '/' ]`

or,

literals = “+-*/”

It is possible to write token functions that perform additional actions when literals are matched.

However, you’ll need to set the token type appropriately. For example:

```literals = [ '{', '}' ]
def t_lbrace(t):
r'{'
t.type = '{' # Set token type to the expected literal (ABSOLUTE MUST if this is a literal)
return t```

Handle errors with t_error function.

`Error handling rule def t_error(t):print("Illegal character '%s'" % t.value)t.lexer.skip(1) # skip the illegal token (don't process it)`

In general, t.lexer.skip(n) skips n characters in the input string.

``Final preparations:``

Build the lexer using lexer = lex.lex().

You can also put everything inside a class and call use instance of the class to define the lexer. Eg:

`import ply.lex as lexclass MyLexer(object):… # everything relating to token rules and error handling comes here as usual`

### Build the lexer

`def build(self, **kwargs):self.lexer = lex.lex(module=self, **kwargs)def test(self, data):self.lexer.input(data)for token in self.lexer.token():print(token)`

#### Build the lexer and try it out

`m = MyLexer()m.build() # Build the lexerm.test("3 + 4") #`

Provide input using lexer.input(data) where data is a string

To get the tokens, use lexer.token() which returns tokens matched. You can iterate over lexer in a loop as in:

`for i in lexer:print(i)`

## Python Lex-Yacc: Part 2: Parsing Tokenized Input with Yacc

This section explains how the tokenized input from Part 1 is processed – it is done using Context Free Grammars (CFGs). The grammar must be specified, and the tokens are processed according to the grammar. Under the hood, the parser uses an LALR parser.

#### Yacc example

```import ply.yacc as yacc
Get the token map from the lexer. This is required. from calclex import tokens```
`def p_expression_plus(p):'expression : expression PLUS term'p = p + pdef p_expression_minus(p):'expression : expression MINUS term'p = p - pdef p_expression_term(p):'expression : term'p = pdef p_term_times(p):'term : term TIMES factor'p = p * pdef p_term_div(p):'term : term DIVIDE factor'p = p / pdef p_term_factor(p):'term : factor'p = pdef p_factor_num(p):'factor : NUMBER'p = pdef p_factor_expr(p):'factor : LPAREN expression RPAREN'p = pError rule for syntax errors def p_error(p):print("Syntax error in input!")Build the parserparser = yacc.yacc()while True:try:s = raw_input('calc > ')except EOFError:breakif not s: continueresult = parser.parse(s)print(result)`

Breakdown

Each grammar rule is defined by a function where the docstring to that function contains the appropriate context-free grammar specification. The statements that make up the function body implement the semantic actions of the rule. Each function accepts a single argument p that is a sequence containing the values of each grammar symbol in the corresponding rule. The values of p[i] are mapped to grammar symbols as shown here:

`def p_expression_plus(p):'expression : expression PLUS term'`

#### p p p p

`p = p + p`

For tokens, the “value” of the corresponding p[i] is the same as the p.value attribute assigned in the lexer module. So, PLUS will have the value +.

For non-terminals, the value is determined by whatever is placed in p. If nothing is placed, the value is None. Also, p[-1] is not the same as p, since p is not a simple list (p[-1] can specify embedded actions (not discussed here)).

Note that the function can have any name, as long as it is preceded by p_.

The p_error(p) rule is defined to catch syntax errors (same as yyerror in yacc/bison).

Multiple grammar rules can be combined into a single function, which is a good idea if productions have a similar structure.

`def p_binary_operators(p):'''expression : expression PLUS term| expression MINUS termterm : term TIMES factorterm DIVIDE factor'''if p == '+':p = p + p elif p == '-':p = p - p elif p == '*':p = p * p elif p == '/':p = p / p`

Character literals can be used instead of tokens.

`def p_binary_operators(p):'''expression : expression '+' term| expression '-' termterm : term '' factor term '/' factor''' if p == '+': p = p + p elif p == '-': p = p - p elif p == '':p = p * p elif p == '/':p = p / p`

Of course, the literals must be specified in the lexer module.

Empty productions have the form ”’symbol : ”’

To explicitly set the start symbol, use start = ‘foo’, where foo is some non-terminal.

Setting precedence and associativity can be done using the precedence variable.

```precedence = (
('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators```
`('left', 'PLUS', 'MINUS'),('left', 'TIMES', 'DIVIDE'),('right', 'UMINUS'), # Unary minus operator)`

Tokens are ordered from lowest to highest precedence. nonassoc means that those tokens do not associate.

This means that something like a < b < c is illegal whereas a < b is still legal.

parser.out is a debugging file that is created when the yacc program is executed for the first time. Whenever a shift/reduce conflict occurs, the parser always shifts.

Previous articleTurtle Graphics
SHARE