The Prefix Expression Grammar

G = (N , T , P,E) where

N = {E}

T = {identifier, number, +, ∗}

P is defined by the set of productions

E →+ E E |∗ E E | number

A grammar, G, consists of three sets: a set of non-terminals symbols denoted by N , a set of terminals or tokens called T , and a set, P, of productions. One of the nonterminals is designated the start symbol of the grammar. For this grammar, the special symbol E is the start symbol and only non-terminal of the grammar. The symbol E stands for any prefix expression. In this grammar there are three productions that provide the rules for how prefix expressions can be constructed. The productions state that any prefix expression is composed of (you can read → as is composed of ) a plus sign followed by two prefix expressions, a multiplication symbol followed by two prefix expressions, or just a number. The grammar is recursive so every time you see E in the grammar, it can be replaced by another prefix expression. This grammar is very easy to convert to a function that given a queue of tokens will build an abstract syntax tree of a prefix expression. A function, like the E function in Sect. 6.4.2, that reads tokens and returns an abstract syntax tree is called a parser. Since the grammar is recursive, the parsing function is recursive as well. It has a base case first, followed by the recursive cases. The code in Sect. 6.4.2 provides that function.

A Prefix Expression Parser

1 import queue


3 def E(q):

4 if q.isEmpty():

5 raise ValueError("Invalid Prefix Expression")


7 token = q.dequeue()


9 if token == "+":

10 return PlusNode(E(q),E(q))


12 if token == "*":

13 return TimesNode(E(q),E(q))


15 return NumNode(float(token))


17 def main():

18 x = input("Please enter a prefix expression: ")


20 lst = x.split()

21 q = queue.Queue()


23 for token in lst:

24 q.enqueue(token)


26 root = E(q)


28 print(root.eval())

29 print(root.inorder())


31 if name == " main ":

32 main()

In Sect. 6.4.2 the parameter q is a queue of the tokens read from the file or string. Code to call this function is provided in the main function of Sect. 6.4.2. The main function gets a string from the user and enqueues all the tokens in the string (tokens must be separated by spaces) on a queue of tokens. Then the queue is passed to the function E. This function is based on the grammar given above. The function looks at the next token and decides which rule to apply. Each call to the E function returns an abstract syntax tree. Calling E from the main function results in parsing the prefix expression and building its corresponding tree. This example gives you a little insight into how Python reads a program and constructs an abstract syntax tree for it. A Python program is parsed according to a grammar and an abstract syntax tree is constructed from the program. The Python interpreter then interprets the program by traversing the tree.

This parser in Sect. 6.4.2 is called a top-down parser. Not all parsers are constructed this way. The prefix grammar presented in this text is a grammar where the top-down parser construction will work. In particular, a grammar cannot have any left-recursive rules if we are to create a top-down parser for it. Left recursive rules occur in the postfix grammar given in Sect. 6.4.3.

The Postfix Expression Grammar

G = (N , T , P,E) where

N = {E}

T = {identifier, number, +, ∗}

P is defined by the set of productions

EE E +| E E ∗| number

In this grammar the first and second productions have an expression composed of an expression, followed by another expression, followed by an addition or multiplication token. If we tried to write a recursive function for this grammar, the base case would not come first. The recursive case would come first and hence the function would not be written correctly since the base case must come first in a recursive function. This type of production is called a left-recursive rule. Grammars with left-recursive rules are not suitable for top-down construction of a parser. There are other ways to construct parsers that are beyond the scope of this text. You can learn more about parser construction by studying a book on compiler construction or programming language implementation.

< Prev   CONTENTS   Next >