CODEWITHSUNDEEP
parsingdata-structurescompiler-constructionrecursive-descent
Hunter McMillen
Hunter McMillen

Reputation: 61512

Encode FIRST and FOLLOW sets into a recursive descent parser

This is a follow up to a previous question I asked How to encode FIRST & FOLLOW sets inside a compiler, but this one is more about the design of my program.

I am implementing the Syntax Analysis phase of my compiler by writing a recursive descent parser. I need to be able to take advantage of the FIRST and FOLLOW sets so I can handle errors in the syntax of the source program more efficiently. I have already calculated the FIRST and FOLLOW for all of my non-terminals, but am have trouble deciding where to logically place them in my program and what the best data-structure would be to do so.

Note: all code will be pseudo code

Option 1) Use a map, and map all non-terminals by their name to two Sets that contains their FIRST and FOLLOW sets:

class ParseConstants
    Map firstAndFollowMap = #create a map .....
    firstAndFollowMap.put("<program>", FIRST_SET, FOLLOW_SET)
end

This seems like a viable option, but inside of my parser I would then need sorta ugly code like this to retrieve the FIRST and FOLLOW and pass to error function:

#processes the <program> non-terminal
def program
    List list    = firstAndFollowMap.get("<program>")
    Set FIRST    = list.get(0)
    Set FOLLOW   = list.get(1)  

   error(current_symbol, FOLLOW)
end

Option 2) Create a class for each non-terminal and have a FIRST and FOLLOW property:

class Program
    FIRST    = .....
    FOLLOW = .... 
end

this leads to code that looks a little nicer:

#processes the <program> non-terminal
def program
   error(current_symbol, Program.FOLLOW)
end

These are the two options I thought up, I would love to hear any other suggestions for ways to encode these two sets, and also any critiques and additions to the two ways I posted would be helpful. Thanks

I have also posted this question here: http://www.coderanch.com/t/570697/java/java/Encode-FIRST-FOLLOW-sets-recursive

Upvotes: 1

Views: 3105

Answers (1)

Shahbaz
Shahbaz

Reputation: 47523

You don't really need the FIRST and FOLLOW sets. You need to compute those to get the parse table. That is a table of {<non-terminal, token> -> <action, rule>} if LL(k) (which means seeing a non-terminal in stack and token in input, which action to take and if applies, which rule to apply), or a table of {<state, token> -> <action, state>} if (C|LA|)LR(k) (which means given state in stack and token in input, which action to take and go to which state.

After you get this table, you don't need the FIRST and FOLLOWS any more.

If you are writing a semantic analyzer, you must assume the parser is working correctly. Phrase level error handling (which means handling parse errors), is totally orthogonal to semantic analysis.

This means that in case of parse error, the phrase level error handler (PLEH) would try to fix the error. If it couldn't, parsing stops. If it could, the semantic analyzer shouldn't know if there was an error which was fixed, or there wasn't any error at all!

You can take a look at my compiler library for examples.

About phrase level error handling, you again don't need FIRST and FOLLOW. Let's talk about LL(k) for now (simply because about LR(k) I haven't thought about much yet). After you build the grammar table, you have many entries, like I said like this:

<non-terminal, token> -> <action, rule>

Now, when you parse, you take whatever is on the stack, if it was a terminal, then you must match it with the input. If it didn't match, the phrase level error handler kicks in:

Role one: handle missing terminals - simply generate a fake terminal of the type you need in your lexer and have the parser retry. You can do other stuff as well (for example check ahead in the input, if you have the token you want, drop one token from lexer)

If what you get is a non-terminal (T) from the stack instead, you must look at your lexer, get the lookahead and look at your table. If the entry <T, lookahead> existed, then you're good to go. Follow the action and push to/pop from the stack. If, however, no such entry existed, again, the phrase level error handler kicks in:

Role two: handle unexpected terminals - you can do many things to get passed this. What you do depends on what T and lookahead are and your expert knowledge of your grammar.

Examples of the things you can do are:

  • Fail! You can do nothing
  • Ignore this terminal. This means that you push lookahead to the stack (after pushing T back again) and have the parser continue. The parser would first match lookahead, throw it away and continues. Example: if you have an expression like this: *1+2/0.5, you can drop the unexpected * this way.
  • Change lookahead to something acceptable, push T back and retry. For example, an expression like this: 5id = 10; could be illegal because you don't accept ids that start with numbers. You can replace it with _5id for example to continue

Upvotes: 3

Related Questions