Tag Archives: productions

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.