Scheme Parser (written for YACC)
This is a C compiler directive used so that I can print out positive reinforcement like " Successful parse ".
%{
#include <stdio.h>
%}
>
%token AMPERSAND ASTERISK ATOM CARET COLON DEFINE DOLLAR EQUAL EXCLAMATION FORESLASH GREATER HYPHEN ID INT LAMBDA LESS LET LPAREN PERCENT PERIOD PLUS QUESTION REAL RPAREN STRING TILDE UNDERSCORE UNKNOWN %%A program is defined as a statement list, followed by an expression. For example,
(define square
(lambda (n)
(* n n)))
(square 5)
is a simple program. The first section (contained within the parentheses associated with the define) is a function definition, which is an example of a statement, one of which can be classified as a statement list, as defined below. The portion (square 5) is an expression because it can be evaluated to some value, in this case, 25.
program : stmtlist expr {printf("Successful parse!");};
An expression list is defined recursively as an exprlist followed by an expression or nothing. So, an expression, as defined below, can be combined with another expression to form an expression list. An example of an expression list:
(square 5) (square .25) (square -.5) (square 10)
exprlist: exprlist expr |;An statement list is defined recursively as an stmtlist followed by an statement, or nothing. This way, an statement can be an statement list, just an statement, or nothing. That is, since a program consists of a statement list and an expression, that statement list can have numerous functions and procedures defined in it to produce a desired result. An example of a statement list:
(define square expr) (define cube expr)
stmtlist: stmtlist stmt |;A statement is defined as a left parenthesis followed by the keyword define and an identifier, an expression, and then a right parenthesis. An example:
(define square expr)
stmt: LPAREN DEFINE ID expr RPAREN;An expression can be any following: an identifier (ID), an ATOM (which is essentially useless in this definition of the syntax of the language, but that is the terminology used in the Scheme language), an integer (INT), a REAL, a STRING, or any of a number of more complex constructions: Examples:
ID: square ATOM: george INT: 2 REAL: 2.5 STRING: "george"1) left parenthesis, an identifier, an expression list, and a right parenthesis. Example:
(square 5)
2) left parenthesis, the keyword let, left parenthesis, a pairlist, right parenthesis, an expression, and a right parenthesis. Example:
(let (x 5) (y 6) (+ x y))
3) left parenthesis, the keyword lambda, left parenthesis, an identifier list, right parenthesis, an expression, and a right parenthesis. Example:
(lambda (x) (+ x 1))
expr: ID | ATOM | INT | REAL | STRING |
LPAREN ID exprlist RPAREN
|LPAREN LET LPAREN pairlist RPAREN expr RPAREN
|LPAREN LAMBDA LPAREN idlist RPAREN expr RPAREN;
An identifier list is simply defined recursively so that it could be an identifier list, an identifier, or nothing. Example:
square cube quad
idlist: idlist ID |;A pairlist is defined as any number of pairs, but must include at least one. (x 5) (y 6)
pairlist: pairlist pair | pair;A pair is defined as simply an identifier followed by an expression. Example:
(x 5)
pair: ID expr;The following code is YACC code used in the parsing of input.
%%
yyerror(char *s){
fprintf(stderr,"%s\n",s);
}
int
yywrap(){
return 1;
}
void
main()
{
yyparse();
}
This paper is divided into six sections:
Scheme Introduction
Scheme Lexer (Scanner) with explanation
Scheme Yacc Parser with explanation
Scheme Semantic Structure with explanation
Special Feature: Continuations and their use in Scheme
An Example of a Scheme program