The world is stuffed with programming languages with all types of various use circumstances. Most of those languages, although, are constructed for very basic functions — generally, we might wish to design a language to suit a really particular use case (e.g. Fb designed React to make it simpler to develop their net purposes, and Apple not too long ago developed Pkl, a language designed to make configurations simpler. There are various extra examples of this in varied fields). As such, figuring out tips on how to construct a programming language is a helpful ability to have in your belt.
On this article, we are going to construct an interpreted programming language from scratch and study somewhat bit about each the lambda calculus and programming languages as a complete alongside the way in which. The language we construct right here might be pretty esoteric, however the course of ought to hopefully provide you with an thought of tips on how to design your individual use-case-specific languages (and educate you helpful details about how programming languages operate below the hood).
Since we’re constructing an interpreted language¹, our overarching circulate will look one thing like this:
Principally, we begin with some concrete syntax (code) written in our goal language (the language that we are attempting to put in writing), go it to some parser that converts it to an summary syntax tree (a tree illustration of the code that’s simple to work with), after which go that to an interpreter that “runs” the summary syntax tree to provide us a last end result. Observe that the parser and interpreter are written in some already present host language — C’s authentic parser and compiler, as an illustration, have been written in meeting.
** Observe: My use of “parser” right here encapsulates the complete parsing course of. Often, lexing is finished previous to “parsing”, however on this case parsing is simply the method of taking concrete syntax to summary syntax, no matter which will seem like.
For instance, think about the next specification for a easy language for primary arithmetic:
EXPR = quantity
| EXPR + EXPR
| EXPR - EXPR
| EXPR * EXPR
| EXPR / EXPR
| (EXPR)
The above, by the way in which, is an EBNF for a context-free grammar². I received’t delve too deeply into what this implies right here, however all programming languages written in a kind like this are parse-able in polynomial time through the CYK algorithm. For this EBNF, one thing like (4 + 4) * 3 is a legitimate program, however one thing like def f(x): return 5; f(5) isn’t.
Suppose we at the moment are given the concrete syntax (4 + 4) * 3 . After parsing, we should always get an summary syntax tree (AST) like this:
Then our interpreter will begin on the root and recursively go down the tree till we get our reply, particularly 24.
Observe shortly that this grammar is ambiguous — as an illustration, how ought to the expression 4 + 4 * 3 parse? It may both parse because the above (that’s, (4 + 4) * 3), or it may additionally parse as 4 + (4 * 3) — neither parsing is inherently extra “right” in the way in which that we now have specified the language, as each are legitimate parse bushes. In circumstances like this, the parser should arbitrarily decide about tips on how to parse our language.
By the circulate chart, our first step ought to logically be to design our concrete syntax. What you select to make your syntax is totally as much as you. I made a decision to create EmojiLang, a (horrible) language that ensures a particularly colourful display screen when you are typing. The grammar is beneath:
grammar EmojiLang;program: '🏃♂️🏃♂️🏃♂️' expr '🛑🛑🛑' EOF;
expr: '(' (ID
| atom
| ifCond
| anonFunctionDefn
| funApplication
| varAssignment
| READ_FLOAT
| READ_STRING
| printExpr
| sequentialOp
| baseComputation) ')';
atom: NUMBER | BOOLEAN | STRING;
ifCond: '🤔' cond=expr '❓' ontrue=expr ':' onfalse=expr;
anonFunctionDefn: '🧑🏭' arg=ID '⚒️' physique=expr;
funApplication: '🏭' enjoyable=expr arg=expr;
varAssignment: '📦' var=ID '🔜' val=expr;
printExpr: '🖨️' expr;
sequentialOp: '📋' first=expr second=expr;
baseComputation: left=expr op=('➕' | '➖' | '✖️' | '➗' | '🟰' | '≤') proper=expr;
ID: [a-zA-Z_][a-zA-Z0-9_]*;
NUMBER: [0-9]+ ('.' [0-9]+)?;
BOOLEAN: '👍' | '👎';
STRING: '"' ~[rn"]* '"';
READ_FLOAT: '🔢';
READ_STRING: '🔤';
WHITESPACE: [ trn]+ -> skip;
COMMENT: '😴' .*? '⏰' -> skip;
LINE_COMMENT: '🥱' ~[rn]* -> skip;
** Observe: the above specification is written for use in a instrument referred to as ANTLR, we’ll get again to this very quickly.
This language is, after all, ridiculous, however it’s attention-grabbing for a few causes. Firstly, all of our expressions are required to be parenthesized. This makes it extraordinarily annoying to code, but in addition makes our grammar non-ambiguous. Secondly, discover how we will solely outline nameless features — there isn’t a equal syntax for one thing like def in Python. Lastly, all features on this language (apart from the bottom computations) have precisely one argument. We’ll discover the implications of the final two design choices after we mess around with our language in a bit.
We are able to, after all, write our personal parser. Fortunately although, there are instruments that may parse arbitrary context-free grammars. For this tutorial, we are going to use ANTLR (you’ll be able to obtain it here). ANTLR is a really good and easy-to-use instrument that takes grammar specs just like the above and creates parsers in quite a lot of goal languages (on this tutorial, we might be utilizing Python).
Utilizing it’s pretty easy, simply observe the next steps:
- Obtain the ANTLR Java binaries from here
- Create a .g4 file (just like the above) on your grammar. Observe that ANTLR can’t really deal with emojis very properly, so in the event you plan to make use of emojis in your language, run the next python script to demojify your grammar:
import emoji
import sysdef demojify_file(input_file, output_file):
with open(input_file, "r", encoding="utf-8") as f:
input_text = f.learn()
input_text = emoji.demojize(input_text)
with open(output_file, "w", encoding="utf-8") as f:
f.write(input_text)
if __name__ == "__main__":
input_file = sys.argv[1]
output_file = sys.argv[2]
demojify_file(input_file, output_file)
3. Run java -Xmx500M -cp <path_to_antlr.jar> org.antlr.v4.Instrument -Dlanguage=Python3 <your_grammar.g4> to generate your parser
You’ll be able to then import the generated parsing recordsdata and use them as follows:
from antlr4 import *
from EmojiLangLexer import EmojiLangLexer
from EmojiLangParser import EmojiLangParser
from EmojiLangListener import EmojiLangListener
import emojiif __name__ == "__main__":
input_file = sys.argv[1]
with open(input_file, "r", encoding="utf-8") as f:
input_text = f.learn()
input_text = emoji.demojize(input_text)
input_stream = InputStream(input_text)
lexer = EmojiLangLexer(input_stream)
token_stream = CommonTokenStream(lexer)
parser = EmojiLangParser(token_stream)
tree = parser.program()
if parser.getNumberOfSyntaxErrors() > 0:
exit(1)
You most likely received’t must do the demojizing step through which case you should utilize antlr4’s FileStream as an alternative of the InputStream , nevertheless it actually doesn’t matter. Now, we now have a really good summary syntax tree that’s simple to work with, and we will transfer on to the exhausting half — interpreting³
As a result of we’re working with bushes, our interpreter will naturally be a recursive entity. We do have some selections although on how precisely we implement a few of its options. For this tutorial, we are going to construct an interpreter that makes use of environments that bind variables to addresses after which a mutable retailer that maps addresses to values. This concept is pretty frequent, although not ubiquitous, and it permits us to keep up correct scope and assist variable mutation. For ease of implementation, we can even make our interpreter return a standard worth construction.
Values, Shops, and the Surroundings
First, let’s outline what our interpreter can output. We’ve three apparent base circumstances in our EBNF (particularly booleans, strings, and numbers) so let’s create worth objects for these:
class Worth:
def __init__(self, worth):
self.worth = worthdef __str__(self) -> str:
return str(self.worth)
class NumValue(Worth):
def __init__(self, worth: float):
tremendous().__init__(worth)
class StringValue(Worth):
def __init__(self, worth: str):
tremendous().__init__(worth)
class BoolValue(Worth):
def __init__(self, worth: bool):
tremendous().__init__(worth)
To retailer mappings of variables to values, we can even create an surroundings and a retailer:
class EnvLookupException(Exception):
goclass Surroundings:
def __init__(self):
self.vars = {}
def set_var(self, title, addr: int):
self.vars[name] = addr
def get_var(self, title):
if title not in self.vars:
increase EnvLookupException(f"Variable {title} not present in surroundings")
return self.vars[name]
def copy(self):
new_env = Surroundings()
new_env.vars = self.vars.copy()
return new_env
class Retailer:
def __init__(self):
self.retailer = []
def alloc(self, worth: Worth):
self.retailer.append(worth)
return len(self.retailer) - 1
def get(self, addr: int):
if addr >= len(self.retailer):
increase EnvLookupException(f"Deal with {addr} not present in retailer")
return self.retailer[addr]
def set(self, addr: int, worth: Worth):
if addr >= len(self.retailer):
increase EnvLookupException(f"Deal with {addr} not present in retailer")
self.retailer[addr] = worth
Successfully, our surroundings will retailer variable → deal with bindings, and our retailer will maintain deal with → worth bindings. The shop is probably not needed with our present characteristic set, but when we allowed for mutation for pass-by-reference variables, it will be useful⁴.
Ideally, we’d additionally wish to go features as variables, so we’d like another worth to signify them. To do that, we create a closure, which comprises the operate’s parameter, physique, and the surroundings that it was created in:
class ClosureValue(Worth):
# Physique ought to be an antlr4 tree
def __init__(self, param: str, physique: object, env: 'Surroundings'):
tremendous().__init__(None)
self.param = param
self.physique = physique
self.env = envdef __str__(self) -> str:
return f"<operate>"
Chances are you’ll fairly ask about why we’d like the surroundings saved within the operate. Suppose as an alternative that we had a operate worth like this:
class FunctionValue(Worth):
# Physique ought to be an antlr4 tree
def __init__(self, param: str, physique: object):
tremendous().__init__(None)
self.param = param
self.physique = physiquedef __str__(self) -> str:
return f"<operate>"
Now, suppose that we had code equal to the next in our language:
# ----------------
# ENV MUST PERSIST
# ----------------
def f(x):
def g(y):
return x + y
return g(x)print((f(4))(5)) # 9
# ----------------
# ENV MUST CLEAR
# ----------------
def f2(x):
return x + y
def g2(y):
return f(5)
print(f(4)) # Ought to crash
To make sure that y remains to be in scope for g within the high case, we must implement dynamic scoping (scope the place variables are added to the surroundings as this system runs with out being cleared) with out closures, that means that the underside code would really run and print 9. For the underside code to correctly crash although, we will’t implement dynamic scope. Thus we wish the features to successfully bear in mind what surroundings they have been created in — therefore why we add environments to our closure class⁵.
The Interpreter
Now, we’re prepared to put in writing our precise interpreter. In ANTLR, our interpreter will prolong the EmojiLangListener class. We can even have to create a top-level surroundings and provides the interpreter a retailer:
class EmojiLangException(Exception):
goTOP_ENV = Surroundings()
class Interpreter(EmojiLangListener):
def __init__(self):
self.retailer = Retailer()
Now, we have to create an interp methodology that handles all of our expression circumstances. It can find yourself wanting one thing as follows:
def interp(self, prog, env: Surroundings) -> Worth:
if prog.ID():
return self.interp_id(prog.ID())
elif prog.atom():
return self.interp_atom(prog.atom())
elif prog.anonFunctionDefn():
return self.interp_function_defn(prog.anonFunctionDefn())
elif prog.READ_FLOAT():
return self.interp_read_float()
elif prog.READ_STRING():
return self.interp_read_string()
elif prog.printExpr():
return self.interp_print_expr()
elif prog.ifCond():
return self.interp_if(prog.ifCond(), env)
elif prog.sequentialOp():
return self.interp_sequential_op(prog.sequentialOp(), env)
elif prog.baseComputation():
return self.interp_base_computation(prog.baseComputation(), env)
elif prog.varAssignment():
return self.interp_var_assignment(prog.varAssignment(), env)
elif prog.funApplication():
return self.interp_fun_application(prog.funApplication(), env)
Our base circumstances (IDs, atoms, operate definitions, studying, and printing) are pretty easy, so we will simply write them in:
def interp(self, prog, env: Surroundings) -> Worth:
if prog.ID():
return self.retailer.get(env.get_var(prog.ID().getText()))
elif prog.atom():
return self.interp_atom(prog.atom())
elif prog.anonFunctionDefn():
return ClosureValue(prog.anonFunctionDefn().arg.textual content, prog.anonFunctionDefn().physique, env)
elif prog.READ_FLOAT():
strive:
return NumValue(float(enter("> ")))
besides ValueError:
increase EmojiLangException("Anticipated float enter")
elif prog.READ_STRING():
return StringValue(enter("> "))
elif prog.printExpr():
worth = self.interp(prog.printExpr().expr(), env)
if isinstance(worth, StringValue):
# print with out quotes
print(str(worth)[1:-1])
else:
print(worth)
return worth
# ...def interp_atom(self, atm):
if atm.NUMBER():
return NumValue(float(atm.NUMBER().getText()))
elif atm.BOOLEAN():
return BoolValue(atm.BOOLEAN().getText() == ":thumbs_up:")
elif atm.STRING():
return StringValue(atm.STRING().getText())
# THIS SHOULD NEVER HAPPEN
increase EmojiLangException(f"Unknown atom {atm.getText()}")
Our if situation can also be pretty easy. We simply have to interpret the situation after which return the results of deciphering the true case if it is true and the false case if its false. The code is thus simply
def interp_if(self, if_cond, env: Surroundings):
cond = self.interp(if_cond.cond, env)
if not isinstance(cond, BoolValue):
increase EmojiLangException(f"Anticipated boolean when evaluating if situation, obtained {cond}")
return self.interp(if_cond.ontrue if cond.worth else if_cond.onfalse, env)
Sequential operations are equally easy, they simply have to interpret the primary expression after which the second. We are able to thus exchange the code in that block as follows:
def interp(self, prog, env: Surroundings) -> Worth:
# ...
elif prog.sequentialOp():
self.interp(prog.sequentialOp().first, env)
return self.interp(prog.sequentialOp().second, env)
# ...
Subsequent are the bottom computations. This can be a first rate quantity of code since we have to deal with numerous operations, nevertheless it’s not tremendous complicated:
def interp_base_computation(self, base_computation, env: Surroundings):
left, proper = self.interp(base_computation.left, env), self.interp(base_computation.proper, env)
if base_computation.op.textual content == ":plus:":
if isinstance(left, NumValue) and isinstance(proper, NumValue):
return NumValue(left.worth + proper.worth)
elif isinstance(left, StringValue) and isinstance(proper, StringValue):
return StringValue(left.worth + proper.worth)
increase EmojiLangException(f"Can not add {left} and {proper}")
if base_computation.op.textual content == ":heavy_equals_sign:":
if sort(left) != sort(proper):
return BoolValue(False)
if isinstance(left, ClosureValue):
increase EmojiLangException("Can not evaluate features")
return BoolValue(left.worth == proper.worth)# NUMBERS ONLY COMPUTATIONS
if not isinstance(left, NumValue) or not isinstance(proper, NumValue):
increase EmojiLangException(f"Anticipated numbers when evaluating base computation, obtained {left} and {proper}")
if base_computation.op.textual content == ":minus:":
return NumValue(left.worth - proper.worth)
elif base_computation.op.textual content == ":multiply:":
return NumValue(left.worth * proper.worth)
elif base_computation.op.textual content == ":divide:":
if proper.worth == 0:
increase EmojiLangException("Division by zero")
return NumValue(left.worth / proper.worth)
elif base_computation.op.textual content == "≤":
return BoolValue(left.worth <= proper.worth)
Maybe this can be cleaned up a bit with the usage of e.g. dictionaries, however that’s not tremendous vital. Subsequent we now have variable assignments, that are additionally not too difficult. We’ve a pair selections right here on what precisely we wish it to do — particularly, ought to it enable new variables to come back into existence or solely modify present ones? I’ll select the latter case, which makes our code seem like this:
def interp_var_assignment(self, var_assign, env: Surroundings):
worth = self.interp(var_assign.val, env)
addr = env.get_var(var_assign.var.textual content)
self.retailer.retailer[addr] = worth
return worth
Lastly, we now have operate purposes. Right here, we now have to do 4 steps. First, we interpret the operate we’re calling to get our closure. Then, we interpret our argument. Then, we bind the argument into a duplicate of the closure’s surroundings. Lastly, we interpret the closure’s physique within the new surroundings. The code finally ends up wanting as follows:
def interp_fun_application(self, fun_app, env: Surroundings):
closure = self.interp(fun_app.enjoyable, env)
if not isinstance(closure, ClosureValue):
increase EmojiLangException(f"Anticipated operate when evaluating operate software, obtained {closure}")
arg = self.interp(fun_app.arg, env)
new_env = closure.env.copy()
new_env.set_var(closure.param, self.retailer.alloc(arg))
return self.interp(closure.physique, new_env)
Now, our interp is absolutely practical! We want solely modify our major program to run it now on a program:
if __name__ == "__main__":
input_file = sys.argv[1]
with open(input_file, "r", encoding="utf-8") as f:
input_text = f.learn()# Preprocess enter to switch emojis with demojized names
input_text = emoji.demojize(input_text)
input_stream = InputStream(input_text)
lexer = EmojiLangLexer(input_stream)
token_stream = CommonTokenStream(lexer)
parser = EmojiLangParser(token_stream)
tree = parser.program()
if parser.getNumberOfSyntaxErrors() > 0:
exit(1)
interpreter = Interpreter()
interpreter.interp(tree.expr(), TOP_ENV)
We at the moment are lastly prepared to begin writing applications in our language. Right here’s a easy hey world program within the emoji language (EML):
🏃♂️🏃♂️🏃♂️
(🖨️ ("Hey World!"))
🛑🛑🛑
And to run it, we simply do
> python emoji_lang.py helloworld.eml
Hey World!
(the above, after all, assumes that this system is current in a file referred to as helloworld.eml )
Currying
Again within the first part, I famous that our programming language is attention-grabbing as a result of features can solely take one argument. How then can we create an impact just like multivariate features? Take into account, as an illustration, the next python code:
def f(x, y):
return x + yprint(f(3, 4))
f right here has arity 2 — that’s, it takes two arguments. We are able to, nonetheless, write equal code that solely makes use of features of arity one (besides addition) as follows:
def f(x):
def g(y):
return x + y
return gprint((f(3))(4))
The above idea of turning larger arity features into unary features is named currying. It really works for features of any arity — for a operate f of arity n, we will merely carry out currying n-1 instances. In emoji language, this enables us to put in writing a program like this:
🏃♂️🏃♂️🏃♂️
(📋
(🖨️ ("Enter two numbers to compute their sum."))
(🖨️
(🏭
(🏭
(🧑🏭 x ⚒️
(🧑🏭 y ⚒️
((x) ➕ (y))
)
)
(🔢))
(🔢))
)
)
🛑🛑🛑
the Python translation of which is
print("Enter two numbers to compute their sum.")
print(((lambda x: (lambda y: x + y)))(float(enter()))(float(enter())))
Or, extra legibly,
print("Enter two numbers to compute their sum.")def f(x):
def g(y):
return x + y
return g
x = float(enter())
y = float(enter())
print(f(x)(y))
Discover additionally how the primary python iteration used no named features. It seems that we don’t actually need them, although after all they’re helpful for readability. Then we get
> python emoji_lang.py currying.eml
Enter two numbers to compute their sum
> 4
> 5
9.0
Recursion
How can we do a loop or recursion on this language although? We’ve no syntax for for or whereas , and with out names for features, it might appear to be recursion is unattainable.
We are able to, nonetheless, do a neat little trick. Since features are values, we will go features to themselves at any time when we name them, thus permitting them to name themselves.
Take, as an illustration, the next python code:
n = int(enter())
whereas n > 0:
print(n)
n -= 1
We are able to convert this to a recursive model utilizing one thing like this⁶:
def while_loop(situation, physique):
"""
A recursive implementation of some time loop.Arguments
-------------
- situation: Some operate of zero arguments that returns a boolean worth
- physique: Some operate of zero arguments to run whereas the situation returns true
"""
if situation():
physique()
while_loop(situation, physique)
else:
return False
class Field:
def __init__(self, n):
self.n = n
def set_n(self, n):
self.n = n
def get_n(self):
return self.n
n = Field(int(enter()))
def physique():
print(n.get_n())
n.set_n(n.get_n() - 1)
while_loop(lambda: n.get_n() > 0, physique)
However we do have an issue right here — particularly, discover how while_loop calls itself. We are able to’t try this in our language with solely nameless features, so how can we repair that? The reply is that we will do one thing like this:
def while_loop(self, situation, physique):
if situation():
physique()
self(self, situation, physique)
else:
return False# ...
# (outline n as a field)
# ...
def physique():
print(n.get_n())
n.set_n(n.get_n() - 1)
def call_while(loop_func, situation, physique):
loop_func(loop_func, situation, physique)
call_while(while_loop, lambda: n.get_n() > 0, physique)
In impact, we make while_loop take itself as a parameter. Then, we will name self inside while_loop , permitting while_loop to name itself recursively.
We nonetheless, after all, have to lambda-fy and curry this for our language, so we have to make code equal to the next:
(((lambda while_loop:
lambda n:
while_loop(while_loop)
(lambda bogus: n.get_n() > 0)
(lambda bogus: print(n.get_n()) or n.set_n(n.get_n() - 1)))
(lambda self:
lambda cond:
lambda physique:
(physique("BOGUS") or self(self)(cond)(physique)) if cond("BOGUS") else False))
(Field(int(enter()))))
This can be a little bit of a doozy, nevertheless it does work. In emoji lang, this then turns into
🏃♂️🏃♂️🏃♂️
(🏭
(🏭
(🧑🏭 whereas ⚒️
(🧑🏭 n ⚒️
(🏭 (🏭 (🏭 (whereas) (whereas))
(🧑🏭 bogus ⚒️ (🤔 ((n) ≤ (0)) ❓ (👎) : (👍))))
(🧑🏭 bogus ⚒️ (📋
(🖨️ (n))
(📦 n 🔜 ((n) ➖ (1)))
)))
))
😴
Beneath is our whereas operate. Observe that it takes
itself as an argument - this enables for recursion
(there are different methods to do that, however recursion through self
passing is pretty easy)ARGS:
1. self(itself)
2. condition_func (operate of zero arguments that returns a boolean)
3. physique (operate of zero arguments that returns nothing to run whereas true)
RETURNS:
false when completed
⏰
(🧑🏭 self ⚒️
(🧑🏭 condition_func ⚒️
(🧑🏭 physique ⚒️
(
🤔 (🏭 (condition_func) ("BOGUS")) ❓
(📋
(🏭 (physique) ("BOGUS"))
(🏭 (🏭 (🏭 (self) (self))
(condition_func))
(physique))) :
(👎)
))))
)
(🔢))
🛑🛑🛑
Then we get
> python emoji_lang.py while_loop.eml
> 4
4.0
3.0
2.0
1.0
Bonus: The Y Combinator
It’s considerably annoying to go in whereas to itself every time we wish to name it, so what if we may create a model of whereas that already had itself curried? It seems we will with one thing referred to as the Y Combinator. The Y combinator is a operate that appears as follows:
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
It’s fully absurd, nevertheless it permits us to successfully “retailer” a operate in itself. I received’t go into an excessive amount of element about it, however in the event you’d wish to study extra I counsel this excellent article
With the combinator although, we will change our code to the next:
🏃♂️🏃♂️🏃♂️
(🏭
(🏭
(🏭
(🧑🏭 y_combinator ⚒️
(🧑🏭 whereas ⚒️
(🧑🏭 n ⚒️
(📋
🥱y-combinate our whereas
(📦 whereas 🔜 (🏭 (y_combinator) (whereas)))
(🏭 (🏭 (whereas)
(🧑🏭 bogus ⚒️ (🤔 ((n) ≤ (0)) ❓ (👎) : (👍))))
(🧑🏭 bogus ⚒️ (📋
(🖨️ (n))
(📦 n 🔜 ((n) ➖ (1)))
))
)
)
)
)
)
😴
Our y combinator operate - this enables for recursion with out e.g. self passing
by successfully currying the operate and passing it to itself.
⏰
(🧑🏭 fn_nr ⚒️
(🏭
(🧑🏭 cc ⚒️
(🏭 (fn_nr)
(🧑🏭 x ⚒️ (🏭 (🏭 (cc) (cc)) (x)))
)
)
(🧑🏭 cc ⚒️
(🏭 (fn_nr)
(🧑🏭 x ⚒️ (🏭 (🏭 (cc) (cc)) (x)))
)
)
)
)
)
(🧑🏭 whereas ⚒️
(🧑🏭 condition_func ⚒️
(🧑🏭 physique ⚒️
(
🤔 (🏭 (condition_func) ("BOGUS")) ❓
(📋
(🏭 (physique) ("BOGUS"))
(🏭 (🏭 (whereas)
(condition_func))
(physique))) :
(👎)
))))
)
(🔢))
🛑🛑🛑
Now, discover how our name to whereas after it has been y-combinated⁷ solely entails passing the situation and the physique — we don’t have to go itself. and we nonetheless get
> python emoji_lang.py y_comb_while.eml
> 4
4.0
3.0
2.0
1.0
Congratulations! You’ve gotten now hopefully constructed your individual programming language and coded some enjoyable issues in it. Although one thing like EmojiLang clearly doesn’t have a lot actual use, you’ll be able to think about some cool use circumstances for constructing your individual languages, e.g. by creating a brilliant case-specific scripting language to hurry up frequent duties.
In case you’d like some challenges, strive the next workouts:
Train 1: Construct a easy parser and interpreter for the next language with out utilizing ANTLR. Be sure that parenthesis at all times take priority, and that operations in any other case have equal priority (e.g. 4 + 4 * 3 ought to consider to 24 , not 16 )
EXPR = quantity
| EXPR + EXPR
| EXPR - EXPR
| EXPR * EXPR
| EXPR / EXPR
| (EXPR)
Train 2: Modify your above code so as to add operator priority
Train 3 (Difficult): We don’t have to make all of our features nameless. Strive implementing an interpreter for the next language (you should utilize ANTLR, however you’ll have to put in writing your individual .g4 file):
program = (FUNDEF | EXPR)* // a number of operate definitions or expressions// NOTE: <one thing> implies that one thing is a string
// additionally, be at liberty to disregard whitespace or add semicolons or parenthesize
// expressions/fundefs in the event you please
EXPR = quantity
| functionApplication
| computation
FUNDEF = 'def' <title> '(' <args>* '):' EXPR
functionApplication = <title> '(' EXPR* ')' // e.g. f(1, 2+2, g(3))
computation = EXPR + EXPR
| EXPR - EXPR
| EXPR * EXPR
| EXPR / EXPR
| (EXPR)
Train 4 (Simple →Very Very Arduous): .g4 recordsdata for a ton of actual languages could be discovered here. Implement an interpreter for any one among them.
Please contact mchak@calpoly.edu for any inquiries
P.S. Thanks to Brian Jones, my CS 430 professor, for instructing me numerous these things.
All photos by writer until in any other case acknowledged.
