0
$\begingroup$

I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (using FIRST, FOLLOW sets) which is basically a large 2D array that predicts which rule should be called or the recursive descent method.

I wanted to know if using a table driven parser would be (is?) feasible since even for a relatively small grammar, the parsing table would get very large since the parsing table I saw just for this grammar that parses (incomplete) expressions is a 5x6 array. here

E --> TE'
E' --> +TE' | ε                
T --> FT'
T' --> *FT' | ε
F --> id | (E)
$\endgroup$

1 Answer 1

1
$\begingroup$

100 x 100 entries wouldn’t be considered large. And in each row of the table, you can store only entries for members of the follow set, which reduces the table size massively. So 1,000 x 1,000 entries with 50 entries in the follow set on average you need only 50,000 entries which is quite trivial. And a recursive descent parser would have to handle the exact same number of cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.