[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
Recognizing strings based on a set of restrictions is a common computational problem. A Slurpy is a string of characters that has certain properties. Your program will read in strings of characters and output whether or not they are Slurpies.
A Slump is a character string that has the following properties:
A Slimp is a character string that has the following properties:
A Slurpy is a character string that consists of a Slimp followed by a
Background & Techniques
This problem is from the 1996 Mid-Atlantic Regional ACM Programming Contest. 56 college teams tried it and 35 solved is successfully. Are you ready to join a team?
My first thought in selecting this problem was that it would make a good filler program while I worked on something more challenging. And it is a pretty good example of a recursive definition, Slumps are defined in terms of letters and Slumps. Slimps are made from letters, Slimps and Slumps.
Then, while thinking about a more concise way to define the problem, I spent a pleasant afternoon rediscovering Extended Backus-Naur Form (EBNF) method of specifying the syntax (the elements and rules of a language). Delphi, Pascal, any other programming language as well as the "Slurp" language of our current problem can be defined using EBNF. It's pretty darn simple to be so powerful. Any EBNF language definition consists of
Because of the variations, every document using EBNF to define a language will usually define the conventions it is using. Mine will be standard except that I'll put the terminal symbols in bold type to distinguish them from non-terminal and meta-symbols. So our problem can be defined with these three rules:
In case you're interested, here's a link to the final draft of the ISO EBNF Standards document. I know little about the International Standard Organization, except that they don't make their standards freely available via the Web and they must use very expensive paper since they want 62 Swiss Francs ($40!) for the 12 page EBNF Standards document! Sounds like a rip-off to me -- maybe it's not surprising that the standard is usually ignored.
Rant aside, EBNF is useful for compiler writers since they provide straightforward language definitions - in fact there are "compiler compilers" that can read any EBNF description set and produce a compiler program based the the rules. YACC (Yet Another Compiler Compiler) is the prototype for this and is widely distributed in the Unix/Linux world. (Windows versions exist).
Running/Exploring the Program
Suggestions for Further Explorations
Modified: July 29, 2017
Copyright © 2000-2017, Gary Darby All rights reserved.