Before implementing a lexer and parser, the syntax and grammar of the language need to be determined first. In this chapter, a TOY language is used to demonstrate how a lexer and a parser can be implemented. The purpose of this recipe is to show how a language is skimmed through. For this purpose, the TOY language to be used is simple but meaningful.
A language typically has some variables, some function calls, some constants, and so on. To keep things simple, our TOY language in consideration has only numeric constants of 32-bit Integer type A, a variable that need not declare its type (like Python, in contrast to C/C++/Java, which require a type declaration) in the TOY language.
The grammar can be defined as follows (the production rules are defined below, with non-terminals on Left Hand Side (LHS) and a combination of terminals and non-terminals on Right Hand Side (RHS); when LHS is encountered, it yields appropriate RHS defined in the production rule):
numeric_expr := number
paran_expr := '(' expression ')'
identifier_expr := identifier := identifier '('expr_list ')'
_expr
is a function call, it will either have no arguments or list of arguments separated by a comma:expr_list := (empty) := expression (',' expression)*
primary := identifier_expr :=numeric_expr :=paran_expr
expression := primary binoprhs
binoprhs := ( binoperator primary )* binoperators := '+'/'-'/'*'/'/'
func_decl := identifier '(' identifier_list ')' identifier_list := (empty) := (identifier)*
def
keyword followed by a function declaration and an expression that defines its body:function_defn := 'def' func_decl expression
toplevel_expr := expression
An example of the TOY language based on the previously defined grammar can be written as follows:
def foo (x , y) x +y * 16
Since we have defined the grammar, the next step is to write a lexer and parser for it.
18.226.185.196