On 03/22/08 22:12, Eric Niebler wrote:
Larry Evans wrote: [snip]
The following grammar I think summarizes the difference between grammar and expression:
expr //describes an expression. = terminal | expr+ //i.e. 1 or more expressions (e.g. expr<tag::plus,expr0,expr1>) ;
In addition, I wanted some way to tell what's a valid 1st arg to matches. The above description of expr is for a grammar. Now a valid 1st arg to matches would apply ::type to each node in the above tree, AFAICT. At first, I thought of: expr_type = terminal::type | expr_type+ ; but that would make: ( terminal::type, terminal::type, terminal::type ) a valid expresion when what's needed is: ( terminal::type, terminal::type, terminal::type )::type OK, it's getting too abstract to make it clear; so I'll have to make it more concrete: expr_gram = expr<tag::terminal> //Args argument not included intentionally | expr<Tag,expr_gram+> ; and expr_type would have to be a kinda algebraic homomorphism: expr_type(expr<tag::terminal>) -> expr<tag::terminal>::type; expr_type(expr<Tag,expr_gram_1, ... expr_gram_n>) -> expr<Tag,expr_type(expr_gram_1), ... expr_type(expr_gram_n)>::type For example, in the case of a_expr_gram == expr<tag::shift_right,expr<tag::terminal>,expr<tag::terminal> > the morphism "trace" would be: expr_type(a_expr_gram) -> expr < tag::shift_right , expr_type(expr<tag::terminal>) , expr_type(expr<tag::terminal>)
::type -> expr < tag::shift_right , expr<tag::terminal>::type , expr<tag::terminal>::type ::type
The definition of algebraic homomorphism I'm using is at planetmath: http://planetmath.org/encyclopedia/HomomorphismBetweenAlgebraicSystems.html The planetmath f corresponds to above the expr_type. The planetmath operators, w_A and w_B, correspond to the above expr<Tag, ...> and expr<Tag, ...>::type, respectively. Is that about right? Also, I've got the feeling that the pass_through transform is similar to a homomorphism. Is that about right?