Working with the Prioritized-Choice Rule

The following exercises demonstrate several cases of valid but problematic CGFs with discussion and prioritized-choice solutions. They are arranged from trivial to head-scratching and it is suggested that you try them in the order presented.

exercise 1 – longest alternative first
exercise 2 – repetitions
exercise 3 – non-trivial
exercise 4 – impossible (almost)

impossible (almost)

Continuing from exercise 3 we turn our attention to the hostname. With the exception that the toplabel must start with a letter, whereas the domainlabel is allowed to start with a digit, they are identical. The languages for each overlap almost completely. But for the hostname it is important semantically that we distiguish between the two. The problem comes from the optional period at the end. If the hostname ends with a period there is no way to find the toplabel. The parse will always fail.

To the best of my knowledge, there is no prioritized-choice solution to this problem. We do, however, have one more trick up our sleeve. Syntactic predicates allow the parser to look ahead and make input-string-dependent, alternate decisions on the fly. We note that (domainlabel ".") must always be followed by an alphanum, whereas (toplabel ["."]) never is. A syntactic predicate can be constructed to insure this condition. Such a solution is demonstrated here.

I've never run into a case where a prioritized-choice, syntactic-predicate solution couldn't be found. But that is, by no means, a guarantee that such specifications do not exist. But APG versions 6.x do provide one further trick to handle it should the occasion arise. Namely, the handwritten option that is available for any given rule. With this interactive format there is no way to provide a demonstration of that here, but you can find several in the sample solutions for the C-language version.