Click here to Skip to main content
12,955,493 members (59,754 online)
Click here to Skip to main content


195 bookmarked
Posted 13 Apr 2005

Crafting an interpreter Part 1 - Parsing and Grammars

, 29 Apr 2005 CPOL
First of a series of articles on building a language interpreter, describing basics about parsing and grammars.
/*  procedural version of Parsing Expression Grammar implementation
	implements the following operations: 
	[A-Za-z] ;	'for' ; e1 e2 ; e1 / e2 ;  e? ; &e ; !e ; .
	the inline functions expect a 'const unsigned char*' as iterator.
	The implementation uses negative values internally to cope with default
	Caution: This is an implementation to demonstrate the concept of PEG's.
#ifndef PEGPROC_H_
#define PEGPROC_H_
namespace peg_proc{//parsing-expression-grammar "procedural" version

typedef unsigned char uchar;

#define PEG_OR2(pSave,p,alt1,alt2)\
        ( (pSave=p,alt1)||(p=pSave,alt2)||(p=pSave,false) )
#define PEG_OR3(pSave,p,alt1,alt2,alt3)\
        ( (pSave=p,alt1)||(p=pSave,alt2)||(p=pSave,alt3)||(p=pSave,false) )
#define PEG_OR4(pSave,p,alt1,alt2,alt3,alt4) \
        ( (pSave=p,alt1)||(p=pSave,alt2)||\
          (p=pSave,alt3)||(p=pSave,alt4)||(p=pSave,false) )
#define PEG_OR5(pSave,p,alt1,alt2,alt3,alt4,alt5) \
        ( (pSave=p,alt1)||(p=pSave,alt2)||\
          (p=pSave,alt3)||(p=pSave,alt4)||(p=pSave,alt5)||(p=pSave,false) )

#define PEG_OPTION(pSave,p,option)  (pSave=p,((option)||(p=pSave,true)))
#define PEG_OPTION_GET(pSave,p,pGet,option)\
#define PEG_AND(pSave,p,sequence)   (pSave=p,((sequence)||(p=pSave,false)))
#define PEG_PEEK(pSave,p,expr)      (pSave=p,(expr)?(p=pSave,true):(p=pSave,false))
#define PEG_NOT(pSave,p,expr)       (pSave=p,(expr)?(p=pSave,false):(p=pSave,true))

// the optimizer should remove cases with default arguments
    inline bool In(const uchar*& p,
                    int cFirst1,int cLast1,
					int cFirst2=-1,int cLast2=-1,
					int cFirst3=-1,int cLast3=-1,
                    int cFirst4=-1,int cLast4=-1)
	{	return *p>=cFirst1 && *p<=cLast1
			|| *p>=cFirst2 && *p<=cLast2 
			|| *p>=cFirst3 && *p<=cLast3
            || *p>=cFirst4 && *p<=cLast4 ? (++p,true)	: false;
    inline bool Char(const uchar*& p,int c)
    {	return *p==c?(++p,true) : false;}
    inline bool OneOfChars(const uchar*& p,
        int c1, int c2,int c3=-1, int c4=-1,
        int c5=-1,int c6=-1,int c7=-1,int c8=-1){
        return *p==c1||*p==c2||*p==c3||*p==c3||*p==c4||*p==c5 
            || *p==c6||*p==c7||*p==c8
                ?	(++p,true) : false; 
    inline bool OneOfCharsGet(const uchar*& p,int* pToGet,
        int c1, int c2,int c3=-1, int c4=-1,
        int c5=-1,int c6=-1,int c7=-1,int c8=-1){
        if( OneOfChars(p,c1,c2,c3,c4,c5,c6,c7,c8) ){
            *pToGet= p[-1];
            return true;
            return false;

    inline bool String(const uchar*& p,
        int c1, int c2=-1,int c3=-1,int c4=-1,int c5=-1,
        int c6=-1,int c7=-1){
        const uchar* p0=p;
        return PEG_AND(p0,p,
            && (c2==-1||Char(p,c2))
            && (c3==-1||Char(p,c3))
            && (c4==-1||Char(p,c4))
            && (c5==-1||Char(p,c5))
            && (c6==-1||Char(p,c6))
            && (c7==-1||Char(p,c7))

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Switzerland Switzerland
No Biography provided

You may also be interested in...

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170525.1 | Last Updated 29 Apr 2005
Article Copyright 2005 by Martin.Holzherr
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid