0

I am trying to create grammar for a naive top-down recursive parser. As I understand the basic idea is to write a list of functions (top-down) that correspond to the productions in the grammar. Each function can call other functions (recursive).

The rules for a list include any number of numbers, but they must be separated by commas.

Here's an example of grammar I came up with:

LIST ::= NUM | LIST "," NUM

NUM ::= [0-9]+

Apparently this is incorrect, so my question is: why is this grammar not able to be parsed by a naive top-down recursive descent parser? What would be an example of a valid solution?

JFreeman
  • 974
  • 1
  • 10
  • 26
  • Why do you think that this is incorrect? – mkrieger1 May 24 '21 at 09:19
  • It might be instructive to write the functions that correspond to these productions, and see how they behave. – Michael Dyck May 25 '21 at 00:45
  • @mkrieger1 - my professor wrote "You need to change the following grammar so that it can be parsed by a naive top-down recursive descent parser". I don't understand though which is why I was asking. – JFreeman May 25 '21 at 01:56

1 Answers1

0

The issue is that for a LL(1) recursive decent parser such as this:

For any i and j (where j ≠ i) there is no symbol that can start both an instance of Wi and an instance of Wj.

This is because otherwise the parser will have errors knowing what path to take.

The correct solution can be obtained by left-factoring, it would be:

LIST ::=   NUM REST
REST ::=   "" | "," NUM
NUM  ::=   [0-9]+
JFreeman
  • 974
  • 1
  • 10
  • 26