The Book

A: The Practice Page

The Model

Scripting and Buttons Explained

Execution of the examples in this book is implemented as a model which represents the state of an example and manipulates it, e.g., by using the parser generators or executing a function produced by action methods.

The model can be controlled by scripting with a Node.js program or through the graphical interface in the Practice Page.

Scripting

script.js is a Node.js module which reads command words from standard input, separated by white space, and applies them to a current Model. As such the code of this script illustrates how the EBNF and BNF modules are used as parser generators. For example

 $ node script.js << 'end'
   model eg/02/11.eg       new parse   stack new parse
   ebnf  tests/02-11a.eg   new parse   stack new parse
end

creates a Model, loads the initial texts from an example file, represents and checks the grammar and performs syntax analysis first with the LL(1) generator implemented by EBNF and next with the SLR(1) generator implemented by BNF, overwrites some texts using a different file, and performs syntax analysis with each generator again.

The command words have the following effects:

word effect
model resets all flags and variables
load resets global strings
ebnf, stack, and bnf clear all flags and select a parser generator
ebnf clears all flags and selects the LL(1) generator
greedy toggles a flag to use the expect() rather than check() algorithm
shallow, deep, and follow toggle flags to trace the corresponding algorithms
lookahead, parser, and actions toggle flags to trace the corresponding operations
noargs toggles a flag to suppress argument count checking for actions
stack clears all flags and selects the SLR(1) generator
using translation from EBNF
error toggles a flag to insert $error when translating from EBNF
sets and states toggle flags to add information to the grammar description
bnf clears all flags and selects the SLR(1) generator
using strict BNF
build toggles a flag to create lists when parsing with the SLR(1) generator
new represents and checks the grammar
scan performs lexical analysis on the program
parse performs syntax analysis on the program, calling actions if any
run runs the executable, if any
1, 10, and 100 execute a number of instructions in a stack machine, if any
exit terminates the script

Any other word is interpreted as a path to a file from which to load texts. In the file each text is preceded by %% and one of the names actions, grammar, output, program, or tokens, enclosed in white space, to overwrite the corresponding global string.

Graphical User Interface

The Practice Page contains resizable text areas which contain grammar rules in the , token definitions as object properties defined in JavaScript in the , optionally a class or an object with action methods defined in JavaScript in the , program text in the , and output from the model. The page also contains buttons which are functionally equivalent to most of the scripting command words described above.

Each text area can be resized by dragging the bottom right corner, and all but the output area can be maximized relative to the others by clicking on the label near the top right of an area; shift-click restores the original layout.

An alt-, meta-, or command-click on the label of a non-empty text area opens a pop-up window containing the text, with syntax highlighting by Sunlight for the tokens and actions areas.

Text in the output area at the bottom can be selected and copied. All other text areas can be edited and their content is available in global variables for programming.

Button states are reflected in their background color, where white indicates that a condition is not set or that a function cannot be executed yet. Buttons are inactive while a text area has focus.

The state of the very first button and the color of all buttons indicates which grammar notation and parser are used:

button state implementation parsing technique grammar notation
EBNF recursive descent LL(1) EBNF
BNF stack-based SLR(1) EBNF
BNF stack-based SLR(1) strict BNF

The label at the top right of each text area indicates which global string the text area corresponds to.

If a stored example is loaded, the button near the top right of the output area connects to this book, near the first reference to the example. Otherwise the button connects to this appendix.

The remaining buttons have the following effects:

button effect
if set, configures new grammar creation to not use the check() algorithm, i.e., to suppress checking for ambiguity; the recursive descent parser will be greedy
if set, configures new grammar creation to trace the shallow() algorithm and display the resulting sets
if set, configures new grammar creation to trace the deep() algorithm and display the resulting sets
if set, configures new grammar creation to trace the follow() algorithm and display the resulting sets
if set, configures new grammar creation to insert $error alternatives when translating braces to BNF; likely to cause shift/reduce conflicts (which are usually benign)

if set, displays the lookahead sets when a BNF grammar is processed

if set, displays the states when a BNF grammar is processed
represents and checks a Grammar and assigns it to g; all but white space in the is significant
applies the scanner created from g, if any, to program; output is a list of tuples
if set, traces scanner progress during parsing
if set, traces parsing program
if set, traces calls to actions, if any, while parsing program
if set, suppresses argument count checking for actions while parsing program
if set, adds an observer to collect input into lists when parsing with a BNF grammar
applies the parser created from g, if any, to program; output can contain nested lists of terminals or results of actions; a function will be assigned to run
executes run, if any, and displays the result
, , and execute and trace a number of instructions in the stack machine, if any

Globals

Constructing a Model creates some global variables which operations on the Model will affect. A question mark after a type below indicates that the global will not be overwritten if it already exists.

name type content
actions string defines the class and action methods to be called by a parser
g Grammar represents grammar if not null
grammar string rules of a grammar, argument for the construction of g
newOutput function? displays it's arguments, blank-separated and marked as a new section
program string should be a sentence conforming to grammar, argument for recognition
prompt function? displays a prompt string, returns input or a default string, else error
puts function? displays it's arguments, blank-separated
run function null or an executable compiled from program by the actions;
a stack machine has two arguments, other executables have none
tokens string defines an object with pattern properties defining the tokens used in grammar and compiled into g. A property with an empty key overwrites white space as text to be skipped in both, grammar and program

The parser generator modules and the modules with classes from the examples are also available through global variables.

tokens are evaluated when grammar is processed by a parser generator. actions are evaluated and used, if available, when a program is parsed. Errors are reported to the output area. Malicious content should be avoided...

Examples and Local Storage

Many examples are available and can be loaded into the Practice Page using a search string, e.g., from the following list:

search string example explained
?eg=interpret interpret arithmetic expressions with numbers.
?eg=compile compile arithmetic expressions into functions.
?eg=postfix compile arithmetic expressions into postfix.
?eg=stack compile arithmetic expressions for a stack machine.
?eg=little compile a little language for a stack machine.
?eg=little_fn compile a little language into functions.
?eg=typing compile a typed little language for a stack machine.
?eg=recursion compile mutually recursive functions.
?eg=functions compile functions with parameters and local variables.
?eg=scopes compile block scopes.
?eg=nesting compile nested functions.
?eg=first_glob compile global first-order functions.
?eg=fn_parameter compile nested functions as parameters.
?eg=first compile first-order functions.
?eg=curry currying.
?eg=compose function composition.
?eg=bootstrap compile the EBNF parser generator.
?eg=extend extend EBNF notation.

With an eg= parameter the search string can select any file with an extension .eg in the folder eg and subfolders, relative to the page. If the search fails the Practice Page is reset and contains brief hints as to the use of the different text areas.

Additionally, the search string can contain a mode= parameter with the values ebnf, stack, or bnf corresponding to the command words described above.

If possible, the current state of the text areas is saved in local storage with the key EBNF/state once the practice page loses visibility.

This state is normally reloaded once the practice page is visible again. It is destroyed if the search string is invalid.

Stored examples and local storage use the file format described above.

A Note on eval()

The Practice Page critically depends on the use of eval() and thus can fail if destructive text is entered into the text areas.

tokens and actions are compiled with eval?.(). Interestingly, the executable run is not — because it is created by the compiled actions.

The rules for specifying grammar could be changed to require that tokens be specified as part of the grammar specification, e.g., as assignments of pattern strings to token names before or after the grammar rules. This would eliminate the need for the .

However the action methods themselves have to be compiled from the text in the before they can be called during parsing. Once they are compiled with eval?.() — just before parsing — they can be called during parsing to create any kind of JavaScript data. This, specifically, includes functions. The executable run is the result of the actions during parsing and as such is a function created by the actions, i.e., it needs no further compilation.