Will this "algorithm" be for zero and first work (in the parser)?

Question

We work with it for fun: http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

An example of calculating NULL values ​​and the first uses fixed-point computation. (see section 3.8)

I do everything on the Scheme and rely a lot on recursion.

If you try to implement nullable or first with recursion, it should be clear that you will endlessly repeat when you create, for example

N -> N ab

where N is nonterminal and a, b are terminals.

Could this be solved, recursively, by supporting the set of non-terminals visible on the left side of the production rules, and ignoring them after we took them into account once?

This seems to work for nullable. What about the first one?

EDIT: This is what I learned from the game. Link to the source code below.

Non-terminals cannot be ignored when computing the first if they cannot be omitted.

Consider:

 N -> N a N -> X N -> 

Here we can ignore N in N a , because N is NULL. We can replace N -> N a with N -> a and deduce that a is a member of first(N) .

Here we cannot ignore N :

 N -> N a N -> M M -> b 

If we ignored N in N -> N a , we would conclude that a is in first(N) , which is false. Instead, we see that N is not null, and therefore, when calculating, we can first omit any product in which N is as the first character in RHS.

This gives:

 N -> M M -> b 

which tells us that b is in first(N) .

Source Code: http://gist.github.com/287069

So ... does this sound natural?

Answer 1

I suggest you keep reading :)

3.13 Rewriting a grammar for LL(1) parsing and especially 3.13.1 Eliminating left-recursion .

Just note that you can also run indirect left recursion:

 A -> Bac B -> A B -> _also something else_ 

But the solution here is very similar to eliminating direct left recursion, as in your first example.

You might want to check out this article , which explains it in a slightly more straightforward way. Less theory :)