Beispiel: Reguläre Ausdrücke im XML Schema Standard

definiert eine ganze Reihe von einfachen Datentypen.

Die zulässigen Werte werden unter anderem mit Hilfe von regulären Ausdrücken beschrieben.

ist ein Datentyp zur Beschreibung von Zeitdauern.

der Repräsentation einer Zeitdauer als Zeichenreihe
(Ausschnitt aus dem XML Schema Standard):

[Definition:]   duration represents a duration of time. The ·value space· of duration is a six-dimensional space where the coordinates designate the Gregorian year, month, day, hour, minute, and second components defined in § 5.5.3.2 of [ISO 8601], respectively. These components are ordered in their significance by their order of appearance i.e. as year, month, day, hour, minute, and second.

...

The lexical representation for duration is the [ISO 8601] extended format PnYn MnDTnH nMnS, where nY represents the number of years, nM the number of months, nD the number of days, 'T' is the date/time separator, nH the number of hours, nM the number of minutes and nS the number of seconds. The number of seconds can include decimal digits to arbitrary precision.

The values of the Year, Month, Day, Hour and Minutes components are not restricted but allow an arbitrary unsigned integer, i.e., an integer that conforms to the pattern [0-9]+.. Similarly, the value of the Seconds component allows an arbitrary unsigned decimal. Following [ISO 8601], at least one digit must follow the decimal point if it appears. That is, the value of the Seconds component must conform to the pattern [0-9]+(\.[0-9]+)?. Thus, the lexical representation of duration does not follow the alternative format of § 5.5.3.2.1 of [ISO 8601].

An optional preceding minus sign ('-') is allowed, to indicate a negative duration. If the sign is omitted a positive duration is indicated. See also ISO 8601 Date and Time Formats (§D).

For example, to indicate a duration of 1 year, 2 months, 3 days, 10 hours, and 30 minutes, one would write: P1Y2M3DT10H30M. One could also indicate a duration of minus 120 days as: -P120D.

Reduced precision and truncated representations of this format are allowed provided they conform to the following:

• If the number of years, months, days, hours, minutes, or seconds in any expression equals zero, the number and its corresponding designator ·may· be omitted. However, at least one number and its designator ·must· be present.
• The seconds part ·may· have a decimal fraction.
• The designator 'T' must be absent if and only if all of the time items are absent. The designator 'P' must always be present.

For example, P1347Y, P1347M and P1Y2MT2H are all allowed; P0Y1347M and P0Y1347M0D are allowed. P-1347M is not allowed although -P1347M is allowed. P1Y2MT is not allowed.

Entwickeln Sie einen regulären Ausdruck für Zeichenreihen, die duration-Werte gemäß des XML Schema Standards formen.

Eine Zerlegung in Teilaufgaben (Muster für Jahr, Monat, Tag, Kombination von Jahr-Monat-Tag, Stunde, Minute, Sekunde) ist aus Übersichtlichkeit dringend zu empfehlen.

Entwickeln Sie eine kontextfreie Grammatik für die gleiche Aufgabenstellung. Das zu Grunde liegende Alphabet sei dabei die Menge aller Zeichen (ASCII oder Unicode).

Entwickeln Sie aus der kontextfreien Grammatik eine gleichwertige LL(1) Grammatik.