<p>I understand that a regular expression can be converted to an equivalent DFA which can then be simulated. However, is it possible to simulate the regular expression directly with the aid of a stack ? I believe that by pushing the alphabets onto a stack and expanding any composite expression such as <code>(r1.r2)</code> into its constituent expressions one can parse against the regular expression but I am unable to figure out how to deal with the <code>|</code> operator . As an example of what I am thinking consider the following regular expression :</p>

<pre><code>a.b.(c.d)*.e
</code></pre>

<p>The string <code>abe</code> can be parsed against the regular expression in the following way using a stack:</p>

<pre><code>Stack:             alphabet action 
|e|(c.d)*|b|a      a        match: pop off the stack
|e|(c.d)*|b        b        match: pop off the stack
|e|(c.d)*          e        composite element , expand          
|e|(c.d)*|d|c      e        no match , but expanding from a composite under kleene closure , pop off
     ^
|e|(c.d)*|d        e        no match , but expanding from a composite under kleene closure , pop off
     ^
|e|(c.d)*          e        stack top not an alphabet, pop off
|e                 e        match : pop off from stack
</code></pre>

CC BY-SA 3.0
2013-10-18T13:06:20.643Z
If you are willing to modify the expression, you should be able to push "|" operators outwards using the equivalences of Kleene algebra, such as $(u|v).w = (u.w)|(v.w)$ and $(u|v)^* = u^*.(v.u^*)^*$. You can then deal with any resulting top-level $|$ operators by checking the (finitely many) cases individually.
Klaus Draeger
CC BY-SA 3.0
2013-10-18T13:51:16.837Z
how do you distinguish between line 3 and line 6 ? do you use a memory state ? what is the precise model you are asking for ? Deterministic pushdown automaton with only one state ?
Denis
CC BY-SA 3.0
2013-10-18T14:07:34.150Z
I guess that is what the marking on the $(c.d)^*$ element is for. I still have to wonder how this approach would deal with expressions like $(a.b)^*.(a.c)^*$, when parsing an $a$.
Klaus Draeger
CC BY-SA 3.0
2013-10-18T14:24:13.867Z
Yes, I now realize that this would be equivalent to simulating a DPDA where I would have to keep track of expansions for "|" and "*" . In that case, for a given regular language, is it possible to mechanically construct a DPDA that would have fewer states than the DFA for the language (considering that certain operations such as concatenation can be handled by the stack ) ?
adi
<regular-expressions><parsing>
Is it possible to simulate a regular expression using a single stack?
adi
# Is it possible to simulate a regular expression using a single stack?

(Asked by: username_0 on 2013-10-18)

I understand that a regular expression can be converted to an equivalent DFA which can then be simulated. However, is it possible to simulate the regular expression directly with the aid of a stack ? I believe that by pushing the alphabets onto a stack and expanding any composite expression such as (r1.r2) into its constituent expressions one can parse against the regular expression but I am unable to figure out how to deal with the | operator . As an example of what I am thinking consider the following regular expression :
a.b.(c.d)*.e

The string abe can be parsed against the regular expression in the following way using a stack:
Stack:             alphabet action 
|e|(c.d)*|b|a      a        match: pop off the stack
|e|(c.d)*|b        b        match: pop off the stack
|e|(c.d)*          e        composite element , expand          
|e|(c.d)*|d|c      e        no match , but expanding from a composite under kleene closure , pop off
     ^
|e|(c.d)*|d        e        no match , but expanding from a composite under kleene closure , pop off
     ^
|e|(c.d)*          e        stack top not an alphabet, pop off
|e                 e        match : pop off from stack

**Tags:** regular-expressions, parsing
> **Comments:**
> **username_1**: If you are willing to modify the expression, you should be able to push "|" operators outwards using the equivalences of Kleene algebra, such as $(u|v).w = (u.w)|(v.w)$ and $(u|v)^* = u^*.(v.u^*)^*$. You can then deal with any resulting top-level $|$ operators by checking the (finitely many) cases individually.  
> **username_2**: how do you distinguish between line 3 and line 6 ? do you use a memory state ? what is the precise model you are asking for ? Deterministic pushdown automaton with only one state ?  
> **username_1**: I guess that is what the marking on the $(c.d)^*$ element is for. I still have to wonder how this approach would deal with expressions like $(a.b)^*.(a.c)^*$, when parsing an $a$.  
> **username_0**: Yes, I now realize that this would be equivalent to simulating a DPDA where I would have to keep track of expansions for "|" and "*" . In that case, for a given regular language, is it possible to mechanically construct a DPDA that would have fewer states than the DFA for the language (considering that certain operations such as concatenation can be handled by the stack ) ?  

---

## 0 answers

