We've used grammars for a number of our examples.  That's partly because they're a particularly simple example of a declarative formalism, partly because logic programming was originally invented by computational linguists, and partly because textual examples work well for a simple web-interface for programming.

Formal grammars are usually described as systems that generate text.  But they're most commonly used in software for parsing text.  Parsing is the process of reversing the generation process: breaking the text into its parts and relating them back to the grammar rules that combined them.

Logic programming has been popular with computational linguists in part because of the special property that logic programs have of often being runnable in reverse, as we saw with the append example. 

The Parse predicate

In fact, we can do that with grammars too.  The higher-order task Parse tells you whether a given call to a grammar can generate a given string, and if so, what its arguments should be.  The call:

[Parse ?generator ?string]

runs ?generator, but redefines output primitives like Write to be matching primitives.  Any time ?generator tries to write something different than the next token from ?string, it fails, causing Step to search for a different choice path that can generate the selected ?string.

Recognizing strings generated by a grammar

For a very example, we can ask our old treasure generator whether it can generate the text “cursed mace of social anxiety”(try it):

# Try: [Parse [Treasure] "cursed mace of social anxiety"]
[predicate]
Treasure: [Weapon]

[predicate]
Weapon: [PreBuff] [WeaponType] [PostBuff]

[predicate] [randomly]
WeaponType: sword
WeaponType: mace

[predicate] [randomly]
PreBuff: +1
PreBuff: +2
PreBuff: cursed

[predicate] [randomly]
PostBuff: of [Element]
PostBuff: of [Effect]

[predicate] [randomly]
Element: earth
Element: air
Element: fire
Element: water
Element: soul

[predicate] [randomly]
Effect: insanity
Effect: sleep
Effect: poison
Effect: social anxiety

It searches for a choice path that generates that text, finds one, and prints “yes”.  But if we change it to “cursed mace of fear”, it says no, because there is no way to generate that given this grammar.

Recovering arguments to the generator

Just as we can pass arguments to the generator to control the text that is generated, we can extract that information from the text as part of the parsing process.  For example, our Greet task took the name of the person we were greeting as an argument:

# Try: [Greet mom]
[predicate] [randomly]
Greet ?who: Hello, ?who.
Greet ?who: Hey, ?who.
Greet ?who: Good evening, ?who.

We can recover that from the parsing process by leaving the argument as a variable:

# Try: [Parse [Greet ?who] "Hey, mom."]
[predicate] [randomly]
Greet ?who: Hello, ?who.
Greet ?who: Hey, ?who.
Greet ?who: Good evening, ?who.