Python programming language created
Install SLY for Python. SLY is a lexing and parsing tool which makes our process much easier.
Building a Lexer
The first phase of a compiler is to convert all the character streams(the high level program that is written) to token streams. This is done by a process called lexical analysis. However, this process is simplified by using SLY
First let’s import all the necessary modules.
Now let’s build a class BasicLexer which extends the Lexer class from SLY. Let’s make a compiler that makes simple arithmetic operations. Thus we will need some basic tokens such as NAME, NUMBER, STRING. In any programming language, there will be space between two characters. Thus we create an ignore literal. Then we also create the basic literals like ‘=’, ‘+’ etc., NAME tokens are basically names of variables, which can be defined by the regular expression [a-zA-Z_][a-zA-Z0-9_]*. STRING tokens are string values and are bounded by quotation marks(” “). This can be defined by the regular expression \”.*?\”.
Whenever we find digit/s, we should allocate it to the token NUMBER and the number must be stored as an integer. We are doing a basic programmable script, so let’s just make it with integers, however, feel free to extend the same for decimals, long etc., We can also make comments. Whenever we find “//”, we ignore whatever that comes next in that line. We do the same thing with new line character. Thus, we have build a basic lexer that converts the character stream to token stream.
First let’s import all the necessary modules.
Now let’s build a class BasicParser which extends the Lexer class. The token stream from the BasicLexer is passed to a variable tokens. The precedence is defined, which is the same for most programming languages. Most of the parsing written in the program below is very simple. When there is nothing, the statement passes nothing. Essentially you can press enter on your keyboard(without typing in anything) and go to the next line. Next, your language should comprehend assignments using the “=”. This is handled in line 18 of the program below. The same thing can be done when assigned to a string.
The parser should also parse in arithmetic operations, this can be done by expressions. Let’s say you want something like shown below. Here all of them are made into token stream line-by-line and parsed line-by-line. Therefore, according to the program above, a = 10 resembles line 22. Same for b =20. a + b resembles line 34, which returns a parse tree (‘add’, (‘var’, ‘a’), (‘var’, ‘b’)).
GFG Language > a + b Now we have converted the token streams to a parse tree. Next step is to interpret it.
Execution
Interpreting is a simple procedure. The basic idea is to take the tree and walk through it to and evaluate arithmetic operations hierarchically. This process is recursively called over and over again till the entire tree is evaluated and the answer is retrieved. Let’s say, for example, 5 + 7 + 4. This character stream is first tokenized to token stream in a lexer. The token stream is then parsed to form a parse tree. The parse tree essentially returns (‘add’, (‘add’, (‘num’, 5), (‘num’, 7)), (‘num’, 4)).
The interpreter is going to add 5 and 7 first and then recursively call walkTree and add 4 to the result of addition of 5 and 7. Thus, we are going to get 16. The below code does the same process.
To display the output from the interpreter, we should write some codes. The code should first call the lexer, then the parser and then the interpreter and finally retrieves the output. The output in then displayed on to the shell.
'It is necessary to know that we haven’t handled any errors. So SLY is going to show it’s error messages whenever you do something that is not specified by the rules you have written.
Execute the program you have written using,
How to Create a Programming Language using Python?
In this article, we will show you how to create your own programming language using SLY(Sly Lex Yacc) and Python. It is important to note that this is not a beginners’ tutorial, and you need to be familiar with the prerequisites given below.
Requirements
- Compiler design knowledge is rough.
- Knowledge of lexical analysis, parsing, and other compiler design aspects.
- Regular expression understanding.
- Knowledge of the Python programming language.
Getting Started
Install the Python version of SLY. SLY simplifies our process by lexing and parsing documents.
Geek alert! Learn Python programming basics with the Python Programming Foundation Course.
The Python DS Course will help you improve your Data Structures concepts for your interview. To get started with your Machine Learning journey, join the Machine Learning — Basic Level Course
Building a Lexer
Compilers begin by converting the character streams (the high level program) into token streams. This is done through a process called lexical analysis. However, SLY simplifies the process
First let’s import all the necessary modules.
«from sly import Lexer»
Now let’s create a class BasicLexer that extends the Lexer class from SLY. Let’s build a simple arithmetic compiler. We will need some basic tokens like NAME, NUMBER, and STRING. In any programming language, there will be a space between two characters. Hence, ignore literals are created. Then we also create the basic literals like ‘=’, ‘+’ etc., NAME tokens are basically names of variables, which can be defined by the regular expression [a-zA-Z_][a-zA-Z0-9_]*. STRING tokens are string values and are bounded by quotation marks(” “). This can be defined by the regular expression \”.*?\”.
If we find a digit/s, we should assign it to the token NUMBER and the number should be stored as an integer. As this is a basic programmable script, let’s just use integers, however, feel free to extend it to decimals, longs, etc. We can also provide comments. Whenever we find “//”, we ignore whatever that comes next in that line. We do the same thing with new line character. Thus, we have build a basic lexer that converts the character stream to token stream.
«class BasicLexer(Lexer):
# Define tokens as regular expressions
# (stored as raw strings)
# convert it into a python integer
# Newline token(used only for showing
self.lineno = t.value.count(‘\n’)»
First let’s import all the necessary modules.
«from sly import Parser»
Let’s now build a BasicParser class that extends Lexer. The BasicLexer passes the token stream to a variable tokens. In most programming languages, the precedence is defined. For example, in the program below, most of the parsing is very simple. No data is passed when there is none. Essentially you can press enter on your keyboard(without typing in anything) and go to the next line. Next, your language should comprehend assignments using the “=”. This is handled in line 18 of the program below. The same thing can be done when assigned to a string.
class BasicParser(Parser):
#tokens are passed from lexer to parser
tokens = BasicLexer.tokens
return (‘add’, p.expr0, p.expr1)
return (‘sub’, p.expr0, p.expr1)
return (‘mul’, p.expr0, p.expr1)
return (‘div’, p.expr0, p.expr1)
By using expressions, the parser can also parse arithmetic operations. Consider the following example. Line by line, all of them are turned into token streams and parsed line by line. Therefore, according to the program above, a = 10 resembles line 22. Same for b =20. a + b resembles line 34, which returns a parse tree (‘add’, (‘var’, ‘a’), (‘var’, ‘b’)).
Now we have converted the token streams to a parse tree. Next step is to interpret it.
Execution
Interpreting is a simple process. Hierarchically evaluating arithmetic operations is basically what we do by looking at the tree and walking through it. The entire tree is evaluated recursively until the answer is obtained. Let’s consider, for instance, five plus seven plus four. A lexer first tokenizes this character stream into a token stream. The token stream is then parsed to form a parse tree. The parse tree essentially returns (‘add’, (‘add’, (‘num’, 5), (‘num’, 7)), (‘num’, 4)). (see image below)
The interpreter is going to add 5 and 7 first and then recursively call walkTree and add 4 to the result of addition of 5 and 7. Thus, we are going to get 16. The below code does the same process. Python3
«def __init__(self, tree, env):
result = self.walkTree(tree)
if result is not None and isinstance(result, int):
if isinstance(result, str) and result[0] == ‘»‘:
def walkTree(self, node):
if isinstance(node, int):
if isinstance(node, str):
return self.walkTree(node[1]) + self.walkTree(node[2])
return self.walkTree(node[1]) — self.walkTree(node[2])
return self.walkTree(node[1]) * self.walkTree(node[2])
return self.walkTree(node[1]) / self.walkTree(node[2])
self.env[node[1]] = self.walkTree(node[2])
print(«Undefined variable ‘»+node[1]+»‘ found!»)
Displaying the Output
In order to display the interpreter’s output, we need to write some codes. In the code, the lexer should be called first, then the parser, then the interpreter, and finally the output should be retrieved. After that, the output is displayed.
if __name__ == ‘__main__’:
text = input(‘GFG Language > ‘)
tree = parser.parse(lexer.tokenize(text))
BasicExecute(tree, env)It is necessary to know that we haven’t handled any errors. So SLY is going to display error messages whenever you do something that isn’t specified by your rules.
Execute the program you have written using,
«python you_program_name.py»
Footnotes
Our interpreter is very basic. Of course, it can be enhanced in a variety of ways. Conditionals and loops can be added. The design can be modular or object oriented. Among the features that can be added to the same are module integration, method definitions, and parameterization of methods.