User's guide

A framework for parsing program source files.

• greedy, prioritized PEG parser
• interpreted grammar rules (rather than hard-coded)
• grammar rules encoded as a graph of Grammar_ objects
• simplified backrat algorithm

Functional view

• look for an expected token in the token stream, without fetching it;
• fetch an accepted token in order to move on in the token stream;
• generate a 'syntax error' message for an unacceptable token in the stream, listing the tokens that would have been accepted;
• store back into the stream a sequence of fetched tokens that turns out to be unacceptable, to give way to another interpretation or to display a syntax error with contextual information (i.e. the tokens recognized thus far).

Parsing source file implies a context-free grammar. Such a grammar describes how an addition is written, a function call, etc.. in the source file. Here, a grammar is described as a PEG (parsing expression grammar) instead of the classical Backus-Naur Form (BNF). The improved formalism of PEG imports some features of regular expressions so that :

• pattern matching is greedy (with suppression of some ambiguity and improved performance);
• matching against several patterns is ordered and thus prioritized (simplifying pattern selection);
• 2 predicates check for respectively the presence (the absence) of a pattern without fetching it (providing additional expressive power).

Grammar_.h provides a framework for encoding grammar rules in PEG and interpreting them. The root grammar rule can be repeatedly applied to a stream of terminal tokens (from Lexer_.h), in order to convert it into a stream of syntactic trees (where an addition is a 'composite token' with 2 'child tokens'). The parser uses a simplified backrat algorithm to match grammar rules : during backtracking, only the latest, partial pattern match is saved (instead of all pattern matches).

Example

PEG Grammar - identical to the BNF grammar in this case :

root::= (variable | function)*
variable ::= 'int'?  identifier  ';'
function ::= identifier  '()'  '{'  variable*  '}' 

Input :

int var;
;
foo(){var;var;}
foo2(){;}

Output :

[token 2 declares int var]    This may  be customized
minimalFile:5 - syntax error : ';' found instead of <anIdentifier>, 'int'
[token 5 declares foo()]
[token 8 declares var]
[token 10 declares var]
[<{<noToken>}>]               These are the curly braces that need no particularly handling
[token 13 declares foo2()]
minimalFile:17 - syntax error after '{' : ';' found instead of <anIdentifier>, 'int', '}'
minimalFile:17 - syntax error : ';' found instead of <anIdentifier>, 'int', '}'
minimalFile:18 - syntax error : '}' found instead of <anIdentifier>, 'int'

static view

Grammar encoding

GrammarSwitch will be evaluated in given order (prioritized parsing). GrammarLoop consumes as much input as possible (greedy parsing).

Recommendation : within a GrammarSwitch( ..) or EITHER( ..), use only THE(), A_() and &aRule [ and no SEQUENCE(), EITHER(), etc.., so that the syntactic tree generated can easily be identified by its type_ field]

Example (as in functional view above)

enum { declarationSyntax=1, functionSyntax };    // passed to pSink->handlePattern( int, SyntacticTree*);

TerminalToken int_( "int"), 
  semicolon_( ";"), 
  braces_( "()"), 
  leftBrace( "{"), 
  rightBrace( "}");
const char* identifier_= "anIdentifier";   // the string that appears in error reports
  // implementation note : unique string shared by all A_( identifier_), for fast pattern matching

GrammarSequence variable_( MAYBE( THE( int_)), A_( identifier_), THE( semicolon_), HANDLE( declarationSyntax), 0);
GrammarSequence function_( A_( identifier_), THE( braces_), HANDLE( functionSyntax), 
  THE( leftBrace), HANDLE_ANY( &variable_), THE( rightBrace), 0);

GrammarLoop root_( EITHER( &variable_, &function_, 0));
  // implementation note : '&' before 'variable_' is unavoidable 
  // because a variable parameter list cannot hold a reference like just 'variable_'

Operation :

class C_tokenFiles : TokenStream {};   // user-supplied lexical analyser, derived from Lexer_
class MinimalSink : SyntacticSink {      // user-supplied handler
  bool handlePattern( int i_, SyntacticTree* t_);
  };
  
main() {
  Token_::currentOut= stderr;  // (or stdout) select destination of error messages

  C_tokenFiles source_;
  if (source_.set_( "path/fn.c") ==0)
    printf( "cannot open file 'path/fn.c'\n");
  
  MinimalSink sink_;
  root_.parseFromTo( &source_, &sink_);
  }

Syntactic trees reported :

minimalSink.handlePattern( declarationSyntax, SyntacticTree( variable_.type_, int_, VariableToken( identifier_, "var"), semicolon_, 0))
//c_tokenFile.printWarning();
minimalSink.handlePattern( functionSyntax, SyntacticTree( function_.type_, VariableToken( identifier_, "foo"), braces_, 0)
minimalSink.handlePattern( declarationSyntax, SyntacticTree( variable_.type_, noToken, VariableToken( identifier_, "var"), semicolon_, 0))
minimalSink.handlePattern( declarationSyntax, SyntacticTree( variable_.type_, noToken, VariableToken( identifier_, "var"), semicolon_, 0))
//c_tokenFile.printWarning();
minimalSink.handle_( SyntacticTree( 0, leftBrace, SyntactiTree( 0, noToken, 0), rightBrace, 0);
minimalSink.handlePattern( functionSyntax, SyntacticTree( function_.type_, VariableToken( identifier_, "foo"), braces_, 0)
//c_tokenFile.printWarning();
//c_tokenFile.printWarning();
//c_tokenFile.printWarning();