A Parse Tutorial Sort of (Open sourced Rebol).

Introduction

If you want to extract data from strings (like HTML, TXT, CSV, etc.) consider Parse.

If you want to just check some user data against a specific format consider using Parse.

If you want to validate some message written in your new dialect use Parse.

Parse is useful.

Parse is quick.

Parse operates on string, binary and block input. Using Parse you can process these types of input in some way, overlaying the input with new meaning. That is you have a string or block and you are perhaps identifying fields of records, tokens of a language or even identifying sections of a message protocol.

This document is a very rough show by example description of Parse with a few warnings thrown in.

Comments to reverseflow at codeconscious.com.

Parse Dialect

You give Parse a rule block containing instructions to follow written in the Parse dialect. These instructions allow you to utilise Parse to interpret custom external formats or protocols. These instructions can be as simple or as complex as you need. A simple example would be to check that some input against postal code format. A sophisticated example is Rebol's URL parser (help sys/*parse-url/rules).

The instructions are written using the Parse dialect and tell Parse how to read through your input. In actual fact, the instructions describe the patterns that the input should take. Parse attempts to match the input against your patterns. Parse will return a TRUE result if your instructions accurately describe the input. If your instructions fail to describe the input (or looking at it the other way, the input fails to follow your rules) Parse will return FALSE. You also have the ability to carry out normal Rebol operations as Parse traverses the input and your rules.

It is very important to realise that the keywords of the Parse dialect are interpreted by Parse in a specific way and should be considered as being different in meaning to Rebol words when used at the console.

Let's start at the end

>> input-string: {}
>> parse input-string [end]
== true

Ah success! Here I am parsing an empty string. My rule says to Parse "check that we are at the end". The result is of course TRUE because the string was empty to begin with.

This is similar in normal Rebol script to:

>> tail? input-string
== true

Baby steps

Next up, let's test that a string matches our expectations:

>> input-string: "fox"
== "fox"
>> parse input-string ["fox" end]
== true

We successfully tested that the input started with "fox" and then finished. Ok, no big deal. But reflect a moment. This is a sequence - first "fox" then END. As Parse traverses the input and your rule block, it keeps track of a current position for both. So at the start, the current position in the input is at the head of the string. After the rule "fox" was matched the current position in the input string will be directly after the "x" of "fox". In this example, this happens to be the tail of the string, so the very next match rule END will succeed.

We do not always have to supply an END in the rule block. You can omit it in the last example because Parse effectively slaps one on at the end anyway.

>> parse input-string ["fox"]
== true

While you can do this for simple examples, remember you'll likely need to add it in explicitly for more complex rules.

Ok, back to the example again. In an ordinary Rebol session the above example is similar to the following:

>> input-string: find/match input-string "fox"
== ""
>> tail? input-string
== true

Note that the ordinary Rebol code examples through this article are provided to help learn Parse. There are enough important differences between the Parse examples and the ordinary code examples that you cannot alway treat them as exactly equivalent.

Failures / challenges

For contrast let's look at an unsuccessful match:

>> input-string: "dog"
== "dog"
>> parse input-string ["fox"]
== false

The meaning of this is pretty obvious. Hang on though, what actually happens when Parse encounters a failure with one of the rules? Well it backtracks the input to the point it was at when the rule started. So in Rebol code what happens is actually more like this:

input-string: "dog"
If position: Find/match input-string "fox" [input-string: position]
Tail? input-string

Keep this little idea in the back of your mind, it becomes more meaningful with more complex rules.

Optional matching and Compound Rules

What if we want to check for a number of common pet alternatives? Let's accept a "dog" or a "cat" or indeed a "bird":

>> input-string: "dog"
== "dog"
>> parse input-string ["dog" | "cat" | "bird"]
== true

In ordinary Rebol this is like coding:

input-string: any [
    find/match input-string "dog"
    find/match input-string "cat"
    find/match input-string "bird"
]
tail? input-string

Now, Rebol can be pretty concise and the ANY function definitely helps in writing concise code, but you can see already that the Parse dialect is looking to be better suited to matching than ordinary scripting.

Reflecting on this a bit. We have here a more interesting rule, a compound rule. Our compound rule is composed of three subrules. Each of the three subrules here are very basic but subrules are allowed to be compound rules themselves. The basic rules perform the lowest level matching of the input, the compound rules check the overall structure/grammar of your data.

Back to options. What about something that may or may not exist at all? Using OPT we can indicate that a bird could be big or just leave it out:

>>  input-string: "bigbird"
== "bigbird"
>>  parse input-string [opt "big" "bird"]
== true

>> input-string: "bird"
== "bird"
>> parse input-string [opt "big" "bird"]
== true

There are more Parse options such as NOT which give you greater flexibility in specifying your rules. We'll cover this later.

Spaces and Split

Parse treats spaces like any other character. Note that Rebol 3 acts differently here to Rebol 2 as whitespace is now parsed by default without needing the /ALL refinement

>>  input-string: "black dog"
== "black dog"
>>  parse input-string ["black" " " "dog"]
== true

There are constants defined for common characters such as SPACE, NEWLINE and TAB which can be used instead.

>>  parse input-string ["black" space "dog"]
== true

To make things easier we can use the SPLIT function to pre-process the input string. SPLIT breaks up the string based on a given delimeter or other rules.

>> parse split "brown dog" " " ["brown" "dog"]
== true

If we look at the output of split we see the following.

>> split "brown dog" " "
== [ "brown" "dog" ]

In this case split is returning a block of strings simplifying our work with Parse.

Blocks, repetition and more

Using Parse for strings is good, but using parse on native Rebol datatypes really shows its power. Rebol has a rich set of datatypes which simplify parsing data, and code.

This mode is used when the value to be parsed is actually a block not a string. You use this mode when you have already loaded data into Rebol values. You write Parse instructions in a rule block using the parse dialect in a similar way to that described for parsing strings except when parsing blocks the semantics are different and you have a couple more keywords to use.

This is the mode of Parse that deserves the attention of anyone using Rebol. The reason is that you are free to store your data in a form understandable by yourself and others and yet is still computer readable.

First steps parsing blocks

As we move from strings to blocks we can start to use some of the Rebol datatypes to make our lives much easier.

>> parse [1234.16] [number!]
== true

Processing dates and times are a good example. You can see how the datatypes support a wide range of input formats. It is worth noting for Americans that Rebol always assumes day/month/year order.

>> parse [12/Dec/2012 2:30pm ] [date! time!]
== true

There are many more datatypes although that does not stop you from using strings for datatypes which do not map to Rebol types.

>> parse [<div> "Hello" http://rebol.com $1.00 </div> bob@test.com ] [ tag! "Hello" url! money! tag! email!]
== true

Repetition - known range of occurrences

Time for some more compound rules.

Here's how to check for exactly two dogs.

>> parse "dogdog" [2 "dog"]
== true

I can specify between 1 and 4 Zs (inclusive) too:

>>  parse "Zzzz" [1 4 "z"]
== true

Note that by default Parse is not case sensitive unless you want it to be by using the /CASE refinement:

>> parse/case "ZZ" [2 "Z"]
== true

This is also very powerful for parsing blocks:

>> parse [ http://rebolsource.net http://rebol.org http://rebol.com ] [ 3 url! ]
== true

Repetition again :) - unknown number of occurrences

What if we grab a net and go prawning? We may not know how many prawns are caught by the net when we catch them:

>> loop random 100 [append input-string: "" "prawn"]
== "prawnprawnprawnprawn"
>> parse input-string [some "prawn"]
== true

Excellent, we have some prawns but we don't know how many. The SOME keyword means "match one or more of the following". Again it is a compound rule because I could have as easily done this if it was "raining cats and dogs":

>> input-string: "dogdogcatdogcat"
== "dogdogcatdogcat"
>> parse input-string [some [ "dog" | "cat"] ]
== true

If it fines up:

>> input-string: {}
== ""
>> parse input-string [some [ "dog" | "cat"]  ]
== false

It returns false because SOME requires at least one instance to be matched. If however, we don't actually care whether we get some or not we can use ANY:

>> input-string: {}
== ""
>> parse input-string [any [ "dog" | "cat" ] ]
== true

>> input-string: "dog"
== "dog"
>> parse input-string [any [ "dog" | "cat"] ]
== true

Here is another example of one of those Rebol words with a new meaning in the context of Parse. In ordinary Rebol ANY is a function that return the first non-false or non-none value in the block it is given. In Parse, by contrast, ANY is a keyword that introduces a compound rule that means, "match zero or more of the following".

Repetition works equally well for blocks:

>> parse [Fibonacci 1 1 2 3 5 8 13] [some [number! | word!] ]
== true

Moving right along...

Sometimes we really couldn't care less what lies between things of interest.

This example does not "skip c" it reads "match a, skip a character, match c, tail?".

>> parse {abc} ["a" skip "c" end]
== true

You want to skip 5 characters? Use repetition:

>> parse {1234567890} ["123" 5 skip "90" end]
== true

Sometimes we don't know how much is in between but we do know what is the next interesting bit:

>> input-string: {1234 fox}
== "1234 fox"
>> parse input-string [thru "fox" end]
== true

This is like the Rebol code of:

>> input-string: find/tail input-string "fox"
== ""
>> tail? input-string
== true

We can stop where fox starts using TO:

>>  input-string: "1234 fox"
== "1234 fox"
>>  parse input-string [to "fox" "fox" end]
== true

And the Rebol code that performs similarly:

input-string: {1234 fox}
input-string: find input-string "fox"
input-string: find/match input-string "fox"
tail? input-string

We can skip to the end as well:

>>  parse {123456} ["123" to end end]
== true

This says "match 123, move to the tail, test tail". Pretty obvious we would get a true result if you think of it in these terms.

While we're here how about a warning. The rule [to end] moves to the tail and reports success every time.

All these characters

Charset. Stands for character set. It is a bitset which makes it fast for pattern matching operations.

Let's say you only want to check that your input contains the digits 0 to 9.

>> digit: charset [#"0" - #"9"]

Now parse can use this directly as a pattern matching instruction. It will match one character (byte) only of those in the set 0 - 9.

>> parse {1} [digit]
== true

Naturally enough you can use these in compound rules too:

An Australian postcode consists of 4 numeric digits so:

>> parse {2069} [4 digit]
== true

Charsets (bitsets) are sets and you can apply the set operations union, intersection, exclude, etc on them:

letter: charset [#"a" - #"z" #"A" - #"Z"]
digit: charset [#"0" - #"9"]
letter-or-digit: union letter digit
valid-name: [letter any letter-or-digit]

>>  parse {1abc} valid-name
== false
>>  parse {rebol} valid-name
== true
>>  parse {xyz1234} valid-name
== true

Maybe you want everything but digits:

>> parse {A} [not digit skip]
== true

Notice how we needed to SKIP forward as NOT simply inverses the following rule and does not advance the input. This is different from the Rebol 2 approach of creating a COMPLEMENT of a charset. This may work in some situations, but will not always give you the desired result due to the use of UNICODE in Rebol 3.

But I want some information from it!

Up to this point I've concentrated on the various matching functionality of Parse. Of course though you want to extract information from your data. The keyword of note for this purpose is COPY. Also of use is the ability to execute Rebol code within the Parse rules (actions) and thereby set and maintain Rebol variables (eg. Counters) using that code.

Ok COPY.

Copy is really really simple really. It is a compound rule that takes two arguments a variable and a subrule. Whatever input the subrule matches gets copied into the variable. If the subrule doesn't match anything (fails) COPY returns the failure but leaves the variable unchanged.

Here the subrule is to match an "A" which obviously fails.

>> parse {123} [copy some-text "A"]
== false
>> some-text
** Script error: some-text has no value

Here the subrule is a simple skip:

>> parse {123} [copy some-text skip to end]
== true
>> some-text
== "1"

And here the subrule is to match nothing NONE which is always successful so copy copies that which was matched...an empty string:

>> parse "123" [copy some-text none]
== false
>> some-text
== ""

Another way of getting data is by using SET:

>> parse [ $100 ] [ set wallet money! ]
== true
>> wallet
== $100

Bring on the code (actions)

Ordinary Rebol code can be used inside the parse dialect via the use of "(" and ")" i.e. a Paren! series:

>> parse {} [(print "some code just executed") end]
some code just executed
== true

Obviously this is very handy. Even nicer is that it runs according to its placement in the rule. Note though that even if the rule ultimately fails your code may have already run:

>> parse {123} [
     "1" (print "found 1!")
     "2" (print "found 2!")
     "A" (print "found an A!")
    end
]
found 1!
found 2!
== false

So the upshot is you can maintain counters and take actions based on your Parse rules. During development it can be useful to put print statements in these allowing you to see what is happening.

Advanced section

Repeated Repetition

Now that I've introduced repetition and compound rules, what happens if I create a compound rule made up of nested repetition rules? Hmm, tricky.

This next example put Parse into a spin - an infinite loop. The escape key will not work, but you can break out with Ctrl+c:

>> input-string: {}
== {}
>> parse input-string [while [any "dog"] ]

To understand why this infinite loop happens you need to know when the ANY rule returns success and when it completes.

Here's the major answer: WHILE ALWAYS returns success. WHILE will keep calling its subrule while that subrule returns success regardless of if the input position advances. WHILE gives up on receipt of bad news (failure) but it itself always returns success. Now if WHILE always receives a success because it's subrule in fact is another WHILE or ANY... Well I think that explains it.

Remember OPT. It always returns success just like WHILE. So putting an OPT inside an WHILE is bound to lead to trouble as well.

The point then is that your repetition compound rules must be carefully written because of the possibility of creating these infinite loops. It is not a bug in Rebol, it is consequence of having a flexible Parse dialect.

Sometimes these infinite loops start only after traversing lots of other complex rules and therefore can become hard to catch. I create these loops less often now since I started considering how I want Parse's input position to move. When writing your rules consider how the input is consumed by the rules.

That's part of the reason why I've been demonstrating the Rebol code similar to the various Parse examples.

Not all combinations of repetition rules create infinite loops:

>>  input-string: {}
== ""
>>  parse input-string [while [some "dog"] ]
== true

This last example is ok because the SOME does not always return success - it must consume some input. If SOME does not have at least one success it returns a failure result. So you can see that at some point, given that we can assume that the input is finite, the overall rule must terminate.

Quoting Ladislav, "The dangerous rules are rules, that don't consume any input, yet they return success."

There is another way to escape when you don't want your rule to progress further - the BREAK keyword. BREAK terminates the rule when it is encountered. This could be used to improve performance by stopping evaluation of unnecessary rules.

>> parse [1 2 end 3 4 5 7 8 9] [some [integer! | 'end break]]
== false

This rule will exist as soon as it reaches the end keyword improving the performance.

Debugging parse rules

The ?? command is invaluable in debugging Parse rules.

>> parse "dog" [ ?? "d" ?? [ "i" | "o" ] ?? "g" ?? ]
"d": "dog"
["i" | "o"]: "og"
"g": "g"
end!: ""
== true

It displays the next rule and the current position in the series being parsed.

The current index and manipulating it

Parse maintains a reference to the input. The reference is a series and so has a current index.

Some special Parse dialect syntax allows you to get and set this reference. You use a set-word and get-word syntax respectively.

In this example I set the word "mark" to the input series at the current index that Parse has, don't worry about the false - it is just saying we didn't get all the way through the input:

>>  parse {123456} ["123" mark:]
== false
>> mark
== "456"

I can manipulate the current index that Parse uses too:

>>  parse {1234567} ["123" mark: (mark: next next mark) :mark "67"]
== true

To explain. First "123" is matched, then the word mark is set to the reference. Then the Rebol code between the parentheses is evaluated. This code manipulates the reference we hold by two characters. I return this modified reference to Parse using the get-word syntax. Parse seeing the get-word syntax knows that it must update it's reference to that given. Finally I match the "67".

More Block examples ...

An example that shows what can be achieved is Carl Sassenrath's stock transaction example which you can see below. Now what if "sell 300 shares at $89.08" came in via email?

If you study this example you will see that Carl, in a very small space, has created a small interpreter that parses, validates and performs computations. This is very powerful technology that is easily underestimated because it is so small and simple.

rule: [
    set action ['buy | 'sell]
    set number integer!
    'shares 'at
    set price money!
    (either action = 'sell [
            print ["income" price * number]
            total: total + (price * number)
        ] [
            print ["cost" price * number]
            total: total - (price * number)
        ]
    )
]

total: 0
parse [sell 100 shares at $123.45] rule
print ["total:" total]

total: 0
parse [
    sell 300 shares at $89.08
    buy 100 shares at $120.45
    sell 400 shares at $270.89
] [some rule]
print ["total:" total]

Another powerful example of this is the VID dialect of Rebol/View 2. VID describes in a effective but simple way what should appear on screen. VID is actually a block using normal Rebol values such as words and strings. The LAYOUT function of Rebol/View 2 takes a VID block as an argument to construct the visual objects. Layout uses Parse to process the VID specification.

Special situations

When you do NOT want to match a pattern

NOT does not consume input, so you can use it one ore more times before matching something else:

>> parse "bird" [not "big" "bird"]
== true

One situation where you might do this is when you have a sub rule that might "consume" something needed by an enclosing rule.

For my example, I'll Parse a block rather than text but the concept still applies. I want to Parse the following block, and print out every word, but if I encounter a bar ("|") I'll print out the text "**********":

my-block: [ the quick brown fox | jumped | over the lazy]

This next bit of code will not work. If you try it you will see that no "*" is printed, instead you will see the "|":

single-word: [set item word! (print mold item)]
phrase: [some single-word]
parse my-block [ phrase some ['| (print "**********") phrase] ]

The thing to note is that the bar "|" is a word too. Therefore the bar is "consumed" by the rule called SINGLE-WORD. So one way to solve this is to give SINGLE-WORD some indigestion (make it fail) when it encounters a bar.

You can force a rule to fail using the FAIL keyword but here we use AND and NOT to make the rule fail under a specific condition.

To make it clear what is happening here, I wrap SINGLE-WORD with a rule I call WORD-EXCEPT-BAR. The purpose of this new rule is to fail if it finds the "|" word otherwise it goes ahead and runs SINGLE-WORD. I've added comments to clarify how WORD-EXCEPT-BAR works:

word-except-bar: [
    and not '| ; Without advancing the input position, is this not a bar?
    single-word ; Match single-word
]

The point to note here is that the rule AND NOT '| is a "guard" - it guards the next rule from consuming input under a specific condition.

I also need to modify PHRASE to call WORD-EXCEPT-BAR.

phrase: [some word-except-bar]

Another way to describe the PHRASE rule, as it is now, is "a rule that matches a series of words which does not contain the word |."

To finish off I'll create a function to call parse with the correct rule and wrap the whole lot in an object just to be tidy:

word-parsing-object: context [
    single-word: [set item word! (print mold item)]
    word-except-bar: [and not '| single-word]
    phrase: [some word-except-bar]
    set 'parse-words func[ a-block [block!] ] [
        parse a-block [phrase some ['| (print "**********") phrase] ]
    ]
]

Here is a test run:

>> parse-words [the quick brown fox | jumped | over the lazy]
the
quick
brown
fox
**********
jumped
**********
over
the
lazy
== true

In summary in this section I have demonstrated how one can match a specific pattern even when a more general pattern (that includes the specific pattern) gets to see the input first.

Why didn't you just write...

parse-words: func [a-block [block!]] [
    parse a-block [
        some [
            '| (print "**********") |
            set item word! (print mold item)
        ]
    ]
]

That is the better way to solve the problem, but the point is to demonstrate the concept of preventing a subrule from consuming certain input and how to use AND as a guard. There are situations when you need these ideas.

The BREAK keyword

From RT's changes document:

When the BREAK word is encountered within a rule block, the block is
immediately terminated regardless of the current input pointer.
Expressions that follow the BREAK within the same rule block will not
be evaluated.

BREAK is usually used with repetition. In this example the SOME rule is exited early:

>> parse "X" [some [ (print "*Break*") break] "X"]
*Break*
== true

Here again the SOME rule is exited early just like the previous example. In this case the rule that SOME is processing is referred to by a word:

>> rule-to-break: [(print "*Break*") break]
== [(print "*Break*") break]
>> parse "X" [some rule-to-break "X"]
*Break*
== true

Related toolset

I have written "Parse Analysis Toolset" to help learn and analyse the way Parse works. The Explain-parse function of the toolset should help with learning Parse. The script has related documentation. You can find the script and a linkg to the documentation at:

parse-analysis.r (at REBOL.org Script Library)

One more program I've made can return a parse tree of your input:

load-parse-tree.r (at REBOL.org Script Library)

Comments

Parse is a key component Rebol. Rebol is promoted as a messaging language. Messages can come in many formats (syntaxes). Parse allows you to define the syntax of a message so that you can interpret the message and transform it to something else or act on it directly. That may sound complex, but it isn't really.

What are messages? Lots of things can be considered as messages. Basically if you can put it into a file and the format of the file has some rule to it, then I think you have a message. You don't have to put it in a file though to use Parse. Rebol's networking functions use Parse to interpret many of the internet protocols that Rebol provides access to.

With Rebol you can define a mini-language for a specific purpose - a dialect. Outside Rebol this would be called a domain-specific language or DSL. Parse helps you to validate and process such dialects. You might want to design a dialect for creating web pages on your internet site. Or perhaps for controlling a special device you have attached to your computer.

Acknowledgement

Thank you to John Kenyon for his initiative, edits and effort as we updated this article from the original.