How to write recursive descent parser for call expression?

Question

I have next rules:

factor ::= id | func | ( expr )  
func ::= id ( list )  
list ::= list , expr | expr

I write simple descent parser:

function factor() {
  if (lookahead === "(") {
    match("(");
    expr();
    return match(")");
  } else {
    id();
  } // How to understand what it can be a func here?
};

function func() {
  id();
  match("(");
  list();
  match(")");
};

But how to combine func and id?

Often you need to order the tests in a parse routine, to ensure that the longest match gets captured. Try calling "func" in factor, before you try for the id. You'll need some support for backing up the input stream when a syntax matching entity fails, or you need to left-factor the common part of the rules. Alternative: lift the func rule content into the factor rule. — Ira Baxter, Apr 01 '16 at 21:41
Your parser is missing a lot of support for handling syntax errors. See my SO answer on how to write recursive descent parsers: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 — Ira Baxter, Apr 01 '16 at 21:42
I'm trying to do left-factor when i can. How to do it here? Or i need lookahead for 2? Or push back token in func rule fails? — Anton Medvedev, Apr 01 '16 at 21:53

score 1 · Accepted Answer · edited Apr 02 '16 at 06:04

1

Left factor the grammar like this:

 factor ::= id ( '(' list ')' )? | '(' expr ')' 
 list ::=  expr ( ',' expr );

Note careful distinction of literal parentheses '(' and ')' and syntax grouping parentheses ( ... )

Coding left to the reader :-}

Check my answer on how to write recursive parser for details.

edited Apr 02 '16 at 06:04

rici

234,347
28
237
341

answered Apr 01 '16 at 22:46

Ira Baxter

93,541
22
172
341

This still is same. I think recover will be best solution. – Anton Medvedev Apr 01 '16 at 22:55
I don't know what you mean by "same" here. In this form, an RE parser never has to back up the input stream. If you want convenience of expression, or fideltity to an original grammar, then rewinding the input stream to a recovery point (e.g., where it was when a recognition routine was entered) is convenient, at the price of more overhead in tracking tokens to enable rewinding to occur. – Ira Baxter Apr 02 '16 at 06:29

How to write recursive descent parser for call expression?

1 Answers1