get actions of a LR(0) parser in the states of its LR(0) automaton

compute a Chomsky normal form, i.e., all production rules are only of the form A -> BC, A -> a and possibly S -> ϵ (if ϵ belongs to the language where S is the start symbol)

This function performs some basic clean-up of a given grammar.

Cocke-Younger-Kasami algorithm for checking which nonterminals of a grammar in Chomsky normal form can produce a given word. The function returns a parse table that maps integers (i,l) to sets of nonterminals such that those nonterminals can produce the subword starting at index i of length l.

This function computes the set of nonterminal symbols of a grammar that can derive other nonterminal symbols via derivations with more than one production step. If one of the nonterminals can produce itself, then the algorithm for elimination of left recursion may end up in an infinite loop, and requires basic cleanup steps in advance. In all other cases, the algorithm for elimination of left recursion will terminate.

Elimination of left factors of grammar rules, i.e., all right hand sides of the production rules of a nonterminal start with different prefixes.

Elimination of left recursion of grammar rules (note that this algorithm may not terminate in case that there is a nonterminal A that can derive itself via more than one production step): For the resulting grammar, the right hand sides of production rules of nonterminal A may only start with a nonterminal if that nonterminal is greater than A (where greater refers to the ordering given in the grammar).

This function computes an equation system that defines the First sets as a least fixpoint. It is directly read from the grammar using the nullable nonterminals. The function returns a map that maps each nonterminal to a set of strings denoting sets whose union is the First set.

compute the First sets of words with respect to the First sets computed for the single symbols of a given grammar

Compute the first sets of all terminals and nonterminals; i.e., the set of terminal symbols that are the leftmost symbols of words that can be derived from the considered symbols (and "" if the empty word can be derived). The result is a pair of maps (firstSets,firstSetsTable) where firstSets maps terminal and nonterminal symbols to a set of strings that are the first sets of those symbols. The second map firstSetsTable shows how the First sets have been computed by a fixpoint iteration.

This function computes an equation system that defines the Follow sets as a least fixpoint. It is directly read from the grammar using the nullable nonterminals. The function returns a map that maps each nonterminal to a set of strings denoting sets whose union is the Follow set.

compute for a given grammar g and its First sets the Follow sets of the nonterminal symbols

generate a grammar for a given PDA according to the standard algorithm; the function returns three grammars (gr1,gr2,gr3) where gr1 is the direct result of the standard algorithm, gr2 is its basic clean-up by removing unreachable and useless symbols, and in grammar gr3, the nonterminals were renamed to A,B,C,.. if possible (therefore it is an option type).

function to be called by the cgi script

Greibach normal form demands that all right hand sides of production rules start with a terminal symbol. The following function assumes that the given grammar has no left recursion so that all right hand sides of production rules of a nonterminal start may only start with nonterminals greater than that nonterminal. This algorithm rewrites also these occurrences so that all right hand sides will start with terminal symbols only.

compute the LR(0) automaton for LR(0) or SLR(1) parsing

write an LR0 automaton in dot format to an output stream

constructs the action and goto table for a LR0 parser whose LR(0) automaton has the given states and transitions

compute the parse table for a LL(1) grammar

NonterminalsOfGrammar computes for a given grammar the set of terminals.

Compute the nonterminal symbols of a grammar that can produce the empty word (this information can alternatively be computed by the First sets).

Parsing a grammar: captial letters are nonterminals, while all other letters are interpreted as terminal symbols. Rules must be given in the form A -> w1 | w2 | ... | wn where in each line contains the rules of one nonterminal symbol

parse a pushdown automaton which should looks, for example, as follows:

     states:  q0,q1,q2
     sigmaPD: $,a,b
     sigmaIN: a,b
     transitions: 
         ($,q0,ϵ,ϵ,q0);
         ($,q0,a,$a,q0);
         (a,q0,a,aa,q0);
         (a,q0,b,ϵ,q1);
         ($,q1,ϵ,ϵ,q1);
         (a,q1,b,ϵ,q1);
 

write a parse tree as generated by ParseTreeOfSLR1Parse to dot format

generate a parse tree of a parse run generated by function PrintSLR1Parse

perform predictive LL(1) parsing based on a ParseTable

perform SLR(1) parsing based on an action table

function to be called by the cgi script

print a grammar

print the parsing derivation as a html table

print the parsing derivation as computed by ParserSLR1 as a html table

Compute the productive symbols of a grammar g, i.e., those nonterminal symbols that can produce a nonempty set of terminal words.

Compute the nonterminal symbols of a grammar g, i.e., those nonterminal symbols that can be reached by productions from the start symbol.

This function removes all chain productions A->B of a grammar.

This function removes all epsilon productions A->ϵ of a grammar.

Clean-up a given context-free grammar by removing useless non-terminals and their rules, i.e., nonterminals that are either not reachable or that are no productive (cannot generate any terminal word). The obtained grammar is equivalent, but has only useful symbols and rules.

TerminalsOfGrammar computes for a given grammar the set of terminals.