You will need to use strings quite a bit, and will not want to worry about memory management for them. A good idea is to create a table of all of the strings that you have seen stored in it. Create such a table. Include a function intern(s) that looks up string s in the table, and returns the string stored for s. If s is not in the table, it should be inserted.
Create a lexical analyzer for SFL using Flex.
Create a header file that defines tokens. It can have a form similar to the following.
#define TOK_DEF 1 #define TOK_END 2 ...Just create a definition for each token.
Some tokens need attributes. Make the attribute be the lexeme. Store the attribute into a variable called yylval, of type YYSTYPE. (There is method in the madness, so do this.) You want YYSTYPE to be a string type.
Create a parser for SFL using Bison.
Initially, the parser should just read a file and either say nothing if the program is syntactically correct, or give an error message if the program is incorrect. If there is a syntax error, the parser should report the line where the error occurs.
Bison manages attributes of tokens automatically. It assumes that the token attribute is in variable yylval, of type YYSTYPE.
Bison also creates its own definition of tokens. Replace your header file for tokens by the one that Bison defines. Failure to do this will cause you trouble.Create a type of syntax trees that describe an expression or definition. Decide on the structure of trees. Define some functions (or constructors) that create particular kinds of nodes in the tree.
Do not try to be too close to the syntax. These trees describe expressions and definitions, they are not direct descriptions of the language syntax. For example, there should be nothing in the syntax tree that corresponds to a parenthesized expression; that is entirely syntactic. You do not need anything that corresponds to a let expression, since those expressions can be translated into a more basic form.
Write two functions that print syntax trees. One should show the details of the structure, and is used for debugging. The other writes the tree in a form that looks similar to the language syntax.
Modify the parser so that it constructs a syntax tree for each definition. After the definition is made, it should make an entry in a table, associating the defined identifier with the syntax tree that it names.
Write an interpreter that evaluates an expression, where the expression is described by a syntax tree. The interpreter should reduce the expression to its simplest form (where no more evaluations can be done) and return that simplified form.
The interpreter should keep track, at each point, of a list of parameter bindings. For example, it might remeber that parameter x was bound to 32. Just keep a list of bindings.
When you store a function, you need to store it as a closure. Augment your syntax trees so that, for each function, you store a list of bindings that were in effect where the function was created. When you use this function, you need to start it out with that list of bindings.
The rules for evaluating expressions should be fairly obvious. Use call-by-value. To evaluate expression A B, first evaluate A, and check that its result is a function. Then evaluate B. Then perform a function application.
Write a program that starts by reading a file of definitions. Then it repeatedly reads expressions or definitions. After reading each one, it prints the expression's value. It should number the expressions, and remember all of the results, by number. To report the third result, type
$3 = ...Allow expressions to contain special form $i, where i is an integer. It refers to the i-th result that was previously computed.