5 Parsed Representation
The parse of a shrubbery can be represented by an S-expression:
Each group is represented as a list that starts 'group, and the rest of the list are the elements of the group.
Atom elements are represented as “themselves” within a group, including identifers a symbols, except that an operator is represented as a 2-element list that is 'op followed by the operator name as a symbol.
A group sequence is represented as a list of 'group lists.
An element created by (…) is represented by 'parens consed onto a group-sequence list.
An element created by […] is represented by 'brackets consed onto a group-sequence list.
An element created by {…} is represented by 'braces consed onto a group-sequence list.
An element created by '…' is represented by 'quotes consed onto a group-sequence list.
A block is represented as 'block consed onto a group-sequence list. A 'block list appears only at the end of a group list or just before an 'alts list that is at the end of the group list.
A sequence of alternatives is represented as 'alts consed onto a list of 'block lists, where each 'block list represents a | alternative. An 'alts list appears only at the end of a group list.
Note that there is no possibility of confusion between symbol atoms in the input and 'group, 'block, etc., at the start of a list in an S-expression representation, because symbol atoms will always appear as non-initial items in a 'group list.
Overall, the grammar of S-expression representations is as follows:
‹document›
::=
(top ‹group› ...)
‹group›
::=
(group ‹item› ... ‹item›)
|
(group ‹item› ... ‹block›)
|
(group ‹item› ... ‹alts›)
|
(group ‹item› ... ‹block› ‹alts›)
‹item›
::=
‹atom›
|
(op ‹symbol›)
|
(parens ‹group› ...)
|
(brackets ‹group› ...)
|
(braces ‹group› ...)
|
(quotes ‹group› ...)
‹block›
::=
(block ‹group› ...)
‹alts›
::=
(alts ‹block› ...)
Here’s the same grammar, but expressed using Rhombus constructors:
‹document›
::=
[#'top, ‹group›, ...]
‹group›
::=
[#'group, ‹item›, ..., ‹item›]
|
[#'group, ‹item›, ..., ‹block›]
|
[#'group, ‹item›, ..., ‹alts›]
|
[#'group, ‹item›, ..., ‹block›, ‹alts›]
‹item›
::=
‹atom›
|
[#'op, ‹symbol›]
|
[#'parens, ‹group›, ...]
|
[#'brackets, ‹group›, ...]
|
[#'braces, ‹group›, ...]
|
[#'quotes, ‹group›, ...]
‹block›
::=
[#'block, ‹group›, ...]
‹alts›
::=
[#'alts, ‹block›, ...]
Here are some example shrubberies with their S-expression parsed representations:
def pi = 3.14 |
|
(group def pi (op =) 3.14) |
|
fun fourth(n :: Int): |
let m = n*n |
let v = m*m |
println(n +& "^4 = " +& v) |
v |
|
(group fun fourth (parens (group n (op ::) Int)) |
(block |
(group let m (op =) n (op *) n) |
(group let v (op =) m (op *) m) |
(group println (parens (group n (op +&) "^4 = " (op +&) v))) |
(group v))) |
|
if x == y |
| #'same |
| #'different |
|
(group if x (op ==) y |
(alts (block (group (op |#'|) same)) |
(block (group (op |#'|) different)))) |
|
fun fib(n): |
match n |
| 0: 0 |
| 1: 1 |
| n: fib(n-1) + fib(n-2) |
|
(group fun fib (parens (group n)) |
(block |
(group match n |
(alts |
(block (group 0 (block (group 0)))) |
(block (group 1 (block (group 1)))) |
(block (group n (block |
(group fib (parens (group n (op -) 1)) |
(op +) |
fib (parens (group n (op -) 2)))))))))))) |