REBOL Programming/Language Features/Parse

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

PARSE is one of the most powerful features in REBOL. It has many capabilities from simple string splitting to parse expression matching. PARSE forms the basis of pattern matching, that is implemented as regular expression matching in other languages.

If you are asking yourself why REBOL has no regular expression matching implementation, PARSE is the answer.

A skeleton of a parsing operation:

parse INPUT RULE

Contents

[edit] Simple splitting

String parsing involves simple splitting:

parse "this is a string" none
; == ["this" "is" "a" "string"]

By providing NONE as the PARSE rule, we are asking PARSE to break a string into a block of string(s) based on whitespace:

whitespace: charset [#"^A" - #" " "^(7F)^(A0)"]

and common delimiters:

common-delimiter: charset ",;"

To facilitate CSV splitting, quotation marks are handled specially (see the CSV example).

[edit] Examples

[edit] Empty string

parse "" none
; == []

[edit] No delimiters in the input string

parse "redbluegreen" none
; == ["redbluegreen"]

[edit] Space

parse "red blue green" none
; == ["red" "blue" "green"]

[edit] Comma

parse "red,blue,green" none
; == ["red" "blue" "green"]

[edit] Tab

parse "red^-blue^-green" none
; == ["red" "blue" "green"]

[edit] Semicolon

parse "red;blue;green" none
; == ["red" "blue" "green"]

[edit] Newline

string: {
red
blue  
green
}
parse string none
; == ["red" "blue" "green"]

[edit] Leading and trailing whitespaces are ignored

parse " 1 " none
; == ["1"]

[edit] A sequence of whitespaces is equivalent to one whitespace

parse "1  2" none
; == ["1" "2"]

[edit] Leading common delimiter delimits an empty substring

parse ",1" none
; == ["" "1"]

[edit] One trailing common delimiter is ignored

parse "1," none
; == ["1"]

[edit] A sequence of common delimiters delimits empty substrings between them

parse "1,,2" none
; == ["1" "" "2"]

[edit] CSV

parse {"red","blue","green"} none
; == ["red" "blue" "green"]

[edit] Splitting using specific delimiters

The

parse string none

expression breaks down when:

  • you want to specify which characters shall be treated as whitespace
  • you want to specify which characters shall be treated as delimiters
  • you don't want the quotation marks to be handled specially
  • you need something other than simple splitting

[edit] Examples

[edit] To eliminate the special treatment of whitespace use the /ALL PARSE refinement

parse/all "only common delimiters; split the text, now" none
; == ["only common delimiters" " split the text" " now"]

If you have different delimiter(s) you can supply a string rule to PARSE containing your delimiters.

[edit] The #"#" character as a delimiter

parse "red#blue#green" "#"
; == ["red" "blue" "green"]

[edit] The space character as a delimiter

parse/all "red blue^-green" " "
; == ["red" "blue^-green"]

[edit] The #"#" and #"*" characters as delimiters

parse "red#blue*green" "#*"
; == ["red" "blue" "green"]

Note that the order of the characters in the delimiter string is not important.

[edit] Parse expressions

Sometimes you want to parse a series to see if it matches a specific format. This can be used for simple things like determining and validating the format of a phone number or an email address.

You may need this even when splitting a string but not wanting to treat the quotation marks specifically as the NONE or string rules do. (See the simply split example.)

Instead of regular expressions PARSE matches parse expressions. Parse expressions are:

PARSE handles powerful dialects that are used throughout the language. An example of this is VID or the Visual Interface Dialect, used for constructing graphical user interfaces.

[edit] Parse expression matching

What PARSE does during parse expression matching is traversing a series (e.g. a block, a string or a binary) and while it does that, you can perform actions or collect information from the series to be used elsewhere or perform actions on the series itself.

There are roughly two ways parse expression matching is used, either on strings matching character patterns, or on blocks matching patterns of REBOL values. This means, that:

Block parsing is generally used to handle dialects, and this is one of the main characteristics of the language.

For parse expression matching the given RULE argument has to be a block. The contents of the block are interpreted as a starting parse expression corresponding to the starting expression of a parsing expression grammar.

When matching parse expressions, PARSE maintains the input position.

Parse expression matching may have two possible results:

  • success, in which case PARSE may optionally move the input position forward, or
  • failure, in which case the input position remains unchanged

PARSE returns TRUE, if:

  • the starting parse expression was found to successfully match the given INPUT
  • the final input position is at the tail of the given INPUT

Otherwise PARSE returns FALSE.

[edit] Atomic parse expressions

Atomic parse expressions are parse expressions, that are represented by just one REBOL value.

[edit] NONE

NONE is treated as a nonterminal that successfully matches any input and generally doesn't move the input position forward, with an exception mentioned at the Character set section.

 parse "" [#[none]]
 ; == true

This returns TRUE because:

  • The NONE value successfully matches any input.
  • PARSE is already at the tail of the string.
parse [] [#[none]]
; == true

Notes:

  • Since the NONE value is used as a nonterminal, it cannot be used to match the NONE terminal in the input block. If you want to match the NONE terminal in the input block, see the Datatype section.

[edit] Character

Characters are treated as terminal symbols when parsing strings as well as when parsing blocks.

parse "a" [#"a"]
; == true

This returns TRUE because:

  • The #"a" character successfully matches the character at the current input position.
  • PARSE moves forward after the successful match, reaching the tail of the input in this case.
parse [#"a"] [#"a"]
; == true

[edit] Any-string

Any-strings are treated as sequences of terminal symbols when parsing strings:

parse "aaa" ["aaa"]
; == true

This returns TRUE because:

  • The string successfully matches a part of the input at the current input position.
  • PARSE moves forward after the successful match, reaching the tail of the input in this case.
parse "<html>" [<html>]
; == true

Any-strings are treated as terminal symbols when parsing blocks:

parse ["aaa"] ["aaa"]
; == true

parse [<html>] [<html>]
; == true

[edit] Block

Blocks are treated as nonterminals; their contents are interpreted as parse expressions and used for matching.

parse "a" [["a"]]
; == true

parse ["a"] [["a"]]
; == true

Notes:

  • Since REBOL blocks are treated as nonterminals, they cannot be used as terminal symbols to literally match specific blocks contained in the input. To match a specific block you can either use the into operator or the lit idiom defined in the Parse idioms section.

[edit] Paren

Parens successfully match any input not advancing the PARSE position; they are treated as actions to be evaluated, which results in printing the string "OK" to the console in the examples below:

parse "" [(print "OK")]
; == true

parse [] [(print "OK")]
; == true

Notes:

  • Since parens are treated as actions, they cannot be used as terminals to match parens in the input block. If you want to match a specific paren, you can either use the into operator or the lit idiom in the Parse idioms section.

[edit] Argument-less PARSE keyword

PARSE keywords not needing any arguments are treated as nonterminals.

[edit] The end keyword
parse "" [end]
; == true

This returns TRUE because:

  • The input is already at its tail.
  • The end keyword successfully matches the input, when it is at its tail.
[edit] The skip keyword
parse "a" [skip]
; == true

This returns TRUE because:

  • The skip keyword successfully matches any terminal.
  • PARSE moves forward after the successful match, reaching the tail of the input in this case.
parse ["aa"] [skip]
; == true

Notes:

  • PARSE keywords cannot be used as terminals to match specific words in the input block. For matching such words see the Lit-word section.

[edit] Word

REBOL words that are not PARSE keywords are treated as nonterminals. The value of such a word is looked up and used for matching.

parse "" [none]
; == true

This returns TRUE because:

  • The 'none variable refers to the NONE value, which successfully matches any input.
  • PARSE was already at the tail of the input.

Notes:

  • For matching specific words in the input see the Lit-word section.
  • Words referring to PARSE keywords are handled as the keywords.
  • Words referring to other words are not supported. When PARSE encounters such a word, it causes an "invalid argument" error.

[edit] Lit-word

Lit-words can be used only during block parsing. Every lit-word is treated as a nonterminal, which successfully matches the corresponding word at the current input position.

parse [Hi] ['Hi]
; == true

A different word match will fail:

parse [Bye] ['Hi]
; == false

Notes:

  • Since lit-words are nonterminals, they cannot be used as terminals to match lit-words in the input block. For matching specific lit-words see the lit idiom in the Parse idioms section.

[edit] Path

Paths work analogically as words, i.e. the value of a path is looked up and used for matching.

[edit] Lit-path

Lit-paths work analogically as lit-words, i.e. they match the corresponding paths in the input block.

[edit] Character set

Bitsets work as character set nonterminals when parsing strings. They successfully match any character they contain.

whitespace: charset [#"^A" - #" " #"^(7F)" #"^(A0)"]
parse/all " " [whitespace]
; == true

Notice, that we "turned off" the special handling of whitespace characters by using the /ALL refinement.

It may be interesting to find out what happens, if we don't "turn off" the special handling of whitespace characters:

whitespace: charset [#"^A" - #" " #"^(7F)" #"^(A0)"]
parse " " [whitespace]
; == false

The result is FALSE, since PARSE "ignores" the whitespace characters in this case, so they cannot be successfully matched.

The next trial doesn't succeed either:

parse " " []
; == false

, since the input position isn't at the tail yet.

To succeed, we need to do:

parse " " [none]
; == true

, where the NONE value is used to match the space and move the PARSE input position forward.

Notes:

  • The above NONE behaviour is a special case, when even the NONE value can move the current input position forward.
  • In case of block parsing bitsets behave as terminal symbols.

[edit] Datatype

We can use REBOL datatypes as nonterminals when parsing blocks. They successfully match any value of corresponding datatype.

parse [5] [integer!]
== true

This returns TRUE because:

  • The INTEGER! datatype referenced by the 'integer! word successfully matched the element in the block.
  • PARSE reached the end of the block after moving forward.

Same thing, only with a date and a string:

parse [25-Dec-2005] [date!]
; == true

parse ["Hello"] [string!]
; == true

The NONE! datatype can be used to match the NONE value in the input:

parse [#[none]] [none!]
; == true

Notes:

  • Since datatypes are treated as nonterminals, they cannot be used as terminals to match datatypes in the input block. To match specific datatypes in the input see the lit idiom in the Parse idioms section.
  • The INTEGER! datatype matches integer representations when used during string parsing. Other datatypes "work" as NONE.

[edit] Set-word

Set-words are treated as nonterminals and used to obtain the current input position. Set-words always succeed not moving the input position.

parse "123" [position:]
; == false
position
; == "123"

Explanation:

  • PARSE sets the 'position variable to refer to the current input position
  • The match succeeds not moving the input position forward
  • PARSE returns FALSE, since the final input position didn't reach the tail of the input

Notes:

  • Since set-words are treated as nonterminals, they cannot be used as terminals to match specific set-words in the input block. To match specific set-words see the lit idiom in the Parse idioms section.

[edit] Get-word

Get-words are treated as nonterminals and used to set the current input position. An attempt to set the input position to a completely distinct series (a series not having the same head as the current input position) causes an error. Otherwise the match succeeds. Example:

string: tail "123"
parse head string [:string]
; == true

Explanation:

  • Match succeeds
  • PARSE returns TRUE since the position is set to the tail of the input in this case.

Notes:

  • Since get-words are treated as nonterminals, they cannot be used as terminals to match specific get-words in the input block. For matching specific get-words see the lit idiom in the Parse idioms section.

[edit] Native

What do natives match during block parsing?

[edit] Other datatype

Values of other datatypes than mentioned above can be used during block parsing as terminal symbols.

[edit] Parse operations

Let's see how PARSE traverses a block:

parse [Hi Bye] [word!]
; == false

What goes wrong here? What happens is that PARSE successfully matches the first word in the INPUT block and advances the input to the second word.

The block hasn't been parsed to the end, which means that PARSE returns FALSE.

To match the input in more complicated cases we need parse operations in addition to the atomic expressions mentioned above.

[edit] Sequence

A sequence operation is a sequence of parse expressions. It does not use a keyword. The general form of a sequence is:

subexpression_1 subexpression_2 ... subexpression_n

When matching a sequence PARSE matches the subexpression_1 and if it succeeds, it tries to match the rest of the sequence. For the sequence match to succeed, all subexpression matches are required to succeed.

Example:

parse [Hi Bye] ['Hi word!]
; == true

In this case the sequence match succeeds and the input is advanced to its tail, which causes PARSE to return TRUE.

[edit] Ordered choice

The ordered choice (a.k.a. "alternative", but the "ordered choice" name is more appropriate, since the order of subexpressions matters) operation uses the | keyword. The general form of this operation is:

subexpression_1 | subexpression_2 | ... | subexpression_n

When matching an ordered choice PARSE tries to match the subexpression_1. If it succeeds, the ordered choice match is successful. If the first subexpression match doesn't succeed, PARSE tries to match the rest of the choice.

The ordered choice operation has lower priority than the sequence operation, which means, that:

e1 e2 | e3

is equivalent to

[e1 e2] | e3

Let's say you want to check that the block element is either an integer or a decimal:

parse [36] [integer! | decimal!]
; == true

parse [37.2] [integer! | decimal!]
; == true

Note: Prioritization of the ordered choice operation causes, that the second subexpression in the:

["a" | "ab"]

choice never succeeds, since the first one takes precedence.

[edit] Repetition operators

Repetition operators specify how many times a given subexpression should match. The general syntax of repetition is

 repetition_operator subexpression

Repetition operators have higher priority than the sequence operator, which means, that

repetition_operator subexpression_1 subexpression_2

means the same as

[repetition_operator subexpression_1] subexpression_2

All repetition operators are greedy, which means, that they always match as many times as possible.

Repetition operators are left-associative, which means, that

any 2 skip

is equivalent to

[any 2] skip

The same holds for the to, thru and into operators.

[edit] Zero or one

This operator uses the opt keyword. It is also known as optional match. Since a zero count is allowed, this operator always succeeds.

Examples:

parse "," [opt #","]
; == true

parse "" [opt #","]
; == true
[edit] One or more

This operator uses the some keyword.

Examples:

parse "," [some #","]
; == true

parse ",," [some #","]
; == true
[edit] Zero or more

This operator uses the any keyword. Since a zero count is allowed, this operator always succeeds.

Examples:

parse ",," [any #","]
; == true

parse "" [any #","]
; == true

parse [Hi Bye] [any word!]
; == true

It returns TRUE, because:

  • The any operator always succeeds
  • The any operator is greedy successfully matching all words in the input, leaving the final input position at the tail

If we add a different datatype to the block:

parse [Hi 36 Bye] [any word!]
; == false

PARSE returns FALSE, since:

  • The any operator successfully matches just the first element of the input and stops not reaching the tail
[edit] Repetition count

The general form of this operation is:

n subexpression

Where N is an integer value. This operation specifies the repetition count for the given subexpression.

Examples:

parse "12" [2 skip]
; == true

The expression checks for exactly two words, no more, no less:

parse [Hi Bye] [2 word!]
; == true
[edit] Range of times

The general form of this operation is:

n m subexpression

Where N and M are integer values. This operation specifies the repetition range for the subexpression.

Examples:

parse "12" [1 2 skip]
; == true

parse [Hi Bye] [1 2 word!]
; == true

The expression checks for not less than 1 and not more than 2 words.

parse [Hi how are you? Bye] [0 5 word!]
; == true

This expression will successfully match between 0 and 5 words.

Note that when parsing for integer values, we have to specify a range since integers are used to specify ranges of matches.

This specifies exactly one match:

parse [-1] [1 1 -1]
; == true

This is an error:

parse [-1] [-1]
; == false

[edit] Skipping data in the input

There are two PARSE operators progressing the input position in accordance with a given parse subexpression:

  • the to operator
  • the thru operator

The general syntax of the operations is:

to subexpression

or

thru subexpression

The purpose of the to operator is to progress the input position up until the position where a successful subexpression match has occurred.

The purpose of the thru operator is to progress the input position to the position after the successful subexpression match.

Both operations fail, if a successful subexpression match isn't found.

The subexpression can be:

  • the end keyword. The
to end
operation always succeeds advancing the input to its tail, while the
thru end
operation always fails
  • a word - in that case its value is looked up and used for matching

The following subexpressions are supported when parsing strings:

  • characters
  • strings

The following subexpressions are supported when parsing blocks:

  • datatypes, they are matched as described in the Datatype section
  • lit-words, they are matched as described in the Lit-word section
  • other values are matched literally, i.e. as terminal symbols

This is nice if you want to parse large amounts of data and don't care about the type or value of certain contents in the block.

Let's say we don't care about anything until we reach a word. That can be done with to:

parse [37.2 38 Bye] [to word!]
; == false

This makes PARSE return FALSE because:

  • We have successfully reached the given word (you can't tell from this example), so the operation succeeded, but
  • we haven't reached the tail of the input.

In order to reach the tail of the input, we can proceed past the word using thru instead of to.

parse [37.2 38 Bye] [thru word!]
; == true

[edit] Subblock parsing

When parsing a block you may need to check its subblocks (or parens, paths, lit-paths or get-paths) for specific patterns. The into operator is suitable for this. The general form of the operation is:

into subexpression

Only blocks or words referring to blocks are accepted as subexpressions.

The subblock parsing operation fails, if the element at the current input position does not have the ANY-BLOCK! type. Otherwise the element (subblock) is used as input and matched against the given subexpression. For the subblock parsing to succeed, the subblock must successfully match the given subexpression and the final subblock input position has to be the tail of the subblock.

Examples:

parse [[]] [into [none]]
; == true
parse [[1]] [into [none]]
; == false
parse [(1)] [into [skip]]
; == true
parse [a/b] [into [2 skip]]
; == true
parse ['a/b] [into ['a 'b]]
; == true

[edit] Using data from the input series

You can also use data from the series to be used in your trigger code. In addition to getting the input position using a set-word there are the following PARSE operations:

set variable subexpression

copy variable subexpression

The set operation is available only during block parsing, while the copy operation is available in both parsing modes. If the subexpression match succeeds, the set operation sets the given variable to the first matched value, while the copy operation copies the whole part of the input matched by the given subexpression. For a more detailed description see the Parse idioms section.

parse [Hi 36 37.2 38 Bye] [
  word!
  any [set int integer! (print ["Integer" int "Found"]) | decimal! (print "Decimal Found")]
  word!
]
; Integer 36 Found
; Decimal Found
; Integer 38 Found
; == true

We can apply normal function of Series to extracting data from the series we are parsing.

parse [Hi 36 37.2 38 Bye] [
  any [
    set int integer! (print ["Integer" int "Found"])
    | dec: decimal! (print ["Decimal Found at position" index? dec])
    | wrd: thru word! (print ["Word" first wrd "is near tail:" tail? wrd])
  ]
]
; Word Hi is near tail: false
; Integer 36 Found
; Decimal Found at Position 3
; Integer 38 Found
; Word Bye is near tail: true
; == true

This copies a part of a string:

parse "123456" [copy part 5 skip to end]
; == true
part
; == "12345"

[edit] Complex parse expressions

It's possible to build complex parse expressions. When you do that, it can be nice to split them in smaller pieces and give them meaningful names.

[edit] Recursion

Recursion is frequently the most elegant way how to describe a grammar. Let's take a grammar consisting of strings of the anbn type, where n >= 1 as an example. Such a grammar can be described using the following parse expression:

anbn: ["a" anbn "b" | "ab"]

Usage:

parse "ab" anbn
; == true
parse "aabb" anbn
; == true

[edit] Parse idioms

Description Operation Idiom
Any-string, string parsing a: ["abc"] a: [#"a" #"b" #"c"][1]
Bitset, string parsing a: charset ",;" a: [#"," | #";"][2]
skip nonterminal, string parsing a: [skip] b: complement charset ""[3]
a: [b][4]
skip nonterminal, block parsing a: [skip] a: [any-type!][5]
opt operator (zero or one) a: [opt b] a: [b |][6][7]
any operator (zero or more)[8] a: [any b] a: [b a |][9][10]
some operator (one or more)[8] a: [some b] a: [b [a |]][11][12]
fail (a nonterminal that always fails) a: [fail] a: [some "a" "a"][13]

a: [end skip][14]
Range of times operator a: [m n b] a: [m b (k: n - m) [k [b | c: fail] | :c]][15][16]
then operator[17]
(match B and if it succeeds, match C; otherwise match D)		 a: [b then c | d] a: [[b (e: c) | (e: d)] e][18]
not predicate[19] (inverse the success) a: [not b] a: [b then fail |][20]
at predicate (match and don't advance) a: [at b] a: [c: b :c][21]

a: [not not b][22]

a: [[b (c: none) | (c: [fail])] fail | c][23][24]
end nonterminal (match the tail of the input) a: [end] a: [not skip][25][26]
start nonterminal (match the head of the input)[27] a: [start] a: [b: (c: unless head? b [[fail]]) c][28][29]
to operator[8]
(advance to the first successful match)		 a: [to b] a: [at b | skip a][30][31][32]

a: [any [not [b (c: none)] (c: [fail]) skip] c][33]

a: [any [[b (c: none d: [fail]) | (c: [fail] d: [skip])] d] c][34]

a: [thru [at b]][35]
correspondence between to and any a: [to [b | end]][36] a: [any [not b skip]]
thru operator[8]
(advance thru the first successful match)		 a: [thru b] a: [b | skip a][37][38][39]

a: [any [not [b c: (d: [:c])] (d: [fail]) skip] d][33]

a: [any [[b c: (d: [:c] e: [fail]) | (d: [fail] e: [skip])] e] d][34]

a: [to [b c:] :c][35]
set operator
(set the variable to the first matched value)		 a: [set b c] f: [(set/any [b] if lesser? index? e index? d [e])][40][41][42]
a: [at [c d:] e: f :d][43]
copy operator
(set the variable to the matched sequence)		 a: [copy b c] f: [(b: if lesser? index? e index? d [copy/part e d])][44][42]
a: [at [c d:] e: f :d][43]
lit operator, block parsing (match a terminal) a: [lit b] a: [copy c skip (d: unless equal? c [b] [[fail]]) d][45][46]

The table illustrates, that:

  1. ↑ When parsing strings, strings can be defined to work as sequences of characters
  2. ↑ When parsing strings, bitsets can be defined to work as choices of characters
  3. ↑ The bitset containing every character can be defined as a complement of the bitset containing no character
  4. ↑ When parsing strings, the skip nonterminal can be defined as the bitset containing every character
  5. ↑ When parsing blocks, the skip nonterminal can be defined as the ANY-TYPE! datatype
  6. ↑ The opt operator can be defined using a common choice
  7. ↑ opt is greedy, since the first choice subexpression takes priority
  8. ↑ a b c d An iterative operator replacing a common recursive nonterminal:
    • enhances expressivity (spares nonterminal definitions)
    • optimizes memory usage (spares stack space)
    • optimizes speed
  9. ↑ The any operator can be defined using a common recursive expression
  10. ↑ any is greedy, since the first choice subexpression takes priority
  11. ↑ The some operator can be defined using a common recursive expression
  12. ↑ some is greedy, since the first choice subexpression takes priority
  13. ↑ The fail nonterminal can be defined (Even without the end keyword!) using the greediness of some
  14. ↑ The fail version using the end and skip keywords is more succint, though
  15. ↑ The range of times operator can be defined using a sequence of repetitions
  16. ↑ The range of times operator is greedy, since the first choice subexpression takes priority
  17. ↑ The then operator enhancing the apparent expressivity is used in the Generalized TDPL
  18. ↑ The then operator can be defined using choice and a computed nonterminal
  19. ↑ "Predicate" means, that it does not advance the input position
  20. ↑ The not predicate can be defined using the then operator and the fail nonterminal
  21. ↑ The at predicate can be defined using the position manipulations (Warning: This is not recursion-safe; the nonterminal B must not change the value of the variable 'c!)
  22. ↑ The at predicate can be defined using the not predicate
  23. ↑ The at predicate can be defined using choice, sequence and computed nonterminals
  24. ↑ Explanation: the first subexpression of the main choice is a sequence that is designed to always fail computing a non-advancing nonterminal C so, that C succeeds, if B succeeded
  25. ↑ The end nonterminal can be defined using the not predicate (Notice, that this is not a cyclic definition!)
  26. ↑ This idiom explains well, why the [end skip] idiom always fails
  27. ↑ Some users suggest, that it might be useful to detect when the input series is at its head
  28. ↑ The start nonterminal can be defined using a sequence and a computed nonterminal
  29. ↑ Explanation: C is computed to fail unless the input position is at the head of the input series
  30. ↑ The to operator can be defined using the at operator and a common recursive expression
  31. ↑ The recursive definition is more general than the current to operator, supporting any nonterminal B
  32. ↑ The recursive definition is identical with the behaviour of the to operator except for:
    • the [to ""] expression always fails when parsing strings, while the recursive expression always succeeds
  33. ↑ a b This is an equivalent iterative definition of the operator using any, not, fail, skip and computed nonterminals
  34. ↑ a b This is an equivalent iterative definition expanding the not idiom
  35. ↑ a b This shows the relation between the to and thru operators
  36. ↑ The | END choice causes, that the to operator always succeeds
  37. ↑ The thru operator can be defined using a common recursive expression
  38. ↑ The recursive definition is more general than the current thru operator, supporting any nonterminal B
  39. ↑ The recursive definition is identical with the behaviour of the thru operator except for:
    • the [thru end] expression always fails, while the recursive expression always succeeds
    • the [thru ""] expression always fails when parsing strings, while the recursive expression always succeeds
  40. ↑ The set operator can be defined using the at operator, position manipulations, actions and sequence
  41. ↑ Notice, that this set definition isn't limited to block parsing
  42. ↑ a b Explanation: Uses D and E to set the 'b variable as needed. Notice, that if the input position didn't move forward, 'b has to be set to NONE
  43. ↑ a b Explanation: The first subexpression in the sequence is defined so, that we know both the position after (used to set 'd) and before (used to set 'e) B was matched
  44. ↑ The copy operator can be defined using the at operator, position manipulations, actions and sequence
  45. ↑ lit idiom usage example: a: [copy c skip (d: unless equal? c ['hi] [[fail]]) d] matches the lit-word 'hi
  46. ↑ Explanation: C is computed to fail unless the first element of the input equals to the given terminal

[edit] Modifying the input series

Since normal series functions such as CHANGE, INSERT or REMOVE can be used on a the input series during a parse operation, it's also possible to manipulate the series during expression matching.

Here are some reasons, why it is not advisable to manipulate the input series during expression matching:

  • Instead of changing the input series it is possible to use a new series and collect its contents as desired.
  • Some manipulations change the length of the series, that is currently parsed. Length-changing operations are inefficient - a length-changing operation takes O(N) time, where N is the length of the series being changed. Contrast this to the APPEND operation used for the collecting approach, which may be roughly N times faster.
  • The length-changing operations mess up the input position bookkeeping. It is easy to produce hard to understand and debug code this way.

Example:

Let's define a test-string:

n: 100
random/seed 0
test-string: copy ""
repeat i n [insert tail test-string pick "abc" random 3]

Let's implement a remove-chars function using PARSE. The first attempt changes the series "in place", but the changes don't influence the length of the input series:

remove-chars1: func [
    {Removes the given chars from a string.}
    string [string!]
    chars [char! string!] "All characters specified will be removed."
    /local chars-to-keep group-start group-end change-position
] [
    ; if a char, use a string instead
    if char? chars [chars: head insert copy "" chars]
    ; define the characters, that we want to keep:
    chars: charset chars
    chars-to-keep: complement chars
    ; the position where the change needs to occur
    change-position: string
    ; turn off the default whitespace handling
    parse/all string [
        any [
            ; ignore chars
            any chars
            ; get a group of chars-to-keep
            group-start: some chars-to-keep group-end:
            (change-position: change/part change-position group-start group-end)
        ]
    ]
    clear change-position
    string
]

The second attempt uses the REMOVE function changing the input series length:

remove-chars2: func [
    {Removes the given chars from a string.}
    string [string!]
    chars [char! string!] "All characters specified will be removed."
    /local chars-to-keep group-start group-end
] [
    ; if a char, use a string instead
    if char? chars [chars: head insert copy "" chars]
    ; define the characters, that we want to keep:
    chars: charset chars
    chars-to-keep: complement chars
    ; turn off the default whitespace handling
    parse/all string [
        any [
            ; ignore chars-to-keep
            any chars-to-keep
            ; remove group of chars
            group-start: some chars group-end:
            (remove/part group-start group-end)
        ]
    ]
    string
]

The result is:

r1: remove-chars1 copy test-string "a"
; == {cbccbbcccbbbbbcccccccbcbbcbcbcbbccbcbbccccbcbbcbbcbbcbccccbcbb}
r2: remove-chars2 copy test-string "a"
; == {cbccbbcccbababbbcccaccccbcbbaacbcbcbbccbcbbccccbcbbcbbcbbcbccccbacbb}

Surprise! The approach using input manipulations didn't remove all #"a"s as we expected! The problem is caused by improper input position handling. So, let's be stubborn and handle the input position properly:

remove-chars3: func [
    {Removes the given chars from a string.}
    string [string!]
    chars [char! string!] "All characters specified will be removed."
    /local chars-to-keep group-start group-end
] [
    ; if a char, use a string instead
    if char? chars [chars: head insert copy "" chars]
    ; define the characters, that we want to keep:
    chars: charset chars
    chars-to-keep: complement chars
    ; turn off the default whitespace handling
    parse/all string [
        any [
            ; ignore chars-to-keep
            any chars-to-keep
            ; remove chars
            group-start: some chars group-end:
            (remove/part group-start group-end)
            ; set the input position properly
            :group-start
        ]
    ]
    string
]

The result is:

r3: remove-chars3 copy test-string "a"
; == {cbccbbcccbbbbbcccccccbcbbcbcbcbbccbcbbccccbcbbcbbcbbcbccccbcbb}

[edit] Troubleshooting

PARSE is a very powerful function, but it can also be troublesome, if you don't keep a good eye on what you are doing. If you are unlucky, PARSE can get stuck in an infinite loop, requiring you to restart REBOL.

But when exactly does it happen?

PARSE normally traverses through the block, but it's really the expressions that make PARSE progress. If you specify an expression that won't make it progress, it will be stuck at the same point forever.

Such an expression can be an expression repetitively matching an empty sequence, empty choice subexpression or a NONE expression.

Examples:

>> parse "abc" [any []]
*** HANGS REBOL ***

>> parse "abc" [some ["a" |]]
*** HANGS REBOL ***

>> parse "abc" [some [none]]
*** HANGS REBOL ***

Note: to be able to escape from infinite loops use () somewhere in the iterated expressions as for example:

 >> parse "abc" [any [()]]
 *** YOU CAN PRESS [ESC] NOW TO STOP THE LOOP ***

[edit] Debugging

[edit] Parsing examples

[edit] Simply split

This is an example of simple splitting using parse expression matching. As opposed to the NONE rule, this example does not treat the quotation marks specially. It can be modified easily to suit your needs.

simply-split: func [
    input [string!]
    /local delimiter whitespace regular result split
] [
    delimiter: charset ",;"
    whitespace: charset [#"^A" - #" " "^(7F)^(A0)"]
    regular: complement union delimiter whitespace
    ; result is a block containing the splits we collect
    result: copy []
    ; turn off the default whitespace handling,
    ; , since we handle whitespace explicitely
    parse/all input [
        ; skip the leading whitespace
        any whitespace
        any [
            ; no split encountered
            delimiter
            (append result copy "")
            any whitespace
            | copy split some regular
            (append result split)
            any whitespace
            [delimiter any whitespace |]
        ]
    ]
    result
]

The SIMPLY-SPLIT function behaves like the PARSE function obtaining the NONE rule (examples above) except for the CSV case:

simply-split {"red","blue","green"}
; == [{"red"} {"blue"} {"green"}]

[edit] Porter measure of a word

; vowel variants
vowel-after-consonant: charset "aeiouyAEIOUY"
vowel-otherwise: charset "aeiouAEIOU"

; consonant variants
consonant-after-consonant: exclude charset [
    #"a" - #"z" #"A" - #"Z"
] vowel-after-consonant
consonant-otherwise: union consonant-after-consonant charset "yY"

; adjusting the Vowel and Consonant rules to the Otherwise state
otherwise: first [
    (
        ; vowel detection does not change state
        vowel: vowel-otherwise
        ; consonant detection changes state to After-consonant
        consonant: [consonant-otherwise after-consonant]
    )
]

; adjusting the Vowel and Consonant rules to the After-consonant state
after-consonant: first [
    (
        ; vowel detection provokes transition to the Otherwise state
        vowel: [vowel-after-consonant otherwise]
        ; consonant detection does not change state
        consonant: consonant-after-consonant
    )
]

measure: [
    ; initialization
    (
        ; zeroing the counter
        m: 0
    )

    ; setting the state to Otherwise
    otherwise
    ; initialization end

    any consonant
    any [some vowel some consonant (m: m + 1)]
    any vowel
]

[edit] Screen validation

Retrieved from "http://en.wikibooks.org/wiki/REBOL_Programming/Language_Features/Parse"