Exercises for Section 2.4

2.4.1

Construct recursive-descent parsers, starting with the following grammars:

1. S -> + S S | - S S | a
2. S -> S ( S ) S | ε
3. S -> 0 S 1 | 0 1

Answer

See 2.4.1.1.c, 2.4.1.2.c, and 2.4.1.3.c for real implementations in C.

1） S -> + S S | - S S | a

void S(){
  switch(lookahead){
    case "+":
      match("+"); S(); S();
      break;
    case "-":
      match("-"); S(); S();
      break;
    case "a":
      match("a");
      break;
    default:
      throw new SyntaxException();
  }
}
void match(Terminal t){
  if(lookahead = t){
    lookahead = nextTerminal();
  }else{
    throw new SyntaxException()
  }
}

2） S -> S ( S ) S | ε

void S(){
  if(lookahead == "("){
    match("("); S(); match(")"); S();
  }
}

3） S -> 0 S 1 | 0 1

void S(){
  switch(lookahead){
    case "0":
      match("0"); S(); match("1");
      break;
    case "1":
      // match(epsilon);
      break;
    default:
      throw new SyntaxException();
  }
}