Detection of optional production

Consider such productions:

class_mod := /* empty */ | VIRTUAL | ABSTRACT
data_type := STRUCT | CLASS
type := class_mod data_type name

The problem lies in the very first entry — the empty one. Naive parser detects a conflict between “class_mod” and “data_type” on both “STRUCT” and “CLASS” when “class_mod” is empty. See below for possible actions (there are lookaheads given in braces):

class_mod = . { STRUCT , CLASS }
data_type = . STRUCT { STRUCT }
data_type = . CLASS { CLASS }

On one hand “data_type” can be shifted (once), on the other — “class_mod” can be reduced (multiple times).

The forking parser can be forced to solve this by trying both moves, but it is obvious it is not efficient, and since I hit this problem several times already I added detection of such scenario. Namely, if the conflicting reduce move is empty one and there is only one shift move parser will reduce and then — without rechecking action table — it will shift.

It works nice (there is no need to fiddle with dependency table) and it does not ruin my testsuite, but because I feel there are some checks needed for reliable detection of optional production I added this feature only to forking parser.

Tagged

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: