Parser generation with page

page is a parser generator implemented in JavaScript. It can use BNF and extended BNF as input languages and LL(1) and SLR(1) as algorithms for parser generation, and it can be deployed in a web page such as this one.

In addition to a parser page can generate a scanner; scanner and parser can be executed without additional code. The parser implements an observer pattern. page can create observers to trace execution, collect scanner values during parsing, and present the values for tree building or interpretation to functions associated with grammar rules.

The tutorials provide an introduction to parser generation and observation, explain architecture and implementation of page, and describe how page can be used interactively within a JavaScript implementation such as the jjs command which is part of a Java installation, or within the Actions area in this web page. The tutorials should be read in order.

Operating this web page

Clockwise from the top left this page has four text areas: to specify a grammar, to provide input for a generated parser, to see output, and to provide semantic actions — functions associated with grammar rules. Menus in the first two areas can load and describe data and interact with page.

Grammar

page reads a grammar as a string from this area. A few predefined examples can be loaded using the first menu. The second menu must specify if the grammar is expressed in BNF or extended BNF.

The third menu has to select the algorithm which the generated parser will use. If SLR(1) is selected, the grammar may use precedences, i.e., page.BNFP and page.EBNFP are used to represent the grammar.

The last menu asks page for information about the grammar: check requests an analysis if the grammar is suitable for the selected algorithm. describe requests additional details about the grammar. pattern displays the regular expression which the generated parser uses to tokenize input.

Input

page can generate a parser from a suitable grammar. The parser reads input as a string from this area.

The menu requests different kinds of execution: tokenize shows the sequence of input symbols which the parser tries to match to the grammar. parse executes the parser. trace executes the parser and displays a trace to show how recognition proceeds.

To allow comparing error recovery strategies, the recursive page.LL1#parser will be used if EBNF and LL(1) are selected; otherwise the stack-based methods page.LL1#parse or page.SLR1#parse are used.

Output

Output from page or the generated parser appears in this area.

Actions

This area is intended for JavaScript code which is executed in the context of page when execute is pressed.

When a generated parser matches phrases of the grammar it can call functions which have access to the input recognized for the phrases. The functions are defined as members of a collection actions which can be created in this area. Function names are selected by the left-hand sides of the phrases in the grammar.

Each function receives a common context as optional second argument. This context can be defined as a variable env in this area.

Code in this area can refer to Grammar.value and Input.value for the string content of either area.

Loading this web page

This page can be called with a URL fragment selecting a text file to load into the areas on the page. The text file must reside on the same server as this page. Text for each area is prefixed by one of the following headers, starting in column 1:

= grammar BNF|EBNF LL1|SLR1 check|describe|pattern
= input tokenize|parse|trace
= actions

Options may appear in any order and are loaded into the drop-down lists for each area, they are not immediately executed.

Downloads

page is structured as a class library and implemented in a collection of files which can be reached from the current directory. For efficiency, page.min.js is optimized code without comments, thanks to Google's Closure Compiler.