SPPF Extraction

To extract a SPPF to a dot file from a BSR set, pf, call pf.ToSPPF().DotFile("fname.dot"). See boolx_test.go for an example.

To generate a PDF from the dot file, run dot -Tpdf <dot file> > <pdf file>. See makefile for an example.

The SPPF has three types of node:

Symbol nodes are ellipses with label: symbol,lext,rext, where:
1. symbol is a grammar terminal (e.g.:var) or non-terminal (e.g.: Expr) symbol;
2. lext (left extent) is the left index of symbol in the token stream - indexing starts from 0;
3. rext (right extent) is the first index in the input token stream after symbol.
Packed nodes are boxes with rounded corners and a thick boundary. The label of a packed node is: slot,lext,pivot,rext, where:
1. slot is a grammar slot, such as Expr: Expr Op •Expr;
2. lext and rext have the meaning as described above;
3. pivot is the token index that corresponds with the left extent of the last recognised symbol of the grammar slot.
Intermediate nodes are boxes with sharp edges and label: slot,lext,rext, where
1. slot has the meaning described above;
2. lext is the index of the first token of the parsed substring of slot;
3. rext is the index of the first token after the parsed substring of slot.

See boolx-sppf.pdf for an example of the SPPF generated by the boolx parser for the input: a | b & c.

For definition of the SPPF see:

GLL parse-tree generation
E. Scott, A. Johnstone
Science of Computer Programming (2012), doi:10.1016/j.scico.2012.03.005

Provide feedback