A Tour of Lamb

In the Nix development shell, type the following command to run a small example:

python -m lamb tests/motivating-example.bnf

Grammar File

The file motivating-example.bnf defines a grammar for a toy imperative language, where a block is defined as a list of statements that are aligned with each other, where each statement is either an empty statement nop or a do-block that recursively takes a block as its body:

block ::= stmt|+|;
stmt  ::= "nop" | "do" block;

where notation |+| is the alignment version of Kleene plus: stmt|+| stands for a nonempty sequence of statements that are aligned to each other (i.e., with the same column number).

Ambiguous Sentence

This grammar is indeed ambiguous:

...lines of solving process omitted...

***
Ambiguous sentence of length 3 found. It shall be listed below.
***

do
nop
nop

***
Found locally ambiguous variable: "new-var-0". It corresponds to token(s) [1, 3] in the ambiguous sentence.
***

NOTE: indexing for tokens in the sentence starts at 1. Spaces in the sentence are denoted as `␣'.
NEXT STEP: Review all parse trees using the following commands (execute line by line):

show tree new-var-0 0
show tree new-var-0 1

Type help for other available commands. Command completion available with TAB key.

Now entering REPL...

smt-ambig>

We see the shortest ambiguous sentence has a length of 3:

do
nop
nop

Parse Trees

In the REPL, type help to see available commands:

smt-ambig> help

The command show tree A tree-index is used to display the (sub)trees rooted at nonterminal A. As hinted by the output, review the two parse trees of this ambiguous sentence:

smt-ambig> show tree new-var-0 0
smt-ambig> show tree new-var-0 1

The S-expression form will always be printed to the console; additionally, a figure will be opened (via open for Mac or xdg-open for Linux) if a preview application has been installed on your OS. Note that although the internal solver works on a binary normal form of the grammar, the trees are still in EBNF.

Try other commands as you wish and exit the REPL via the command exit.

Build Usage