Re: [9fans] Recursive structural expressions?

["J.R. Mauro" <jrm8005@gmail.com>]

On Thu, Aug 20, 2009 at 5:26 PM, erik quanstrom<quanstro@quanstro.net> wrote:
>> No, I know you can apply them `recursively', I mean something more
>> like an expression in a CFG or yacc.
>>
>> >
>> > can you outline somehow what you're thinking of?
>>
>> Basically, if you could take a bracketed expression in sam and then
>> name it, and then call it recursively.
>>
>> All the problems with CFGs (shift/reduce problems, ambiguities, etc)
>> would possibly apply.
>
> could you give an example in your proposed language?
> i don't see how greedy regular expressions wouldn't kill you.
> example.  let's say you have a SRE that breaks text into lines,
> you couldn't apply that recursively.  in fact i think you'd have
> the same problem with any SRE, since they are greedy and
> can't count.
>
> maybe i'm just confused because 'x' goes from a blob of text
> to a stream of tokens.  where as grammars go from a stream
> of tokens to productions.  maybe you mean to replace the
> traditional tokenizer with named SREs?

Here's an example. Let's make the syntax extra pukey: @#, where # is
1-9, defines a `named procedure', which is the same thing as putting
something in braces in Sam.

x/.*\n/ @1{ ( @1 ) | @1 ( @1 ) ( ) | }

Spaces have been added to reduce ugliness, but in the ``real'' syntax,
the spaces would have to be left out. The last pipe followed by a
space represents the null string. The entire expression should,
despite me being really rusty at CS Theory, match balanced strings of
parentheses.

The problems that would arise with this scheme include:
0) Infinite recursion
1) Shift/reduce errors
2) Ambiguities

I'm not sure if this is as powerful as CFGs, but it is at least more
powerful than regular expressions. Again, I'm not great at theory and
it's been a while since I did any. If we call this syntax S, I have
proven (hopefully correctly) only this:

L(Reg) < L(S) <= L(CFG)

Newsham was thinking about it more lucidly than I was on the IRC
channel about what it's really equivalent to.

Hopefully this makes it clear.

>
> - erik
>
>