/* templated PEG parser for Calc0 toy language
Module: Parser
Author: Martin.Holzherr@infobrain.com
Date: April 2005
Purpose: demonstrate error handling and direct evaluation during parsing
*/
/*
calc0_grammar: S
( print_variables /
assignement /
full_expression /
Fatal<eExprAssPrintExpected>;
)
S
( '\0' / Fatal<eEndOfInputExpected>) ;
assignement: variable S '=' S expression ;
print_variables: '!'
S
(
identFirst
S
( '-' S ( identLast / Fatal<eIdentExpected> ) )?
)? ;
expression: multiplicative_expression
(S ('+' / '-') S multiplicative_expression)* ;
multiplicative_expression:
power_expression (S ('*' / '/') S power_expression)* ;
power_expression: primary_expression (S '^' S primary_epression)? ;
primary_expression: ('+' / '-')? S
( identifier /
number /
'(' S expression S ( ')' / Fatal<eRParenExpected> ) /
Fatal<eIdentNumOrExprExpected>
) ;
number: ([0-9]+ '.'? / '.' ([0-9] / Fatal<eFracDigitsExpected>) )
[0-9]*
( ('e'|'E') ( '+' / '-' )? ([0-9]+ / Fatal<eExponentDigitsExpected>))?;
identifier: [A-Za-z_][A-Za-z_0-9]* ;
variable: identifier ;
identFirst: identifier ;
identLast: identifier ;
S: [ \r\v\t]* ;
*/
#pragma warning(disable:4786)
#include <map>
#include <string>
#include <cstring>
#include <ostream>
#include "float.h"
#include <exception>
#include <cmath>
#include <set>
#include <vector>
#include <iostream>
#include <iomanip>
#include <sstream>
#include "peg_templ.h"
#include "calc0_templ_parse.h"
namespace calc0_templ{
typedef unsigned char uchar;
inline int CompareStrNoCase(const std::string& s0,const std::string& s1)
{ return stricmp(s0.c_str(),s1.c_str());}
struct CompareNoCase{
bool operator()(const std::string& s0,const std::string& s1)const
{ return CompareStrNoCase(s0,s1)<0;
}
};
typedef std::set<std::string,CompareNoCase> set_istring;
struct Formula{
Formula(std::string e="",double v=0.0,
const set_istring& sUsed=set_istring())
:expression(e),value(v),setUsedIdents(sUsed){}
std::string expression;
double value;
set_istring setUsedIdents;
};
typedef std::map<std::string,Formula,CompareNoCase> NameValue;
NameValue variables;
int g_nNofRecursiveCalls;
const int g_nMaxNofRecursiveCalls=10;
void ExecuteImpl(const char* pCommand,std::ostream& os,std::ostream& errOs);
namespace calc0_templ_parse{
using namespace peg_templ;
struct Calc0_templ_parse_exception : public std::exception{
Calc0_templ_parse_exception(){}
};
struct StateInfo{
StateInfo(const uchar*& src,std::ostream& os,std::ostream& errOs)
:srcStart(src),os(os),errOs(errOs){}
void ErrMsg(const uchar* p, std::string sMsg){
for(int i=0;i<p-srcStart;i++){errOs<<" ";}
for(int j=0;*p && j<3;j++){ errOs << *p++; }
errOs << ".. ";
errOs << sMsg << std::endl;
}
bool Fatal(const uchar* p, std::string sMsg){
ErrMsg(p,sMsg);
throw Calc0_templ_parse_exception();
}
bool Severe(const uchar* p,std::string sMsg){
ErrMsg(p,sMsg);
return true;
}
bool CheckFloatingPointError(const uchar* p,double& result)
{
switch( _fpclass(result) ){
case _FPCLASS_NINF:
Severe(p,"floating point underflow (=-DBL_MAX)");
result= -DBL_MAX;
return true;
case _FPCLASS_PINF:
Severe(p,"floating point overflow (=DBL_MAX)");
result= DBL_MAX;
return true;
case _FPCLASS_SNAN: case _FPCLASS_QNAN:
Severe(p,"result is not a number");
result= 0.0;
return true;
default:
return false;
}
}
std::ostream &os,&errOs;
double result;
std::string sIdent;
set_istring setUsedIdentifiers;
std::string sIdentChars[2];
const uchar* srcStart;
};
enum EParseErrors{ eRParenExpected,
eIdentNumOrExprExpected,
eExprAssPrintExpected,
eEndOfInputExpected,
eFracDigitsExpected,
eExponentDigitsExpected,
eIdentExpected};
template<EParseErrors e>
struct Fatal{
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
switch(e){
case eRParenExpected:
pS->Fatal(p,"closing ')' missing");
case eIdentNumOrExprExpected:
pS->Fatal(p,"identifier, number or '(' expected");
case eExprAssPrintExpected:
pS->Fatal(p,"expression, assignement or '!' expected");
case eEndOfInputExpected:
pS->Fatal(p,"end of input expected");
case eFracDigitsExpected:
pS->Fatal(p,". must be followed by digits");
case eExponentDigitsExpected:
pS->Fatal(p,"e must be followed by digits");
case eIdentExpected:
pS->Fatal(p,"identifier expected");
}
return false;
}
};
struct expression;
struct primary_expression;
typedef And< Or<In<'A','Z','a','z'>,Char<'_'> >,
OptRepeat<
Or<In<'A','Z','a','z','0','9'>,Char<'_'> >
>
> TIdentifier;
struct S{
typedef OptRepeat<OneOfChars<' ','\r','\v','\t'> > rule;
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
return rule::Matches(p,pS);
}
};
struct number{
/*number: ([0-9]+ '.'? / '.' ([0-9] / Fatal<eFracDigitsExpected>) )
[0-9]*
( ('e'|'E')
( '+' / '-' )?
([0-9]+ / Fatal<eExponentDigitsExpected>))?; */
typedef
And<
Or< And<PlusRepeat<In<'0','9'> >,Option<Char<'.'> > >,
And< Char<'.'>,
Or< In<'0','9'>,
Fatal<eFracDigitsExpected>
>
>
>,
OptRepeat<In<'0','9'> >,
Option< And< OneOfChars<'e','E'>,
Option<OneOfChars<'+','-'> >,
Or< PlusRepeat<In<'0','9'> >,
Fatal<eExponentDigitsExpected>
>
>
>
> rule;
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
It p0=p;
if( rule::Matches(p,pS)){
char buf[64];
if( p-p0<64 ){
strncpy(buf,(const char*)p0,p-p0);
buf[p-p0]='\0';
pS->result= atof(buf);
return true;
}else{
pS->Fatal(p,"number too long (64 digits)");
}
}
return false;
}
};
struct identifier{//identifier: [A-Za-z_][A-Za-z_0-9]*;
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{using namespace peg_templ;
It p0=p;
if( TIdentifier::Matches(p,pS) ){
std::string theIdentifier((const char*)p0,p-p0);
if( variables.find(theIdentifier)==variables.end() ){
pS->Severe(p0,
theIdentifier+ " not defined (set to 0.0)");
}
pS->result= variables[theIdentifier].value;
pS->setUsedIdentifiers.insert(theIdentifier);
return true;
}else{
return false;
}
}
};
struct variable{
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{using namespace peg_templ;
It p0=p;
if( TIdentifier::Matches(p,pS) ){
pS->sIdent= std::string((const char*)p0,p-p0);
return true;
}else{
return false;
}
}
};
struct identFirst{
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
It p0= p;
if( TIdentifier::Matches(p,pS) ){
pS->sIdentChars[1]=pS->sIdentChars[0]=
std::string((const char*)p0,p-p0);
return true;
}else{
return false;
}
}
};
struct identLast{
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
It p0= p;
if( TIdentifier::Matches(p,pS) ){
pS->sIdentChars[1]= std::string((const char*)p0,p-p0);
return true;
}else{
return false;
}
}
};
struct primary_expression{
/*primary_expression:
('+' / '-')? S
( identifier /
number /
'(' S expression S ( ')' / Fatal<eRParenExpected> ) /
Fatal<eIdentNumOrExprExpected>
) ;
*/
typedef And<
S,
Or<
identifier,
number,
And<
Char<'('>,
S,
expression,
S,
Or<Char<')'>,Fatal<eRParenExpected> >
>,
Fatal<eIdentNumOrExprExpected>
>
>choices;
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{using namespace peg_templ;
if( And< Char<'-'>,S,choices>::Matches(p,pS) ){
pS->result= -pS->result;
return true;
}else{
return And< Option<Char<'+'> >,S,choices>::Matches(p,pS);
}
}
};
struct power_expression{
/*power_expression: primary_expression (S '^' S primary_epression)?;*/
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{ using namespace peg_templ;
if( primary_expression::Matches(p,pS) ){
double result= pS->result;
if( And<S,Char<'^'>,S,primary_expression>::Matches(p,pS) ){
if( result<=0 && pS->result<0
&& floor(pS->result)!=pS->result ){
pS->Severe(p,"sqrt of negative value illegal");
pS->result= floor(pS->result);
}
pS->result= pow(result,pS->result);
}
return true;
}
return false;
}
};
struct multiplicative_expression{
/*multiplicative_expression:
power_expression (S ( '*' / '/' )S power_expression)* ;*/
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{using namespace peg_templ;
if( power_expression::Matches(p,pS) ){
double result= pS->result;
for(; ;){
S::Matches(p,pS);
if( And<Char<'*'>,S,power_expression>::Matches(p,pS)){
result*= pS->result;
}else if(
And<Char<'/'>,S,power_expression>::Matches(p,pS)){
result/=pS->result;
}else{
pS->result= result;
return true;
}
}
}
return false;
}
};
struct expression{/*expression: multiplicative_expression
(S ('+' / '-') S multiplicative_expression)*; */
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{ using namespace peg_templ;
if( multiplicative_expression::Matches(p,pS) ){
double result= pS->result;
for(;;){
S::Matches(p,pS);
if( And<Char<'+'>,S,
multiplicative_expression>::Matches(p,pS)){
result+= pS->result;
}else if( And<Char<'-'>,S,
multiplicative_expression>::Matches(p,pS)){
result-= pS->result;
}else{
pS->result= result;
return true;
}
}
}
return false;
}
};
struct full_expression //full_expression : expression ;
{ template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{using namespace peg_templ;
if( expression::Matches(p,pS) ){
if( Peek<And<S,Char<'\0'> > >::Matches(p,pS) ){
pS->os << ">> = " << pS->result << std::endl;
}
return true;
}
return false;
}
};
struct print_variables{/*print_variables:
'!' S (identFirst S ( '-' S ( identLast / Fatal<eIdentExpected>) )?)? ; */
typedef And<
Char<'!'>,
S,
Option<
And<
identFirst,
S,
Option<
And<Char<'-'>,
S,
Or<identLast,Fatal<eIdentExpected> >
>
>
>
>
> rule;
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
if( rule::Matches(p,pS) ){
NameValue::iterator it,end;
if( pS->sIdentChars[0].empty() ){
pS->sIdentChars[0]= 'a';
pS->sIdentChars[1]= 'z';
}
it= variables.lower_bound(pS->sIdentChars[0]);
end= variables.upper_bound(pS->sIdentChars[1]);
if( it==end ){
pS->os << "no variable found (try a-z)" << std::endl;
}else{
for( ;it!=end;++it){
pS->os << it->first << "\t"
<< it->second.value << " ("
<< it->second.expression << ")" << std::endl;
}
}
return true;
}
return false;
}
};
struct assignement{/*assignement: variable S '=' S expression ;*/
typedef And<variable,S,Char<'='>,S,expression> rule;
static void ExecuteUsersOf(std::string sFormulaChanged,
StateInfo* pS)
{
if( g_nNofRecursiveCalls++ >= g_nMaxNofRecursiveCalls ){
pS->errOs << "stopped: more than "
<< g_nMaxNofRecursiveCalls
<< " recursive calls " << std::endl;
return;
}
set_istring::iterator itUsedBy;
NameValue::iterator itV;
std::vector<std::string> vecToRecalc;
for(itV= calc0_templ::variables.begin();
itV!=variables.end();
++itV){
for(set_istring::iterator itUsed=
itV->second.setUsedIdents.begin();
itUsed!= itV->second.setUsedIdents.end();
++itUsed){
if( CompareStrNoCase(sFormulaChanged,*itUsed)==0 ){
vecToRecalc.push_back(itV->second.expression);
}
}
}
for(size_t i=0;i<vecToRecalc.size();i++){
ExecuteImpl(vecToRecalc[i].c_str(), pS->os,pS->errOs);
}
}
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{using namespace peg_templ;
if( rule::Matches(p,pS) ){
if( Peek<And<S,Char<'\0'> > >::Matches(p,pS) ){
pS->os << ">> " << pS->sIdent
<< "= " << pS->result << std::endl;
if( pS->CheckFloatingPointError(p, pS->result) ){
pS->os << ">> " << pS->sIdent
<< "= " << pS->result << std::endl;
}
Formula f((const char*)pS->srcStart, pS->result,
pS->setUsedIdentifiers);
std::pair<NameValue::iterator,bool> res=
variables.insert(std::make_pair(pS->sIdent,f));
if( !res.second ){
res.first->second= f;
}
ExecuteUsersOf(pS->sIdent,pS);
}
return true;
}
return false;
}
};
struct calc0_grammar{/*calc0_grammar:
S
(print_variables/assignement/full_expression/Fatal<eExprAssPrintExpected>)
S
('\0' / Fatal<eEndOfInputExpected>) ;*/
typedef And<
S,
Or<
print_variables,
assignement,
full_expression,
Fatal<eExprAssPrintExpected>
>,
S,
Or<Char<0>,Fatal<eEndOfInputExpected> >
> rule;
template<typename It, typename Context>
static bool Matches(It& p,Context* pS)
{
return rule::Matches(p,pS);
}
};
void Parse(const uchar* pSrc,std::ostream& os,std::ostream& errOs)
{
StateInfo stateInfo(pSrc,os,errOs);
stateInfo.os << std::setprecision(16);
try{
calc0_grammar::Matches(pSrc,&stateInfo);
}catch(Calc0_templ_parse_exception){
}
}
}
void ExecuteImpl(const char* pCommand,std::ostream& os,std::ostream& errOs)
{
calc0_templ_parse::Parse((const uchar*)pCommand,os,errOs);
}
void Execute(const char* pCommand,std::ostream& os,std::ostream& errOs)
{
g_nNofRecursiveCalls=0;
ExecuteImpl(pCommand,os,errOs);
g_nNofRecursiveCalls=0;
}
}
Submit an article or tip