Skip to content

Instantly share code, notes, and snippets.

@mikearmstrong001
Created November 5, 2014 09:35
Show Gist options
  • Save mikearmstrong001/c87682bbd5753e71204e to your computer and use it in GitHub Desktop.
Save mikearmstrong001/c87682bbd5753e71204e to your computer and use it in GitHub Desktop.
Playing with simple grammar to cpp recursive descent
BoolExpression =
Expression "==" Expression
Expression ">=" Expression
Expression "<=" Expression
Expression ">" Expression
Expression "<" Expression
.
IfStatement =
"if" "(" BoolExpression ")" Block "else" IfStatement
"if" "(" BoolExpression ")" Block "else" Block
"if" "(" BoolExpression ")" Block
.
AddSubOp =
"+"
"-"
.
ExpressionCont *
AddSubOp Expression
.
Expression =
Term ExpressionCont
.
MulDivOp =
"*"
"/"
.
TermCont *
MulDivOp Term
.
Term =
Factor TermCont
.
Factor =
"(" Expression ")"
"-" Factor
ident
.
AssignStatement =
ident "=" Expression ";"
.
DoStatement =
"do" Block "while" "(" BoolExpression ")"
.
WhileStatement =
"while" "(" BoolExpression ")" Block
.
Statement =
IfStatement
AssignStatement
DoStatement
WhileStatement
Block
.
Statements *
Statement
.
Block =
"{" Statements "}"
.
Type =
"int"
"uint"
"float"
.
ReturnType =
Type
"void"
.
Arg =
Type ident
.
MoreArgs *
"," Arg
.
Args =
Arg MoreArgs
.
Func =
"func" ReturnType ident "(" Args ")" Block
"func" ReturnType ident "(" ")" Block
.
Var =
"var" Type ident ";"
.
FuncVar =
Func
Var
.
FuncVarDecls *
FuncVar
.
Program =
FuncVarDecls
.
#include "lang.bnfish.h"
#include "parseinfo.h"
bool BoolExpression( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Expression(pi)
&& match( pi, "==" )
&& Expression(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& Expression(pi)
&& match( pi, ">=" )
&& Expression(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& Expression(pi)
&& match( pi, "<=" )
&& Expression(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& Expression(pi)
&& match( pi, ">" )
&& Expression(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& Expression(pi)
&& match( pi, "<" )
&& Expression(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool IfStatement( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "if" )
&& match( pi, "(" )
&& BoolExpression(pi)
&& match( pi, ")" )
&& Block(pi)
&& match( pi, "else" )
&& IfStatement(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "if" )
&& match( pi, "(" )
&& BoolExpression(pi)
&& match( pi, ")" )
&& Block(pi)
&& match( pi, "else" )
&& Block(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "if" )
&& match( pi, "(" )
&& BoolExpression(pi)
&& match( pi, ")" )
&& Block(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool AddSubOp( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "+" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "-" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool ExpressionCont( ParseInfo &_pi )
{
ParseInfo pi(_pi);
while ( 1
&& AddSubOp(pi)
&& Expression(pi)
)
{ }
pi.commit(_pi);
return true;
}
bool Expression( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Term(pi)
&& ExpressionCont(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool MulDivOp( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "*" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "/" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool TermCont( ParseInfo &_pi )
{
ParseInfo pi(_pi);
while ( 1
&& MulDivOp(pi)
&& Term(pi)
)
{ }
pi.commit(_pi);
return true;
}
bool Term( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Factor(pi)
&& TermCont(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Factor( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "(" )
&& Expression(pi)
&& match( pi, ")" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "-" )
&& Factor(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& ident(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool AssignStatement( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& ident(pi)
&& match( pi, "=" )
&& Expression(pi)
&& match( pi, ";" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool DoStatement( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "do" )
&& Block(pi)
&& match( pi, "while" )
&& match( pi, "(" )
&& BoolExpression(pi)
&& match( pi, ")" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool WhileStatement( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "while" )
&& match( pi, "(" )
&& BoolExpression(pi)
&& match( pi, ")" )
&& Block(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Statement( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& IfStatement(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& AssignStatement(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& DoStatement(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& WhileStatement(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& Block(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Statements( ParseInfo &_pi )
{
ParseInfo pi(_pi);
while ( 1
&& Statement(pi)
)
{ }
pi.commit(_pi);
return true;
}
bool Block( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "{" )
&& Statements(pi)
&& match( pi, "}" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Type( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "int" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "uint" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "float" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool ReturnType( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Type(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "void" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Arg( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Type(pi)
&& ident(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool MoreArgs( ParseInfo &_pi )
{
ParseInfo pi(_pi);
while ( 1
&& match( pi, "," )
&& Arg(pi)
)
{ }
pi.commit(_pi);
return true;
}
bool Args( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Arg(pi)
&& MoreArgs(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Func( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "func" )
&& ReturnType(pi)
&& ident(pi)
&& match( pi, "(" )
&& Args(pi)
&& match( pi, ")" )
&& Block(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& match( pi, "func" )
&& ReturnType(pi)
&& ident(pi)
&& match( pi, "(" )
&& match( pi, ")" )
&& Block(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool Var( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& match( pi, "var" )
&& Type(pi)
&& ident(pi)
&& match( pi, ";" )
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool FuncVar( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& Func(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
if ( 1
&& Var(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
bool FuncVarDecls( ParseInfo &_pi )
{
ParseInfo pi(_pi);
while ( 1
&& FuncVar(pi)
)
{ }
pi.commit(_pi);
return true;
}
bool Program( ParseInfo &_pi )
{
ParseInfo pi(_pi);
if ( 1
&& FuncVarDecls(pi)
)
{
pi.commit(_pi);
return true;
}
_pi.commit(pi);
return false;
}
#include "parseinfo.h"
bool BoolExpression( ParseInfo &_pi );
bool IfStatement( ParseInfo &_pi );
bool AddSubOp( ParseInfo &_pi );
bool ExpressionCont( ParseInfo &_pi );
bool Expression( ParseInfo &_pi );
bool MulDivOp( ParseInfo &_pi );
bool TermCont( ParseInfo &_pi );
bool Term( ParseInfo &_pi );
bool Factor( ParseInfo &_pi );
bool AssignStatement( ParseInfo &_pi );
bool DoStatement( ParseInfo &_pi );
bool WhileStatement( ParseInfo &_pi );
bool Statement( ParseInfo &_pi );
bool Statements( ParseInfo &_pi );
bool Block( ParseInfo &_pi );
bool Type( ParseInfo &_pi );
bool ReturnType( ParseInfo &_pi );
bool Arg( ParseInfo &_pi );
bool MoreArgs( ParseInfo &_pi );
bool Args( ParseInfo &_pi );
bool Func( ParseInfo &_pi );
bool Var( ParseInfo &_pi );
bool FuncVar( ParseInfo &_pi );
bool FuncVarDecls( ParseInfo &_pi );
bool Program( ParseInfo &_pi );
// lang.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string>
#include <vector>
#include <assert.h>
#include "parseinfo.h"
struct Parser
{
std::string str;
std::string::size_type cursor;
Parser() : cursor(0)
{
}
Parser( std::string &ln ) : str(ln), cursor(0)
{
}
void read( const char *filename )
{
FILE *f = fopen( filename, "rb" );
if ( f == NULL )
{
return;
}
fseek( f, 0, SEEK_END );
int p = ftell( f );
fseek( f, 0, SEEK_SET );
str.resize( p );
fread( &str[0], 1, p, f );
fclose( f );
cursor = 0;
}
std::string token()
{
if ( cursor == std::string::npos )
{
return "";
}
std::string::size_type s = str.find_first_not_of( " \t\n\r", cursor );
if ( s == std::string::npos )
{
return "";
}
std::string::size_type e = str.find_first_of( " \t\n\r", s );
cursor = e;
if ( e == std::string::npos )
{
return str.substr( s );
}
return str.substr( s, (e-s) );
}
void skipws()
{
cursor = str.find_first_not_of( " \t\n\r", cursor );
}
bool eof()
{
if ( cursor == std::string::npos )
{
return true;
}
std::string::size_type s = str.find_first_not_of( " \t\n\r", cursor );
if ( s == std::string::npos )
{
return true;
}
return false;
}
void expect( const char *e )
{
std::string t = token();
assert( t == e );
}
bool test( const char *e )
{
std::string::size_type c = cursor;
std::string t = token();
if ( t == e )
{
return true;
}
cursor = c;
return false;
}
std::string peek()
{
std::string::size_type c = cursor;
std::string t = token();
cursor = c;
return t;
}
std::string readline()
{
if ( cursor == std::string::npos )
{
return "";
}
std::string::size_type s = str.find_first_not_of( "\n", cursor );
if ( s == std::string::npos )
{
return "";
}
std::string::size_type e = str.find_first_of( "\n", s );
cursor = e;
if ( e == std::string::npos )
{
return str.substr( s );
}
return str.substr( s, (e-s) );
}
std::string extractclosing()
{
std::string::size_type s = cursor;
int open = 0;
do
{
std::string t = token();
if ( t == "(" || t == "[" || t == "{" )
{
open++;
}
if ( t == ")" || t == "]" || t == "}" )
{
open--;
}
} while ( open );
if ( cursor == std::string::npos )
{
return str.substr( s );
} else
{
return str.substr( s, (cursor-s) );
}
}
};
void ParseState( FILE *cpp, FILE *hdr, Parser &p )
{
std::string tok = p.token();
if ( p.test( "*" ) )
{
p.skipws();
fprintf( hdr, "bool %s( ParseInfo &_pi );\n", tok.c_str() );
fprintf( cpp, "bool %s( ParseInfo &_pi )\n", tok.c_str() );
fprintf( cpp, "{\n", tok.c_str() );
fprintf( cpp, "\tParseInfo pi(_pi);\n" );
//tok = p.token();
std::string ln = p.readline();
Parser lnp( ln );
fprintf( cpp, "\twhile ( 1\n" );
while ( !lnp.eof() )
{
std::string c = lnp.token();
if ( c[0] == '"' )
{
fprintf( cpp, "\t\t&& match( pi, %s )\n", c.c_str() );
} else
{
fprintf( cpp, "\t\t&& %s(pi)\n", c.c_str() );
}
}
fprintf( cpp, "\t\t )\n" );
fprintf( cpp, "\t{ }\n" );
p.expect( "." );
fprintf( cpp, "\tpi.commit(_pi);\n" );
fprintf( cpp, "\treturn true;\n" );
fprintf( cpp, "}\n\n", tok.c_str() );
} else
{
p.expect( "=" );
p.skipws();
fprintf( hdr, "bool %s( ParseInfo &_pi );\n", tok.c_str() );
fprintf( cpp, "bool %s( ParseInfo &_pi )\n", tok.c_str() );
fprintf( cpp, "{\n", tok.c_str() );
fprintf( cpp, "\tParseInfo pi(_pi);\n" );
while ( !p.test( "." ) )
{
std::string ln = p.readline();
Parser lnp( ln );
fprintf( cpp, "\tif ( 1\n" );
while ( !lnp.eof() )
{
std::string c = lnp.token();
if ( c[0] == '"' )
{
fprintf( cpp, "\t\t&& match( pi, %s )\n", c.c_str() );
} else
{
fprintf( cpp, "\t\t&& %s(pi)\n", c.c_str() );
}
}
fprintf( cpp, "\t\t )\n" );
fprintf( cpp, "\t{\n" );
fprintf( cpp, "\t\tpi.commit(_pi);\n" );
fprintf( cpp, "\t\treturn true;\n" );
fprintf( cpp, "\t}\n" );
fprintf( cpp, "\t_pi.commit(pi);\n");
}
fprintf( cpp, "\treturn false;\n" );
fprintf( cpp, "}\n\n", tok.c_str() );
}
}
void test( std::string const &str );
#define STR(a) #a
const char *testprog = STR(
func void a()
{
if ( a == b )
{
}
}
func void b( int g )
{
t = 5 + 7 * 8;
}
func void c( int g , float f )
{
{
}
}
var int t;
);
int _tmain(int argc, _TCHAR* argv[])
{
test( testprog );
Parser p;
p.read( "E:\\Dev\\mike\\lang\\lang.bnfish" );
FILE *cpp = fopen( "lang.bnfish.cpp", "wb" );
FILE *hdr = fopen( "lang.bnfish.h", "wb" );
fprintf( cpp, "#include \"lang.bnfish.h\"\n" );
fprintf( cpp, "#include \"parseinfo.h\"\n" );
fprintf( hdr, "#include \"parseinfo.h\"\n" );
while ( !p.eof() )
{
ParseState( cpp, hdr, p );
}
fclose( hdr );
fclose( cpp );
return 0;
}
bool match( ParseInfo &_pi, const char *test )
{
ParseInfo pi(_pi);
if ( pi.test( test ) )
{
pi.commit(_pi);
return true;
}
return false;
}
bool ident( ParseInfo &_pi )
{
ParseInfo pi(_pi);
std::string t = pi.ident();
pi.commit(_pi);
return true;
}
#include "lang.bnfish.h"
void test( std::string const &str )
{
ParseInfo pi;
pi.str = &str;
bool r = Program( pi ) && pi.cursor==std::string::npos;
}
bool BoolExpression( ParseInfo &_pi );
bool IfStatement( ParseInfo &_pi );
bool StatementExpression( ParseInfo &_pi );
bool Statement( ParseInfo &_pi );
bool Statements( ParseInfo &_pi );
bool Block( ParseInfo &_pi );
bool Type( ParseInfo &_pi );
bool Arg( ParseInfo &_pi );
bool MoreArgs( ParseInfo &_pi );
bool Args( ParseInfo &_pi );
bool Func( ParseInfo &_pi );
bool Var( ParseInfo &_pi );
bool FuncVar( ParseInfo &_pi );
bool FuncVarDecls( ParseInfo &_pi );
bool Program( ParseInfo &_pi );
#pragma once
#include <string>
#include <stdio.h>
#include <assert.h>
bool match( struct ParseInfo &_pi, const char *test );
bool ident( struct ParseInfo &_pi );
struct ParseInfo
{
const std::string *str;
std::string::size_type cursor;
ParseInfo() : str(NULL), cursor(0)
{
}
void read( const char *filename )
{
FILE *f = fopen( filename, "rb" );
if ( f == NULL )
{
return;
}
fseek( f, 0, SEEK_END );
int p = ftell( f );
fseek( f, 0, SEEK_SET );
std::string *s = new std::string();
s->resize( p );
fread( &(*s)[0], 1, p, f );
fclose( f );
str = s;
cursor = 0;
}
std::string token()
{
if ( cursor == std::string::npos )
{
return "";
}
std::string::size_type s = str->find_first_not_of( " \t\n\r", cursor );
if ( s == std::string::npos )
{
return "";
}
const char *twochar[] = { "==", "!=", ">=", "<=", NULL };
for (int i=0; twochar[i]; i++)
{
std::string::size_type sc = str->substr(s, 2).find(twochar[i] );
if ( sc != std::string::npos )
{
cursor = s + 2;
if ( cursor >= str->size() )
{
cursor = std::string::npos;
}
return str->substr( s, 2 );
}
}
std::string::size_type sc = str->substr(s, 1).find_first_of( "[](){};,.:" );
if ( sc != std::string::npos )
{
cursor = s + 1;
if ( cursor >= str->size() )
{
cursor = std::string::npos;
}
return str->substr( s, 1 );
}
std::string::size_type e = str->find_first_of( " \t\n\r", s );
cursor = e;
if ( e == std::string::npos )
{
return str->substr( s );
}
return str->substr( s, (e-s) );
}
std::string ident()
{
if ( cursor == std::string::npos )
{
return "";
}
std::string::size_type s = str->find_first_not_of( " \t\n\r", cursor );
if ( s == std::string::npos )
{
return "";
}
std::string::size_type e = str->find_first_of( " \t\n\r()[];", s );
cursor = e;
if ( e == std::string::npos )
{
return str->substr( s );
}
return str->substr( s, (e-s) );
}
void skipws()
{
cursor = str->find_first_not_of( " \t\n\r", cursor );
}
bool eof()
{
if ( cursor == std::string::npos )
{
return true;
}
std::string::size_type s = str->find_first_not_of( " \t\n\r", cursor );
if ( s == std::string::npos )
{
return true;
}
return false;
}
void expect( const char *e )
{
std::string t = token();
assert( t == e );
}
bool test( const char *e )
{
std::string::size_type c = cursor;
std::string t = token();
if ( t == e )
{
return true;
}
cursor = c;
return false;
}
std::string peek()
{
std::string::size_type c = cursor;
std::string t = token();
cursor = c;
return t;
}
std::string readline()
{
if ( cursor == std::string::npos )
{
return "";
}
std::string::size_type s = str->find_first_not_of( "\n", cursor );
if ( s == std::string::npos )
{
return "";
}
std::string::size_type e = str->find_first_of( "\n", s );
cursor = e;
if ( e == std::string::npos )
{
return str->substr( s );
}
return str->substr( s, (e-s) );
}
std::string extractclosing()
{
std::string::size_type s = cursor;
int open = 0;
do
{
std::string t = token();
if ( t == "(" || t == "[" || t == "{" )
{
open++;
}
if ( t == ")" || t == "]" || t == "}" )
{
open--;
}
} while ( open );
if ( cursor == std::string::npos )
{
return str->substr( s );
} else
{
return str->substr( s, (cursor-s) );
}
}
void commit( ParseInfo &o )
{
o.cursor = cursor;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment