How to deal with the implicit 'cat' operator while building a syntax tree for RE(use stack evaluation)

Question

I am trying to build a syntax tree for regular expression. I use the strategy similar to arithmetic expression evaluation (i know that there are ways like recursive descent), that is, use two stack, the OPND stack and the OPTR stack, then to process.

I use different kind of node to represent different kind of RE. For example, the SymbolExpression, the CatExpression, the OrExpression and the StarExpression, all of them are derived from RegularExpression.

So the OPND stack stores the RegularExpression*.

while(c || optr.top()):
    if(!isOp(c):
        opnd.push(c)
        c = getchar();
    else:
        switch(precede(optr.top(), c){
        case Less:
          optr.push(c)
          c = getchar();
        case Equal:
          optr.pop()
          c = getchar();
        case Greater:
          pop from opnd and optr then do operation, 
          then push the result back to opnd
        }

But my primary question is, in typical RE, the cat operator is implicit. a|bc represents a|b.c, (a|b)*abb represents (a|b)*.a.b.b. So when meeting an non-operator, how should i do to determine whether there's a cat operator or not? And how should i deal with the cat operator, to correctly implement the conversion?

Update

Now i've learn that there is a kind of grammar called "operator precedence grammar", its evaluation is similar to arithmetic expression's. It require that the pattern of the grammar cannot have the form of S -> ...AB...(A and B are non-terminal). So i guess that i just cannot directly use this method to parse the regular expression.

Update II

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.（\| is the escape character, since | is a special character in grammar's pattern)

E -> E \| T | T
T -> TF | F
F -> P* | P
P -> (E) | i

To remove the left recursive, import new Variable

E -> TE'
E' -> \| TE' | ε
T -> FT'
T' -> FT' | ε
F -> P* | P   
P -> (E) | i

now, for pattern F -> P* | P， import P'

P' -> * | ε
F -> PP'

However, the pattern T' -> FT' | ε has problem. Consider case (a|b):

E => TE' 
  => FT' E'
  => PT' E'
  => (E)T' E'
  => (TE')T'E'
  => (FT'E')T'E'
  => (PT'E')T'E'
  => (iT'E')T'E'
  => (iFT'E')T'E'

Here, our human know that we should substitute the Variable T' with T' -> ε, but program will just call T' -> FT', which is wrong.

So, what's wrong with this grammar? And how should i rewrite it to make it suitable for the recursive descendent method.

Answer 1

1. LL(1) grammar

I don't see any problem with your LL(1) grammar. You are parsing the string

(a|b)

and you have gotten to this point:

(a   T'E')T'E'   |b)

The lookahead symbol is | and you have two possible productions:

T' ⇒ FT'
T' ⇒ ε

FIRST(F) is {(, i}, so the first production is clearly incorrect, both for the human and the LL(1) parser. (A parser without lookahead couldn't make the decision, but parsers without lookahead are almost useless for practical parsing.)

2. Operator precedence parsing

You are technically correct. Your original grammar is not an operator grammar. However, it is normal to augment operator precedence parsers with a small state machine (otherwise algebraic expressions including unary minus, for example, cannot be correctly parsed), and once you have done that it is clear where the implicit concatenation operator must go.

The state machine is logically equivalent to preprocessing the input to insert an explicit concatenation operator where necessary -- that is, between a and b whenever a is in {), *, i} and b is in {), i}.

You should take note that your original grammar does not really handle regular expressions unless you augment it with an explicit ε primitive to represent the empty string. Otherwise, you have no way to express optional choices, usually represented in regular expressions as an implicit operand (such as (a|), also often written as a?). However, the state machine is easily capable of detecting implicit operands as well because there is no conflict in practice between implicit concatenation and implicit epsilon.