PEG grammar to accept late definition

Question

I want to write a PEG parser with PackCC (but also peg/leg or other libraries are possible) which is able to calculate some fields with variables on random position. The first simplified approach is the following grammar:

%source {                                                                      
  int vars[256];                                                                
}                                                            

statement <- e:term EOL      { printf("answer=%d\n", e); }                     

term <- l:primary 
      ( '+' r:primary        { l += r; }                                   
      / '-' r:primary        { l -= r; }
      )*                     { $$ = l; }                               
      / i:var '=' s:term     { $$ = vars[i] = s; }                             
      / e:primary            { $$ = e; }             

primary <- < [0-9]+ >        { $$ = atoi($1); }              
         / i:var !'='        { $$ = vars[i]; }                                    

var <- < [a-z] >             { $$ = $1[0]; }                                      

EOL    <- '\n' / ';'                                              

%%     

When testing with sequential order, it works fine:

a=42;a+1
answer=42
answer=43

But when having the variable definition behind the usage, it fails:

a=42;a+b;b=1
answer=42
answer=42
answer=1

And even deeper chained late definitions shall work, like:

a=42;a+b;b=c;c=1
answer=42
answer=42
answer=0
answer=1

Lets think about the input not as a sequential programming language, but more as a Excel-like spreadsheet e.g.:

A1: 42
A2: =A1+A3
A3: 1

Is it possible to parse and handle such kind of text with a PEG grammar?

Is two-pass or multi-pass an option here?

Or do I need to switch over to old style lex/yacc flex/bison?

Answer 1

I'm not familiar with PEG per se, but it looks like what you have is an attributed grammar where you perform the execution logic directly within the semantic action.

That won't work if you have use before definition.

You can use the same parser generator but you'll probably have to define some sort of abstract syntax tree to capture the semantics and postpone evaluation until you've parsed all input.

Answer 2

Yes, it is possible to parse this with a PEG grammar. PEG is effectively greedy LL(*) with infinite lookahead. Expressions like this are easy.

But the grammar you have written is left recursive, which is not PEG. Although some PEG parsers can handle left recursion, until you're an expert it's best to avoid it, and use only right recursion if needed.