From: Peter Hickman <peter@...>
Date: 2002-07-04T22:38:16+09:00
Subject: Re: the pains of parsing

>
>
>"Tom Sawyer" <transami@transami.net> wrote in message
>news:1025743968.2467.123.camel@silver...
>
>>i find myself spending alot of time writing routines to parse complex
>>strings. here's a mock example string of my current problem:
>>
>>a<b>[c]{d}"e"f {{g}} [[h]]*i**j*"k"
>>
>>and i want to parse this into an array like so:
>>
>>['a','<b>','[c]','{d}','"e"','f','{{g}}','[[h]]','*i*','*j*','"k"']
>>

If my very rusty CS is correct this is one of the hardest types of 
matching that a Finite State Machine can do. If I am correct then the 
whole ('a' * n) + 'b' + ('a' * m) where n == m is virually imposible for 
most classes of FSM. In effect you need to match, for example, x '<'s on 
the left hand side and then match x '>'s on the right hand side, by the 
time the FSM has started matching the right hand side then it has 
forgotten how many there were on the left.

So a regex will not do it (as it is a FSM of the wrong type).

A stack based FSM machine that pushed each <, [, {, (, " or * that it 
encountered onto a stack and then when it encountered a ), }, etc made 
sure that it's oposite was on the top of the stack. However there is a 
problem with the requirement to parse *i**j*, how do we know that it is 
not the start of something like *i**j***, a structure like [i, [j]]? If 
these nested structures are not possible the count the number of <s that 
you push onto the stack and when you have unpushed the requisit number 
of >s pop the term.

What may trip up your code is working out when you encounter a " or * if 
it is an open or close. It would be trivial otherwise. If you could 
ditch these symetrical symbols for something more pair like, --x++ or 
//x** etc then life would be much easier.