% $Id: Grammar.lsl,v 1.3 2000/01/17 21:33:40 connolly Exp $
%
% Finite context-free grammars.
[Dragon]
Grammar: trait
includes
List(Symbol, String for List[E]), % assumes list?
Set(Symbol, FiniteSet[Symbol] for Set[E]),
RelSet(String, Set[String]),
Set(Rule, FiniteSet[Rule] for Set[E]),
Relation(String, Rel[String],
__ \< __ \> __ for __ á __ ñ __,
bot for \bot, top for \top)
Rule tuple of lhs: Symbol, rhs: String
Grammar tuple of start: Symbol, terminals: FiniteSet[Symbol],
rules: FiniteSet[Rule]
introduces
derives1: Grammar ® Rel[String]
derives: Grammar ® Rel[String]
L: Grammar ® Set[String]
stringsOver: FiniteSet[Symbol] ® Set[String]
__ Þ __ : Symbol, String ® Rule
asserts
" A: Symbol, alpha, beta, gamma, w: String,
G: Grammar, sigma: FiniteSet[Symbol]
w Î L(G) = (({G.start}) \< derives(G) \> w)
Ù w Î stringsOver(G.terminals);
derives(G) = derives1(G) \superplus;
[A, gamma] Î G.rules Þ
(alpha||{A}||beta) \< derives1(G) \> (alpha||gamma||beta);
empty Î stringsOver(sigma);
({A} || w) Î stringsOver(sigma) = (A Î sigma Ù
w Î stringsOver(sigma));
(A Þ gamma) Î G.rules Þ A \notin G.terminals;
(A Þ gamma) = [A, gamma];
[Index]
[source]
HTML generated using lsl2html.