Converting a PCCTS grammar to a set of syntax diagrams is fairly
straight-forward. Each grammar rule can be represented by a diagram.
Here, we'll place nonterminals in rectangles and terminals in rectangles with
45-degree corners. PCCTS has one rule per nonterminal, which consists of a
label, followed by a semicolon, followed by the alternatives.
For example, the following rule describes a program in a small language:
program: { K_PROGRAM } (declaration)* (function)+;
This says that a program optionally starts with the token K_PROGRAM,
followed by zero or more declarations, followed by one or more functions.
When translating a grammar rule to a syntax diagram, we replace the label with
the start of the diagram. Nonterminals are replaced by rectangles with the
name of the nonterminal inside, and terminals are replaced by rounded-off
rectangles with the name of the terminal inside. After doing this to the above
rule, we have:
/-----------\ --------------- ------------
program --> --{ | K_PROGRAM | }-- | declaration | * --- | function | + --->
\-----------/ --------------- ------------
This isn't done yet, because we need to do something about the '{', '}', '*'
and '+'. We'll talk about these next.
Whenever we see a brace pair '{' and '}', we provide an alternative path
around the subrule that it applies to as follows:
-------------------------
| |
| ----------- \|/
---> ------------| subrule |--------------->
-----------
Following the arrows, we see that we can either skip the subrule altogether,
or go through it exactly one time before leaving. Thus, we execute the
subrule zero or one times.
Whenever we see a '+', we enclose the subrule that it applies to with the
following construct:
-----------
---> ------------| subrule |--------------->
/|\ ----------- |
| |
-------------------------
Following the arrows, we see that we have to go through the subrule at least
once, but can then leave or loop back to go through it again. Thus, we
execute the subrule one or more times.
Whenever we see a '*', we enclose the subrule that it applies to with the
following construct:
-----------------------------------
| |
| ----------- \|/
---> ------------| subrule |--------------->
/|\ ----------- |
| |
-------------------------
Following the arrows, we see that we have can completely skip over the
subrule and leave, otherwise, we have to go through the subrule at least
once, after which, we can then leave or loop back to go through it again.
Thus, we execute the subrule zero or more times. Examining these diagrams
makes it clear that "(subrule)*" is equivalent to "{(subrule)+}".
Now we need to go back and use these constructs to build a syntax diagram for
the above rule. Let's look at the rule again:
program: { K_PROGRAM } (declaration)* (function)+;
To make a diagram for "program", we need to combine a diagram for zero or one
K_PROGRAMs followed by a diagram for zero or more declarations, followed by
one or more functions. Because these parts are sequential parts of the rule
(i.e. not alternatives), we just connect their diagrams serially:
-------------------------
| |
| ------------- \|/
program ---> ------------| K_PROGRAM |--------------->----
------------- |
|
------<----------------------------------------------<----
|
| -----------------------------------
| | |
| | --------------- \|/
-----------> ----------| declaration |------------->------
/|\ --------------- | |
| | |
------------------------- |
|
------<----------------------------------------------<----
|
| ------------
-----------> -----------| function |--------------->-------------->
/|\ ------------ |
| |
-------------------------
Alternates for the same rule are written in the grammar as "alt1 | alt2". To
convert this a syntax diagram, we first draw the diagrams for the alternates,
then connect them in parallel:
--------
------| alt1 |------
| -------- |
| \|/
rule ---> --| X-------->
| /|\
| -------- |
------| alt2 |------
--------
Following the arrows, we see that we have can choose to go through alt1 once
and leave or go through alt2 once and leave. Thus, we execute one alternative
of the other: not both.
This page was last modified
.